src/ucx/map.c

Mon, 18 Apr 2022 13:17:50 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Mon, 18 Apr 2022 13:17:50 +0200
branch
webdav
changeset 296
78e92337fa4e
parent 260
4779a6fb4fbe
permissions
-rw-r--r--

implement pg rmdir

91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
1 /*
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
3 *
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
4 * Copyright 2017 Mike Becker, Olaf Wintermann All rights reserved.
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
5 *
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
6 * Redistribution and use in source and binary forms, with or without
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
7 * modification, are permitted provided that the following conditions are met:
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
8 *
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
9 * 1. Redistributions of source code must retain the above copyright
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
10 * notice, this list of conditions and the following disclaimer.
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
11 *
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
12 * 2. Redistributions in binary form must reproduce the above copyright
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
13 * notice, this list of conditions and the following disclaimer in the
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
14 * documentation and/or other materials provided with the distribution.
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
15 *
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
26 * POSSIBILITY OF SUCH DAMAGE.
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
27 */
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
28
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
29 #include "ucx/map.h"
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
30
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
31 #include <stdlib.h>
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
32 #include <string.h>
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
33
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
34 UcxMap *ucx_map_new(size_t size) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
35 return ucx_map_new_a(NULL, size);
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
36 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
37
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
38 UcxMap *ucx_map_new_a(UcxAllocator *allocator, size_t size) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
39 if(size == 0) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
40 size = 16;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
41 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
42
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
43 if(!allocator) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
44 allocator = ucx_default_allocator();
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
45 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
46
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
47 UcxMap *map = (UcxMap*)almalloc(allocator, sizeof(UcxMap));
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
48 if (!map) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
49 return NULL;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
50 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
51
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
52 map->allocator = allocator;
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
53 map->map = (UcxMapElement**)alcalloc(
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
54 allocator, size, sizeof(UcxMapElement*));
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
55 if(map->map == NULL) {
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
56 alfree(allocator, map);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
57 return NULL;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
58 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
59 map->size = size;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
60 map->count = 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
61
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
62 return map;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
63 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
64
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
65 static void ucx_map_free_elmlist_contents(UcxMap *map) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
66 for (size_t n = 0 ; n < map->size ; n++) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
67 UcxMapElement *elem = map->map[n];
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
68 if (elem != NULL) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
69 do {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
70 UcxMapElement *next = elem->next;
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
71 alfree(map->allocator, elem->key.data);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
72 alfree(map->allocator, elem);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
73 elem = next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
74 } while (elem != NULL);
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
75 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
76 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
77 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
78
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
79 void ucx_map_free(UcxMap *map) {
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
80 ucx_map_free_elmlist_contents(map);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
81 alfree(map->allocator, map->map);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
82 alfree(map->allocator, map);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
83 }
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
84
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
85 void ucx_map_free_content(UcxMap *map, ucx_destructor destr) {
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
86 UcxMapIterator iter = ucx_map_iterator(map);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
87 void *val;
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
88 UCX_MAP_FOREACH(key, val, iter) {
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
89 if (destr) {
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
90 destr(val);
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
91 } else {
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
92 alfree(map->allocator, val);
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
93 }
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
94 }
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
95 }
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
96
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
97 void ucx_map_clear(UcxMap *map) {
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
98 if (map->count == 0) {
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
99 return; // nothing to do
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
100 }
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
101 ucx_map_free_elmlist_contents(map);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
102 memset(map->map, 0, map->size*sizeof(UcxMapElement*));
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
103 map->count = 0;
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
104 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
105
260
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
106 int ucx_map_copy(UcxMap const *from, UcxMap *to, copy_func fnc, void *data) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
107 UcxMapIterator i = ucx_map_iterator(from);
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
108 void *value;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
109 UCX_MAP_FOREACH(key, value, i) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
110 if (ucx_map_put(to, key, fnc ? fnc(value, data) : value)) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
111 return 1;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
112 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
113 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
114 return 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
115 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
116
260
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
117 UcxMap *ucx_map_clone(UcxMap const *map, copy_func fnc, void *data) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
118 return ucx_map_clone_a(ucx_default_allocator(), map, fnc, data);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
119 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
120
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
121 UcxMap *ucx_map_clone_a(UcxAllocator *allocator,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
122 UcxMap const *map, copy_func fnc, void *data) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
123 size_t bs = (map->count * 5) >> 1;
260
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
124 UcxMap *newmap = ucx_map_new_a(allocator, bs > map->size ? bs : map->size);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
125 if (!newmap) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
126 return NULL;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
127 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
128 ucx_map_copy(map, newmap, fnc, data);
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
129 return newmap;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
130 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
131
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
132 int ucx_map_rehash(UcxMap *map) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
133 size_t load = (map->size * 3) >> 2;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
134 if (map->count > load) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
135 UcxMap oldmap;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
136 oldmap.map = map->map;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
137 oldmap.size = map->size;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
138 oldmap.count = map->count;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
139 oldmap.allocator = map->allocator;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
140
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
141 map->size = (map->count * 5) >> 1;
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
142 map->map = (UcxMapElement**)alcalloc(
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
143 map->allocator, map->size, sizeof(UcxMapElement*));
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
144 if (!map->map) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
145 *map = oldmap;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
146 return 1;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
147 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
148 map->count = 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
149 ucx_map_copy(&oldmap, map, NULL, NULL);
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
150
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
151 /* free the UcxMapElement list of oldmap */
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
152 ucx_map_free_elmlist_contents(&oldmap);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
153 alfree(map->allocator, oldmap.map);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
154 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
155 return 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
156 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
157
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
158 int ucx_map_put(UcxMap *map, UcxKey key, void *data) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
159 UcxAllocator *allocator = map->allocator;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
160
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
161 if (key.hash == 0) {
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
162 key.hash = ucx_hash((const char*)key.data, key.len);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
163 }
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
164
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
165 struct UcxMapKey mapkey;
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
166 mapkey.hash = key.hash;
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
167
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
168 size_t slot = mapkey.hash%map->size;
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
169 UcxMapElement *elm = map->map[slot];
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
170 UcxMapElement *prev = NULL;
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
171
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
172 while (elm && elm->key.hash < mapkey.hash) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
173 prev = elm;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
174 elm = elm->next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
175 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
176
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
177 if (!elm || elm->key.hash != mapkey.hash) {
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
178 UcxMapElement *e = (UcxMapElement*)almalloc(
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
179 allocator, sizeof(UcxMapElement));
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
180 if (!e) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
181 return -1;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
182 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
183 e->key.data = NULL;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
184 if (prev) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
185 prev->next = e;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
186 } else {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
187 map->map[slot] = e;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
188 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
189 e->next = elm;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
190 elm = e;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
191 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
192
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
193 if (!elm->key.data) {
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
194 void *kd = almalloc(allocator, key.len);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
195 if (!kd) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
196 return -1;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
197 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
198 memcpy(kd, key.data, key.len);
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
199 mapkey.data = kd;
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
200 mapkey.len = key.len;
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
201 elm->key = mapkey;
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
202 map->count++;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
203 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
204 elm->data = data;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
205
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
206 return 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
207 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
208
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
209 static void* ucx_map_get_and_remove(UcxMap *map, UcxKey key, int remove) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
210 if(key.hash == 0) {
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
211 key.hash = ucx_hash((const char*)key.data, key.len);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
212 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
213
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
214 size_t slot = key.hash%map->size;
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
215 UcxMapElement *elm = map->map[slot];
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
216 UcxMapElement *pelm = NULL;
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
217 while (elm && elm->key.hash <= key.hash) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
218 if(elm->key.hash == key.hash) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
219 int n = (key.len > elm->key.len) ? elm->key.len : key.len;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
220 if (memcmp(elm->key.data, key.data, n) == 0) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
221 void *data = elm->data;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
222 if (remove) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
223 if (pelm) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
224 pelm->next = elm->next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
225 } else {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
226 map->map[slot] = elm->next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
227 }
99
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
228 alfree(map->allocator, elm->key.data);
b9a6af0ae41a ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 91
diff changeset
229 alfree(map->allocator, elm);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
230 map->count--;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
231 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
232
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
233 return data;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
234 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
235 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
236 pelm = elm;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
237 elm = pelm->next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
238 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
239
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
240 return NULL;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
241 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
242
260
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
243 void *ucx_map_get(UcxMap const *map, UcxKey key) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
244 return ucx_map_get_and_remove((UcxMap *)map, key, 0);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
245 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
246
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
247 void *ucx_map_remove(UcxMap *map, UcxKey key) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
248 return ucx_map_get_and_remove(map, key, 1);
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
249 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
250
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
251 UcxKey ucx_key(const void *data, size_t len) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
252 UcxKey key;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
253 key.data = data;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
254 key.len = len;
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
255 key.hash = ucx_hash((const char*)data, len);
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
256 return key;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
257 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
258
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
259
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
260 int ucx_hash(const char *data, size_t len) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
261 /* murmur hash 2 */
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
262
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
263 int m = 0x5bd1e995;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
264 int r = 24;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
265
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
266 int h = 25 ^ len;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
267
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
268 int i = 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
269 while (len >= 4) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
270 int k = data[i + 0] & 0xFF;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
271 k |= (data[i + 1] & 0xFF) << 8;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
272 k |= (data[i + 2] & 0xFF) << 16;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
273 k |= (data[i + 3] & 0xFF) << 24;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
274
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
275 k *= m;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
276 k ^= k >> r;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
277 k *= m;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
278
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
279 h *= m;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
280 h ^= k;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
281
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
282 i += 4;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
283 len -= 4;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
284 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
285
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
286 switch (len) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
287 case 3: h ^= (data[i + 2] & 0xFF) << 16;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
288 /* no break */
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
289 case 2: h ^= (data[i + 1] & 0xFF) << 8;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
290 /* no break */
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
291 case 1: h ^= (data[i + 0] & 0xFF); h *= m;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
292 /* no break */
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
293 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
294
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
295 h ^= h >> 13;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
296 h *= m;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
297 h ^= h >> 15;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
298
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
299 return h;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
300 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
301
260
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
302 UcxMapIterator ucx_map_iterator(UcxMap const *map) {
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
303 UcxMapIterator i;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
304 i.map = map;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
305 i.cur = NULL;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
306 i.index = 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
307 return i;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
308 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
309
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
310 int ucx_map_iter_next(UcxMapIterator *i, UcxKey *key, void **elm) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
311 UcxMapElement *e = i->cur;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
312
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
313 if (e) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
314 e = e->next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
315 } else {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
316 e = i->map->map[0];
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
317 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
318
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
319 while (i->index < i->map->size) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
320 if (e) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
321 if (e->data) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
322 i->cur = e;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
323 *elm = e->data;
254
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
324 key->data = e->key.data;
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
325 key->hash = e->key.hash;
4784c14aa639 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 135
diff changeset
326 key->len = e->key.len;
91
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
327 return 1;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
328 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
329
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
330 e = e->next;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
331 } else {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
332 i->index++;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
333
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
334 if (i->index < i->map->size) {
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
335 e = i->map->map[i->index];
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
336 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
337 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
338 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
339
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
340 return 0;
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
341 }
fac51f87def0 ucx update
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff changeset
342
260
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
343 UcxMap* ucx_map_union(const UcxMap *first, const UcxMap *second,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
344 copy_func cpfnc, void* cpdata) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
345 return ucx_map_union_a(ucx_default_allocator(),
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
346 first, second, cpfnc, cpdata);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
347 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
348
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
349 UcxMap* ucx_map_union_a(UcxAllocator *allocator,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
350 const UcxMap *first, const UcxMap *second,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
351 copy_func cpfnc, void* cpdata) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
352 UcxMap* result = ucx_map_clone_a(allocator, first, cpfnc, cpdata);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
353 ucx_map_copy(second, result, cpfnc, cpdata);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
354 return result;
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
355 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
356
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
357 UcxMap* ucx_map_intersection(const UcxMap *first, const UcxMap *second,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
358 copy_func cpfnc, void* cpdata) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
359 return ucx_map_intersection_a(ucx_default_allocator(),
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
360 first, second, cpfnc, cpdata);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
361 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
362
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
363 UcxMap* ucx_map_intersection_a(UcxAllocator *allocator,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
364 const UcxMap *first, const UcxMap *second,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
365 copy_func cpfnc, void* cpdata) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
366 UcxMap *result = ucx_map_new_a(allocator, first->size < second->size ?
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
367 first->size : second->size);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
368
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
369 UcxMapIterator iter = ucx_map_iterator(first);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
370 void* value;
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
371 UCX_MAP_FOREACH(key, value, iter) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
372 if (ucx_map_get(second, key)) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
373 ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
374 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
375 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
376
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
377 return result;
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
378 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
379
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
380 UcxMap* ucx_map_difference(const UcxMap *first, const UcxMap *second,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
381 copy_func cpfnc, void* cpdata) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
382 return ucx_map_difference_a(ucx_default_allocator(),
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
383 first, second, cpfnc, cpdata);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
384 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
385
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
386 UcxMap* ucx_map_difference_a(UcxAllocator *allocator,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
387 const UcxMap *first, const UcxMap *second,
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
388 copy_func cpfnc, void* cpdata) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
389
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
390 UcxMap *result = ucx_map_new_a(allocator, first->size - second->count);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
391
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
392 UcxMapIterator iter = ucx_map_iterator(first);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
393 void* value;
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
394 UCX_MAP_FOREACH(key, value, iter) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
395 if (!ucx_map_get(second, key)) {
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
396 ucx_map_put(result, key, cpfnc ? cpfnc(value, cpdata) : value);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
397 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
398 }
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
399
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
400 ucx_map_rehash(result);
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
401 return result;
4779a6fb4fbe fix freebsd build
Olaf Wintermann <olaf.wintermann@gmail.com>
parents: 254
diff changeset
402 }

mercurial