grep/regex/hashtable.c

40  * Return a 32-bit hash of the given buffer.  The init
41  * value should be 0, or the previous hash value to extend
42  * the previous hash.
45 hash32_buf(const void *buf, size_t len, uint32_t hash)
50     hash = HASHSTEP(hash, *p++);
52   return hash;
56  * Initializes a hash table that can hold table_size number of entries,
58  * bytes. On successful allocation returns a pointer to the hash table.
95  *   HASH_OK:		if the key was not present in the hash table yet
99  *   HASH_FULL:		if the hash table is full and the entry could not
107   uint32_t hash = 0;
115   hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size;
116   DPRINT(("hashtable_put: calculated hash %" PRIu32 "\n", hash));
119    * On hash collision entries are inserted at the next free space,
125       if (tbl->entries[hash] == NULL)
127       else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0)
129 	  memcpy(tbl->entries[hash]->value, value, tbl->value_size);
131 		  ", entry updated\n", hash));
134       if (++hash == tbl->table_size)
135 	hash = 0;
138   DPRINT(("hashtable_put: effective location is %" PRIu32 "\n", hash));
140   tbl->entries[hash] = malloc(sizeof(hashtable_entry));
141   if (tbl->entries[hash] == NULL)
147   tbl->entries[hash]->key = malloc(tbl->key_size);
148   if (tbl->entries[hash]->key == NULL)
154   tbl->entries[hash]->value = malloc(tbl->value_size);
155   if (tbl->entries[hash]->value == NULL)
161   memcpy(tbl->entries[hash]->key, key, tbl->key_size);
162   memcpy(tbl->entries[hash]->value, value, tbl->value_size);
170   free(tbl->entries[hash]->key);
172   free(tbl->entries[hash]);
181   uint32_t hash = 0;
183   hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size;
187       if (tbl->entries[hash] == NULL)
189       else if (memcmp(key, tbl->entries[hash]->key, tbl->key_size) == 0)
191 	  DPRINT(("hashtable_lookup: entry found at location %" PRIu32 "\n", hash));
192 	  return (&tbl->entries[hash]);
195       if (++hash == tbl->table_size)
196 	hash = 0;
201  * Retrieves the value for key from the hash table tbl and places
224  * Removes the entry with the specifified key from the hash table
251  * Frees the resources associated with the hash table tbl.