irods  4.2.8
About: iRODS (the integrated Rule Oriented Data System) is a distributed data-management system for creating data grids, digital libraries, persistent archives, and real-time data systems.
  Fossies Dox: irods-4.2.8.tar.gz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

hashtable.cpp
Go to the documentation of this file.
1 /* For copyright information please refer to files in the COPYRIGHT directory
2  */
3 #include "irods_hashtable.h"
4 #include <cstdlib>
5 //#include "utils.hpp"
11 static char *cpStringExtForHashTable( const char *str, Region *r ) {
12  char *strCp = ( char * )region_alloc( r, ( strlen( str ) + 1 ) * sizeof( char ) );
13  strcpy( strCp, str );
14  return strCp;
15 }
16 
17 
18 struct bucket *newBucket( const char* key, const void* value ) {
19  struct bucket *b = ( struct bucket * )malloc( sizeof( struct bucket ) );
20  if ( b == NULL ) {
21  return NULL;
22  }
23  b->next = NULL;
24  b->key = strdup( key );
25  b->value = value;
26  return b;
27 }
28 
32 struct bucket *newBucket2( char* key, const void* value, Region *r ) {
33  struct bucket *b = ( struct bucket * )region_alloc( r, sizeof( struct bucket ) );
34  if ( b == NULL ) {
35  return NULL;
36  }
37  b->next = NULL;
38  b->key = key;
39  b->value = value;
40  return b;
41 }
42 
47  Hashtable *h = ( Hashtable * )malloc( sizeof( Hashtable ) );
48  if ( NULL == h ) { // JMC cppcheck - nullptr ref
49  return 0;
50  }
51  memset( h, 0, sizeof( Hashtable ) );
52 
53 // if(h==NULL) {
54 // return NULL;
55 // }
56  h->dynamic = 0;
57  h->bucketRegion = NULL;
58  h->size = size;
59  h->buckets = ( struct bucket ** )malloc( sizeof( struct bucket * ) * size );
60  if ( h->buckets == NULL ) {
61  free( h );
62  return NULL;
63  }
64  memset( h->buckets, 0, sizeof( struct bucket * )*size );
65  h->len = 0;
66  return h;
67 }
73 
74  Hashtable *h = ( Hashtable * )region_alloc( r, sizeof( Hashtable ) );
75  if ( NULL == h ) { // JMC cppcheck - nullptr ref
76  return 0;
77  }
78  memset( h, 0, sizeof( Hashtable ) );
79 
80 // if(h==NULL) {
81 // return NULL;
82 // }
83  h->dynamic = 1;
84  h->bucketRegion = r;
85  h->size = size;
86  h->buckets = ( struct bucket ** )region_alloc( h->bucketRegion, sizeof( struct bucket * ) * size );
87  if ( h->buckets == NULL ) {
88  return NULL;
89  }
90  memset( h->buckets, 0, sizeof( struct bucket * )*size );
91  h->len = 0;
92  return h;
93 }
99 int insertIntoHashTable( Hashtable *h, const char* key, const void *value ) {
100  /*
101  printf("insert %s=%s\n", key, value==NULL?"null":"<value>");
102  */
103  if ( h->dynamic ) {
104  if ( h->len >= h->size ) {
105  Hashtable *h2 = newHashTable2( h->size * 2, h->bucketRegion );
106  int i;
107  for ( i = 0; i < h->size; i++ ) {
108  if ( h->buckets[i] != NULL ) {
109  struct bucket *b = h->buckets[i];
110  do {
111  insertIntoHashTable( h2, b->key, b->value );
112  b = b->next;
113 
114  }
115  while ( b != NULL );
116  }
117  }
118  memcpy( h, h2, sizeof( Hashtable ) );
119  }
121  if ( b == NULL ) {
122  return 0;
123  }
124 
125  unsigned long hs = myhash( key );
126  unsigned long index = hs % h->size;
127  if ( h->buckets[index] == NULL ) {
128  h->buckets[index] = b;
129  }
130  else {
131  struct bucket *b0 = h->buckets[index];
132  while ( b0->next != NULL ) {
133  b0 = b0->next;
134  }
135  b0->next = b;
136  }
137  h->len ++;
138  return 1;
139  }
140  else {
141  struct bucket *b = newBucket( key, value );
142  if ( b == NULL ) {
143  return 0;
144  }
145  unsigned long hs = myhash( key );
146  unsigned long index = hs % h->size;
147  if ( h->buckets[index] == NULL ) {
148  h->buckets[index] = b;
149  }
150  else {
151  struct bucket *b0 = h->buckets[index];
152  while ( b0->next != NULL ) {
153  b0 = b0->next;
154  }
155  b0->next = b;
156  }
157  h->len ++;
158  return 1;
159  }
160 }
164 const void* updateInHashTable( Hashtable *h, const char* key, const void* value ) {
165  unsigned long hs = myhash( key );
166  unsigned long index = hs % h->size;
167  if ( h->buckets[index] != NULL ) {
168  struct bucket *b0 = h->buckets[index];
169  while ( b0 != NULL ) {
170  if ( strcmp( b0->key, key ) == 0 ) {
171  const void* tmp = b0->value;
172  b0->value = value;
173  return tmp;
174  /* do not free the value */
175  }
176  b0 = b0->next;
177  }
178  }
179  return NULL;
180 }
184 const void *deleteFromHashTable( Hashtable *h, const char* key ) {
185  unsigned long hs = myhash( key );
186  unsigned long index = hs % h->size;
187  const void *temp = NULL;
188  if ( h->buckets[index] != NULL ) {
189  struct bucket *b0 = h->buckets[index];
190  if ( strcmp( b0->key, key ) == 0 ) {
191  h->buckets[index] = b0->next;
192  temp = b0->value;
193  if ( !h->dynamic ) {
194  free( b0->key );
195  free( b0 );
196  }
197  h->len --;
198  }
199  else {
200  while ( b0->next != NULL ) {
201  if ( strcmp( b0->next->key, key ) == 0 ) {
202  struct bucket *tempBucket = b0->next;
203  temp = b0->next->value;
204  b0->next = b0->next->next;
205  if ( !h->dynamic ) {
206  free( tempBucket->key );
207  free( tempBucket );
208  }
209  h->len --;
210  break;
211  }
212  b0 = b0->next; // JMC - backport 4799
213  }
214  }
215  }
216 
217  return temp;
218 }
222 const void* lookupFromHashTable( Hashtable *h, const char* key ) {
223  unsigned long hs = myhash( key );
224  unsigned long index = hs % h->size;
225  struct bucket *b0 = h->buckets[index];
226  while ( b0 != NULL ) {
227  if ( strcmp( b0->key, key ) == 0 ) {
228  return b0->value;
229  }
230  b0 = b0->next;
231  }
232  return NULL;
233 }
237 struct bucket* lookupBucketFromHashTable( Hashtable *h, const char* key ) {
238  unsigned long hs = myhash( key );
239  unsigned long index = hs % h->size;
240  struct bucket *b0 = h->buckets[index];
241  while ( b0 != NULL ) {
242  if ( strcmp( b0->key, key ) == 0 ) {
243  return b0;
244  }
245  b0 = b0->next;
246  }
247  return NULL;
248 }
249 struct bucket* nextBucket( struct bucket *b0, const char* key ) {
250  b0 = b0->next;
251  while ( b0 != NULL ) {
252  if ( strcmp( b0->key, key ) == 0 ) {
253  return b0;
254  }
255  b0 = b0->next;
256  }
257  return NULL;
258 }
259 
260 void deleteHashTable( Hashtable *h, void ( *f )( const void * ) ) {
261  if ( !h->dynamic ) {
262  int i;
263  for ( i = 0; i < h->size; i++ ) {
264  struct bucket *b0 = h->buckets[i];
265  if ( b0 != NULL ) {
266  deleteBucket( b0, f );
267  }
268  }
269  free( h->buckets );
270  free( h );
271  }
272 }
273 void deleteBucket( struct bucket *b0, void ( *f )( const void * ) ) {
274  if ( b0->next != NULL ) {
275  deleteBucket( b0->next, f );
276  }
277  /* todo do not delete keys if they are allocated in regions */
278  free( b0->key );
279  if ( f != NULL ) {
280  f( b0->value );
281  }
282  free( b0 );
283 }
284 void nop( const void* ) {
285 }
286 
287 void free_const( const void *a ) {
288  free( const_cast< void * >( a ) );
289 }
290 
291 
292 
293 unsigned long B_hash( unsigned char* string ) { /* Bernstein hash */
294  unsigned long hash = HASH_BASE;
295  while ( *string != '\0' ) {
296  hash = ( ( hash << 5 ) + hash ) + ( int ) * string;
297  string++;
298  }
299  return hash;
300 
301 }
302 unsigned long sdbm_hash( char* str ) { /* sdbm */
303  unsigned long hash = 0;
304  while ( *str != '\0' ) {
305  hash = ( ( int ) * str ) + ( hash << 6 ) + ( hash << 16 ) - hash;
306  str++;
307  }
308 
309  return hash;
310 }
311 
312 /*
313 #include "utils.hpp"
314 #include "index.hpp"
315 
316 void dumpHashtableKeys( Hashtable *t ) {
317  int i;
318  for ( i = 0; i < t->size; i++ ) {
319  struct bucket *b = t->buckets[i];
320  while ( b != NULL ) {
321  writeToTmp( "htdump", b->key );
322  writeToTmp( "htdump", "\n" );
323  b = b->next;
324  }
325  }
326 }
327 */
NULL
#define NULL
Definition: rodsDef.h:70
updateInHashTable
const void * updateInHashTable(Hashtable *h, const char *key, const void *value)
Definition: hashtable.cpp:164
cpStringExtForHashTable
static char * cpStringExtForHashTable(const char *str, Region *r)
Definition: hashtable.cpp:11
deleteHashTable
void deleteHashTable(Hashtable *h, void(*f)(const void *))
Definition: hashtable.cpp:260
hashtable::dynamic
int dynamic
Definition: irods_hashtable.h:20
bucket::key
char * key
Definition: irods_hashtable.h:12
region_alloc
void * region_alloc(Region *r, size_t s)
Definition: region.cpp:138
bucket
Definition: irods_hashtable.h:11
myhash
#define myhash(x)
Definition: irods_hashtable.h:9
HASH_BASE
#define HASH_BASE
Definition: irods_hashtable.h:8
newBucket
struct bucket * newBucket(const char *key, const void *value)
Definition: hashtable.cpp:18
lookupBucketFromHashTable
struct bucket * lookupBucketFromHashTable(Hashtable *h, const char *key)
Definition: hashtable.cpp:237
hashtable::buckets
struct bucket ** buckets
Definition: irods_hashtable.h:17
nop
void nop(const void *)
Definition: hashtable.cpp:284
irods_hashtable.h
deleteBucket
void deleteBucket(struct bucket *b0, void(*f)(const void *))
Definition: hashtable.cpp:273
hashtable::bucketRegion
Region * bucketRegion
Definition: irods_hashtable.h:21
get_irods_version.value
dictionary value
Definition: get_irods_version.py:27
hashtable::len
int len
Definition: irods_hashtable.h:19
bucket::next
struct bucket * next
Definition: irods_hashtable.h:14
region
Definition: region.h:45
int
typedef int((*funcPtr)())
free_const
void free_const(const void *a)
Definition: hashtable.cpp:287
newBucket2
struct bucket * newBucket2(char *key, const void *value, Region *r)
Definition: hashtable.cpp:32
nextBucket
struct bucket * nextBucket(struct bucket *b0, const char *key)
Definition: hashtable.cpp:249
insertIntoHashTable
int insertIntoHashTable(Hashtable *h, const char *key, const void *value)
Definition: hashtable.cpp:99
irods.six.b
def b(s)
Definition: six.py:606
lookupFromHashTable
const void * lookupFromHashTable(Hashtable *h, const char *key)
Definition: hashtable.cpp:222
sdbm_hash
unsigned long sdbm_hash(char *str)
Definition: hashtable.cpp:302
hashtable::size
int size
Definition: irods_hashtable.h:18
bucket::value
const void * value
Definition: irods_hashtable.h:13
newHashTable
Hashtable * newHashTable(int size)
Definition: hashtable.cpp:46
hashtable
Definition: irods_hashtable.h:16
size
long long size
Definition: filesystem.cpp:102
newHashTable2
Hashtable * newHashTable2(int size, Region *r)
Definition: hashtable.cpp:72
deleteFromHashTable
const void * deleteFromHashTable(Hashtable *h, const char *key)
Definition: hashtable.cpp:184
B_hash
unsigned long B_hash(unsigned char *string)
Definition: hashtable.cpp:293