Wed, 31 May 2023 12:49:44 +0200
don't add empty query to rq->reqpb
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
1 | /* |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
2 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
3 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
4 | * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
5 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
6 | * Redistribution and use in source and binary forms, with or without |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
7 | * modification, are permitted provided that the following conditions are met: |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
8 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
9 | * 1. Redistributions of source code must retain the above copyright |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
10 | * notice, this list of conditions and the following disclaimer. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
11 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
12 | * 2. Redistributions in binary form must reproduce the above copyright |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
13 | * notice, this list of conditions and the following disclaimer in the |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
14 | * documentation and/or other materials provided with the distribution. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
15 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
26 | * POSSIBILITY OF SUCH DAMAGE. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
27 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
28 | /** |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
29 | * \file hash_map.h |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
30 | * \brief Hash map implementation. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
31 | * \author Mike Becker |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
32 | * \author Olaf Wintermann |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
33 | * \version 3.0 |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
34 | * \copyright 2-Clause BSD License |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
35 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
36 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
37 | #ifndef UCX_HASH_MAP_H |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
38 | #define UCX_HASH_MAP_H |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
39 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
40 | #include "map.h" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
41 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
42 | #ifdef __cplusplus |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
43 | extern "C" { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
44 | #endif |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
45 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
46 | /** Internal structure for an element of a hash map. */ |
490 | 47 | struct cx_hash_map_element_s; |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
48 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
49 | /** |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
50 | * Internal structure for a hash map. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
51 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
52 | struct cx_hash_map_s { |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
53 | /** |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
54 | * Base structure for maps. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
55 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
56 | struct cx_map_s base; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
57 | /** |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
58 | * The buckets of this map, each containing a linked list of elements. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
59 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
60 | struct cx_hash_map_element_s **buckets; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
61 | /** |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
62 | * The number of buckets. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
63 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
64 | size_t bucket_count; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
65 | }; |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
66 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
67 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
68 | /** |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
69 | * Creates a new hash map with the specified number of buckets. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
70 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
71 | * If \p buckets is zero, an implementation defined default will be used. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
72 | * |
490 | 73 | * If \p item_size is CX_STORE_POINTERS, the created map will be created as if |
74 | * cxMapStorePointers() was called immediately after creation. | |
75 | * | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
76 | * @note Iterators provided by this hash map implementation provide the remove operation. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
77 | * The index value of an iterator is the incremented when the iterator advanced without removal. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
78 | * In other words, when the iterator is finished, \c index==size . |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
79 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
80 | * @param allocator the allocator to use |
490 | 81 | * @param itemsize the size of one element |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
82 | * @param buckets the initial number of buckets in this hash map |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
83 | * @return a pointer to the new hash map |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
84 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
85 | __attribute__((__nonnull__, __warn_unused_result__)) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
86 | CxMap *cxHashMapCreate( |
490 | 87 | CxAllocator const *allocator, |
88 | size_t itemsize, | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
89 | size_t buckets |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
90 | ); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
91 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
92 | /** |
490 | 93 | * Creates a new hash map with a default number of buckets. |
94 | * | |
95 | * If \p item_size is CX_STORE_POINTERS, the created map will be created as if | |
96 | * cxMapStorePointers() was called immediately after creation. | |
97 | * | |
98 | * @note Iterators provided by this hash map implementation provide the remove operation. | |
99 | * The index value of an iterator is the incremented when the iterator advanced without removal. | |
100 | * In other words, when the iterator is finished, \c index==size . | |
101 | * | |
102 | * @param itemsize the size of one element | |
103 | * @return a pointer to the new hash map | |
104 | */ | |
105 | #define cxHashMapCreateSimple(itemsize) \ | |
106 | cxHashMapCreate(cxDefaultAllocator, itemsize, 0) | |
107 | ||
108 | /** | |
415
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
109 | * Increases the number of buckets, if necessary. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
110 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
111 | * The load threshold is \c 0.75*buckets. If the element count exceeds the load |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
112 | * threshold, the map will be rehashed. Otherwise, no action is performed and |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
113 | * this function simply returns 0. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
114 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
115 | * The rehashing process ensures, that the number of buckets is at least |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
116 | * 2.5 times the element count. So there is enough room for additional |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
117 | * elements without the need of another soon rehashing. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
118 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
119 | * You can use this function after filling a map to increase access performance. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
120 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
121 | * @note If the specified map is not a hash map, the behavior is undefined. |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
122 | * |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
123 | * @param map the map to rehash |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
124 | * @return zero on success, non-zero if a memory allocation error occurred |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
125 | */ |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
126 | __attribute__((__nonnull__)) |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
127 | int cxMapRehash(CxMap *map); |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
128 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
129 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
130 | #ifdef __cplusplus |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
131 | } // extern "C" |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
132 | #endif |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
133 | |
d938228c382e
switch from ucx 2 to 3
Olaf Wintermann <olaf.wintermann@gmail.com>
parents:
diff
changeset
|
134 | #endif // UCX_HASH_MAP_H |