+
+\f
+/***********************************************************************
+ Hash Tables
+ ***********************************************************************/
+
+/* The structure of a Lisp hash table. */
+
+struct Lisp_Hash_Table
+{
+ /* Vector fields. The hash table code doesn't refer to these. */
+ EMACS_INT size;
+ struct Lisp_Vector *vec_next;
+
+ /* Function used to compare keys. */
+ Lisp_Object test;
+
+ /* Nil if table is non-weak. Otherwise a symbol describing the
+ weakness of the table. */
+ Lisp_Object weak;
+
+ /* When the table is resized, and this is an integer, compute the
+ new size by adding this to the old size. If a float, compute the
+ new size by multiplying the old size with this factor. */
+ Lisp_Object rehash_size;
+
+ /* Resize hash table when number of entries/ table size is >= this
+ ratio, a float. */
+ Lisp_Object rehash_threshold;
+
+ /* Number of key/value entries in the table. */
+ Lisp_Object count;
+
+ /* Vector of keys and values. The key of item I is found at index
+ 2 * I, the value is found at index 2 * I + 1. */
+ Lisp_Object key_and_value;
+
+ /* Vector of hash codes.. If hash[I] is nil, this means that that
+ entry I is unused. */
+ Lisp_Object hash;
+
+ /* Vector used to chain entries. If entry I is free, next[I] is the
+ entry number of the next free item. If entry I is non-free,
+ next[I] is the index of the next entry in the collision chain. */
+ Lisp_Object next;
+
+ /* Index of first free entry in free list. */
+ Lisp_Object next_free;
+
+ /* Bucket vector. A non-nil entry is the index of the first item in
+ a collision chain. This vector's size can be larger than the
+ hash table size to reduce collisions. */
+ Lisp_Object index;
+
+ /* Next weak hash table if this is a weak hash table. The head
+ of the list is in Vweak_hash_tables. */
+ Lisp_Object next_weak;
+
+ /* User-supplied hash function, or nil. */
+ Lisp_Object user_hash_function;
+
+ /* User-supplied key comparison function, or nil. */
+ Lisp_Object user_cmp_function;
+
+ /* C function to compare two keys. */
+ int (* cmpfn) P_ ((struct Lisp_Hash_Table *, Lisp_Object,
+ unsigned, Lisp_Object, unsigned));
+
+ /* C function to compute hash code. */
+ unsigned (* hashfn) P_ ((struct Lisp_Hash_Table *, Lisp_Object));
+};
+
+
+#define XHASH_TABLE(OBJ) \
+ ((struct Lisp_Hash_Table *) XPNTR (OBJ))
+
+#define XSET_HASH_TABLE(VAR, PTR) \
+ (XSETPSEUDOVECTOR (VAR, PTR, PVEC_HASH_TABLE))
+
+#define HASH_TABLE_P(OBJ) PSEUDOVECTORP (OBJ, PVEC_HASH_TABLE)
+#define GC_HASH_TABLE_P(x) GC_PSEUDOVECTORP (x, PVEC_HASH_TABLE)
+
+#define CHECK_HASH_TABLE(x, i) \
+ do \
+ { \
+ if (!HASH_TABLE_P ((x))) \
+ x = wrong_type_argument (Qhash_table_p, (x)); \
+ } \
+ while (0)
+
+/* Default size for hash tables if not specified. */
+
+#define DEFAULT_HASH_SIZE 65
+
+/* Default threshold specifying when to resize a hash table. The
+ value gives the ratio of current entries in the hash table and the
+ size of the hash table. */
+
+#define DEFAULT_REHASH_THRESHOLD 0.8
+
+/* Default factor by which to increase the size of a hash table. */
+
+#define DEFAULT_REHASH_SIZE 1.5
+