1 // ================================================================
2 // Array-only (open addressing) string-to-void 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 LHMSV_H
17 #define LHMSV_H
18 
19 #include "containers/sllv.h"
20 #include "lib/free_flags.h"
21 
22 // ----------------------------------------------------------------
23 typedef struct _lhmsve_t {
24 	int   ideal_index;
25 	char* key;
26 	void* pvvalue;
27 	char  free_flags;
28 	struct _lhmsve_t *pprev;
29 	struct _lhmsve_t *pnext;
30 } lhmsve_t;
31 
32 typedef unsigned char lhmsve_state_t;
33 
34 typedef struct _lhmsv_t {
35 	int             num_occupied;
36 	int             num_freed;
37 	int             array_length;
38 	lhmsve_t*       entries;
39 	lhmsve_state_t* states;
40 	lhmsve_t*       phead;
41 	lhmsve_t*       ptail;
42 } lhmsv_t;
43 
44 // ----------------------------------------------------------------
45 lhmsv_t* lhmsv_alloc();
46 void  lhmsv_free(lhmsv_t* pmap);
47 void  lhmsv_clear(lhmsv_t* pmap);
48 
49 void  lhmsv_put(lhmsv_t* pmap, char* key, void* pvvalue, char free_flags);
50 void* lhmsv_get(lhmsv_t* pmap, char* key);
51 int   lhmsv_has_key(lhmsv_t* pmap, char* key);
52 
53 // Unit-test hook
54 int lhmsv_check_counts(lhmsv_t* pmap);
55 
56 #endif // LHMSV_H
57