src/cx/hash_map.h

Tue, 04 Oct 2022 19:25:07 +0200

author
Mike Becker <universe@uap-core.de>
date
Tue, 04 Oct 2022 19:25:07 +0200
changeset 591
7df0bcaecffa
parent 563
69a83fad8a35
child 658
56c62780582e
permissions
-rw-r--r--

fix over-optimization of strstr

1. it's actually less performant to frequently read bytes
from an array instead of using the native word length
2. the SBO buffer should be local and not static to allow
multi-threading usage

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

mercurial