src/ucx/hash_map.c

Sun, 13 Nov 2022 10:57:38 +0100

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Sun, 13 Nov 2022 10:57:38 +0100
changeset 432
7c9137f9e7f9
parent 415
d938228c382e
child 438
22eca559aded
permissions
-rw-r--r--

add http_send_response function that is usable for non-blocking IO

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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33 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
34 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
35 cx_for_n(i, hash_map->bucket_count) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36 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
37 if (elem != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
38 do {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 struct cx_hash_map_element_s *next = elem->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 // free the key data
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41 cxFree(map->allocator, elem->key.data.obj);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42 // free the node
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43 cxFree(map->allocator, elem);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 // proceed
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 elem = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46 } while (elem != NULL);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
47
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 // do not leave a dangling pointer
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 hash_map->buckets[i] = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
52 map->size = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
53 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
54
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 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
56 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
57
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
58 // free the buckets
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59 cx_hash_map_clear(map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60 cxFree(map->allocator, hash_map->buckets);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 // free the map structure
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 cxFree(map->allocator, map);
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 static int cx_hash_map_put(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67 CxMap *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 CxHashKey key,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 void *value
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 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 CxAllocator *allocator = map->allocator;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74 unsigned hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 if (hash == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 cx_hash_murmur(&key);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 hash = key.hash;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
80 size_t slot = hash % hash_map->bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
81 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
82 struct cx_hash_map_element_s *prev = NULL;
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 while (elm != NULL && elm->key.hash < hash) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
85 prev = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
86 elm = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
87 }
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 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
90 memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
91 // overwrite existing element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
92 elm->data = value;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
93 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
94 // allocate new element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
95 struct cx_hash_map_element_s *e = cxMalloc(allocator, sizeof(struct cx_hash_map_element_s));
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
96 if (e == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
97 return -1;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
100 // write the value
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
101 // TODO: depending on future map features, we may want to copy here
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
102 e->data = value;
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 // copy the key
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105 void *kd = cxMalloc(allocator, key.len);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
106 if (kd == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 return -1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 memcpy(kd, key.data.obj, key.len);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 e->key.data.obj = kd;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 e->key.len = key.len;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 e->key.hash = hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 // insert the element into the linked list
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 if (prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116 hash_map->buckets[slot] = e;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
117 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
118 prev->next = e;
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 e->next = elm;
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 // increase the size
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 map->size++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
124 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 return 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 }
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 static void cx_hash_map_unlink(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 struct cx_hash_map_s *hash_map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131 size_t slot,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 struct cx_hash_map_element_s *prev,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 struct cx_hash_map_element_s *elm
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 // unlink
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136 if (prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
137 hash_map->buckets[slot] = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 prev->next = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141 // free element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
142 cxFree(hash_map->base.allocator, elm->key.data.obj);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
143 cxFree(hash_map->base.allocator, elm);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
144 // decrease size
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 hash_map->base.size--;
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
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 * Helper function to avoid code duplication.
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 * @param map the map
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
152 * @param key the key to look up
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
153 * @param remove flag indicating whether the looked up entry shall be removed
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 * @return the value corresponding to the key or \c NULL
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155 */
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 static void *cx_hash_map_get_remove(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157 CxMap *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 CxHashKey key,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 bool remove
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 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
162
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 unsigned hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
164 if (hash == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
165 cx_hash_murmur(&key);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
166 hash = key.hash;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
167 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
168
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
169 size_t slot = hash % hash_map->bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
170 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
171 struct cx_hash_map_element_s *prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
172 while (elm && elm->key.hash <= hash) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 if (elm->key.hash == hash && elm->key.len == key.len) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 if (memcmp(elm->key.data.obj, key.data.obj, key.len) == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 void *data = elm->data;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176 if (remove) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
177 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
178 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
179 return data;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
180 }
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 prev = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
183 elm = prev->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
184 }
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 return NULL;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
189 static void *cx_hash_map_get(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
190 CxMap const *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
191 CxHashKey key
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 // we can safely cast, because we know when remove=false, the map stays untouched
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
194 return cx_hash_map_get_remove((CxMap *) map, key, false);
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 static void *cx_hash_map_remove(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
198 CxMap *map,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
199 CxHashKey key
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
200 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
201 return cx_hash_map_get_remove(map, key, true);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
202 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
203
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
204 static void *cx_hash_map_iter_current_entry(CxIterator const *iter) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
205 // struct has to have a compatible signature
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
206 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
207 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
208
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
209 static void *cx_hash_map_iter_current_key(CxIterator const *iter) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210 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
211 return &elm->key;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 static void *cx_hash_map_iter_current_value(CxIterator const *iter) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
215 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
216 // TODO: return a pointer to data if this map is storing copies
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
217 return elm->data;
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 static bool cx_hash_map_iter_valid(CxIterator const *iter) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
221 return iter->elem_handle != NULL;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
224 static void cx_hash_map_iter_next(CxIterator *iter) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
225 struct cx_hash_map_s *map = iter->src_handle;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 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
227
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
228 // remove current element, if asked
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
229 if (iter->remove) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
230 // clear the flag
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 iter->remove = false;
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 // determine the next element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
234 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
235
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
236 // search the previous element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 struct cx_hash_map_element_s *prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238 if (map->buckets[iter->slot] != elm) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
239 prev = map->buckets[iter->slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
240 while (prev->next != elm) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 prev = prev->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242 }
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
245 // unlink
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
246 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
247
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
248 // advance
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
249 elm = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
250 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
251 // just advance
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
252 elm = elm->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
253 iter->index++;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
254 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
255
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
256 // search the next bucket, if required
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
257 while (elm == NULL && ++iter->slot < map->bucket_count) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
258 elm = map->buckets[iter->slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
259 }
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 // fill the struct with the next element
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
262 iter->elem_handle = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
263 if (elm == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
264 iter->kv_data.key = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
265 iter->kv_data.value = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
266 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
267 iter->kv_data.key = &elm->key;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
268 // TODO: pointer to data if this map is storing copies
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
269 iter->kv_data.value = elm->data;
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 }
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 static CxIterator cx_hash_map_iterator(CxMap *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
274 CxIterator iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
275
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
276 iter.src_handle = map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
277 iter.valid = cx_hash_map_iter_valid;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
278 iter.next = cx_hash_map_iter_next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
279 iter.current = cx_hash_map_iter_current_entry;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
280
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
281 iter.slot = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
282 iter.index = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
283 iter.remove = false;
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 if (map->size > 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
286 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
287 struct cx_hash_map_element_s *elm = hash_map->buckets[0];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
288 for (; elm == NULL; iter.slot++) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
289 elm = hash_map->buckets[iter.slot];
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 iter.elem_handle = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
292 iter.kv_data.key = &elm->key;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
293 // TODO: pointer to data if this map is storing copies
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
294 iter.kv_data.value = elm->data;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
295 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
296 iter.elem_handle = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
297 iter.kv_data.key = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
298 iter.kv_data.value = NULL;
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
301 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
302 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
303
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
304 static CxIterator cx_hash_map_iterator_keys(CxMap *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
305 CxIterator iter = cx_hash_map_iterator(map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
306 iter.current = cx_hash_map_iter_current_key;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
307 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
308 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
309
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
310 static CxIterator cx_hash_map_iterator_values(CxMap *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
311 CxIterator iter = cx_hash_map_iterator(map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
312 iter.current = cx_hash_map_iter_current_value;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
313 return iter;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
314 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
315
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
316 static cx_map_class cx_hash_map_class = {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
317 cx_hash_map_destructor,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
318 cx_hash_map_clear,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
319 cx_hash_map_put,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
320 cx_hash_map_get,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
321 cx_hash_map_remove,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
322 cx_hash_map_iterator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
323 cx_hash_map_iterator_keys,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
324 cx_hash_map_iterator_values,
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
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
327 CxMap *cxHashMapCreate(
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
328 CxAllocator *allocator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
329 size_t buckets
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
330 ) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
331 if (buckets == 0) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
332 // implementation defined default
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
333 buckets = 16;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
334 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
335
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
336 struct cx_hash_map_s *map = cxMalloc(allocator, sizeof(struct cx_hash_map_s));
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
337 if (map == NULL) return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
338
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
339 // initialize hash map members
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
340 map->bucket_count = buckets;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
341 map->buckets = cxCalloc(allocator, buckets, sizeof(struct cx_hash_map_element_s *));
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
342 if (map->buckets == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
343 cxFree(allocator, map);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
344 return NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
345 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
346
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
347 // initialize base members
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
348 map->base.cl = &cx_hash_map_class;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
349 map->base.allocator = allocator;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
350 map->base.size = 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
351
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
352 return (CxMap *) map;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
353 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
354
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
355 int cxMapRehash(CxMap *map) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
356 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
357 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
358
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
359 size_t new_bucket_count = (map->size * 5) >> 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
360 struct cx_hash_map_element_s **new_buckets = cxCalloc(map->allocator,
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
361 new_bucket_count, sizeof(struct cx_hash_map_element_s *));
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
362
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
363 if (new_buckets == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
364 return 1;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
365 }
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 // 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
368 cx_for_n(slot, hash_map->bucket_count) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
369 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
370 while (elm != NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
371 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
372 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
373
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
374 // find position where to insert
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
375 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
376 struct cx_hash_map_element_s *bucket_prev = NULL;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
377 while (bucket_next != NULL && bucket_next->key.hash < elm->key.hash) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
378 bucket_prev = bucket_next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
379 bucket_next = bucket_next->next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
380 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
381
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
382 // insert
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
383 if (bucket_prev == NULL) {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
384 elm->next = new_buckets[new_slot];
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
385 new_buckets[new_slot] = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
386 } else {
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
387 bucket_prev->next = elm;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
388 elm->next = bucket_next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
389 }
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 // advance
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
392 elm = next;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
393 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
394 }
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
395
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
396 // assign result to the map
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
397 hash_map->bucket_count = new_bucket_count;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
398 cxFree(map->allocator, hash_map->buckets);
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
399 hash_map->buckets = new_buckets;
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 return 0;
d938228c382e switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
402 }

mercurial