ucx/hash_map.c

Thu, 23 May 2024 23:24:37 +0200

author
Olaf Wintermann <olaf.wintermann@gmail.com>
date
Thu, 23 May 2024 23:24:37 +0200
branch
ucx-3.1
changeset 819
833bbb830330
parent 816
839fefbdedc7
permissions
-rw-r--r--

close branch ucx-3.1

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

mercurial