Mercurial > gnulib
annotate lib/gl_linkedhash_map.c @ 40186:8964917f9574
autoupdate
| author | Karl Berry <karl@freefriends.org> |
|---|---|
| date | Mon, 18 Feb 2019 08:02:49 -0800 |
| parents | b06060465f09 |
| children |
| rev | line source |
|---|---|
| 40019 | 1 /* Map data type implemented by a hash table with a linked list. |
|
40057
b06060465f09
maint: Run 'make update-copyright'
Paul Eggert <eggert@cs.ucla.edu>
parents:
40019
diff
changeset
|
2 Copyright (C) 2006, 2008-2019 Free Software Foundation, Inc. |
| 40019 | 3 Written by Bruno Haible <bruno@clisp.org>, 2018. |
| 4 | |
| 5 This program is free software: you can redistribute it and/or modify | |
| 6 it under the terms of the GNU General Public License as published by | |
| 7 the Free Software Foundation; either version 3 of the License, or | |
| 8 (at your option) any later version. | |
| 9 | |
| 10 This program is distributed in the hope that it will be useful, | |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 13 GNU General Public License for more details. | |
| 14 | |
| 15 You should have received a copy of the GNU General Public License | |
| 16 along with this program. If not, see <https://www.gnu.org/licenses/>. */ | |
| 17 | |
| 18 #include <config.h> | |
| 19 | |
| 20 /* Specification. */ | |
| 21 #include "gl_linkedhash_map.h" | |
| 22 | |
| 23 #include <stdint.h> /* for SIZE_MAX */ | |
| 24 #include <stdlib.h> | |
| 25 | |
| 26 #include "xsize.h" | |
| 27 | |
| 28 #ifndef uintptr_t | |
| 29 # define uintptr_t unsigned long | |
| 30 #endif | |
| 31 | |
| 32 /* --------------------------- gl_map_t Data Type --------------------------- */ | |
| 33 | |
| 34 #include "gl_anyhash1.h" | |
| 35 | |
| 36 /* Concrete list node implementation, valid for this file only. */ | |
| 37 struct gl_list_node_impl | |
| 38 { | |
| 39 struct gl_hash_entry h; /* hash table entry fields; must be first */ | |
| 40 struct gl_list_node_impl *next; | |
| 41 struct gl_list_node_impl *prev; | |
| 42 const void *key; | |
| 43 const void *value; | |
| 44 }; | |
| 45 typedef struct gl_list_node_impl * gl_list_node_t; | |
| 46 | |
| 47 /* Concrete gl_map_impl type, valid for this file only. */ | |
| 48 struct gl_map_impl | |
| 49 { | |
| 50 struct gl_map_impl_base base; | |
| 51 gl_mapkey_hashcode_fn hashcode_fn; | |
| 52 /* A hash table: managed as an array of collision lists. */ | |
| 53 struct gl_hash_entry **table; | |
| 54 size_t table_size; | |
| 55 /* A circular list anchored at root. | |
| 56 The first node is = root.next, the last node is = root.prev. | |
| 57 The root's value is unused. */ | |
| 58 struct gl_list_node_impl root; | |
| 59 /* Number of list nodes, excluding the root. */ | |
| 60 size_t count; | |
| 61 }; | |
| 62 | |
| 63 #define CONTAINER_T gl_map_t | |
| 64 #define CONTAINER_COUNT(map) (map)->count | |
| 65 #include "gl_anyhash2.h" | |
| 66 | |
| 67 /* If the symbol SIGNAL_SAFE_MAP is defined, the code is compiled in such | |
| 68 a way that a gl_map_t data structure may be used from within a signal | |
| 69 handler. The operations allowed in the signal handler are: | |
| 70 gl_map_iterator, gl_map_iterator_next, gl_map_iterator_free. | |
| 71 The map and node fields that are therefore accessed from the signal handler | |
| 72 are: | |
| 73 map->root, node->next, node->value. | |
| 74 We are careful to make modifications to these fields only in an order | |
| 75 that maintains the consistency of the list data structure at any moment, | |
| 76 and we use 'volatile' assignments to prevent the compiler from reordering | |
| 77 such assignments. */ | |
| 78 #ifdef SIGNAL_SAFE_MAP | |
| 79 # define ASYNCSAFE(type) *(type volatile *)& | |
| 80 #else | |
| 81 # define ASYNCSAFE(type) | |
| 82 #endif | |
| 83 | |
| 84 /* --------------------------- gl_map_t Data Type --------------------------- */ | |
| 85 | |
| 86 static gl_map_t | |
| 87 gl_linkedhash_nx_create_empty (gl_map_implementation_t implementation, | |
| 88 gl_mapkey_equals_fn equals_fn, | |
| 89 gl_mapkey_hashcode_fn hashcode_fn, | |
| 90 gl_mapkey_dispose_fn kdispose_fn, | |
| 91 gl_mapvalue_dispose_fn vdispose_fn) | |
| 92 { | |
| 93 struct gl_map_impl *map = | |
| 94 (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl)); | |
| 95 | |
| 96 if (map == NULL) | |
| 97 return NULL; | |
| 98 | |
| 99 map->base.vtable = implementation; | |
| 100 map->base.equals_fn = equals_fn; | |
| 101 map->base.kdispose_fn = kdispose_fn; | |
| 102 map->base.vdispose_fn = vdispose_fn; | |
| 103 map->hashcode_fn = hashcode_fn; | |
| 104 map->table_size = 11; | |
| 105 map->table = | |
| 106 (gl_hash_entry_t *) calloc (map->table_size, sizeof (gl_hash_entry_t)); | |
| 107 if (map->table == NULL) | |
| 108 goto fail; | |
| 109 map->root.next = &map->root; | |
| 110 map->root.prev = &map->root; | |
| 111 map->count = 0; | |
| 112 | |
| 113 return map; | |
| 114 | |
| 115 fail: | |
| 116 free (map); | |
| 117 return NULL; | |
| 118 } | |
| 119 | |
| 120 static size_t _GL_ATTRIBUTE_PURE | |
| 121 gl_linkedhash_size (gl_map_t map) | |
| 122 { | |
| 123 return map->count; | |
| 124 } | |
| 125 | |
| 126 static bool _GL_ATTRIBUTE_PURE | |
| 127 gl_linkedhash_search (gl_map_t map, const void *key, const void **valuep) | |
| 128 { | |
| 129 size_t hashcode = | |
| 130 (map->hashcode_fn != NULL | |
| 131 ? map->hashcode_fn (key) | |
| 132 : (size_t)(uintptr_t) key); | |
| 133 size_t bucket = hashcode % map->table_size; | |
| 134 gl_mapkey_equals_fn equals = map->base.equals_fn; | |
| 135 | |
| 136 /* Look for a match in the hash bucket. */ | |
| 137 gl_list_node_t node; | |
| 138 | |
| 139 for (node = (gl_list_node_t) map->table[bucket]; | |
| 140 node != NULL; | |
| 141 node = (gl_list_node_t) node->h.hash_next) | |
| 142 if (node->h.hashcode == hashcode | |
| 143 && (equals != NULL | |
| 144 ? equals (key, node->key) | |
| 145 : key == node->key)) | |
| 146 { | |
| 147 *valuep = node->value; | |
| 148 return true; | |
| 149 } | |
| 150 return false; | |
| 151 } | |
| 152 | |
| 153 static int | |
| 154 gl_linkedhash_nx_getput (gl_map_t map, const void *key, const void *value, | |
| 155 const void **oldvaluep) | |
| 156 { | |
| 157 size_t hashcode = | |
| 158 (map->hashcode_fn != NULL | |
| 159 ? map->hashcode_fn (key) | |
| 160 : (size_t)(uintptr_t) key); | |
| 161 size_t bucket = hashcode % map->table_size; | |
| 162 gl_mapkey_equals_fn equals = map->base.equals_fn; | |
| 163 | |
| 164 /* Look for a match in the hash bucket. */ | |
| 165 { | |
| 166 gl_list_node_t node; | |
| 167 | |
| 168 for (node = (gl_list_node_t) map->table[bucket]; | |
| 169 node != NULL; | |
| 170 node = (gl_list_node_t) node->h.hash_next) | |
| 171 if (node->h.hashcode == hashcode | |
| 172 && (equals != NULL | |
| 173 ? equals (key, node->key) | |
| 174 : key == node->key)) | |
| 175 { | |
| 176 *oldvaluep = node->value; | |
| 177 node->value = value; | |
| 178 return 0; | |
| 179 } | |
| 180 } | |
| 181 | |
| 182 /* Allocate a new node. */ | |
| 183 gl_list_node_t node = | |
| 184 (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); | |
| 185 | |
| 186 if (node == NULL) | |
| 187 return -1; | |
| 188 | |
| 189 ASYNCSAFE(const void *) node->key = key; | |
| 190 ASYNCSAFE(const void *) node->value = value; | |
| 191 node->h.hashcode = hashcode; | |
| 192 | |
| 193 /* Add node to the hash table. */ | |
| 194 node->h.hash_next = map->table[bucket]; | |
| 195 map->table[bucket] = &node->h; | |
| 196 | |
| 197 /* Add node to the map. */ | |
| 198 ASYNCSAFE(gl_list_node_t) node->next = &map->root; | |
| 199 node->prev = map->root.prev; | |
| 200 ASYNCSAFE(gl_list_node_t) node->prev->next = node; | |
| 201 map->root.prev = node; | |
| 202 map->count++; | |
| 203 | |
| 204 hash_resize_after_add (map); | |
| 205 | |
| 206 return 1; | |
| 207 } | |
| 208 | |
| 209 static bool | |
| 210 gl_linkedhash_getremove (gl_map_t map, const void *key, const void **oldvaluep) | |
| 211 { | |
| 212 size_t hashcode = | |
| 213 (map->hashcode_fn != NULL | |
| 214 ? map->hashcode_fn (key) | |
| 215 : (size_t)(uintptr_t) key); | |
| 216 size_t bucket = hashcode % map->table_size; | |
| 217 gl_mapkey_equals_fn equals = map->base.equals_fn; | |
| 218 | |
| 219 /* Look for the first match in the hash bucket. */ | |
| 220 gl_list_node_t *nodep; | |
| 221 | |
| 222 for (nodep = (gl_list_node_t *) &map->table[bucket]; | |
| 223 *nodep != NULL; | |
| 224 nodep = (gl_list_node_t *) &(*nodep)->h.hash_next) | |
| 225 { | |
| 226 gl_list_node_t node = *nodep; | |
| 227 if (node->h.hashcode == hashcode | |
| 228 && (equals != NULL | |
| 229 ? equals (key, node->key) | |
| 230 : key == node->key)) | |
| 231 { | |
| 232 *oldvaluep = node->value; | |
| 233 | |
| 234 /* Remove node from the hash table. */ | |
| 235 *nodep = (gl_list_node_t) node->h.hash_next; | |
| 236 | |
| 237 /* Remove node from the list. */ | |
| 238 { | |
| 239 gl_list_node_t prev = node->prev; | |
| 240 gl_list_node_t next = node->next; | |
| 241 | |
| 242 ASYNCSAFE(gl_list_node_t) prev->next = next; | |
| 243 next->prev = prev; | |
| 244 } | |
| 245 map->count--; | |
| 246 | |
| 247 if (map->base.kdispose_fn != NULL) | |
| 248 map->base.kdispose_fn (node->key); | |
| 249 free (node); | |
| 250 return true; | |
| 251 } | |
| 252 } | |
| 253 | |
| 254 return false; | |
| 255 } | |
| 256 | |
| 257 static void | |
| 258 gl_linkedhash_free (gl_map_t map) | |
| 259 { | |
| 260 gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn; | |
| 261 gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn; | |
| 262 gl_list_node_t node; | |
| 263 | |
| 264 for (node = map->root.next; node != &map->root; ) | |
| 265 { | |
| 266 gl_list_node_t next = node->next; | |
| 267 if (vdispose != NULL) | |
| 268 vdispose (node->value); | |
| 269 if (kdispose != NULL) | |
| 270 kdispose (node->key); | |
| 271 free (node); | |
| 272 node = next; | |
| 273 } | |
| 274 free (map->table); | |
| 275 free (map); | |
| 276 } | |
| 277 | |
| 278 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */ | |
| 279 | |
| 280 /* Iterate through the list, not through the hash buckets, so that the order | |
| 281 in which the pairs are returned is predictable. */ | |
| 282 | |
| 283 static gl_map_iterator_t | |
| 284 gl_linkedhash_iterator (gl_map_t map) | |
| 285 { | |
| 286 gl_map_iterator_t result; | |
| 287 | |
| 288 result.vtable = map->base.vtable; | |
| 289 result.map = map; | |
| 290 result.p = map->root.next; | |
| 291 result.q = &map->root; | |
| 292 #if defined GCC_LINT || defined lint | |
| 293 result.i = 0; | |
| 294 result.j = 0; | |
| 295 result.count = 0; | |
| 296 #endif | |
| 297 | |
| 298 return result; | |
| 299 } | |
| 300 | |
| 301 static bool | |
| 302 gl_linkedhash_iterator_next (gl_map_iterator_t *iterator, | |
| 303 const void **keyp, const void **valuep) | |
| 304 { | |
| 305 if (iterator->p != iterator->q) | |
| 306 { | |
| 307 gl_list_node_t node = (gl_list_node_t) iterator->p; | |
| 308 *keyp = node->key; | |
| 309 *valuep = node->value; | |
| 310 iterator->p = node->next; | |
| 311 return true; | |
| 312 } | |
| 313 else | |
| 314 return false; | |
| 315 } | |
| 316 | |
| 317 static void | |
| 318 gl_linkedhash_iterator_free (gl_map_iterator_t *iterator) | |
| 319 { | |
| 320 } | |
| 321 | |
| 322 | |
| 323 const struct gl_map_implementation gl_linkedhash_map_implementation = | |
| 324 { | |
| 325 gl_linkedhash_nx_create_empty, | |
| 326 gl_linkedhash_size, | |
| 327 gl_linkedhash_search, | |
| 328 gl_linkedhash_nx_getput, | |
| 329 gl_linkedhash_getremove, | |
| 330 gl_linkedhash_free, | |
| 331 gl_linkedhash_iterator, | |
| 332 gl_linkedhash_iterator_next, | |
| 333 gl_linkedhash_iterator_free | |
| 334 }; |