Tcl_HashTable - tcl/tkコードリーディング

概要

ハッシュテーブル構造体の定義

tcl/generic/tcl.h

メンバー

• Tcl_HashEntry **buckets; bucket配列へのポインター。それぞれの要素は、bucket's hash chain の中の最初の要素を指すか、NULLである。
• Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE]; mallocとfreeをさけるために、小さいテーブルに使用する。
• int numBuckets; bucketPtrにアロケートされているbuckets数。
• int numEntries; テーブルの中のエントリー数
• int rebuildSize; numEntriesがこの大きさになったら、テーブルを大きくする。
• int downShift; ハッシュ関数で使用するShift count。ランダムなキーの上位ビット向けにデザインされている。
• int mask; ハッシュ関数のマスク値
• int keyType; このテーブルで使っているキーのタイプ。TCL_CUSTOM_KEYS, TCL_STRING_KEYS,　TCL_ONE_WORD_KEYS、整数のどれか
• Tcl_HashEntry *(*findProc) _ANSI_ARGS_(*1);
• Tcl_HashEntry *(*createProc) _ANSI_ARGS_(*2);
• Tcl_HashKeyType *typePtr; Tcl_HashTableで使用しているキーの型

ソース

 /*
  * Structure definition for a hash table.  Must be in tcl.h so clients can
  * allocate space for these structures, but clients should never access any
  * fields in this structure.
  */
 
 #define TCL_SMALL_HASH_TABLE 4
 struct Tcl_HashTable {
     [[Tcl_HashEntry]] **buckets;	/* Pointer to bucket array. Each element
 				 * points to first entry in bucket's hash
 				 * chain, or NULL. */
     Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
 				/* Bucket array used for small tables (to
 				 * avoid mallocs and frees). */
     int numBuckets;		/* Total number of buckets allocated at
 				 * **bucketPtr. */
     int numEntries;		/* Total number of entries present in
 				 * table. */
     int rebuildSize;		/* Enlarge table when numEntries gets to be
 				 * this large. */
     int downShift;		/* Shift count used in hashing function.
 				 * Designed to use high-order bits of
 				 * randomized keys. */
     int mask;			/* Mask value used in hashing function. */
     int keyType;		/* Type of keys used in this table. It's
 				 * either TCL_CUSTOM_KEYS, TCL_STRING_KEYS,
 				 * TCL_ONE_WORD_KEYS, or an integer giving the
 				 * number of ints that is the size of the
 				 * key. */
     Tcl_HashEntry *(*findProc) _ANSI_ARGS_((Tcl_HashTable *tablePtr,
 	    CONST char *key));
     Tcl_HashEntry *(*createProc) _ANSI_ARGS_((Tcl_HashTable *tablePtr,
 	    CONST char *key, int *newPtr));
     [[Tcl_HashKeyType]] *typePtr;	/* Type of the keys used in the
 				 * Tcl_HashTable. */
 };

---

*1 Tcl_HashTable *tablePtr, CONST char *key

*2 Tcl_HashTable *tablePtr, CONST char *key, int *newPtr