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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
#ifndef HT_H
#define HT_H
#include "util.h"
enum { HT_INIT_CAP = 1 << 8 };
/* The algorithm here imitates 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> */
/* We can use anything as the key, except that 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);
/* FIXME: Hide this struct from the header file. */
/* WARNING: Don't use these fields directly. These fields are exposed
in this header file simply because I want to use pointers to ht and
do arithmetic on those pointers. But these fields might change
anytime in the future, if I think of some new ideas, or something
like that. */
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_FIRST" or "EVERY" 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);
void ht_reset(ht * const restrict htp, HT_DELETE_FLAG flag);
P_ATTR void *ht_find(CCR_MOD(ht *) htp, void *key);
/* Pairing hash tables */
struct pair2_s { NUM x; NUM y; };
typedef struct pair2_s pair2;
/* On error return NULL */
ht *new_ht2(UNUM size);
struct pair3_s { NUM x; NUM y; NUM z; };
typedef struct pair3_s pair3;
/* On error return NULL */
ht *new_ht3(UNUM size);
struct pair4_s { NUM x; NUM y; NUM z; NUM w; };
typedef struct pair4_s pair4;
ht *new_ht4(UNUM size);
#define NEW_P2(P, X, Y, CLEAN) do { \
SAFE_MALLOC(pair2, P, 1, CLEAN); \
P->x = X; \
P->y = Y; \
} while (0)
#define NEW_P3(P, X, Y, Z, CLEAN) do { \
SAFE_MALLOC(pair3, P, 1, CLEAN); \
P->x = X; \
P->y = Y; \
P->z = Z; \
} while (0)
#define NEW_P4(P, X, Y, Z, W, CLEAN) do { \
SAFE_MALLOC(pair4, P, 1, CLEAN); \
P->x = X; \
P->y = Y; \
P->z = Z; \
P->w = W; \
} while (0)
#endif
|
