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