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