1 /********************************************************************* 2 * Copyright 1993, UCAR/Unidata 3 * See netcdf/COPYRIGHT file for copying and redistribution conditions. 4 * $Header$ 5 *********************************************************************/ 6 #ifndef NCHASHMAP_H 7 #define NCHASHMAP_H 8 9 /* 10 This hashmap is optimized to assume null-terminated strings as the 11 key. 12 13 Data is presumed to be an index into some other table Assume it 14 can be compared using simple == The key is some hash of some 15 null terminated string. 16 17 One problem here is that we need to do a final equality check on 18 the name string to avoid an accidental hash collision. It would 19 be nice if we had a large enough hashkey that was known to have 20 an extremely low probability of collisions so we could compare 21 the hashkeys to determine exact match. A quick internet search 22 indicates that this is rather more tricky than just using 23 e.g. crc64 or such. Needs some thought. 24 */ 25 26 /*! Hashmap-related structs. 27 NOTES: 28 1. 'data' is the an arbitrary uintptr_t integer or void* pointer. 29 2. hashkey is a crc32 hash of key 30 31 WARNINGS: 32 1. It is critical that |uintptr_t| == |void*| 33 */ 34 35 typedef struct NC_hentry { 36 int flags; 37 uintptr_t data; 38 unsigned int hashkey; /* Hash id */ 39 size_t keysize; 40 char* key; /* copy of the key string; kept as unsigned char */ 41 } NC_hentry; 42 43 /* 44 The hashmap object must give us the hash table (table), 45 the |table| size, and the # of defined entries in the table 46 */ 47 typedef struct NC_hashmap { 48 size_t alloc; /* allocated # of entries */ 49 size_t active; /* # of active entries */ 50 NC_hentry* table; 51 } NC_hashmap; 52 53 /* defined in nchashmap.c */ 54 55 /* 56 There are two "kinds" of functions: 57 1. those that take the key+size -- they compute the hashkey internally. 58 2. those that take the hashkey directly 59 */ 60 61 /** Creates a new hashmap near the given size. */ 62 extern NC_hashmap* NC_hashmapnew(size_t startsize); 63 64 /** Inserts a new element into the hashmap; takes key+size */ 65 /* key points to size bytes to convert to hash key */ 66 extern int NC_hashmapadd(NC_hashmap*, uintptr_t data, const char* key, size_t keysize); 67 68 /** Removes the storage for the element of the key; takes key+size. 69 Return 1 if found, 0 otherwise; returns the data in datap if !null 70 */ 71 extern int NC_hashmapremove(NC_hashmap*, const char* key, size_t keysize, uintptr_t* datap); 72 73 /** Returns the data for the key; takes key+size. 74 Return 1 if found, 0 otherwise; returns the data in datap if !null 75 */ 76 extern int NC_hashmapget(NC_hashmap*, const char* key, size_t keysize, uintptr_t* datap); 77 78 /** Change the data for the specified key; takes hashkey. 79 Return 1 if found, 0 otherwise 80 */ 81 extern int NC_hashmapsetdata(NC_hashmap*, const char* key, size_t keylen, uintptr_t newdata); 82 83 /** Returns the number of saved elements. */ 84 extern size_t NC_hashmapcount(NC_hashmap*); 85 86 /** Reclaims the hashmap structure. */ 87 extern int NC_hashmapfree(NC_hashmap*); 88 89 /* Return the hash key for specified key; takes key+size*/ 90 extern unsigned int NC_hashmapkey(const char* key, size_t size); 91 92 #endif /*NCHASHMAP_H*/ 93 94