/src/dovecot/src/lib/hash.c

Source
/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */

/* @UNSAFE: whole file */

#include "lib.h"
#include "hash.h"
#include "primes.h"

#include <ctype.h>

#define HASH_TABLE_MIN_SIZE 67

#undef hash_table_create
#undef hash_table_create_direct
#undef hash_table_destroy
#undef hash_table_clear
#undef hash_table_lookup
#undef hash_table_lookup_full
#undef hash_table_insert
#undef hash_table_update
#undef hash_table_try_remove
#undef hash_table_count
#undef hash_table_iterate_init
#undef hash_table_iterate
#undef hash_table_freeze
#undef hash_table_thaw
#undef hash_table_copy

struct hash_node {
  struct hash_node *next;
  void *key;
  void *value;
};

struct hash_table {
  pool_t node_pool;

  int frozen;
  unsigned int initial_size, nodes_count, removed_count;

  unsigned int size;
  struct hash_node *nodes;
  struct hash_node *free_nodes;

  hash_callback_t *hash_cb;
  hash_cmp_callback_t *key_compare_cb;
};

struct hash_iterate_context {
  struct hash_table *table;
  struct hash_node *next;
  unsigned int pos;
};

enum hash_table_operation{
  HASH_TABLE_OP_INSERT,
  HASH_TABLE_OP_UPDATE,
  HASH_TABLE_OP_RESIZE
};

static bool hash_table_resize(struct hash_table *table, bool grow);

void hash_table_create(struct hash_table **table_r, pool_t node_pool,
           unsigned int initial_size, hash_callback_t *hash_cb,
           hash_cmp_callback_t *key_compare_cb)
{
  struct hash_table *table;

  pool_ref(node_pool);
  table = i_new(struct hash_table, 1);
  table->node_pool = node_pool;
  table->initial_size =
    I_MAX(primes_closest(initial_size), HASH_TABLE_MIN_SIZE);

  table->hash_cb = hash_cb;
  table->key_compare_cb = key_compare_cb;

  table->size = table->initial_size;
  table->nodes = i_new(struct hash_node, table->size);
  *table_r = table;
}

static unsigned int direct_hash(const void *p)
{
  /* NOTE: may truncate the value, but that doesn't matter. */
  return POINTER_CAST_TO(p, unsigned int);
}

static int direct_cmp(const void *p1, const void *p2)
{
  return p1 == p2 ? 0 : 1;
}

void hash_table_create_direct(struct hash_table **table_r, pool_t node_pool,
            unsigned int initial_size)
{
  hash_table_create(table_r, node_pool, initial_size,
        direct_hash, direct_cmp);
}

static void free_node(struct hash_table *table, struct hash_node *node)
{
  if (!table->node_pool->alloconly_pool)
    p_free(table->node_pool, node);
  else {
    node->next = table->free_nodes;
    table->free_nodes = node;
  }
}

static void destroy_node_list(struct hash_table *table, struct hash_node *node)
{
  struct hash_node *next;

  while (node != NULL) {
    next = node->next;
    p_free(table->node_pool, node);
    node = next;
  }
}

static void hash_table_destroy_nodes(struct hash_table *table)
{
  unsigned int i;

  for (i = 0; i < table->size; i++) {
    if (table->nodes[i].next != NULL)
      destroy_node_list(table, table->nodes[i].next);
  }
}

void hash_table_destroy(struct hash_table **_table)
{
  struct hash_table *table = *_table;

  if (table == NULL)
    return;
  *_table = NULL;

  i_assert(table->frozen == 0);

  if (!table->node_pool->alloconly_pool) {
    hash_table_destroy_nodes(table);
    destroy_node_list(table, table->free_nodes);
  }

  pool_unref(&table->node_pool);
  i_free(table->nodes);
  i_free(table);
}

void hash_table_clear(struct hash_table *table, bool free_nodes)
{
  i_assert(table->frozen == 0);

  if (!table->node_pool->alloconly_pool)
    hash_table_destroy_nodes(table);

  if (free_nodes) {
    if (!table->node_pool->alloconly_pool)
      destroy_node_list(table, table->free_nodes);
    table->free_nodes = NULL;
  }

  memset(table->nodes, 0, sizeof(struct hash_node) * table->size);

  table->nodes_count = 0;
  table->removed_count = 0;
}

