src/ucx/hash_map.c

Fri, 05 May 2023 18:02:11 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Fri, 05 May 2023 18:02:11 +0200
changeset 490
d218607f5a7e
parent 484
c036a8b242a8
child 504
c094afcdfb27
permissions
-rw-r--r--

update ucx

415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
29 #include <string.h>
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
30 #include "cx/hash_map.h"
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
31 #include "cx/utils.h"
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
33 struct cx_hash_map_element_s {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
34 /** A pointer to the next element in the current bucket. */
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
35 struct cx_hash_map_element_s *next;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
36
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
37 /** The corresponding key. */
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
38 CxHashKey key;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
39
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
40 /** The value data. */
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
41 char data[];
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
42 };
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
43
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 static void cx_hash_map_clear(struct cx_map_s *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 cx_for_n(i, hash_map->bucket_count) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
47 struct cx_hash_map_element_s *elem = hash_map->buckets[i];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 if (elem != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 do {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 struct cx_hash_map_element_s *next = elem->next;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
51 // invoke the destructor
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
52 cx_invoke_destructor(map, elem->data);
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 // free the key data
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
54 cxFree(map->allocator, (void *) elem->key.data);
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 // free the node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
56 cxFree(map->allocator, elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
57 // proceed
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
58 elem = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59 } while (elem != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61 // do not leave a dangling pointer
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 hash_map->buckets[i] = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
65 map->size = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 static void cx_hash_map_destructor(struct cx_map_s *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
71 // free the buckets
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
72 cx_hash_map_clear(map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 cxFree(map->allocator, hash_map->buckets);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 // free the map structure
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 cxFree(map->allocator, map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79 static int cx_hash_map_put(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
80 CxMap *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 CxHashKey key,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
82 void *value
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
83 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
84 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
85 CxAllocator const *allocator = map->allocator;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 unsigned hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
88 if (hash == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
89 cx_hash_murmur(&key);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90 hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93 size_t slot = hash % hash_map->bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 struct cx_hash_map_element_s *prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97 while (elm != NULL && elm->key.hash < hash) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
98 prev = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
99 elm = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
103 memcmp(elm->key.data, key.data, key.len) == 0) {
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104 // overwrite existing element
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
105 if (map->store_pointer) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
106 memcpy(elm->data, &value, sizeof(void *));
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
107 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
108 memcpy(elm->data, value, map->item_size);
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
109 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 // allocate new element
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
112 struct cx_hash_map_element_s *e = cxMalloc(
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
113 allocator,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
114 sizeof(struct cx_hash_map_element_s) + map->item_size
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
115 );
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 if (e == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117 return -1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
119
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
120 // write the value
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
121 if (map->store_pointer) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
122 memcpy(e->data, &value, sizeof(void *));
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
123 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
124 memcpy(e->data, value, map->item_size);
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
125 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 // copy the key
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128 void *kd = cxMalloc(allocator, key.len);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 if (kd == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 return -1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 }
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
132 memcpy(kd, key.data, key.len);
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
133 e->key.data = kd;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 e->key.len = key.len;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 e->key.hash = hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
137 // insert the element into the linked list
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 if (prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 hash_map->buckets[slot] = e;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141 prev->next = e;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
142 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
143 e->next = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
144
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 // increase the size
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
146 map->size++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
147 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
148
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
149 return 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
150 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
151
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
152 static void cx_hash_map_unlink(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
153 struct cx_hash_map_s *hash_map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 size_t slot,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155 struct cx_hash_map_element_s *prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 struct cx_hash_map_element_s *elm
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 // unlink
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 if (prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160 hash_map->buckets[slot] = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
162 prev->next = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
164 // free element
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
165 cxFree(hash_map->base.allocator, (void *) elm->key.data);
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
166 cxFree(hash_map->base.allocator, elm);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
167 // decrease size
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
168 hash_map->base.size--;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
169 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
170
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
171 /**
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
172 * Helper function to avoid code duplication.
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 *
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 * @param map the map
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 * @param key the key to look up
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176 * @param remove flag indicating whether the looked up entry shall be removed
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
177 * @param destroy flag indicating whether the destructor shall be invoked
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
178 * @return a pointer to the value corresponding to the key or \c NULL
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
179 */
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
180 static void *cx_hash_map_get_remove(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
181 CxMap *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
182 CxHashKey key,
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
183 bool remove,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
184 bool destroy
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
185 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
186 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
187
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
188 unsigned hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
189 if (hash == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
190 cx_hash_murmur(&key);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
191 hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
192 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
193
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
194 size_t slot = hash % hash_map->bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
195 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
196 struct cx_hash_map_element_s *prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 while (elm && elm->key.hash <= hash) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
198 if (elm->key.hash == hash && elm->key.len == key.len) {
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
199 if (memcmp(elm->key.data, key.data, key.len) == 0) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
200 void *data = NULL;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
201 if (destroy) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
202 cx_invoke_destructor(map, elm->data);
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
203 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
204 if (map->store_pointer) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
205 data = *(void **) elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
206 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
207 data = elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
208 }
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
209 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210 if (remove) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
211 cx_hash_map_unlink(hash_map, slot, prev, elm);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
212 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
213 return data;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
215 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
216 prev = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
217 elm = prev->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
218 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
219
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
220 return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
221 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
222
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
223 static void *cx_hash_map_get(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
224 CxMap const *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
225 CxHashKey key
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 ) {
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
227 // we can safely cast, because we know the map stays untouched
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
228 return cx_hash_map_get_remove((CxMap *) map, key, false, false);
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
229 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
230
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 static void *cx_hash_map_remove(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
232 CxMap *map,
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
233 CxHashKey key,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
234 bool destroy
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
235 ) {
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
236 return cx_hash_map_get_remove(map, key, true, destroy);
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
239 static void *cx_hash_map_iter_current_entry(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
240 struct cx_iterator_s const *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 // struct has to have a compatible signature
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242 return (struct cx_map_entry_s *) &(iter->kv_data);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
243 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
244
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
245 static void *cx_hash_map_iter_current_key(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
246 struct cx_iterator_s const *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
247 struct cx_hash_map_element_s *elm = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
248 return &elm->key;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
249 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
250
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
251 static void *cx_hash_map_iter_current_value(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
252 struct cx_iterator_s const *iter = it;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
253 struct cx_hash_map_s const *map = iter->src_handle;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
254 struct cx_hash_map_element_s *elm = iter->elem_handle;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
255 if (map->base.store_pointer) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
256 return *(void **) elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
257 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
258 return elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
259 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
260 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
261
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
262 static bool cx_hash_map_iter_valid(void const *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
263 struct cx_iterator_s const *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
264 return iter->elem_handle != NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
265 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
266
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
267 static void cx_hash_map_iter_next(void *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
268 struct cx_iterator_s *iter = it;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
269 struct cx_hash_map_element_s *elm = iter->elem_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
270
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
271 // remove current element, if asked
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
272 if (iter->base.remove) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
273 // obtain mutable pointer to the map
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
274 struct cx_mut_iterator_s *miter = it;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
275 struct cx_hash_map_s *map = miter->src_handle;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
276
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
277 // clear the flag
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
278 iter->base.remove = false;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
279
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
280 // determine the next element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
281 struct cx_hash_map_element_s *next = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
282
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
283 // search the previous element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
284 struct cx_hash_map_element_s *prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
285 if (map->buckets[iter->slot] != elm) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
286 prev = map->buckets[iter->slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
287 while (prev->next != elm) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
288 prev = prev->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
289 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
290 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
291
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
292 // destroy
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
293 cx_invoke_destructor((struct cx_map_s *) map, elm->data);
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
294
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
295 // unlink
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
296 cx_hash_map_unlink(map, iter->slot, prev, elm);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
297
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
298 // advance
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
299 elm = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
300 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
301 // just advance
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
302 elm = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
303 iter->index++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
304 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
305
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
306 // search the next bucket, if required
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
307 struct cx_hash_map_s const *map = iter->src_handle;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
308 while (elm == NULL && ++iter->slot < map->bucket_count) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
309 elm = map->buckets[iter->slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
310 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
311
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
312 // fill the struct with the next element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
313 iter->elem_handle = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
314 if (elm == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
315 iter->kv_data.key = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
316 iter->kv_data.value = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
317 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
318 iter->kv_data.key = &elm->key;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
319 if (map->base.store_pointer) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
320 iter->kv_data.value = *(void **) elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
321 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
322 iter->kv_data.value = elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
323 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
324 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
325 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
326
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
327 static bool cx_hash_map_iter_flag_rm(void *it) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
328 struct cx_iterator_base_s *iter = it;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
329 if (iter->mutating) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
330 iter->remove = true;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
331 return true;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
332 } else {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
333 return false;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
334 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
335 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
336
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
337 static CxIterator cx_hash_map_iterator(CxMap const *map) {
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
338 CxIterator iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
339
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
340 iter.src_handle = map;
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
341 iter.base.valid = cx_hash_map_iter_valid;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
342 iter.base.next = cx_hash_map_iter_next;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
343 iter.base.current = cx_hash_map_iter_current_entry;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
344 iter.base.flag_removal = cx_hash_map_iter_flag_rm;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
345 iter.base.remove = false;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
346 iter.base.mutating = false;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
347
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
348 iter.slot = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
349 iter.index = 0;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
350
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
351 if (map->size > 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
352 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
353 struct cx_hash_map_element_s *elm = hash_map->buckets[0];
484
c036a8b242a8 implement webdav xattr namespace lists
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 438
diff changeset
354 while (elm == NULL) {
c036a8b242a8 implement webdav xattr namespace lists
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 438
diff changeset
355 elm = hash_map->buckets[++iter.slot];
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
356 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
357 iter.elem_handle = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
358 iter.kv_data.key = &elm->key;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
359 if (map->store_pointer) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
360 iter.kv_data.value = *(void **) elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
361 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
362 iter.kv_data.value = elm->data;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
363 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
364 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
365 iter.elem_handle = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
366 iter.kv_data.key = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
367 iter.kv_data.value = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
368 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
369
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
370 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
371 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
372
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
373 static CxIterator cx_hash_map_iterator_keys(CxMap const *map) {
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
374 CxIterator iter = cx_hash_map_iterator(map);
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
375 iter.base.current = cx_hash_map_iter_current_key;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
376 return iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
377 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
378
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
379 static CxIterator cx_hash_map_iterator_values(CxMap const *map) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
380 CxIterator iter = cx_hash_map_iterator(map);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
381 iter.base.current = cx_hash_map_iter_current_value;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
382 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
383 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
384
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
385 static CxMutIterator cx_hash_map_mut_iterator(CxMap *map) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
386 CxIterator it = cx_hash_map_iterator(map);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
387 it.base.mutating = true;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
388
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
389 // we know the iterators share the same memory layout
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
390 CxMutIterator iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
391 memcpy(&iter, &it, sizeof(CxMutIterator));
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
392 return iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
393 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
394
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
395 static CxMutIterator cx_hash_map_mut_iterator_keys(CxMap *map) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
396 CxMutIterator iter = cx_hash_map_mut_iterator(map);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
397 iter.base.current = cx_hash_map_iter_current_key;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
398 return iter;
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
399 }
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
400
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
401 static CxMutIterator cx_hash_map_mut_iterator_values(CxMap *map) {
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
402 CxMutIterator iter = cx_hash_map_mut_iterator(map);
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
403 iter.base.current = cx_hash_map_iter_current_value;
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
404 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
405 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
406
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
407 static cx_map_class cx_hash_map_class = {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
408 cx_hash_map_destructor,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
409 cx_hash_map_clear,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
410 cx_hash_map_put,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
411 cx_hash_map_get,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
412 cx_hash_map_remove,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
413 cx_hash_map_iterator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
414 cx_hash_map_iterator_keys,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
415 cx_hash_map_iterator_values,
438
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
416 cx_hash_map_mut_iterator,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
417 cx_hash_map_mut_iterator_keys,
22eca559aded refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 415
diff changeset
418 cx_hash_map_mut_iterator_values,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
419 };
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
420
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
421 CxMap *cxHashMapCreate(
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
422 CxAllocator const *allocator,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
423 size_t itemsize,
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
424 size_t buckets
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
425 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
426 if (buckets == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
427 // implementation defined default
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
428 buckets = 16;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
429 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
430
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
431 struct cx_hash_map_s *map = cxCalloc(allocator, 1,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
432 sizeof(struct cx_hash_map_s));
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
433 if (map == NULL) return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
434
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
435 // initialize hash map members
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
436 map->bucket_count = buckets;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
437 map->buckets = cxCalloc(allocator, buckets,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
438 sizeof(struct cx_hash_map_element_s *));
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
439 if (map->buckets == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
440 cxFree(allocator, map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
441 return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
442 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
443
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
444 // initialize base members
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
445 map->base.cl = &cx_hash_map_class;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
446 map->base.allocator = allocator;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
447
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
448 if (itemsize > 0) {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
449 map->base.store_pointer = false;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
450 map->base.item_size = itemsize;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
451 } else {
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
452 map->base.store_pointer = true;
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
453 map->base.item_size = sizeof(void *);
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
454 }
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
455
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
456 return (CxMap *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
457 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
458
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
459 int cxMapRehash(CxMap *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
460 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
461 if (map->size > ((hash_map->bucket_count * 3) >> 2)) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
462
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
463 size_t new_bucket_count = (map->size * 5) >> 1;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
464 struct cx_hash_map_element_s **new_buckets = cxCalloc(
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
465 map->allocator,
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
466 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
467 );
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
468
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
469 if (new_buckets == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
470 return 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
471 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
472
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
473 // iterate through the elements and assign them to their new slots
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
474 cx_for_n(slot, hash_map->bucket_count) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
475 struct cx_hash_map_element_s *elm = hash_map->buckets[slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
476 while (elm != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
477 struct cx_hash_map_element_s *next = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
478 size_t new_slot = elm->key.hash % new_bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
479
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
480 // find position where to insert
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
481 struct cx_hash_map_element_s *bucket_next = new_buckets[new_slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
482 struct cx_hash_map_element_s *bucket_prev = NULL;
490
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
483 while (bucket_next != NULL &&
d218607f5a7e update ucx
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 484
diff changeset
484 bucket_next->key.hash < elm->key.hash) {
415
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
485 bucket_prev = bucket_next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
486 bucket_next = bucket_next->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
487 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
488
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
489 // insert
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
490 if (bucket_prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
491 elm->next = new_buckets[new_slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
492 new_buckets[new_slot] = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
493 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
494 bucket_prev->next = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
495 elm->next = bucket_next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
496 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
497
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
498 // advance
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
499 elm = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
500 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
501 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
502
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
503 // assign result to the map
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
504 hash_map->bucket_count = new_bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
505 cxFree(map->allocator, hash_map->buckets);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
506 hash_map->buckets = new_buckets;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
507 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
508 return 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
509 }

mercurial