1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#ifndef HT_H
#define HT_H
#include "util.h"
enum { HT_INIT_CAP = 256 };
/* TODO: Modify the probing algorithm. Imitate the algorithm used by
python's hash tables. The source code of the python dict object
can be found in the following URL:
<https://hg.python.org/cpython/file/52f68c95e025/Objects/dictobject.c#l33> */
/* TODO: Generalize the type of the keys, so that we can use anything
as the key. The type of the keys should satisfy the following
conditions.
- Hash-able: We must know how to produce the hash value of a
key.
- Comparable: We must know how to compare two keys, in order to
know if two keys are "equal". */
/* type for a hash function */
typedef NUM (*hash_func_t) (CCR_MOD(void *)key);
/* comparison function type */
typedef BOOL (*compare_func_t)
(CCR_MOD(void *)keya, CCR_MOD(void *)keyb);
struct ht_s {
void **keys;
void **values;
NUM *indices;
UNUM capability;
/* REVIEW: What is the purpose of SIZE? */
/* ANSWER: For looping over keys / values. */
int size;
hash_func_t hf;
compare_func_t cf;
};
typedef struct ht_s ht;
/* On error return NULL */
ht *new_ht(UNUM size, int nargs, ...);
/* This enum empowers the user the ability to control how to free the
hash table. The destroy function always frees keys, values, and
indices pointers.
If the option contains the word "SELF", it means to also free the
hash table pointer itself. Otherwise, it contains NO_SELF, and it
means not to free the hash table pointer.
If it contains the word "KEY" (respectively "VALUE"), then it means
to also free the pointers stored in the keys (respectively values)
array. How to free the pointers? If the option contains the word
"FIRST", then it means to free the first pointer stored in the
array corresponding to the word before "FIRST". And it frees each
and every of the other word's pointers. To free both keys and
values pointers in the same manner, i.e. free both of the first
pointers or free each and every pointers, use the option containing
"EVERY" or "EVERY_FIRST" respectively. */
enum HT_DESTROY_FLAG_e {
DESTROY_NONE_NO_SELF,
DESTROY_NONE_SELF,
DESTROY_KEY_SELF,
DESTROY_KEY_FIRST_SELF,
DESTROY_KEY_NO_SELF,
DESTROY_KEY_FIRST_NO_SELF,
DESTROY_VALUE_SELF,
DESTROY_VALUE_FIRST_SELF,
DESTROY_VALUE_NO_SELF,
DESTROY_VALUE_FIRST_NO_SELF,
DESTROY_EVERY_SELF,
DESTROY_EVERY_FIRST_SELF,
DESTROY_EVERY_NO_SELF,
DESTROY_EVERY_FIRST_NO_SELF,
DESTROY_KEY_FIRST_VALUE_SELF,
DESTROY_KEY_FIRST_VALUE_NO_SELF,
DESTROY_KEY_VALUE_FIRST_SELF,
DESTROY_KEY_VALUE_FIRST_NO_SELF
};
typedef enum HT_DESTROY_FLAG_e HT_DESTROY_FLAG;
void destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag);
BOOL ht_insert(ht * const restrict htp, void *key, void *value);
P_ATTR NUM ht_size(CCR_MOD(ht *) htp);
P_ATTR void **ht_values(CCR_MOD(ht *) htp);
P_ATTR void **ht_keys(CCR_MOD(ht *) htp);
enum HT_DELETE_FLAG_e {
DELETE_NONE,
DELETE_KEY,
DELETE_VALUE,
DELETE_EVERY
};
typedef enum HT_DELETE_FLAG_e HT_DELETE_FLAG;
BOOL ht_delete(ht * const restrict htp, void *key,
HT_DELETE_FLAG flag);
P_ATTR void *ht_find(CCR_MOD(ht *) htp, void *key);
#endif
|
