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;
20  for(size_t i = 1; i < sizeof(size_t) * CHAR_BIT; i *= 2)
21  x |= x >> i;
22  return x + 1;
23 }
24 
27 typedef size_t CMR_LINEARHASHTABLE_HASH;
28 
30  CMR* cmr,
31  CMR_LINEARHASHTABLE_ARRAY** phashtable,
32  size_t initialSize,
33  size_t initialKeyMemory
34 );
35 
37  CMR* cmr,
38  CMR_LINEARHASHTABLE_ARRAY** phashtable
39 );
40 
42  CMR_LINEARHASHTABLE_ARRAY* hashtable,
43  const void* keyArray,
44  size_t keyLength,
47 );
48 
49 const void* CMRlinearhashtableArrayKey(
50  CMR_LINEARHASHTABLE_ARRAY* hashtable,
52  size_t* pKeyLength
53 );
54 
56  CMR_LINEARHASHTABLE_ARRAY* hashtable,
58 );
59 
61  CMR* cmr,
62  CMR_LINEARHASHTABLE_ARRAY* hashtable,
63  const void* keyArray,
64  size_t keyLength,
67  const void* value
68 );
69 
71  CMR* cmr,
72  CMR_LINEARHASHTABLE_ARRAY* hashtable,
73  const void* keyArray,
74  size_t keyLength,
75  const void* value
76 );
77 
78 
79 
81 typedef size_t CMR_LISTHASHTABLE_VALUE;
82 typedef size_t CMR_LISTHASHTABLE_HASH;
83 typedef size_t CMR_LISTHASHTABLE_BUCKET;
84 typedef size_t CMR_LISTHASHTABLE_ENTRY;
85 
87  CMR* cmr,
88  CMR_LISTHASHTABLE** phashtable,
89  size_t initialNumBuckets,
90  size_t initialMemNodes
91 );
92 
94  CMR* cmr,
95  CMR_LISTHASHTABLE** phashtable
96 );
97 
99  CMR_LISTHASHTABLE* hashtable,
101 );
102 
104  CMR_LISTHASHTABLE* hashtable,
107 );
108 
110  CMR_LISTHASHTABLE* hashtable,
112 );
113 
115  CMR_LISTHASHTABLE* hashtable,
117 );
118 
120  CMR_LISTHASHTABLE* hashtable
121 );
122 
128  CMR* cmr,
129  CMR_LISTHASHTABLE* hashtable,
132  CMR_LISTHASHTABLE_ENTRY* pentry
133 );
134 
136  CMR* cmr,
137  CMR_LISTHASHTABLE* hashtable,
139 );
140 
141 #define RANGE_SIGNED_HASH (LLONG_MAX/2)
142 
147 static inline
148 long long projectSignedHash(long long value)
149 {
150  return ((value + RANGE_SIGNED_HASH - 1) % (2*RANGE_SIGNED_HASH-1)) - (RANGE_SIGNED_HASH-1);
151 }
152 
153 #ifdef __cplusplus
154 }
155 #endif
156 
157 #endif /* CMR_HASHTABLE_INTERNAL_H */
CMR_ERROR
Type for return codes of library functions.
Definition: env.h:32
size_t CMRlisthashtableNumBuckets(CMR_LISTHASHTABLE *hashtable)
Definition: hashtable.c:366
CMR_ERROR CMRlisthashtableCreate(CMR *cmr, CMR_LISTHASHTABLE **phashtable, size_t initialNumBuckets, size_t initialMemNodes)
Definition: hashtable.c:265
size_t CMR_LISTHASHTABLE_VALUE
Definition: hashtable.h:81
size_t CMR_LISTHASHTABLE_ENTRY
Definition: hashtable.h:84
size_t CMR_LINEARHASHTABLE_HASH
Definition: hashtable.h:27
CMR_ERROR CMRlinearhashtableArrayInsert(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, const void *value)
Definition: hashtable.c:229
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:146
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:371
CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindNext(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:335
CMR_LISTHASHTABLE_HASH CMRlisthashtableHash(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:359
static size_t nextPower2(size_t x)
Returns the smallest power of 2 at least as large as x.
Definition: hashtable.h:17
size_t CMR_LISTHASHTABLE_BUCKET
Definition: hashtable.h:83
CMR_LISTHASHTABLE_VALUE CMRlisthashtableValue(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:352
size_t CMR_LINEARHASHTABLE_BUCKET
Definition: hashtable.h:26
CMR_ERROR CMRlinearhashtableArrayCreate(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY **phashtable, size_t initialSize, size_t initialKeyMemory)
Definition: hashtable.c:42
const void * CMRlinearhashtableArrayValue(CMR_LINEARHASHTABLE_ARRAY *hashtable, CMR_LINEARHASHTABLE_BUCKET bucket)
Definition: hashtable.c:95
CMR_ERROR CMRlisthashtableFree(CMR *cmr, CMR_LISTHASHTABLE **phashtable)
Definition: hashtable.c:295
CMR_ERROR CMRlinearhashtableArrayFree(CMR *cmr, CMR_LINEARHASHTABLE_ARRAY **phashtable)
Definition: hashtable.c:69
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:148
#define RANGE_SIGNED_HASH
Definition: hashtable.h:141
CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindFirst(CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash)
Definition: hashtable.c:319
size_t CMR_LISTHASHTABLE_HASH
Definition: hashtable.h:82
CMR_ERROR CMRlisthashtableRemove(CMR *cmr, CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
Definition: hashtable.c:403
const void * CMRlinearhashtableArrayKey(CMR_LINEARHASHTABLE_ARRAY *hashtable, CMR_LINEARHASHTABLE_BUCKET bucket, size_t *pKeyLength)
Definition: hashtable.c:85
bool CMRlinearhashtableArrayFind(CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, CMR_LINEARHASHTABLE_BUCKET *pbucket, CMR_LINEARHASHTABLE_HASH *phash)
Definition: hashtable.c:102
Definition: env_internal.h:45
Definition: hashtable.c:23
Definition: hashtable.c:255