static struct hash_node *
hash_table_lookup_node(const struct hash_table *table,
           const void *key, unsigned int hash)
{
  struct hash_node *node;

  node = &table->nodes[hash % table->size];

  do {
    if (node->key != NULL) {
      if (table->key_compare_cb(node->key, key) == 0)
        return node;
    }
    node = node->next;
  } while (node != NULL);

  return NULL;
}

void *hash_table_lookup(const struct hash_table *table, const void *key)
{
  struct hash_node *node;

  node = hash_table_lookup_node(table, key, table->hash_cb(key));
  return node != NULL ? node->value : NULL;
}

bool hash_table_lookup_full(const struct hash_table *table,
          const void *lookup_key,
          void **orig_key, void **value)
{
  struct hash_node *node;

  node = hash_table_lookup_node(table, lookup_key,
              table->hash_cb(lookup_key));
  if (node == NULL)
    return FALSE;

  *orig_key = node->key;
  *value = node->value;
  return TRUE;
}

static void
hash_table_insert_node(struct hash_table *table, void *key, void *value,
           enum hash_table_operation opcode)
{
  struct hash_node *node, *prev;
  unsigned int hash;
  bool check_existing = TRUE;

  i_assert(table->nodes_count < UINT_MAX);
  i_assert(key != NULL);

  if(opcode == HASH_TABLE_OP_RESIZE)
    check_existing = FALSE;
  hash = table->hash_cb(key);

  if (check_existing && table->removed_count > 0) {
    /* there may be holes, have to check everything */
    node = hash_table_lookup_node(table, key, hash);
    if (node != NULL) {
      i_assert(opcode == HASH_TABLE_OP_UPDATE);
      node->value = value;
      return;
    }

    check_existing = FALSE;
  }

  /* a) primary node */
  node = &table->nodes[hash % table->size];
  if (node->key == NULL) {
    table->nodes_count++;

    node->key = key;
    node->value = value;
    return;
  }
  if (check_existing) {
    if (table->key_compare_cb(node->key, key) == 0) {
      i_assert(opcode == HASH_TABLE_OP_UPDATE);
      node->value = value;
      return;
    }
  }

  /* b) collisions list */
  prev = node; node = node->next;
  while (node != NULL) {
    if (node->key == NULL)
      break;

    if (check_existing) {
      if (table->key_compare_cb(node->key, key) == 0) {
        i_assert(opcode == HASH_TABLE_OP_UPDATE);
        node->value = value;
        return;
      }
    }
    prev = node;
    node = node->next;
  }

  if (node == NULL) {
    if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
      /* resized table, try again */
      hash_table_insert_node(table, key, value, HASH_TABLE_OP_RESIZE);
      return;
    }

    if (table->free_nodes == NULL)
      node = p_new(table->node_pool, struct hash_node, 1);
    else {
      node = table->free_nodes;
      table->free_nodes = node->next;
      node->next = NULL;
    }
    prev->next = node;
  }

  node->key = key;
  node->value = value;

  table->nodes_count++;
}

void hash_table_insert(struct hash_table *table, void *key, void *value)
{
  hash_table_insert_node(table, key, value, HASH_TABLE_OP_INSERT);
}

void hash_table_update(struct hash_table *table, void *key, void *value)
{
  hash_table_insert_node(table, key, value, HASH_TABLE_OP_UPDATE);
}

static void
hash_table_compress(struct hash_table *table, struct hash_node *root)
{
  struct hash_node *node, *next;

  i_assert(table->frozen == 0);

  /* remove deleted nodes from the list */
  for (node = root; node->next != NULL; ) {
    next = node->next;

    if (next->key == NULL) {
      node->next = next->next;
      free_node(table, next);
    } else {
      node = next;
    }
  }

  /* update root */
  if (root->key == NULL && root->next != NULL) {
    next = root->next;
    *root = *next;
    free_node(table, next);
  }
}

