src/hash_map.c

Sun, 22 Dec 2024 22:10:04 +0100

author
Mike Becker <universe@uap-core.de>
date
Sun, 22 Dec 2024 22:10:04 +0100
changeset 1047
40aad3f0bc9e
parent 1040
1ecf4dbbc60c
permissions
-rw-r--r--

don't trust that size_t always has word width

it should be the case on all platforms supported by UCX, but it's not strictly defined in POSIX that it must be the case

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 "cx/hash_map.h"
d7f0b5a9a985 #189 declare basic map functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
30
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
31 #include <string.h>
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
32 #include <assert.h>
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 994
diff changeset
33 #include <errno.h>
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
34
658
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 {
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
36 /** 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
37 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
38
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
39 /** 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
40 CxHashKey key;
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
41
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
42 /** 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
43 char data[];
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
44 };
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
45
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
46 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
47 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
962
cd418898af5c remove cx_for_n() macro - fixes #467
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
48 for (size_t i = 0; i < hash_map->bucket_count; i++) {
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
49 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
50 if (elem != NULL) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
51 do {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
52 struct cx_hash_map_element_s *next = elem->next;
686
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
53 // invoke the destructor
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
54 cx_invoke_destructor(map, elem->data);
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
55 // free the key data
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
56 cxFree(map->collection.allocator, (void *) elem->key.data);
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
57 // free the node
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
58 cxFree(map->collection.allocator, elem);
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
59 // proceed
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
60 elem = next;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
61 } while (elem != NULL);
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 // do not leave a dangling pointer
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
64 hash_map->buckets[i] = NULL;
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 }
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
67 map->collection.size = 0;
550
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
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
70 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
71 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
72
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
73 // free the buckets
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
74 cx_hash_map_clear(map);
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
75 cxFree(map->collection.allocator, hash_map->buckets);
550
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 // free the map structure
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
78 cxFree(map->collection.allocator, map);
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
79 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
80
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
81 static int cx_hash_map_put(
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
82 CxMap *map,
563
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
83 CxHashKey key,
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
84 void *value
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
85 ) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
86 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
87 const CxAllocator *allocator = map->collection.allocator;
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
88
563
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
89 unsigned hash = key.hash;
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
90 if (hash == 0) {
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
91 cx_hash_murmur(&key);
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
92 hash = key.hash;
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
93 }
550
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 size_t slot = hash % hash_map->bucket_count;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
96 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
97 struct cx_hash_map_element_s *prev = NULL;
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 while (elm != NULL && elm->key.hash < hash) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
100 prev = elm;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
101 elm = elm->next;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
102 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
103
575
b05935945637 fix #200 - key contents not compared in cx_hash_map_put()
Mike Becker <universe@uap-core.de>
parents: 574
diff changeset
104 if (elm != NULL && elm->key.hash == hash && elm->key.len == key.len &&
690
2c2304622981 simplify CxHashKey
Mike Becker <universe@uap-core.de>
parents: 688
diff changeset
105 memcmp(elm->key.data, key.data, key.len) == 0) {
574
d566bd3e6af8 invert if-condition in preparation for the next bugfix
Mike Becker <universe@uap-core.de>
parents: 573
diff changeset
106 // overwrite existing element
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
107 if (map->collection.store_pointer) {
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
108 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
109 } else {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
110 memcpy(elm->data, value, map->collection.elem_size);
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
111 }
574
d566bd3e6af8 invert if-condition in preparation for the next bugfix
Mike Becker <universe@uap-core.de>
parents: 573
diff changeset
112 } else {
575
b05935945637 fix #200 - key contents not compared in cx_hash_map_put()
Mike Becker <universe@uap-core.de>
parents: 574
diff changeset
113 // 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
114 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
115 allocator,
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
116 sizeof(struct cx_hash_map_element_s) + map->collection.elem_size
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
117 );
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
118 if (e == NULL) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
119 return -1;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
120 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
121
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
122 // write the value
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
123 if (map->collection.store_pointer) {
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
124 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
125 } else {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
126 memcpy(e->data, value, map->collection.elem_size);
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
127 }
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
128
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
129 // copy the key
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
130 void *kd = cxMalloc(allocator, key.len);
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
131 if (kd == NULL) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
132 return -1;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
133 }
690
2c2304622981 simplify CxHashKey
Mike Becker <universe@uap-core.de>
parents: 688
diff changeset
134 memcpy(kd, key.data, key.len);
2c2304622981 simplify CxHashKey
Mike Becker <universe@uap-core.de>
parents: 688
diff changeset
135 e->key.data = kd;
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
136 e->key.len = key.len;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
137 e->key.hash = hash;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
138
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
139 // insert the element into the linked list
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
140 if (prev == NULL) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
141 hash_map->buckets[slot] = e;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
142 } else {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
143 prev->next = e;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
144 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
145 e->next = elm;
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 // increase the size
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
148 map->collection.size++;
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
149 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
150
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
151 return 0;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
152 }
549
d7f0b5a9a985 #189 declare basic map functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
153
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
154 static void cx_hash_map_unlink(
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
155 struct cx_hash_map_s *hash_map,
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
156 size_t slot,
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
157 struct cx_hash_map_element_s *prev,
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
158 struct cx_hash_map_element_s *elm
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
159 ) {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
160 // unlink
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
161 if (prev == NULL) {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
162 hash_map->buckets[slot] = elm->next;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
163 } else {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
164 prev->next = elm->next;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
165 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
166 // free element
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
167 cxFree(hash_map->base.collection.allocator, (void *) elm->key.data);
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
168 cxFree(hash_map->base.collection.allocator, elm);
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
169 // decrease size
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
170 hash_map->base.collection.size--;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
171 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
172
549
d7f0b5a9a985 #189 declare basic map functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
173 /**
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
174 * Helper function to avoid code duplication.
549
d7f0b5a9a985 #189 declare basic map functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
175 *
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
176 * If \p remove is true, and \p targetbuf is \c NULL, the element
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
177 * will be destroyed when found.
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
178 *
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
179 * If \p remove is true, and \p targetbuf is set, the element will
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
180 * be copied to that buffer and no destructor function is called.
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
181 *
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
182 * If \p remove is false, \p targetbuf must not be non-null and
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
183 * either the pointer, when the map is storing pointers, is copied
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
184 * to the target buffer, or a pointer to the stored object will
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
185 * be copied to the target buffer.
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
186 *
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
187 * @param map the map
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
188 * @param key the key to look up
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
189 * @param targetbuf see description
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
190 * @param remove flag indicating whether the looked up entry shall be removed
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
191 * @return zero, if the key was found, non-zero otherwise
549
d7f0b5a9a985 #189 declare basic map functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
192 */
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
193 static int cx_hash_map_get_remove(
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
194 CxMap *map,
563
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
195 CxHashKey key,
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
196 void *targetbuf,
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
197 bool remove
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
198 ) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
199 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
200
563
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
201 unsigned hash = key.hash;
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
202 if (hash == 0) {
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
203 cx_hash_murmur(&key);
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
204 hash = key.hash;
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
205 }
550
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 size_t slot = hash % hash_map->bucket_count;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
208 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
209 struct cx_hash_map_element_s *prev = NULL;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
210 while (elm && elm->key.hash <= hash) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
211 if (elm->key.hash == hash && elm->key.len == key.len) {
690
2c2304622981 simplify CxHashKey
Mike Becker <universe@uap-core.de>
parents: 688
diff changeset
212 if (memcmp(elm->key.data, key.data, key.len) == 0) {
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
213 if (remove) {
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
214 if (targetbuf == NULL) {
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
215 cx_invoke_destructor(map, elm->data);
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
216 } else {
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
217 memcpy(targetbuf, elm->data, map->collection.elem_size);
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
218 }
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
219 cx_hash_map_unlink(hash_map, slot, prev, elm);
686
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
220 } else {
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
221 assert(targetbuf != NULL);
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
222 void *data = NULL;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
223 if (map->collection.store_pointer) {
686
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
224 data = *(void **) elm->data;
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
225 } else {
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
226 data = elm->data;
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
227 }
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
228 memcpy(targetbuf, &data, sizeof(void *));
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
229 }
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
230 return 0;
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
231 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
232 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
233 prev = elm;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
234 elm = prev->next;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
235 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
236
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
237 return 1;
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
238 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
239
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
240 static void *cx_hash_map_get(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
241 const CxMap *map,
563
69a83fad8a35 improve hash key handling
Mike Becker <universe@uap-core.de>
parents: 562
diff changeset
242 CxHashKey key
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
243 ) {
688
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
244 // we can safely cast, because we know the map stays untouched
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
245 void *ptr = NULL;
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
246 int found = cx_hash_map_get_remove((CxMap *) map, key, &ptr, false);
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
247 return found == 0 ? ptr : NULL;
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
248 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
249
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
250 static int cx_hash_map_remove(
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
251 CxMap *map,
686
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
252 CxHashKey key,
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
253 void *targetbuf
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
254 ) {
994
3603bdf4a78b remove map detach function - fixes #487
Mike Becker <universe@uap-core.de>
parents: 989
diff changeset
255 return cx_hash_map_get_remove(map, key, targetbuf, true);
549
d7f0b5a9a985 #189 declare basic map functions
Mike Becker <universe@uap-core.de>
parents:
diff changeset
256 }
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
257
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
258 static void *cx_hash_map_iter_current_entry(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
259 const struct cx_iterator_s *iter = it;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
260 // struct has to have a compatible signature
573
3f3a0d19db58 remove unused variable (return immediately)
Mike Becker <universe@uap-core.de>
parents: 563
diff changeset
261 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
262 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
263
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
264 static void *cx_hash_map_iter_current_key(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
265 const struct cx_iterator_s *iter = it;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
266 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
267 return &elm->key;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
268 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
269
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
270 static void *cx_hash_map_iter_current_value(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
271 const struct cx_iterator_s *iter = it;
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
272 const struct cx_hash_map_s *map = iter->src_handle.c;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
273 struct cx_hash_map_element_s *elm = iter->elem_handle;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
274 if (map->base.collection.store_pointer) {
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
275 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
276 } else {
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
277 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
278 }
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
279 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
280
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
281 static bool cx_hash_map_iter_valid(const void *it) {
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
282 const struct cx_iterator_s *iter = it;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
283 return iter->elem_handle != NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
284 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
285
630
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 575
diff changeset
286 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
287 struct cx_iterator_s *iter = it;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
288 struct cx_hash_map_element_s *elm = iter->elem_handle;
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
289 struct cx_hash_map_s *map = iter->src_handle.m;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
290
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
291 // remove current element, if asked
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
292 if (iter->base.remove) {
630
ac5e7f789048 separate iterators and mutating iterators
Mike Becker <universe@uap-core.de>
parents: 575
diff changeset
293
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
294 // clear the flag
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
295 iter->base.remove = false;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
296
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
297 // determine the next element
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
298 struct cx_hash_map_element_s *next = elm->next;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
299
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
300 // search the previous element
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
301 struct cx_hash_map_element_s *prev = NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
302 if (map->buckets[iter->slot] != elm) {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
303 prev = map->buckets[iter->slot];
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
304 while (prev->next != elm) {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
305 prev = prev->next;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
306 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
307 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
308
686
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
309 // destroy
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
310 cx_invoke_destructor((struct cx_map_s *) map, elm->data);
64919f63f059 add destructor functions for maps - fixes #253
Mike Becker <universe@uap-core.de>
parents: 685
diff changeset
311
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
312 // unlink
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
313 cx_hash_map_unlink(map, iter->slot, prev, elm);
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
314
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
315 // advance
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
316 elm = next;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
317 } else {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
318 // just advance
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
319 elm = elm->next;
560
2d6a3e2dc8ff fix wrong slot and index numbers
Mike Becker <universe@uap-core.de>
parents: 557
diff changeset
320 iter->index++;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
321 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
322
560
2d6a3e2dc8ff fix wrong slot and index numbers
Mike Becker <universe@uap-core.de>
parents: 557
diff changeset
323 // search the next bucket, if required
2d6a3e2dc8ff fix wrong slot and index numbers
Mike Becker <universe@uap-core.de>
parents: 557
diff changeset
324 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
325 elm = map->buckets[iter->slot];
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
326 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
327
560
2d6a3e2dc8ff fix wrong slot and index numbers
Mike Becker <universe@uap-core.de>
parents: 557
diff changeset
328 // fill the struct with the next element
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
329 iter->elem_handle = elm;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
330 if (elm == NULL) {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
331 iter->kv_data.key = NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
332 iter->kv_data.value = NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
333 } else {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
334 iter->kv_data.key = &elm->key;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
335 if (map->base.collection.store_pointer) {
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
336 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
337 } else {
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
338 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
339 }
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
340 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
341 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
342
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
343 static CxIterator cx_hash_map_iterator(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
344 const CxMap *map,
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
345 enum cx_map_iterator_type type
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
346 ) {
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
347 CxIterator iter;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
348
853
d4baf4dd55c3 simplify iterator structures
Mike Becker <universe@uap-core.de>
parents: 850
diff changeset
349 iter.src_handle.c = map;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
350 iter.elem_count = map->collection.size;
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
351
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
352 switch (type) {
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
353 case CX_MAP_ITERATOR_PAIRS:
850
b2bc48c2b251 add iterator over raw C arrays - closes #389
Mike Becker <universe@uap-core.de>
parents: 829
diff changeset
354 iter.elem_size = sizeof(CxMapEntry);
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
355 iter.base.current = cx_hash_map_iter_current_entry;
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
356 break;
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
357 case CX_MAP_ITERATOR_KEYS:
850
b2bc48c2b251 add iterator over raw C arrays - closes #389
Mike Becker <universe@uap-core.de>
parents: 829
diff changeset
358 iter.elem_size = sizeof(CxHashKey);
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
359 iter.base.current = cx_hash_map_iter_current_key;
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
360 break;
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
361 case CX_MAP_ITERATOR_VALUES:
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
362 iter.elem_size = map->collection.elem_size;
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
363 iter.base.current = cx_hash_map_iter_current_value;
709
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
364 break;
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
365 default:
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
366 assert(false);
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
367 }
1e8ba59e7911 simplify map class structure
Mike Becker <universe@uap-core.de>
parents: 691
diff changeset
368
854
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
369 iter.base.valid = cx_hash_map_iter_valid;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
370 iter.base.next = cx_hash_map_iter_next;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
371 iter.base.remove = false;
fe0d69d72bcd fix members inherited by macro or include are not documented
Mike Becker <universe@uap-core.de>
parents: 853
diff changeset
372 iter.base.mutating = false;
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
373
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
374 iter.slot = 0;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
375 iter.index = 0;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
376
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
377 if (map->collection.size > 0) {
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
378 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
379 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
380 while (elm == NULL) {
c4041b07165e fix hashmap iterator skipping the second element in some cases
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 658
diff changeset
381 elm = hash_map->buckets[++iter.slot];
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
382 }
554
fd3d843b839d fix kv-pair not initialized
Mike Becker <universe@uap-core.de>
parents: 551
diff changeset
383 iter.elem_handle = elm;
fd3d843b839d fix kv-pair not initialized
Mike Becker <universe@uap-core.de>
parents: 551
diff changeset
384 iter.kv_data.key = &elm->key;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
385 if (map->collection.store_pointer) {
658
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
386 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
387 } else {
56c62780582e make hashmap store objects instead of pointers by default - fixes #239
Mike Becker <universe@uap-core.de>
parents: 630
diff changeset
388 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
389 }
551
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
390 } else {
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
391 iter.elem_handle = NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
392 iter.kv_data.key = NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
393 iter.kv_data.value = NULL;
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
394 }
2946e13c89a4 #189 implement map iterators
Mike Becker <universe@uap-core.de>
parents: 550
diff changeset
395
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
396 return iter;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
397 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
398
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
399 static cx_map_class cx_hash_map_class = {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
400 cx_hash_map_destructor,
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
401 cx_hash_map_clear,
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
402 cx_hash_map_put,
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
403 cx_hash_map_get,
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
404 cx_hash_map_remove,
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
405 cx_hash_map_iterator,
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
406 };
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 CxMap *cxHashMapCreate(
890
54565fd74e74 move all const keywords to the west - fixes #426
Mike Becker <universe@uap-core.de>
parents: 856
diff changeset
409 const 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
410 size_t itemsize,
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
411 size_t buckets
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
412 ) {
989
8aa57a7fecc4 improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents: 962
diff changeset
413 if (allocator == NULL) {
8aa57a7fecc4 improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents: 962
diff changeset
414 allocator = cxDefaultAllocator;
8aa57a7fecc4 improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents: 962
diff changeset
415 }
8aa57a7fecc4 improve consistency for allocator arguments - fixes #485
Mike Becker <universe@uap-core.de>
parents: 962
diff changeset
416
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
417 if (buckets == 0) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
418 // implementation defined default
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
419 buckets = 16;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
420 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
421
688
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
422 struct cx_hash_map_s *map = cxCalloc(allocator, 1,
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
423 sizeof(struct cx_hash_map_s));
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
424 if (map == NULL) return NULL;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
425
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
426 // initialize hash map members
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
427 map->bucket_count = buckets;
688
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
428 map->buckets = cxCalloc(allocator, buckets,
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
429 sizeof(struct cx_hash_map_element_s *));
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
430 if (map->buckets == NULL) {
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
431 cxFree(allocator, map);
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
432 return NULL;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
433 }
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
434
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
435 // initialize base members
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
436 map->base.cl = &cx_hash_map_class;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
437 map->base.collection.allocator = allocator;
668
d7129285ac32 add CX_STORE_POINTERS special item size for maps
Mike Becker <universe@uap-core.de>
parents: 665
diff changeset
438
d7129285ac32 add CX_STORE_POINTERS special item size for maps
Mike Becker <universe@uap-core.de>
parents: 665
diff changeset
439 if (itemsize > 0) {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
440 map->base.collection.store_pointer = false;
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
441 map->base.collection.elem_size = itemsize;
668
d7129285ac32 add CX_STORE_POINTERS special item size for maps
Mike Becker <universe@uap-core.de>
parents: 665
diff changeset
442 } else {
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
443 map->base.collection.store_pointer = true;
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
444 map->base.collection.elem_size = sizeof(void *);
668
d7129285ac32 add CX_STORE_POINTERS special item size for maps
Mike Becker <universe@uap-core.de>
parents: 665
diff changeset
445 }
550
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
446
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
447 return (CxMap *) map;
89b2a83728b1 #189 basic map implementation
Mike Becker <universe@uap-core.de>
parents: 549
diff changeset
448 }
562
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 int cxMapRehash(CxMap *map) {
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
451 struct cx_hash_map_s *hash_map = (struct cx_hash_map_s *) map;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
452 if (map->collection.size > ((hash_map->bucket_count * 3) >> 2)) {
562
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
453
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
454 size_t new_bucket_count = (map->collection.size * 5) >> 1;
1040
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 994
diff changeset
455 if (new_bucket_count < hash_map->bucket_count) {
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 994
diff changeset
456 errno = EOVERFLOW;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 994
diff changeset
457 return 1;
1ecf4dbbc60c add some more overflow treatment and make sure to set errno properly
Mike Becker <universe@uap-core.de>
parents: 994
diff changeset
458 }
688
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
459 struct cx_hash_map_element_s **new_buckets = cxCalloc(
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
460 map->collection.allocator,
688
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
461 new_bucket_count, sizeof(struct cx_hash_map_element_s *)
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
462 );
562
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
463
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
464 if (new_buckets == NULL) {
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
465 return 1;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
466 }
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
467
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
468 // iterate through the elements and assign them to their new slots
962
cd418898af5c remove cx_for_n() macro - fixes #467
Mike Becker <universe@uap-core.de>
parents: 890
diff changeset
469 for (size_t slot = 0; slot < hash_map->bucket_count; slot++) {
562
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
470 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
471 while (elm != NULL) {
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
472 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
473 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
474
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
475 // find position where to insert
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
476 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
477 struct cx_hash_map_element_s *bucket_prev = NULL;
688
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
478 while (bucket_next != NULL &&
c27fa8b67286 serious code formatting problems ;-)
Mike Becker <universe@uap-core.de>
parents: 686
diff changeset
479 bucket_next->key.hash < elm->key.hash) {
562
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
480 bucket_prev = bucket_next;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
481 bucket_next = bucket_next->next;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
482 }
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
483
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
484 // insert
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
485 if (bucket_prev == NULL) {
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
486 elm->next = new_buckets[new_slot];
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
487 new_buckets[new_slot] = elm;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
488 } else {
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
489 bucket_prev->next = elm;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
490 elm->next = bucket_next;
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
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
493 // advance
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
494 elm = next;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
495 }
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
496 }
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
497
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
498 // assign result to the map
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
499 hash_map->bucket_count = new_bucket_count;
856
6bbbf219251d fix name of collection base member (to avoid base.base)
Mike Becker <universe@uap-core.de>
parents: 855
diff changeset
500 cxFree(map->collection.allocator, hash_map->buckets);
562
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
501 hash_map->buckets = new_buckets;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
502 }
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
503 return 0;
fd3368c20413 #189 #199 implement and test map rehash
Mike Becker <universe@uap-core.de>
parents: 560
diff changeset
504 }

mercurial