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
|
#ifndef HT_H
#define HT_H
#include "util.h"
enum { HT_INIT_CAP = 257 };
/* 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) (void *key);
/* comparison function type */
typedef BOOL (*compare_func_t) (void *keya, void *keyb);
struct ht_s {
NUM *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);
enum HT_DESTROY_FLAG_e {
DESTROY_NONE_NO_SELF,
DESTROY_NONE_SELF,
DESTROY_EVERY_NO_SELF,
DESTROY_EVERY_SELF,
DESTROY_FIRST_NO_SELF,
DESTROY_FIRST_SELF
};
typedef enum HT_DESTROY_FLAG_e HT_DESTROY_FLAG;
void destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag);
BOOL ht_insert(ht *htp, NUM key, void *value);
P_ATTR NUM ht_size(CCR_MOD(ht *) htp);
P_ATTR void **ht_values(CCR_MOD(ht *) htp);
P_ATTR NUM *ht_keys(CCR_MOD(ht *) htp);
/* If FLAG is non-zero, also free the value pointer. */
BOOL ht_delete(ht * const restrict htp, NUM key, int flag);
P_ATTR void *ht_find(CCR_MOD(ht *) htp, NUM key);
#endif
|
