1 // ================================================================ 2 // Array-only (open addressing) string-to-int linked hash map with linear 3 // probing for collisions. 4 // 5 // John Kerl 2012-08-13 6 // 7 // Notes: 8 // * null key is not supported. 9 // * null value is supported. 10 // 11 // See also: 12 // * http://en.wikipedia.org/wiki/Hash_table 13 // * http://docs.oracle.com/javase/6/docs/api/java/util/Map.html 14 // ================================================================ 15 16 #ifndef LHMSLL_H 17 #define LHMSLL_H 18 19 // ---------------------------------------------------------------- 20 typedef struct _lhmslle_t { 21 int ideal_index; 22 char* key; 23 long long value; 24 char free_flags; 25 struct _lhmslle_t *pprev; 26 struct _lhmslle_t *pnext; 27 } lhmslle_t; 28 29 typedef unsigned char lhmslle_state_t; 30 31 typedef struct _lhmsll_t { 32 int num_occupied; 33 int num_freed; 34 int array_length; 35 lhmslle_t* entries; 36 lhmslle_state_t* states; 37 lhmslle_t* phead; 38 lhmslle_t* ptail; 39 } lhmsll_t; 40 41 // ---------------------------------------------------------------- 42 lhmsll_t* lhmsll_alloc(); 43 44 lhmsll_t* lhmsll_copy(lhmsll_t* pmap); 45 46 void lhmsll_free(lhmsll_t* pmap); 47 void lhmsll_put(lhmsll_t* pmap, char* key, int value, char free_flags); 48 long long lhmsll_get(lhmsll_t* pmap, char* key); // caller must do lhmsll_has_key to check validity 49 int lhmsll_test_and_get(lhmsll_t* pmap, char* key, long long* pval); // *pval undefined if return is FALSE 50 int lhmsll_test_and_increment(lhmsll_t* pmap, char* key); // increments value only if mapping exists 51 lhmslle_t* lhmsll_get_entry(lhmsll_t* pmap, char* key); 52 int lhmsll_has_key(lhmsll_t* pmap, char* key); 53 54 // Unit-test hook 55 int lhmsll_check_counts(lhmsll_t* pmap); 56 57 #endif // LHMSLL_H 58