src/hash_map.c

Tue, 28 Mar 2023 21:00:33 +0200

author
Mike Becker <universe@uap-core.de>
date
Tue, 28 Mar 2023 21:00:33 +0200
changeset 670
4ad8ea3aee49
parent 669
dce9b8450656
child 677
b09aae58bba4
permissions
-rw-r--r--

allow NULL for allocator and comparator

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

mercurial