static void hash_table_compress_removed(struct hash_table *table)
{
  unsigned int i;

  for (i = 0; i < table->size; i++)
    hash_table_compress(table, &table->nodes[i]);

  table->removed_count = 0;
}

bool hash_table_try_remove(struct hash_table *table, const void *key)
{
  struct hash_node *node;
  unsigned int hash;

  hash = table->hash_cb(key);

  node = hash_table_lookup_node(table, key, hash);
  if (unlikely(node == NULL))
    return FALSE;

  node->key = NULL;
  table->nodes_count--;

  if (table->frozen != 0)
    table->removed_count++;
  else if (!hash_table_resize(table, FALSE))
    hash_table_compress(table, &table->nodes[hash % table->size]);
  return TRUE;
}

unsigned int hash_table_count(const struct hash_table *table)
{
  return table->nodes_count;
}

struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table)
{
  struct hash_iterate_context *ctx;

  hash_table_freeze(table);

  ctx = i_new(struct hash_iterate_context, 1);
  ctx->table = table;
  ctx->next = &table->nodes[0];
  return ctx;
}

static struct hash_node *
hash_table_iterate_next(struct hash_iterate_context *ctx,
      struct hash_node *node)
{
  do {
    node = node->next;
    if (node == NULL) {
      if (++ctx->pos == ctx->table->size) {
        ctx->pos--;
        return NULL;
      }
      node = &ctx->table->nodes[ctx->pos];
    }
  } while (node->key == NULL);

  return node;
}

bool hash_table_iterate(struct hash_iterate_context *ctx,
      void **key_r, void **value_r)
{
  struct hash_node *node;

  node = ctx->next;
  if (node != NULL && node->key == NULL)
    node = hash_table_iterate_next(ctx, node);
  if (node == NULL) {
    *key_r = *value_r = NULL;
    return FALSE;
  }
  *key_r = node->key;
  *value_r = node->value;

  ctx->next = hash_table_iterate_next(ctx, node);
  return TRUE;
}

void hash_table_iterate_deinit(struct hash_iterate_context **_ctx)
{
  struct hash_iterate_context *ctx = *_ctx;

  if (ctx == NULL)
    return;

  *_ctx = NULL;
  hash_table_thaw(ctx->table);
  i_free(ctx);
}

void hash_table_freeze(struct hash_table *table)
{
  table->frozen++;
}

void hash_table_thaw(struct hash_table *table)
{
  i_assert(table->frozen > 0);

  if (--table->frozen > 0)
    return;

  if (table->removed_count > 0) {
    if (!hash_table_resize(table, FALSE))
      hash_table_compress_removed(table);
  }
}

static bool hash_table_resize(struct hash_table *table, bool grow)
{
  struct hash_node *old_nodes, *node, *next;
  unsigned int next_size, old_size, i;
  float nodes_per_list;

  i_assert(table->frozen == 0);

  nodes_per_list = (float) table->nodes_count / (float) table->size;
  if (nodes_per_list > 0.3 && nodes_per_list < 2.0)
    return FALSE;

  next_size = I_MAX(primes_closest(table->nodes_count+1),
        table->initial_size);
  if (next_size == table->size)
    return FALSE;

  if (grow && table->size >= next_size)
    return FALSE;

  /* recreate primary table */
  old_size = table->size;
  old_nodes = table->nodes;

  table->size = I_MAX(next_size, HASH_TABLE_MIN_SIZE);
  table->nodes = i_new(struct hash_node, table->size);

  table->nodes_count = 0;
  table->removed_count = 0;

  table->frozen++;

  /* move the data */
  for (i = 0; i < old_size; i++) {
    node = &old_nodes[i];
    if (node->key != NULL) {
      hash_table_insert_node(table, node->key,
                 node->value, HASH_TABLE_OP_RESIZE);
    }

    for (node = node->next; node != NULL; node = next) {
      next = node->next;

      if (node->key != NULL) {
        hash_table_insert_node(table, node->key,
                   node->value, HASH_TABLE_OP_RESIZE);
      }
      free_node(table, node);
    }
  }

  table->frozen--;

  i_free(old_nodes);
  return TRUE;
}

