CMR  1.3.0
hashtable.h
Go to the documentation of this file.
1 #ifndef CMR_HASHTABLE_INTERNAL_H
2 #define CMR_HASHTABLE_INTERNAL_H
3 
4 #include "env_internal.h"
5 
6 #include <limits.h>
7 
8 #ifdef __cplusplus
9 extern "C" {
10 #endif
11 
16 static inline
17 size_t nextPower2(size_t x)
18 {
19  x |= x >> 1;
20  x |= x >> 2;
21  x |= x >> 4;
22  x |= x >> 8;
23  x |= x >> 16;
24  x |= x >> 32;
25  return x + 1;
26 }
27 
30 typedef size_t CMR_LINEARHASHTABLE_HASH;
31 
33  CMR* cmr,
34  CMR_LINEARHASHTABLE_ARRAY** phashtable,
35  size_t initialSize,
36  size_t initialKeyMemory
37 );
38 
40  CMR* cmr,
41  CMR_LINEARHASHTABLE_ARRAY** phashtable
42 );
43 
45  CMR_LINEARHASHTABLE_ARRAY* hashtable,
46  const void* keyArray,
47  size_t keyLength,
48  CMR_LINEARHASHTABLE_BUCKET* pbucket,
49  CMR_LINEARHASHTABLE_HASH* phash
50 );
51 
52 const void* CMRlinearhashtableArrayKey(
53  CMR_LINEARHASHTABLE_ARRAY* hashtable,
54  CMR_LINEARHASHTABLE_BUCKET bucket,
55  size_t* pKeyLength
56 );
57 
59  CMR_LINEARHASHTABLE_ARRAY* hashtable,
60  CMR_LINEARHASHTABLE_BUCKET bucket
61 );
62 
64  CMR* cmr,
65  CMR_LINEARHASHTABLE_ARRAY* hashtable,
66  const void* keyArray,
67  size_t keyLength,
68  CMR_LINEARHASHTABLE_BUCKET bucket,
69  CMR_LINEARHASHTABLE_HASH hash,
70  const void* value
71 );
72 
74  CMR* cmr,
75  CMR_LINEARHASHTABLE_ARRAY* hashtable,
76  const void* keyArray,
77  size_t keyLength,
78  const void* value
79 );
80 
81 
82 
84 typedef size_t CMR_LISTHASHTABLE_VALUE;
85 typedef size_t CMR_LISTHASHTABLE_HASH;
86 typedef size_t CMR_LISTHASHTABLE_BUCKET;
87 typedef size_t CMR_LISTHASHTABLE_ENTRY;
88 
90  CMR* cmr,
91  CMR_LISTHASHTABLE** phashtable,
92  size_t initialNumBuckets,
93  size_t initialMemNodes
94 );
95 
97  CMR* cmr,
98  CMR_LISTHASHTABLE** phashtable
99 );
100 
101 CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindFirst(
102  CMR_LISTHASHTABLE* hashtable,
103  CMR_LISTHASHTABLE_HASH hash
104 );
105 
106 CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindNext(
107  CMR_LISTHASHTABLE* hashtable,
108  CMR_LISTHASHTABLE_HASH hash,
109  CMR_LISTHASHTABLE_ENTRY entry
110 );
111 
112 CMR_LISTHASHTABLE_VALUE CMRlisthashtableValue(
113  CMR_LISTHASHTABLE* hashtable,
114  CMR_LISTHASHTABLE_ENTRY entry
115 );
116 
117 CMR_LISTHASHTABLE_HASH CMRlisthashtableHash(
118  CMR_LISTHASHTABLE* hashtable,
119  CMR_LISTHASHTABLE_ENTRY entry
120 );
121 
123  CMR_LISTHASHTABLE* hashtable
124 );
125 
131  CMR* cmr,
132  CMR_LISTHASHTABLE* hashtable,
133  CMR_LISTHASHTABLE_HASH hash,
134  CMR_LISTHASHTABLE_VALUE value,
135  CMR_LISTHASHTABLE_ENTRY* pentry
136 );
137 
139  CMR* cmr,
140  CMR_LISTHASHTABLE* hashtable,
141  CMR_LISTHASHTABLE_ENTRY entry
142 );
143 
144 #define RANGE_SIGNED_HASH (LLONG_MAX/2)
145 
150 static inline
151 long long projectSignedHash(long long value)
152 {
153  return ((value + RANGE_SIGNED_HASH - 1) % (2*RANGE_SIGNED_HASH-1)) - (RANGE_SIGNED_HASH-1);
154 }
155 
156 #ifdef __cplusplus
157 }
158 #endif
159 
160 #endif /* CMR_HASHTABLE_INTERNAL_H */
const void * CMRlinearhashtableArrayKey(CMR_LINEARHASHTABLE_ARRAY *hashtable, CMR_LINEARHASHTABLE_BUCKET bucket, size_t *pKeyLength)
Definition: hashtable.c:84
const void * CMRlinearhashtableArrayValue(CMR_LINEARHASHTABLE_ARRAY *hashtable, CMR_LINEARHASHTABLE_BUCKET bucket)
Definition: hashtable.c:94
CMR_ERROR CMRlisthashtableFree(CMR *cmr, CMR_LISTHASHTABLE **phashtable)
Definition: hashtable.c:294
size_t CMR_LINEARHASHTABLE_HASH
Definition: hashtable.h:30
CMR_ERROR CMRlinearhashtableArrayFree(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY **phashtable)
Definition: hashtable.c:68
static long long projectSignedHash(long long value)
Projects value into the range [-RANGE_SIGNED_HASH, +RANGE_SIGNED_HASH] via a modulo computation...
Definition: hashtable.h:151
size_t CMRlisthashtableNumBuckets(CMR_LISTHASHTABLE *hashtable)
Definition: hashtable.c:365
CMR_LISTHASHTABLE_VALUE CMRlisthashtableValue(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:351
CMR_ERROR CMRlinearhashtableArrayInsert(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, const void *value)
Definition: hashtable.c:228
static size_t nextPower2(size_t x)
Returns the smallest power of 2 at least as large as x.
Definition: hashtable.h:17
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:26
size_t CMR_LISTHASHTABLE_VALUE
Definition: hashtable.h:84
Definition: hashtable.c:253
size_t CMR_LISTHASHTABLE_ENTRY
Definition: hashtable.h:87
CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindNext(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:334
Definition: env_internal.h:44
CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindFirst(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash)
Definition: hashtable.c:318
Definition: hashtable.c:21
CMR_ERROR CMRlisthashtableCreate(CMR *cmr, CMR_LISTHASHTABLE **phashtable, size_t initialNumBuckets, size_t initialMemNodes)
Definition: hashtable.c:264
CMR_ERROR CMRlinearhashtableArrayInsertBucketHash(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, CMR_LINEARHASHTABLE_BUCKET bucket, CMR_LINEARHASHTABLE_HASH hash, const void *value)
Definition: hashtable.c:145
size_t CMR_LISTHASHTABLE_HASH
Definition: hashtable.h:85
size_t CMR_LISTHASHTABLE_BUCKET
Definition: hashtable.h:86
CMR_ERROR CMRlisthashtableInsert(CMR *cmr, CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash, CMR_LISTHASHTABLE_VALUE value, CMR_LISTHASHTABLE_ENTRY *pentry)
Inserts value with hash into the hash table, even if an entry with the same hash exists.
Definition: hashtable.c:370
CMR_LISTHASHTABLE_HASH CMRlisthashtableHash(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:358
bool CMRlinearhashtableArrayFind(CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, CMR_LINEARHASHTABLE_BUCKET *pbucket, CMR_LINEARHASHTABLE_HASH *phash)
Definition: hashtable.c:101
CMR_ERROR CMRlisthashtableRemove(CMR *cmr, CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:402
size_t CMR_LINEARHASHTABLE_BUCKET
Definition: hashtable.h:29
CMR_ERROR CMRlinearhashtableArrayCreate(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY **phashtable, size_t initialSize, size_t initialKeyMemory)
Definition: hashtable.c:41
#define RANGE_SIGNED_HASH
Definition: hashtable.h:144