Mercurial > dovecot > core-2.2

annotate src/lib/hash2.c @ 23007:36e01285b5b8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
lib: buffer - Improve header comment for buffer_insert() and buffer_delete().
author Stephan Bosch <stephan.bosch@dovecot.fi>
date Mon, 18 Mar 2019 00:52:37 +0100
parents cb108f786fb4
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
22713
cb108f786fb4 Updated copyright notices to include the year 2018.
Stephan Bosch <stephan.bosch@dovecot.fi>
parents: 21390
diff changeset
1 /* Copyright (c) 2002-2018 Dovecot authors, see the included COPYING file */
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3 #include "lib.h"
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4 #include "array.h"
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 #include "primes.h"
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6 #include "hash2.h"
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
7
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
8 #define HASH_TABLE_MIN_SIZE 131
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
9
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
10 struct hash2_value {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 struct hash2_value *next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 unsigned int key_hash;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
13 /* user_data[value_size] */
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14 };
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
15 ARRAY_DEFINE_TYPE(hash2_value, struct hash2_value *);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 struct hash2_table {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18 unsigned int count;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19 unsigned int initial_size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 unsigned int hash_table_size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21 unsigned int value_size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 pool_t value_pool;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
24 struct hash2_value *deleted_values;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 ARRAY_TYPE(hash2_value) hash_table;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 hash2_key_callback_t *key_hash_cb;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29 hash2_cmp_callback_t *key_compare_cb;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30 void *context;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 };
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
33 static void hash2_alloc_table(struct hash2_table *hash, unsigned int size)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
34 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
35 hash->hash_table_size = size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
36
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
37 i_array_init(&hash->hash_table, hash->hash_table_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
38 (void)array_idx_modifiable(&hash->hash_table, hash->hash_table_size-1);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
39 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
41 struct hash2_table *
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
42 hash2_create(unsigned int initial_size, unsigned int value_size,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
43 hash2_key_callback_t *key_hash_cb,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
44 hash2_cmp_callback_t *key_compare_cb, void *context)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
45 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
46 struct hash2_table *hash;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
47
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
48 hash = i_new(struct hash2_table, 1);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
49 hash->initial_size = I_MAX(initial_size, HASH_TABLE_MIN_SIZE);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
50 hash->value_size = value_size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
51 hash->key_hash_cb = key_hash_cb;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
52 hash->key_compare_cb = key_compare_cb;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
53 hash->context = context;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
54
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
55 hash->value_pool = pool_alloconly_create("hash2 value pool", 16384);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
56 hash2_alloc_table(hash, hash->initial_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
57 return hash;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
58 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
59
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
60 void hash2_destroy(struct hash2_table **_hash)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
61 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
62 struct hash2_table *hash = *_hash;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
63
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
64 *_hash = NULL;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
65 array_free(&hash->hash_table);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
66 pool_unref(&hash->value_pool);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
67 i_free(hash);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
68 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
69
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
70 void hash2_clear(struct hash2_table *hash)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
71 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
72 array_free(&hash->hash_table);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
73 hash2_alloc_table(hash, hash->initial_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
74 p_clear(hash->value_pool);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
75 hash->count = 0;
8153
30fedb49296e hash2_clear() didn't reset deleted_values list, causing bugs later on.
Timo Sirainen <tss@iki.fi>
parents: 8151
diff changeset
76 hash->deleted_values = NULL;
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
77 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
78
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
79 static void hash2_resize(struct hash2_table *hash, bool grow)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
80 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
81 ARRAY_TYPE(hash2_value) old_hash_table;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82 struct hash2_value *const *old_hash, *value, **valuep, *next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
83 unsigned int next_size, old_count, i, idx;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 float nodes_per_list;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
85
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
86 nodes_per_list = (float)hash->count / (float)hash->hash_table_size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
87 if (nodes_per_list > 0.3 && nodes_per_list < 2.0)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
88 return;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
89
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
90 next_size = I_MAX(primes_closest(hash->count + 1), hash->initial_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
91 if (hash->hash_table_size >= next_size &&
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
92 (grow || next_size == hash->hash_table_size))
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
93 return;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
94
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
95 old_hash_table = hash->hash_table;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
96 hash2_alloc_table(hash, next_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
97
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
98 old_count = array_count(&old_hash_table);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
99 for (i = 0; i < old_count; i++) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
100 old_hash = array_idx(&old_hash_table, i);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
101 for (value = *old_hash; value != NULL; value = next) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
102 next = value->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
103
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
104 idx = value->key_hash % hash->hash_table_size;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
105 valuep = array_idx_modifiable(&hash->hash_table, idx);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
106 value->next = *valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
107 *valuep = value;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
108 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
109 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
110 array_free(&old_hash_table);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
111 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
112
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
113 void *hash2_lookup(const struct hash2_table *hash, const void *key)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
114 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
115 unsigned int key_hash = hash->key_hash_cb(key);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
116 struct hash2_value *const *valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
117 struct hash2_value *value;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
118 void *user_value;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
119
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
120 valuep = array_idx(&hash->hash_table, key_hash % hash->hash_table_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
121 value = *valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
122 while (value != NULL) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
123 if (value->key_hash == key_hash) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
124 user_value = value + 1;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
125 if (hash->key_compare_cb(key, user_value,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
126 hash->context))
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
127 return user_value;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
128 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
129 value = value->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
130 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
131 return NULL;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
132 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
133
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
134 void *hash2_iterate(const struct hash2_table *hash,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
135 unsigned int key_hash, struct hash2_iter *iter)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
136 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
137 struct hash2_value *const *valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
138
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
139 if (iter->value == NULL) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
140 iter->key_hash = key_hash;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
141 valuep = array_idx(&hash->hash_table,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
142 key_hash % hash->hash_table_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143 iter->next_value = *valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
144 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
145 while (iter->next_value != NULL) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
146 if (iter->next_value->key_hash == key_hash) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
147 iter->value = iter->next_value;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
148 iter->next_value = iter->next_value->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
149 return iter->value + 1;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
151 iter->next_value = iter->next_value->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
152 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153 return NULL;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
155
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
156 void *hash2_insert(struct hash2_table *hash, const void *key)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
157 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
158 return hash2_insert_hash(hash, hash->key_hash_cb(key));
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
159 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
160
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
161 void *hash2_insert_hash(struct hash2_table *hash, unsigned int key_hash)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
163 struct hash2_value *value, **valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
164
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
165 hash2_resize(hash, TRUE);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
166
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
167 if (hash->deleted_values != NULL) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
168 value = hash->deleted_values;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
169 hash->deleted_values = value->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
170 value->next = NULL;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
171 memset(value + 1, 0, hash->value_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
172 } else {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
173 value = p_malloc(hash->value_pool,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
174 sizeof(*value) + hash->value_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
175 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
176 value->key_hash = key_hash;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
177
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
178 valuep = array_idx_modifiable(&hash->hash_table,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
179 key_hash % hash->hash_table_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
180 value->next = *valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
181 *valuep = value;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
182
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
183 hash->count++;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
184 return value + 1;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
185 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
186
8151
10a5483c0d02 hash2_remove_iter(): Never resize hash table, otherwise iteration breaks.
Timo Sirainen <tss@iki.fi>
parents: 8150
diff changeset
187 static void
8154
f15ce57d84d1 hash2: minor code cleanup.
Timo Sirainen <tss@iki.fi>
parents: 8153
diff changeset
188 hash2_remove_value_p(struct hash2_table *hash, struct hash2_value **valuep)
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
189 {
8150
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
190 struct hash2_value *deleted_value;
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
191
8150
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
192 deleted_value = *valuep;
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
193 *valuep = deleted_value->next;
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
194
8150
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
195 deleted_value->next = hash->deleted_values;
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
196 hash->deleted_values = deleted_value;
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
197
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
198 hash->count--;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
199 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
200
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
201 void hash2_remove(struct hash2_table *hash, const void *key)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
202 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
203 unsigned int key_hash = hash->key_hash_cb(key);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
204 struct hash2_value **valuep;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
205
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
206 valuep = array_idx_modifiable(&hash->hash_table,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
207 key_hash % hash->hash_table_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
208 while (*valuep != NULL) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
209 if ((*valuep)->key_hash == key_hash &&
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
210 hash->key_compare_cb(key, (*valuep) + 1, hash->context)) {
8154
f15ce57d84d1 hash2: minor code cleanup.
Timo Sirainen <tss@iki.fi>
parents: 8153
diff changeset
211 hash2_remove_value_p(hash, valuep);
f15ce57d84d1 hash2: minor code cleanup.
Timo Sirainen <tss@iki.fi>
parents: 8153
diff changeset
212 hash2_resize(hash, FALSE);
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
213 return;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
214 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
215 valuep = &(*valuep)->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
216 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
217 i_panic("hash2_remove(): key not found");
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
218 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
219
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
220 void hash2_remove_iter(struct hash2_table *hash, struct hash2_iter *iter)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
221 {
8150
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
222 struct hash2_value **valuep, *next;
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
223
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
224 valuep = array_idx_modifiable(&hash->hash_table,
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
225 iter->key_hash % hash->hash_table_size);
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
226 while (*valuep != NULL) {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
227 if (*valuep == iter->value) {
8150
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
228 next = (*valuep)->next;
8151
10a5483c0d02 hash2_remove_iter(): Never resize hash table, otherwise iteration breaks.
Timo Sirainen <tss@iki.fi>
parents: 8150
diff changeset
229 /* don't allow resizing, otherwise iterating would
10a5483c0d02 hash2_remove_iter(): Never resize hash table, otherwise iteration breaks.
Timo Sirainen <tss@iki.fi>
parents: 8150
diff changeset
230 break completely */
8154
f15ce57d84d1 hash2: minor code cleanup.
Timo Sirainen <tss@iki.fi>
parents: 8153
diff changeset
231 hash2_remove_value_p(hash, valuep);
8150
7b5120f7f732 hash2_remove_iter() was broken when it resized the hash table.
Timo Sirainen <tss@iki.fi>
parents: 8143
diff changeset
232 iter->next_value = next;
8143
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
233 return;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
234 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
235 valuep = &(*valuep)->next;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
236 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
237 i_panic("hash2_remove_value(): key/value not found");
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
238 }
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
239
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
240 unsigned int hash2_count(const struct hash2_table *hash)
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
241 {
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
242 return hash->count;
29ed66459a74 Added an alternative hash table implementation.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
243 }