void hash_table_copy(struct hash_table *dest, struct hash_table *src)
{
  struct hash_iterate_context *iter;
  void *key, *value;

  hash_table_freeze(dest);

  iter = hash_table_iterate_init(src);
  while (hash_table_iterate(iter, &key, &value))
    hash_table_insert(dest, key, value);
  hash_table_iterate_deinit(&iter);

  hash_table_thaw(dest);
}

/* a char* hash function from ASU -- from glib */
unsigned int ATTR_NO_SANITIZE_INTEGER
str_hash(const char *p)
{
  const unsigned char *s = (const unsigned char *)p;
  unsigned int g, h = 0;

  while (*s != '\0') {
    h = (h << 4) + *s;
    if ((g = h & 0xf0000000UL) != 0) {
      h = h ^ (g >> 24);
      h = h ^ g;
    }
    s++;
  }

  return h;
}

/* a char* hash function from ASU -- from glib */
unsigned int ATTR_NO_SANITIZE_INTEGER
strcase_hash(const char *p)
{
  const unsigned char *s = (const unsigned char *)p;
  unsigned int g, h = 0;

  while (*s != '\0') {
    h = (h << 4) + i_toupper(*s);
    if ((g = h & 0xf0000000UL) != 0) {
      h = h ^ (g >> 24);
      h = h ^ g;
    }
    s++;
  }

  return h;
}

unsigned int ATTR_NO_SANITIZE_INTEGER
mem_hash(const void *p, unsigned int size)
{
  const unsigned char *s = p;
  unsigned int i, g, h = 0;

  for (i = 0; i < size; i++) {
    h = (h << 4) + *s;
    if ((g = h & 0xf0000000UL) != 0) {
      h = h ^ (g >> 24);
      h = h ^ g;
    }
    s++;
  }
  return h;
}

unsigned int ATTR_NO_SANITIZE_INTEGER
strfastcase_hash(const char *p)
{
  const unsigned char *s = (const unsigned char *)p;
  unsigned int g, h = 0;

  while (*s != '\0') {
    h = (h << 4) + ((*s) & ~0x20U);
    if ((g = h & 0xf0000000UL) != 0) {
      h = h ^ (g >> 24);
      h = h ^ g;
    }
    s++;
  }

  return h;
}

Coverage Report

Created: 2025-12-11 07:13

