Mercurial > dovecot > core-2.2

annotate src/lib/hash.c @ 22664:fea53c2725c0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
director: Fix director_max_parallel_moves/kicks type Should be uint, not time.
author Timo Sirainen <timo.sirainen@dovecot.fi>
date Thu, 09 Nov 2017 12:24:16 +0200
parents 7ff9bc554381
children cb108f786fb4
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
21390
2e2563132d5f Updated copyright notices to include the year 2017.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 19552
diff changeset
1 /* Copyright (c) 2002-2017 Dovecot authors, see the included COPYING file */
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
2
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
3 /* @UNSAFE: whole file */
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 #include "lib.h"
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6 #include "hash.h"
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
7 #include "primes.h"
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
8
59
296c6dbf50a5 Don't include system headers before lib.h, since config.h may change their
Timo Sirainen <tss@iki.fi>
parents: 44
diff changeset
9 #include <ctype.h>
296c6dbf50a5 Don't include system headers before lib.h, since config.h may change their
Timo Sirainen <tss@iki.fi>
parents: 44
diff changeset
10
15127
9f691edba099 Decrease minimum memory allocations.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
11 #define HASH_TABLE_MIN_SIZE 67
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
13 #undef hash_table_create
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
14 #undef hash_table_create_direct
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
15 #undef hash_table_destroy
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
16 #undef hash_table_clear
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
17 #undef hash_table_lookup
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
18 #undef hash_table_lookup_full
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
19 #undef hash_table_insert
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
20 #undef hash_table_update
17454
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
21 #undef hash_table_try_remove
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
22 #undef hash_table_count
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
23 #undef hash_table_iterate_init
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
24 #undef hash_table_iterate
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
25 #undef hash_table_freeze
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
26 #undef hash_table_thaw
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
27 #undef hash_table_copy
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
28
903
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the
Timo Sirainen <tss@iki.fi>
parents: 705
diff changeset
29 struct hash_node {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
30 struct hash_node *next;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 void *key;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32 void *value;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
33 };
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
34
903
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the
Timo Sirainen <tss@iki.fi>
parents: 705
diff changeset
35 struct hash_table {
14917
1ce71b5bc94a hash_table_create(): Removed table_pool parameter.
Timo Sirainen <tss@iki.fi>
parents: 14689
diff changeset
36 pool_t node_pool;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
37
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
38 int frozen;
3906
51db9cedc120 size_t -> unsigned int. It's enough.
Timo Sirainen <tss@iki.fi>
parents: 3879
diff changeset
39 unsigned int initial_size, nodes_count, removed_count;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40
3906
51db9cedc120 size_t -> unsigned int. It's enough.
Timo Sirainen <tss@iki.fi>
parents: 3879
diff changeset
41 unsigned int size;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
42 struct hash_node *nodes;
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
43 struct hash_node *free_nodes;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
44
1038
60646878858e Function typedefs now define them as functions, not function pointers.
Timo Sirainen <tss@iki.fi>
parents: 974
diff changeset
45 hash_callback_t *hash_cb;
60646878858e Function typedefs now define them as functions, not function pointers.
Timo Sirainen <tss@iki.fi>
parents: 974
diff changeset
46 hash_cmp_callback_t *key_compare_cb;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
47 };
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
48
1898
54e60d63a942 cleanup
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
49 struct hash_iterate_context {
54e60d63a942 cleanup
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
50 struct hash_table *table;
54e60d63a942 cleanup
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
51 struct hash_node *next;
3906
51db9cedc120 size_t -> unsigned int. It's enough.
Timo Sirainen <tss@iki.fi>
parents: 3879
diff changeset
52 unsigned int pos;
1898
54e60d63a942 cleanup
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
53 };
54e60d63a942 cleanup
Timo Sirainen <tss@iki.fi>
parents: 1897
diff changeset
54
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
55 static bool hash_table_resize(struct hash_table *table, bool grow);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
56
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
57 void hash_table_create(struct hash_table **table_r, pool_t node_pool,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
58 unsigned int initial_size, hash_callback_t *hash_cb,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
59 hash_cmp_callback_t *key_compare_cb)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
60 {
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
61 struct hash_table *table;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
62
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
63 pool_ref(node_pool);
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
64 table = i_new(struct hash_table, 1);
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
65 table->node_pool = node_pool;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
66 table->initial_size =
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
67 I_MAX(primes_closest(initial_size), HASH_TABLE_MIN_SIZE);
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
68
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
69 table->hash_cb = hash_cb;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
70 table->key_compare_cb = key_compare_cb;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
71
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
72 table->size = table->initial_size;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
73 table->nodes = i_new(struct hash_node, table->size);
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
74 *table_r = table;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
75 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
76
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
77 static unsigned int direct_hash(const void *p)
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
78 {
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
79 /* NOTE: may truncate the value, but that doesn't matter. */
195
db6e288be0e9 Replaced INT_TO_POINTER and POINTER_TO_INT macros with POINTER_CAST and
Timo Sirainen <tss@iki.fi>
parents: 59
diff changeset
80 return POINTER_CAST_TO(p, unsigned int);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
81 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
83 static int direct_cmp(const void *p1, const void *p2)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 {
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
85 return p1 == p2 ? 0 : 1;
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
86 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
87
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
88 void hash_table_create_direct(struct hash_table **table_r, pool_t node_pool,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
89 unsigned int initial_size)
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
90 {
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
91 hash_table_create(table_r, node_pool, initial_size,
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
92 direct_hash, direct_cmp);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
93 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
94
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
95 static void free_node(struct hash_table *table, struct hash_node *node)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
96 {
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
97 if (!table->node_pool->alloconly_pool)
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
98 p_free(table->node_pool, node);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
99 else {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
100 node->next = table->free_nodes;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
101 table->free_nodes = node;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
102 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
103 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
104
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
105 static void destroy_node_list(struct hash_table *table, struct hash_node *node)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
106 {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
107 struct hash_node *next;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
108
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
109 while (node != NULL) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
110 next = node->next;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
111 p_free(table->node_pool, node);
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
112 node = next;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
113 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
114 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
115
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
116 static void hash_table_destroy_nodes(struct hash_table *table)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
117 {
3906
51db9cedc120 size_t -> unsigned int. It's enough.
Timo Sirainen <tss@iki.fi>
parents: 3879
diff changeset
118 unsigned int i;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
119
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
120 for (i = 0; i < table->size; i++) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
121 if (table->nodes[i].next != NULL)
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
122 destroy_node_list(table, table->nodes[i].next);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
123 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
124 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
125
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
126 void hash_table_destroy(struct hash_table **_table)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
127 {
3879
928229f8b3e6 deinit, unref, destroy, close, free, etc. functions now take a pointer to
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
128 struct hash_table *table = *_table;
928229f8b3e6 deinit, unref, destroy, close, free, etc. functions now take a pointer to
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
129
928229f8b3e6 deinit, unref, destroy, close, free, etc. functions now take a pointer to
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
130 *_table = NULL;
928229f8b3e6 deinit, unref, destroy, close, free, etc. functions now take a pointer to
Timo Sirainen <tss@iki.fi>
parents: 3863
diff changeset
131
21412
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
132 i_assert(table->frozen == 0);
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
133
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
134 if (!table->node_pool->alloconly_pool) {
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
135 hash_table_destroy_nodes(table);
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
136 destroy_node_list(table, table->free_nodes);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
137 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
138
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
139 pool_unref(&table->node_pool);
14917
1ce71b5bc94a hash_table_create(): Removed table_pool parameter.
Timo Sirainen <tss@iki.fi>
parents: 14689
diff changeset
140 i_free(table->nodes);
1ce71b5bc94a hash_table_create(): Removed table_pool parameter.
Timo Sirainen <tss@iki.fi>
parents: 14689
diff changeset
141 i_free(table);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
142 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
144 void hash_table_clear(struct hash_table *table, bool free_nodes)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
145 {
21412
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
146 i_assert(table->frozen == 0);
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
147
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
148 if (!table->node_pool->alloconly_pool)
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
149 hash_table_destroy_nodes(table);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
151 if (free_nodes) {
949
e601f13d95b1 hash_clear() can now be used to drop the memory allocated using node_pool.
Timo Sirainen <tss@iki.fi>
parents: 946
diff changeset
152 if (!table->node_pool->alloconly_pool)
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
153 destroy_node_list(table, table->free_nodes);
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
154 table->free_nodes = NULL;
949
e601f13d95b1 hash_clear() can now be used to drop the memory allocated using node_pool.
Timo Sirainen <tss@iki.fi>
parents: 946
diff changeset
155 }
e601f13d95b1 hash_clear() can now be used to drop the memory allocated using node_pool.
Timo Sirainen <tss@iki.fi>
parents: 946
diff changeset
156
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
157 memset(table->nodes, 0, sizeof(struct hash_node) * table->size);
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
158
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
159 table->nodes_count = 0;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
160 table->removed_count = 0;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
161 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
163 static struct hash_node *
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
164 hash_table_lookup_node(const struct hash_table *table,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
165 const void *key, unsigned int hash)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
166 {
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
167 struct hash_node *node;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
168
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
169 node = &table->nodes[hash % table->size];
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
170
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
171 do {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
172 if (node->key != NULL) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
173 if (table->key_compare_cb(node->key, key) == 0)
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
174 return node;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
175 }
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
176 node = node->next;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
177 } while (node != NULL);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
178
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
179 return NULL;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
180 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
181
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
182 void *hash_table_lookup(const struct hash_table *table, const void *key)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
183 {
903
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the
Timo Sirainen <tss@iki.fi>
parents: 705
diff changeset
184 struct hash_node *node;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
185
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
186 node = hash_table_lookup_node(table, key, table->hash_cb(key));
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
187 return node != NULL ? node->value : NULL;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
188 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
189
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
190 bool hash_table_lookup_full(const struct hash_table *table,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
191 const void *lookup_key,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
192 void **orig_key, void **value)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
193 {
903
fd8888f6f037 Naming style changes, finally got tired of most of the typedefs. Also the
Timo Sirainen <tss@iki.fi>
parents: 705
diff changeset
194 struct hash_node *node;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
195
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
196 node = hash_table_lookup_node(table, lookup_key,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
197 table->hash_cb(lookup_key));
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
198 if (node == NULL)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
199 return FALSE;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
200
14629
c93ca5e46a8a Marked functions parameters that are allowed to be NULL. Some APIs were also changed.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
201 *orig_key = node->key;
c93ca5e46a8a Marked functions parameters that are allowed to be NULL. Some APIs were also changed.
Timo Sirainen <tss@iki.fi>
parents: 14133
diff changeset
202 *value = node->value;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
203 return TRUE;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
204 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
205
14689
096e4c4d62bb Try to avoid (void) casts by adding more ATTR_NOWARN_UNUSED_RESULT.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
206 static struct hash_node * ATTR_NOWARN_UNUSED_RESULT
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
207 hash_table_insert_node(struct hash_table *table, void *key, void *value,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
208 bool check_existing)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
209 {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
210 struct hash_node *node, *prev;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
211 unsigned int hash;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
212
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
213 i_assert(key != NULL);
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
214
953
411006be3c66 Naming change for function typedefs.
Timo Sirainen <tss@iki.fi>
parents: 949
diff changeset
215 hash = table->hash_cb(key);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
216
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
217 if (check_existing && table->removed_count > 0) {
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
218 /* there may be holes, have to check everything */
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
219 node = hash_table_lookup_node(table, key, hash);
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
220 if (node != NULL) {
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
221 node->value = value;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
222 return node;
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
223 }
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
224
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
225 check_existing = FALSE;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
226 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
227
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
228 /* a) primary node */
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
229 node = &table->nodes[hash % table->size];
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
230 if (node->key == NULL) {
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
231 table->nodes_count++;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
232
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
233 node->key = key;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
234 node->value = value;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
235 return node;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
236 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
237
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
238 if (check_existing) {
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
239 if (table->key_compare_cb(node->key, key) == 0) {
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
240 node->value = value;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
241 return node;
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
242 }
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
243 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
244
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
245 /* b) collisions list */
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
246 prev = node; node = node->next;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
247 while (node != NULL) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
248 if (node->key == NULL)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
249 break;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
250
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
251 if (check_existing) {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
252 if (table->key_compare_cb(node->key, key) == 0) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
253 node->value = value;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
254 return node;
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
255 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
256 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
257
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
258 prev = node;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
259 node = node->next;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
260 }
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
261
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
262 if (node == NULL) {
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
263 if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
264 /* resized table, try again */
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
265 return hash_table_insert_node(table, key, value, FALSE);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
266 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
267
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
268 if (table->free_nodes == NULL)
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
269 node = p_new(table->node_pool, struct hash_node, 1);
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
270 else {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
271 node = table->free_nodes;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
272 table->free_nodes = node->next;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
273 node->next = NULL;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
274 }
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
275 prev->next = node;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
276 }
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
277
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
278 node->key = key;
8442
944a13d1fe83 Minor code cleanup: Removed extra ';' characters.
Timo Sirainen <tss@iki.fi>
parents: 8142
diff changeset
279 node->value = value;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
280
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
281 table->nodes_count++;
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
282 return node;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
283 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
284
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
285 void hash_table_insert(struct hash_table *table, void *key, void *value)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
286 {
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
287 struct hash_node *node;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
288
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
289 node = hash_table_insert_node(table, key, value, TRUE);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
290 node->key = key;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
291 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
292
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
293 void hash_table_update(struct hash_table *table, void *key, void *value)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
294 {
14689
096e4c4d62bb Try to avoid (void) casts by adding more ATTR_NOWARN_UNUSED_RESULT.
Timo Sirainen <tss@iki.fi>
parents: 14682
diff changeset
295 hash_table_insert_node(table, key, value, TRUE);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
296 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
297
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
298 static void
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
299 hash_table_compress(struct hash_table *table, struct hash_node *root)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
300 {
5087
37e3fac0aa2f Optimization: Hash compression didn't remove NULL nodes from roots.
Timo Sirainen <tss@iki.fi>
parents: 4591
diff changeset
301 struct hash_node *node, *next;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
302
21412
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
303 i_assert(table->frozen == 0);
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
304
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
305 /* remove deleted nodes from the list */
5087
37e3fac0aa2f Optimization: Hash compression didn't remove NULL nodes from roots.
Timo Sirainen <tss@iki.fi>
parents: 4591
diff changeset
306 for (node = root; node->next != NULL; ) {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
307 next = node->next;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
308
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
309 if (next->key == NULL) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
310 node->next = next->next;
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
311 free_node(table, next);
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
312 } else {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
313 node = next;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
314 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
315 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
316
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
317 /* update root */
5087
37e3fac0aa2f Optimization: Hash compression didn't remove NULL nodes from roots.
Timo Sirainen <tss@iki.fi>
parents: 4591
diff changeset
318 if (root->key == NULL && root->next != NULL) {
37e3fac0aa2f Optimization: Hash compression didn't remove NULL nodes from roots.
Timo Sirainen <tss@iki.fi>
parents: 4591
diff changeset
319 next = root->next;
37e3fac0aa2f Optimization: Hash compression didn't remove NULL nodes from roots.
Timo Sirainen <tss@iki.fi>
parents: 4591
diff changeset
320 *root = *next;
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
321 free_node(table, next);
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
322 }
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
323 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
324
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
325 static void hash_table_compress_removed(struct hash_table *table)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
326 {
3906
51db9cedc120 size_t -> unsigned int. It's enough.
Timo Sirainen <tss@iki.fi>
parents: 3879
diff changeset
327 unsigned int i;
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
328
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
329 for (i = 0; i < table->size; i++)
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
330 hash_table_compress(table, &table->nodes[i]);
946
3681ff89f0e2 Few fixes
Timo Sirainen <tss@iki.fi>
parents: 945
diff changeset
331
3681ff89f0e2 Few fixes
Timo Sirainen <tss@iki.fi>
parents: 945
diff changeset
332 table->removed_count = 0;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
333 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
334
17454
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
335 bool hash_table_try_remove(struct hash_table *table, const void *key)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
336 {
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
337 struct hash_node *node;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
338 unsigned int hash;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
339
953
411006be3c66 Naming change for function typedefs.
Timo Sirainen <tss@iki.fi>
parents: 949
diff changeset
340 hash = table->hash_cb(key);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
341
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
342 node = hash_table_lookup_node(table, key, hash);
6825
85385079b044 Use likely() and unlikely() macros to make commonly checked error handling
Timo Sirainen <tss@iki.fi>
parents: 6475
diff changeset
343 if (unlikely(node == NULL))
17454
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
344 return FALSE;
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
345
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
346 node->key = NULL;
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
347 table->nodes_count--;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
348
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
349 if (table->frozen != 0)
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
350 table->removed_count++;
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
351 else if (!hash_table_resize(table, FALSE))
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
352 hash_table_compress(table, &table->nodes[hash % table->size]);
17454
5c617a5036f3 lib: Changed hash_table_remove() "key not found" panic to be in a macro itself.
Timo Sirainen <tss@iki.fi>
parents: 17130
diff changeset
353 return TRUE;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
354 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
355
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
356 unsigned int hash_table_count(const struct hash_table *table)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
357 {
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
358 return table->nodes_count;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
359 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
360
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
361 struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
362 {
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
363 struct hash_iterate_context *ctx;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
364
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
365 hash_table_freeze(table);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
366
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
367 ctx = i_new(struct hash_iterate_context, 1);
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
368 ctx->table = table;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
369 ctx->next = &table->nodes[0];
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
370 return ctx;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
371 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
372
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
373 static struct hash_node *
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
374 hash_table_iterate_next(struct hash_iterate_context *ctx,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
375 struct hash_node *node)
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
376 {
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
377 do {
1899
Timo Sirainen <tss@iki.fi>
parents: 1898
diff changeset
378 node = node->next;
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
379 if (node == NULL) {
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
380 if (++ctx->pos == ctx->table->size) {
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
381 ctx->pos--;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
382 return NULL;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
383 }
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
384 node = &ctx->table->nodes[ctx->pos];
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
385 }
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
386 } while (node->key == NULL);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
387
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
388 return node;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
389 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
390
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
391 bool hash_table_iterate(struct hash_iterate_context *ctx,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
392 void **key_r, void **value_r)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
393 {
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
394 struct hash_node *node;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
395
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
396 node = ctx->next;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
397 if (node != NULL && node->key == NULL)
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
398 node = hash_table_iterate_next(ctx, node);
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
399 if (node == NULL) {
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
400 *key_r = *value_r = NULL;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
401 return FALSE;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
402 }
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
403 *key_r = node->key;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
404 *value_r = node->value;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
405
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
406 ctx->next = hash_table_iterate_next(ctx, node);
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
407 return TRUE;
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
408 }
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
409
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
410 void hash_table_iterate_deinit(struct hash_iterate_context **_ctx)
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
411 {
6417
047d0d8bbf0a hash_destroy() and hash_iterate_deinit() now take ** pointer.
Timo Sirainen <tss@iki.fi>
parents: 5087
diff changeset
412 struct hash_iterate_context *ctx = *_ctx;
047d0d8bbf0a hash_destroy() and hash_iterate_deinit() now take ** pointer.
Timo Sirainen <tss@iki.fi>
parents: 5087
diff changeset
413
047d0d8bbf0a hash_destroy() and hash_iterate_deinit() now take ** pointer.
Timo Sirainen <tss@iki.fi>
parents: 5087
diff changeset
414 *_ctx = NULL;
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
415 hash_table_thaw(ctx->table);
1897
1e6ed8045f2b Changed hash_foreach() to iterator.
Timo Sirainen <tss@iki.fi>
parents: 1741
diff changeset
416 i_free(ctx);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
417 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
418
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
419 void hash_table_freeze(struct hash_table *table)
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
420 {
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
421 table->frozen++;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
422 }
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
423
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
424 void hash_table_thaw(struct hash_table *table)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
425 {
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
426 i_assert(table->frozen > 0);
946
3681ff89f0e2 Few fixes
Timo Sirainen <tss@iki.fi>
parents: 945
diff changeset
427
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
428 if (--table->frozen > 0)
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
429 return;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
430
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
431 if (table->removed_count > 0) {
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
432 if (!hash_table_resize(table, FALSE))
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
433 hash_table_compress_removed(table);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
434 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
435 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
436
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
437 static bool hash_table_resize(struct hash_table *table, bool grow)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
438 {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
439 struct hash_node *old_nodes, *node, *next;
3906
51db9cedc120 size_t -> unsigned int. It's enough.
Timo Sirainen <tss@iki.fi>
parents: 3879
diff changeset
440 unsigned int next_size, old_size, i;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
441 float nodes_per_list;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
442
21412
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
443 i_assert(table->frozen == 0);
7ff9bc554381 lib: Add asserts to make sure hash table isn't freed while it's frozen.
Timo Sirainen <timo.sirainen@dovecot.fi>
parents: 21390
diff changeset
444
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
445 nodes_per_list = (float) table->nodes_count / (float) table->size;
974
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
446 if (nodes_per_list > 0.3 && nodes_per_list < 2.0)
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
447 return FALSE;
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
448
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
449 next_size = I_MAX(primes_closest(table->nodes_count+1),
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
450 table->initial_size);
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
451 if (next_size == table->size)
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
452 return FALSE;
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
453
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
454 if (grow && table->size >= next_size)
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
455 return FALSE;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
456
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
457 /* recreate primary table */
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
458 old_size = table->size;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
459 old_nodes = table->nodes;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
460
974
d9df59a406fb Still more fixes
Timo Sirainen <tss@iki.fi>
parents: 972
diff changeset
461 table->size = I_MAX(next_size, HASH_TABLE_MIN_SIZE);
14917
1ce71b5bc94a hash_table_create(): Removed table_pool parameter.
Timo Sirainen <tss@iki.fi>
parents: 14689
diff changeset
462 table->nodes = i_new(struct hash_node, table->size);
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
463
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
464 table->nodes_count = 0;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
465 table->removed_count = 0;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
466
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
467 table->frozen++;
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
468
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
469 /* move the data */
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
470 for (i = 0; i < old_size; i++) {
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
471 node = &old_nodes[i];
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
472 if (node->key != NULL) {
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
473 hash_table_insert_node(table, node->key,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
474 node->value, FALSE);
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
475 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
476
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
477 for (node = node->next; node != NULL; node = next) {
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
478 next = node->next;
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
479
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
480 if (node->key != NULL) {
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
481 hash_table_insert_node(table, node->key,
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
482 node->value, FALSE);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
483 }
972
0857c8c7ddf9 Removed the collision table, it was a bad idea and was buggy when nodes were
Timo Sirainen <tss@iki.fi>
parents: 957
diff changeset
484 free_node(table, node);
957
c1a97fc30d1c hash_resize() leaked memory, hash_insert/update didn't update value for
Timo Sirainen <tss@iki.fi>
parents: 953
diff changeset
485 }
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
486 }
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
487
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
488 table->frozen--;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
489
14917
1ce71b5bc94a hash_table_create(): Removed table_pool parameter.
Timo Sirainen <tss@iki.fi>
parents: 14689
diff changeset
490 i_free(old_nodes);
945
501f076f2e74 Rewrote hash table code, works with less memory now. Also some memory
Timo Sirainen <tss@iki.fi>
parents: 942
diff changeset
491 return TRUE;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
492 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
493
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
494 void hash_table_copy(struct hash_table *dest, struct hash_table *src)
3616
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
495 {
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
496 struct hash_iterate_context *iter;
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
497 void *key, *value;
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
498
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
499 hash_table_freeze(dest);
3616
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
500
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
501 iter = hash_table_iterate_init(src);
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
502 while (hash_table_iterate(iter, &key, &value))
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
503 hash_table_insert(dest, key, value);
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
504 hash_table_iterate_deinit(&iter);
3616
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
505
8573
f9166a09423a Renamed hash_*() to hash_table_*() to avoid conflicts with OSX's strhash.h
Timo Sirainen <tss@iki.fi>
parents: 8442
diff changeset
506 hash_table_thaw(dest);
3616
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
507 }
906b87e236bf Added hash_copy() and added some consts
Timo Sirainen <tss@iki.fi>
parents: 1899
diff changeset
508
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
509 /* a char* hash function from ASU -- from glib */
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
510 unsigned int str_hash(const char *p)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
511 {
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
512 const unsigned char *s = (const unsigned char *)p;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
513 unsigned int g, h = 0;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
514
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
515 while (*s != '\0') {
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
516 h = (h << 4) + *s;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
517 if ((g = h & 0xf0000000UL)) {
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
518 h = h ^ (g >> 24);
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
519 h = h ^ g;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
520 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
521 s++;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
522 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
523
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
524 return h;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
525 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
526
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
527 /* a char* hash function from ASU -- from glib */
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
528 unsigned int strcase_hash(const char *p)
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
529 {
14918
8eae4e205c82 Hash table API is now (mostly) type safe.
Timo Sirainen <tss@iki.fi>
parents: 14917
diff changeset
530 const unsigned char *s = (const unsigned char *)p;
0
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
531 unsigned int g, h = 0;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
532
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
533 while (*s != '\0') {
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
534 h = (h << 4) + i_toupper(*s);
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
535 if ((g = h & 0xf0000000UL)) {
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
536 h = h ^ (g >> 24);
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
537 h = h ^ g;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
538 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
539 s++;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
540 }
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
541
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
542 return h;
3b1985cbc908 Initial revision
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
543 }
13222
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
544
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
545 unsigned int mem_hash(const void *p, unsigned int size)
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
546 {
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
547 const unsigned char *s = p;
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
548 unsigned int i, g, h = 0;
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
549
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
550 for (i = 0; i < size; i++) {
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
551 h = (h << 4) + *s;
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
552 if ((g = h & 0xf0000000UL)) {
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
553 h = h ^ (g >> 24);
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
554 h = h ^ g;
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
555 }
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
556 s++;
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
557 }
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
558 return h;
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
559 }
83699b38229b liblib: Added generic mem_hash()
Timo Sirainen <tss@iki.fi>
parents: 12782
diff changeset
560