Wed, 05 Jun 2024 19:50:44 +0200
add extra nullptr check in the event loop to handle the case when the finish ptr is set to NULL after it was already scheduled
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 "cx/hash_map.h" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
30 | #include "cx/utils.h" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31 | |
504 | 32 | #include <string.h> |
33 | #include <assert.h> | |
34 | ||
490 | 35 | struct cx_hash_map_element_s { |
36 | /** A pointer to the next element in the current bucket. */ | |
37 | struct cx_hash_map_element_s *next; | |
38 | ||
39 | /** The corresponding key. */ | |
40 | CxHashKey key; | |
41 | ||
42 | /** The value data. */ | |
43 | char data[]; | |
44 | }; | |
45 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | 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
|
47 | 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
|
48 | cx_for_n(i, hash_map->bucket_count) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
49 | 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
|
50 | if (elem != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51 | do { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52 | struct cx_hash_map_element_s *next = elem->next; |
490 | 53 | // invoke the destructor |
54 | cx_invoke_destructor(map, elem->data); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55 | // free the key data |
490 | 56 | cxFree(map->allocator, (void *) elem->key.data); |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57 | // free the node |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58 | cxFree(map->allocator, elem); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
59 | // proceed |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60 | elem = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61 | } while (elem != NULL); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
63 | // do not leave a dangling pointer |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
64 | hash_map->buckets[i] = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
65 | } |
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 | map->size = 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
68 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
69 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70 | 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
|
71 | 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
|
72 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
73 | // free the buckets |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
74 | cx_hash_map_clear(map); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
75 | cxFree(map->allocator, hash_map->buckets); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77 | // free the map structure |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78 | cxFree(map->allocator, map); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
80 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
81 | static int cx_hash_map_put( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
82 | CxMap *map, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
83 | CxHashKey key, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84 | void *value |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86 | struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map; |
490 | 87 | CxAllocator const *allocator = map->allocator; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
88 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
89 | unsigned hash = key.hash; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
90 | if (hash == 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
91 | cx_hash_murmur(&key); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
92 | hash = key.hash; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
93 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
94 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
95 | size_t slot = hash % hash_map->bucket_count; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
96 | 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
|
97 | struct cx_hash_map_element_s *prev = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
98 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
99 | while (elm != NULL && elm->key.hash < hash) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
100 | prev = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
101 | elm = elm->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
102 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
103 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
104 | if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len && |
490 | 105 | 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
|
106 | // overwrite existing element |
490 | 107 | if (map->store_pointer) { |
108 | memcpy(elm->data, &value, sizeof(void *)); | |
109 | } else { | |
110 | memcpy(elm->data, value, map->item_size); | |
111 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
112 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
113 | // allocate new element |
490 | 114 | struct cx_hash_map_element_s *e = cxMalloc( |
115 | allocator, | |
116 | sizeof(struct cx_hash_map_element_s) + map->item_size | |
117 | ); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
118 | if (e == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
119 | return -1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
120 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
121 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
122 | // write the value |
490 | 123 | if (map->store_pointer) { |
124 | memcpy(e->data, &value, sizeof(void *)); | |
125 | } else { | |
126 | memcpy(e->data, value, map->item_size); | |
127 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
128 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
129 | // copy the key |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
130 | void *kd = cxMalloc(allocator, key.len); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
131 | if (kd == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
132 | return -1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
133 | } |
490 | 134 | memcpy(kd, key.data, key.len); |
135 | e->key.data = kd; | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
136 | e->key.len = key.len; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
137 | e->key.hash = hash; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
138 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
139 | // insert the element into the linked list |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
140 | if (prev == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
141 | hash_map->buckets[slot] = e; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
142 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
143 | prev->next = e; |
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 | e->next = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
146 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
147 | // increase the size |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
148 | map->size++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
149 | } |
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 | return 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
152 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
153 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
154 | static void cx_hash_map_unlink( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
155 | struct cx_hash_map_s *hash_map, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
156 | size_t slot, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
157 | struct cx_hash_map_element_s *prev, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
158 | struct cx_hash_map_element_s *elm |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
159 | ) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
160 | // unlink |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
161 | if (prev == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
162 | hash_map->buckets[slot] = elm->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
163 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
164 | prev->next = elm->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
165 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
166 | // free element |
490 | 167 | 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
|
168 | cxFree(hash_map->base.allocator, elm); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
169 | // decrease size |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
170 | hash_map->base.size--; |
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 | |
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 | * Helper function to avoid code duplication. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
175 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
176 | * @param map the map |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
177 | * @param key the key to look up |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
178 | * @param remove flag indicating whether the looked up entry shall be removed |
490 | 179 | * @param destroy flag indicating whether the destructor shall be invoked |
180 | * @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
|
181 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
182 | static void *cx_hash_map_get_remove( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
183 | CxMap *map, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
184 | CxHashKey key, |
490 | 185 | bool remove, |
186 | bool destroy | |
415
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 | 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
|
189 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
190 | unsigned hash = key.hash; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
191 | if (hash == 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
192 | cx_hash_murmur(&key); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
193 | hash = key.hash; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
194 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
195 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
196 | size_t slot = hash % hash_map->bucket_count; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
197 | 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
|
198 | struct cx_hash_map_element_s *prev = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
199 | while (elm && elm->key.hash <= hash) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
200 | if (elm->key.hash == hash && elm->key.len == key.len) { |
490 | 201 | if (memcmp(elm->key.data, key.data, key.len) == 0) { |
202 | void *data = NULL; | |
203 | if (destroy) { | |
204 | cx_invoke_destructor(map, elm->data); | |
205 | } else { | |
206 | if (map->store_pointer) { | |
207 | data = *(void **) elm->data; | |
208 | } else { | |
209 | data = elm->data; | |
210 | } | |
211 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
212 | if (remove) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
213 | 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
|
214 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
215 | return data; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
216 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
217 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
218 | prev = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
219 | elm = prev->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
220 | } |
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 | return NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
223 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
224 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
225 | static void *cx_hash_map_get( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
226 | CxMap const *map, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
227 | CxHashKey key |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
228 | ) { |
490 | 229 | // we can safely cast, because we know the map stays untouched |
230 | 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
|
231 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
232 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
233 | static void *cx_hash_map_remove( |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
234 | CxMap *map, |
490 | 235 | CxHashKey key, |
236 | bool destroy | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
237 | ) { |
490 | 238 | 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
|
239 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
240 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
241 | 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
|
242 | struct cx_iterator_s const *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
243 | // struct has to have a compatible signature |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
244 | 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
|
245 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
246 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
247 | 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
|
248 | struct cx_iterator_s const *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
249 | 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
|
250 | return &elm->key; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
251 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
252 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
253 | 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
|
254 | struct cx_iterator_s const *iter = it; |
490 | 255 | 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
|
256 | struct cx_hash_map_element_s *elm = iter->elem_handle; |
490 | 257 | if (map->base.store_pointer) { |
258 | return *(void **) elm->data; | |
259 | } else { | |
260 | return elm->data; | |
261 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
262 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
263 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
264 | 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
|
265 | struct cx_iterator_s const *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
266 | return iter->elem_handle != NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
267 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
268 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
269 | static void cx_hash_map_iter_next(void *it) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
270 | struct cx_iterator_s *iter = it; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
271 | 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
|
272 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
273 | // remove current element, if asked |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
274 | if (iter->base.remove) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
275 | // obtain mutable pointer to the map |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
276 | struct cx_mut_iterator_s *miter = it; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
277 | struct cx_hash_map_s *map = miter->src_handle; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
278 | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
279 | // clear the flag |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
280 | iter->base.remove = false; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
281 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
282 | // determine the next element |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
283 | 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
|
284 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
285 | // search the previous element |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
286 | struct cx_hash_map_element_s *prev = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
287 | if (map->buckets[iter->slot] != elm) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
288 | prev = map->buckets[iter->slot]; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
289 | while (prev->next != elm) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
290 | prev = prev->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
291 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
292 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
293 | |
490 | 294 | // destroy |
295 | cx_invoke_destructor((struct cx_map_s *) map, elm->data); | |
296 | ||
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
297 | // unlink |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
298 | 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
|
299 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
300 | // advance |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
301 | elm = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
302 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
303 | // just advance |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
304 | elm = elm->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
305 | iter->index++; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
306 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
307 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
308 | // search the next bucket, if required |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
309 | 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
|
310 | while (elm == NULL && ++iter->slot < map->bucket_count) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
311 | elm = map->buckets[iter->slot]; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
312 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
313 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
314 | // fill the struct with the next element |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
315 | iter->elem_handle = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
316 | if (elm == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
317 | iter->kv_data.key = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
318 | iter->kv_data.value = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
319 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
320 | iter->kv_data.key = &elm->key; |
490 | 321 | if (map->base.store_pointer) { |
322 | iter->kv_data.value = *(void **) elm->data; | |
323 | } else { | |
324 | iter->kv_data.value = elm->data; | |
325 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
326 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
327 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
328 | |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
329 | 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
|
330 | struct cx_iterator_base_s *iter = it; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
331 | if (iter->mutating) { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
332 | iter->remove = true; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
333 | return true; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
334 | } else { |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
335 | return false; |
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 | } |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
338 | |
504 | 339 | static CxIterator cx_hash_map_iterator( |
340 | CxMap const *map, | |
341 | enum cx_map_iterator_type type | |
342 | ) { | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
343 | CxIterator iter; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
344 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
345 | iter.src_handle = map; |
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
346 | iter.base.valid = cx_hash_map_iter_valid; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
347 | iter.base.next = cx_hash_map_iter_next; |
504 | 348 | |
349 | switch (type) { | |
350 | case CX_MAP_ITERATOR_PAIRS: | |
351 | iter.base.current = cx_hash_map_iter_current_entry; | |
352 | break; | |
353 | case CX_MAP_ITERATOR_KEYS: | |
354 | iter.base.current = cx_hash_map_iter_current_key; | |
355 | break; | |
356 | case CX_MAP_ITERATOR_VALUES: | |
357 | iter.base.current = cx_hash_map_iter_current_value; | |
358 | break; | |
359 | default: | |
360 | assert(false); | |
361 | } | |
362 | ||
438
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
363 | 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
|
364 | iter.base.remove = false; |
22eca559aded
refactore http listener creation
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
415
diff
changeset
|
365 | iter.base.mutating = false; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
366 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
367 | iter.slot = 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
368 | iter.index = 0; |
490 | 369 | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
370 | if (map->size > 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
371 | 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
|
372 | 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
|
373 | while (elm == NULL) { |
c036a8b242a8
implement webdav xattr namespace lists
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
438
diff
changeset
|
374 | elm = hash_map->buckets[++iter.slot]; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
375 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
376 | iter.elem_handle = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
377 | iter.kv_data.key = &elm->key; |
490 | 378 | if (map->store_pointer) { |
379 | iter.kv_data.value = *(void **) elm->data; | |
380 | } else { | |
381 | iter.kv_data.value = elm->data; | |
382 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
383 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
384 | iter.elem_handle = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
385 | iter.kv_data.key = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
386 | iter.kv_data.value = NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
387 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
388 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
389 | return iter; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
390 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
391 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
392 | static cx_map_class cx_hash_map_class = { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
393 | cx_hash_map_destructor, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
394 | cx_hash_map_clear, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
395 | cx_hash_map_put, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
396 | cx_hash_map_get, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
397 | cx_hash_map_remove, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
398 | cx_hash_map_iterator, |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
399 | }; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
400 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
401 | CxMap *cxHashMapCreate( |
490 | 402 | CxAllocator const *allocator, |
403 | size_t itemsize, | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
404 | size_t buckets |
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 | if (buckets == 0) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
407 | // implementation defined default |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
408 | buckets = 16; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
409 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
410 | |
490 | 411 | struct cx_hash_map_s *map = cxCalloc(allocator, 1, |
412 | sizeof(struct cx_hash_map_s)); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
413 | if (map == NULL) return NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
414 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
415 | // initialize hash map members |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
416 | map->bucket_count = buckets; |
490 | 417 | map->buckets = cxCalloc(allocator, buckets, |
418 | sizeof(struct cx_hash_map_element_s *)); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
419 | if (map->buckets == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
420 | cxFree(allocator, map); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
421 | return NULL; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
422 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
423 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
424 | // initialize base members |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
425 | map->base.cl = &cx_hash_map_class; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
426 | map->base.allocator = allocator; |
490 | 427 | |
428 | if (itemsize > 0) { | |
429 | map->base.store_pointer = false; | |
430 | map->base.item_size = itemsize; | |
431 | } else { | |
432 | map->base.store_pointer = true; | |
433 | map->base.item_size = sizeof(void *); | |
434 | } | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
435 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
436 | return (CxMap *) map; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
437 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
438 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
439 | int cxMapRehash(CxMap *map) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
440 | 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
|
441 | 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
|
442 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
443 | size_t new_bucket_count = (map->size * 5) >> 1; |
490 | 444 | struct cx_hash_map_element_s **new_buckets = cxCalloc( |
445 | map->allocator, | |
446 | new_bucket_count, sizeof(struct cx_hash_map_element_s *) | |
447 | ); | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
448 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
449 | if (new_buckets == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
450 | return 1; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
451 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
452 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
453 | // 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
|
454 | cx_for_n(slot, hash_map->bucket_count) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
455 | 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
|
456 | while (elm != NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
457 | 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
|
458 | 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
|
459 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
460 | // find position where to insert |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
461 | 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
|
462 | struct cx_hash_map_element_s *bucket_prev = NULL; |
490 | 463 | while (bucket_next != NULL && |
464 | bucket_next->key.hash < elm->key.hash) { | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
465 | bucket_prev = bucket_next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
466 | bucket_next = bucket_next->next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
467 | } |
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 | // insert |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
470 | if (bucket_prev == NULL) { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
471 | elm->next = new_buckets[new_slot]; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
472 | new_buckets[new_slot] = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
473 | } else { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
474 | bucket_prev->next = elm; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
475 | elm->next = bucket_next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
476 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
477 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
478 | // advance |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
479 | elm = next; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
480 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
481 | } |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
482 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
483 | // assign result to the map |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
484 | hash_map->bucket_count = new_bucket_count; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
485 | cxFree(map->allocator, hash_map->buckets); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
486 | hash_map->buckets = new_buckets; |
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 | return 0; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
489 | } |