Line	Count	Source
1		/* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
2
3		/* @UNSAFE: whole file */
4
5		#include "lib.h"
6		#include "hash.h"
7		#include "primes.h"
8
9		#include <ctype.h>
10
11		#define HASH_TABLE_MIN_SIZE 67
12
13		#undef hash_table_create
14		#undef hash_table_create_direct
15		#undef hash_table_destroy
16		#undef hash_table_clear
17		#undef hash_table_lookup
18		#undef hash_table_lookup_full
19		#undef hash_table_insert
20		#undef hash_table_update
21		#undef hash_table_try_remove
22		#undef hash_table_count
23		#undef hash_table_iterate_init
24		#undef hash_table_iterate
25		#undef hash_table_freeze
26		#undef hash_table_thaw
27		#undef hash_table_copy
28
29		struct hash_node {
30		struct hash_node *next;
31		void *key;
32		void *value;
33		};
34
35		struct hash_table {
36		pool_t node_pool;
37
38		int frozen;
39		unsigned int initial_size, nodes_count, removed_count;
40
41		unsigned int size;
42		struct hash_node *nodes;
43		struct hash_node *free_nodes;
44
45		hash_callback_t *hash_cb;
46		hash_cmp_callback_t *key_compare_cb;
47		};
48
49		struct hash_iterate_context {
50		struct hash_table *table;
51		struct hash_node *next;
52		unsigned int pos;
53		};
54
55		enum hash_table_operation{
56		HASH_TABLE_OP_INSERT,
57		HASH_TABLE_OP_UPDATE,
58		HASH_TABLE_OP_RESIZE
59		};
60
61		static bool hash_table_resize(struct hash_table *table, bool grow);
62
63		void hash_table_create(struct hash_table **table_r, pool_t node_pool,
64		unsigned int initial_size, hash_callback_t *hash_cb,
65		hash_cmp_callback_t *key_compare_cb)
66	0	{
67	0	struct hash_table *table;
68
69	0	pool_ref(node_pool);
70	0	table = i_new(struct hash_table, 1);
71	0	table->node_pool = node_pool;
72	0	table->initial_size =
73	0	I_MAX(primes_closest(initial_size), HASH_TABLE_MIN_SIZE);
74
75	0	table->hash_cb = hash_cb;
76	0	table->key_compare_cb = key_compare_cb;
77
78	0	table->size = table->initial_size;
79	0	table->nodes = i_new(struct hash_node, table->size);
80	0	*table_r = table;
81	0	}
82
83		static unsigned int direct_hash(const void *p)
84	0	{
85		/* NOTE: may truncate the value, but that doesn't matter. */
86	0	return POINTER_CAST_TO(p, unsigned int);
87	0	}
88
89		static int direct_cmp(const void p1, const void p2)
90	0	{
91	0	return p1 == p2 ? 0 : 1;
92	0	}
93
94		void hash_table_create_direct(struct hash_table **table_r, pool_t node_pool,
95		unsigned int initial_size)
96	0	{
97	0	hash_table_create(table_r, node_pool, initial_size,
98	0	direct_hash, direct_cmp);
99	0	}
100
101		static void free_node(struct hash_table table, struct hash_node node)
102	0	{
103	0	if (!table->node_pool->alloconly_pool)
104	0	p_free(table->node_pool, node);
105	0	else {
106	0	node->next = table->free_nodes;
107	0	table->free_nodes = node;
108	0	}
109	0	}
110
111		static void destroy_node_list(struct hash_table table, struct hash_node node)
112	0	{
113	0	struct hash_node *next;
114
115	0	while (node != NULL) {
116	0	next = node->next;
117	0	p_free(table->node_pool, node);
118	0	node = next;
119	0	}
120	0	}
121
122		static void hash_table_destroy_nodes(struct hash_table *table)
123	0	{
124	0	unsigned int i;
125
126	0	for (i = 0; i < table->size; i++) {
127	0	if (table->nodes[i].next != NULL)
128	0	destroy_node_list(table, table->nodes[i].next);
129	0	}
130	0	}
131
132		void hash_table_destroy(struct hash_table **_table)
133	0	{
134	0	struct hash_table table = _table;
135
136	0	if (table == NULL)
137	0	return;
138	0	*_table = NULL;
139
140	0	i_assert(table->frozen == 0);
141
142	0	if (!table->node_pool->alloconly_pool) {
143	0	hash_table_destroy_nodes(table);
144	0	destroy_node_list(table, table->free_nodes);
145	0	}
146
147	0	pool_unref(&table->node_pool);
148	0	i_free(table->nodes);
149	0	i_free(table);
150	0	}
151
152		void hash_table_clear(struct hash_table *table, bool free_nodes)
153	0	{
154	0	i_assert(table->frozen == 0);
155
156	0	if (!table->node_pool->alloconly_pool)
157	0	hash_table_destroy_nodes(table);
158
159	0	if (free_nodes) {
160	0	if (!table->node_pool->alloconly_pool)
161	0	destroy_node_list(table, table->free_nodes);
162	0	table->free_nodes = NULL;
163	0	}
164
165	0	memset(table->nodes, 0, sizeof(struct hash_node) * table->size);
166
167	0	table->nodes_count = 0;
168	0	table->removed_count = 0;
169	0	}
170
171		static struct hash_node *
172		hash_table_lookup_node(const struct hash_table *table,
173		const void *key, unsigned int hash)
174	0	{
175	0	struct hash_node *node;
176
177	0	node = &table->nodes[hash % table->size];
178
179	0	do {
180	0	if (node->key != NULL) {
181	0	if (table->key_compare_cb(node->key, key) == 0)
182	0	return node;
183	0	}
184	0	node = node->next;
185	0	} while (node != NULL);
186
187	0	return NULL;
188	0	}
189
190		void hash_table_lookup(const struct hash_table table, const void *key)
191	0	{
192	0	struct hash_node *node;
193
194	0	node = hash_table_lookup_node(table, key, table->hash_cb(key));
195	0	return node != NULL ? node->value : NULL;
196	0	}
197
198		bool hash_table_lookup_full(const struct hash_table *table,
199		const void *lookup_key,
200		void orig_key, void value)
201	0	{
202	0	struct hash_node *node;
203
204	0	node = hash_table_lookup_node(table, lookup_key,
205	0	table->hash_cb(lookup_key));
206	0	if (node == NULL)
207	0	return FALSE;
208
209	0	*orig_key = node->key;
210	0	*value = node->value;
211	0	return TRUE;
212	0	}
213
214		static void
215		hash_table_insert_node(struct hash_table table, void key, void *value,
216		enum hash_table_operation opcode)
217	0	{
218	0	struct hash_node node, prev;
219	0	unsigned int hash;
220	0	bool check_existing = TRUE;
221
222	0	i_assert(table->nodes_count < UINT_MAX);
223	0	i_assert(key != NULL);
224
225	0	if(opcode == HASH_TABLE_OP_RESIZE)
226	0	check_existing = FALSE;
227	0	hash = table->hash_cb(key);
228
229	0	if (check_existing && table->removed_count > 0) {
230		/* there may be holes, have to check everything */
231	0	node = hash_table_lookup_node(table, key, hash);
232	0	if (node != NULL) {
233	0	i_assert(opcode == HASH_TABLE_OP_UPDATE);
234	0	node->value = value;
235	0	return;
236	0	}
237
238	0	check_existing = FALSE;
239	0	}
240
241		/* a) primary node */
242	0	node = &table->nodes[hash % table->size];
243	0	if (node->key == NULL) {
244	0	table->nodes_count++;
245
246	0	node->key = key;
247	0	node->value = value;
248	0	return;
249	0	}
250	0	if (check_existing) {
251	0	if (table->key_compare_cb(node->key, key) == 0) {
252	0	i_assert(opcode == HASH_TABLE_OP_UPDATE);
253	0	node->value = value;
254	0	return;
255	0	}
256	0	}
257
258		/* b) collisions list */
259	0	prev = node; node = node->next;
260	0	while (node != NULL) {
261	0	if (node->key == NULL)
262	0	break;
263
264	0	if (check_existing) {
265	0	if (table->key_compare_cb(node->key, key) == 0) {
266	0	i_assert(opcode == HASH_TABLE_OP_UPDATE);
267	0	node->value = value;
268	0	return;
269	0	}
270	0	}
271	0	prev = node;
272	0	node = node->next;
273	0	}
274
275	0	if (node == NULL) {
276	0	if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
277		/* resized table, try again */
278	0	hash_table_insert_node(table, key, value, HASH_TABLE_OP_RESIZE);
279	0	return;
280	0	}
281
282	0	if (table->free_nodes == NULL)
283	0	node = p_new(table->node_pool, struct hash_node, 1);
284	0	else {
285	0	node = table->free_nodes;
286	0	table->free_nodes = node->next;
287	0	node->next = NULL;
288	0	}
289	0	prev->next = node;
290	0	}
291
292	0	node->key = key;
293	0	node->value = value;
294
295	0	table->nodes_count++;
296	0	}
297
298		void hash_table_insert(struct hash_table table, void key, void *value)
299	0	{
300	0	hash_table_insert_node(table, key, value, HASH_TABLE_OP_INSERT);
301	0	}
302
303		void hash_table_update(struct hash_table table, void key, void *value)
304	0	{
305	0	hash_table_insert_node(table, key, value, HASH_TABLE_OP_UPDATE);
306	0	}
307
308		static void
309		hash_table_compress(struct hash_table table, struct hash_node root)
310	0	{
311	0	struct hash_node node, next;
312
313	0	i_assert(table->frozen == 0);
314
315		/* remove deleted nodes from the list */
316	0	for (node = root; node->next != NULL; ) {
317	0	next = node->next;
318
319	0	if (next->key == NULL) {
320	0	node->next = next->next;
321	0	free_node(table, next);
322	0	} else {
323	0	node = next;
324	0	}
325	0	}
326
327		/* update root */
328	0	if (root->key == NULL && root->next != NULL) {
329	0	next = root->next;
330	0	root = next;
331	0	free_node(table, next);
332	0	}
333	0	}
334
335		static void hash_table_compress_removed(struct hash_table *table)
336	0	{
337	0	unsigned int i;
338
339	0	for (i = 0; i < table->size; i++)
340	0	hash_table_compress(table, &table->nodes[i]);
341
342	0	table->removed_count = 0;
343	0	}
344
345		bool hash_table_try_remove(struct hash_table table, const void key)
346	0	{
347	0	struct hash_node *node;
348	0	unsigned int hash;
349
350	0	hash = table->hash_cb(key);
351
352	0	node = hash_table_lookup_node(table, key, hash);
353	0	if (unlikely(node == NULL))
354	0	return FALSE;
355
356	0	node->key = NULL;
357	0	table->nodes_count--;
358
359	0	if (table->frozen != 0)
360	0	table->removed_count++;
361	0	else if (!hash_table_resize(table, FALSE))
362	0	hash_table_compress(table, &table->nodes[hash % table->size]);
363	0	return TRUE;
364	0	}
365
366		unsigned int hash_table_count(const struct hash_table *table)
367	0	{
368	0	return table->nodes_count;
369	0	}
370
371		struct hash_iterate_context hash_table_iterate_init(struct hash_table table)
372	0	{
373	0	struct hash_iterate_context *ctx;
374
375	0	hash_table_freeze(table);
376
377	0	ctx = i_new(struct hash_iterate_context, 1);
378	0	ctx->table = table;
379	0	ctx->next = &table->nodes[0];
380	0	return ctx;
381	0	}
382
383		static struct hash_node *
384		hash_table_iterate_next(struct hash_iterate_context *ctx,
385		struct hash_node *node)
386	0	{
387	0	do {
388	0	node = node->next;
389	0	if (node == NULL) {
390	0	if (++ctx->pos == ctx->table->size) {
391	0	ctx->pos--;
392	0	return NULL;
393	0	}
394	0	node = &ctx->table->nodes[ctx->pos];
395	0	}
396	0	} while (node->key == NULL);
397
398	0	return node;
399	0	}
400
401		bool hash_table_iterate(struct hash_iterate_context *ctx,
402		void key_r, void value_r)
403	0	{
404	0	struct hash_node *node;
405
406	0	node = ctx->next;
407	0	if (node != NULL && node->key == NULL)
408	0	node = hash_table_iterate_next(ctx, node);
409	0	if (node == NULL) {
410	0	key_r = value_r = NULL;
411	0	return FALSE;
412	0	}
413	0	*key_r = node->key;
414	0	*value_r = node->value;
415
416	0	ctx->next = hash_table_iterate_next(ctx, node);
417	0	return TRUE;
418	0	}
419
420		void hash_table_iterate_deinit(struct hash_iterate_context **_ctx)
421	0	{
422	0	struct hash_iterate_context ctx = _ctx;
423
424	0	if (ctx == NULL)
425	0	return;
426
427	0	*_ctx = NULL;
428	0	hash_table_thaw(ctx->table);
429	0	i_free(ctx);
430	0	}
431
432		void hash_table_freeze(struct hash_table *table)
433	0	{
434	0	table->frozen++;
435	0	}
436
437		void hash_table_thaw(struct hash_table *table)
438	0	{
439	0	i_assert(table->frozen > 0);
440
441	0	if (--table->frozen > 0)
442	0	return;
443
444	0	if (table->removed_count > 0) {
445	0	if (!hash_table_resize(table, FALSE))
446	0	hash_table_compress_removed(table);
447	0	}
448	0	}
449
450		static bool hash_table_resize(struct hash_table *table, bool grow)
451	0	{
452	0	struct hash_node old_nodes, node, *next;
453	0	unsigned int next_size, old_size, i;
454	0	float nodes_per_list;
455
456	0	i_assert(table->frozen == 0);
457
458	0	nodes_per_list = (float) table->nodes_count / (float) table->size;
459	0	if (nodes_per_list > 0.3 && nodes_per_list < 2.0)
460	0	return FALSE;
461
462	0	next_size = I_MAX(primes_closest(table->nodes_count+1),
463	0	table->initial_size);
464	0	if (next_size == table->size)
465	0	return FALSE;
466
467	0	if (grow && table->size >= next_size)
468	0	return FALSE;
469
470		/* recreate primary table */
471	0	old_size = table->size;
472	0	old_nodes = table->nodes;
473
474	0	table->size = I_MAX(next_size, HASH_TABLE_MIN_SIZE);
475	0	table->nodes = i_new(struct hash_node, table->size);
476
477	0	table->nodes_count = 0;
478	0	table->removed_count = 0;
479
480	0	table->frozen++;
481
482		/* move the data */
483	0	for (i = 0; i < old_size; i++) {
484	0	node = &old_nodes[i];
485	0	if (node->key != NULL) {
486	0	hash_table_insert_node(table, node->key,
487	0	node->value, HASH_TABLE_OP_RESIZE);
488	0	}
489
490	0	for (node = node->next; node != NULL; node = next) {
491	0	next = node->next;
492
493	0	if (node->key != NULL) {
494	0	hash_table_insert_node(table, node->key,
495	0	node->value, HASH_TABLE_OP_RESIZE);
496	0	}
497	0	free_node(table, node);
498	0	}
499	0	}
500
501	0	table->frozen--;
502
503	0	i_free(old_nodes);
504	0	return TRUE;
505	0	}
506
507		void hash_table_copy(struct hash_table dest, struct hash_table src)
508	0	{
509	0	struct hash_iterate_context *iter;
510	0	void key, value;
511
512	0	hash_table_freeze(dest);
513
514	0	iter = hash_table_iterate_init(src);
515	0	while (hash_table_iterate(iter, &key, &value))
516	0	hash_table_insert(dest, key, value);
517	0	hash_table_iterate_deinit(&iter);
518
519	0	hash_table_thaw(dest);
520	0	}
521
522		/* a char* hash function from ASU -- from glib */
523		unsigned int ATTR_NO_SANITIZE_INTEGER
524		str_hash(const char *p)
525	0	{
526	0	const unsigned char s = (const unsigned char )p;
527	0	unsigned int g, h = 0;
528
529	0	while (*s != '\0') {
530	0	h = (h << 4) + *s;
531	0	if ((g = h & 0xf0000000UL) != 0) {
532	0	h = h ^ (g >> 24);
533	0	h = h ^ g;
534	0	}
535	0	s++;
536	0	}
537
538	0	return h;
539	0	}
540
541		/* a char* hash function from ASU -- from glib */
542		unsigned int ATTR_NO_SANITIZE_INTEGER
543		strcase_hash(const char *p)
544	0	{
545	0	const unsigned char s = (const unsigned char )p;
546	0	unsigned int g, h = 0;
547
548	0	while (*s != '\0') {
549	0	h = (h << 4) + i_toupper(*s);
550	0	if ((g = h & 0xf0000000UL) != 0) {
551	0	h = h ^ (g >> 24);
552	0	h = h ^ g;
553	0	}
554	0	s++;
555	0	}
556
557	0	return h;
558	0	}
559
560		unsigned int ATTR_NO_SANITIZE_INTEGER
561		mem_hash(const void *p, unsigned int size)
562	0	{
563	0	const unsigned char *s = p;
564	0	unsigned int i, g, h = 0;
565
566	0	for (i = 0; i < size; i++) {
567	0	h = (h << 4) + *s;
568	0	if ((g = h & 0xf0000000UL) != 0) {
569	0	h = h ^ (g >> 24);
570	0	h = h ^ g;
571	0	}
572	0	s++;
573	0	}
574	0	return h;
575	0	}
576
577		unsigned int ATTR_NO_SANITIZE_INTEGER
578		strfastcase_hash(const char *p)
579	0	{
580	0	const unsigned char s = (const unsigned char )p;
581	0	unsigned int g, h = 0;
582
583	0	while (*s != '\0') {
584	0	h = (h << 4) + ((*s) & ~0x20U);
585	0	if ((g = h & 0xf0000000UL) != 0) {
586	0	h = h ^ (g >> 24);
587	0	h = h ^ g;
588	0	}
589	0	s++;
590	0	}
591
592	0	return h;
593	0	}