1 // ================================================================ 2 // Array-only (open addressing) string-to-string 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 LHMSS_H 17 #define LHMSS_H 18 19 #include "containers/sllv.h" 20 21 // ---------------------------------------------------------------- 22 typedef struct _lhmsse_t { 23 int ideal_index; 24 char free_flags; 25 char* key; 26 char* value; 27 struct _lhmsse_t *pprev; 28 struct _lhmsse_t *pnext; 29 } lhmsse_t; 30 31 typedef unsigned char lhmsse_state_t; 32 33 typedef struct _lhmss_t { 34 int num_occupied; 35 int num_freed; 36 int array_length; 37 lhmsse_t* entries; 38 lhmsse_state_t* states; 39 lhmsse_t* phead; 40 lhmsse_t* ptail; 41 } lhmss_t; 42 43 // ---------------------------------------------------------------- 44 lhmss_t* lhmss_alloc(); 45 lhmss_t* lhmss_copy(lhmss_t* pmap); 46 void lhmss_free(lhmss_t* pmap); 47 void lhmss_put(lhmss_t* pmap, char* key, char* value, char free_flags); 48 char* lhmss_get(lhmss_t* pmap, char* key); 49 int lhmss_has_key(lhmss_t* pmap, char* key); 50 void lhmss_rename(lhmss_t* pmap, char* old_key, char* new_key); 51 52 void lhmss_dump(lhmss_t* pmap); 53 54 // Unit-test hook 55 int lhmss_check_counts(lhmss_t* pmap); 56 57 #endif // LHMSS_H 58