Commit | Line | Data |
---|---|---|
588a2232 BA |
1 | /** |
2 | * @file Set.c | |
3 | */ | |
4 | ||
5 | #include "cgds/Set.h" | |
6 | ||
7 | void _set_init(Set* set, size_t dataSize, size_t hashSize, | |
8 | UInt (*getHash)(void*, size_t)) | |
9 | { | |
10 | set->hashSize = hashSize; | |
11 | set->dataSize = dataSize; | |
12 | set->head = safe_malloc(hashSize * sizeof(SetCell*)); | |
13 | for (UInt i = 0; i < hashSize; i++) | |
14 | set->head[i] = NULL; | |
15 | set->size = 0; | |
16 | set->getHash = getHash; //may be NULL | |
17 | } | |
18 | ||
19 | Set* _set_new(size_t dataSize, size_t hashSize, UInt (*getHash)(void*, size_t)) | |
20 | { | |
21 | Set* set = (Set*) safe_malloc(sizeof(Set)); | |
22 | _set_init(set, dataSize, hashSize, getHash); | |
23 | return set; | |
24 | } | |
25 | ||
26 | Set* set_copy(Set* set) | |
27 | { | |
28 | Set* setCopy = _set_new(set->dataSize, set->hashSize, set->getHash); | |
29 | setCopy->size = set->size; | |
30 | for (UInt i = 0; i < set->hashSize; i++) | |
31 | { | |
32 | SetCell *cell = set->head[i], | |
33 | *cellCopy = setCopy->head[i], | |
34 | *prev = NULL; | |
35 | while (cell != NULL) | |
36 | { | |
37 | // cellCopy == NULL (from empty list) | |
38 | cellCopy = (SetCell*) safe_malloc(sizeof(SetCell)); | |
39 | cellCopy->item = safe_malloc(set->dataSize); | |
40 | memcpy(cellCopy->item, cell->item, set->dataSize); | |
41 | if (prev == NULL) setCopy->head[i] = cellCopy; | |
42 | else prev->next = cellCopy; | |
43 | prev = cellCopy; | |
44 | cell = cell->next; | |
45 | } | |
46 | if (cellCopy != NULL) cellCopy->next = NULL; | |
47 | } | |
48 | return setCopy; | |
49 | } | |
50 | ||
51 | bool set_empty(Set* set) | |
52 | { | |
53 | return (set->size == 0); | |
54 | } | |
55 | ||
56 | UInt set_size(Set* set) | |
57 | { | |
58 | return set->size; | |
59 | } | |
60 | ||
61 | // Function (string) key --> (integer) hash [internal usage] | |
62 | // Default function. Can be changed (see hashtable_new()) | |
63 | UInt _set_compute_hash(void* key, size_t dataSize, size_t hashSize) | |
64 | { | |
65 | UInt res = 0; | |
66 | // Interpret the bytes in key as a piece of string | |
67 | unsigned char* keyStr = (unsigned char*)key; | |
68 | for (size_t i = 0; i < dataSize; i++) | |
69 | // NOTE: '31' from here https://stackoverflow.com/a/4384446 | |
70 | res = (*(keyStr+i) + 31 * res) % hashSize; | |
71 | return res; | |
72 | } | |
73 | ||
74 | // Get hash index from key [internal usage] | |
75 | UInt _set_get_hindex(Set* set, void* key) | |
76 | { | |
77 | if (set->getHash == NULL) | |
78 | return _set_compute_hash(key, set->dataSize, set->hashSize); | |
79 | return set->getHash(key, set->hashSize); | |
80 | } | |
81 | ||
82 | bool set_has(Set* set, void* item) | |
83 | { | |
84 | UInt hashIdx = _set_get_hindex(set, item); | |
85 | SetCell* cell = set->head[hashIdx]; | |
86 | while (cell != NULL) | |
87 | { | |
88 | if (memcmp(cell->item, item, set->dataSize) == 0) | |
89 | return true; | |
90 | cell = cell->next; | |
91 | } | |
92 | return false; | |
93 | } | |
94 | ||
95 | void _set_add(Set* set, void* item) | |
96 | { | |
97 | UInt hashIdx = _set_get_hindex(set, item); | |
98 | SetCell *cell = set->head[hashIdx], | |
99 | *prev = NULL; | |
100 | while (cell != NULL) | |
101 | { | |
102 | if (memcmp(cell->item, item, set->dataSize) == 0) | |
103 | // Already here: nothing to do | |
104 | return; | |
105 | prev = cell; | |
106 | cell = cell->next; | |
107 | } | |
108 | // New element: insert after prev (which may be NULL) | |
109 | SetCell* newCell = (SetCell*) safe_malloc(sizeof(SetCell)); | |
110 | newCell->item = safe_malloc(set->dataSize); | |
111 | memcpy(newCell->item, item, set->dataSize); | |
112 | newCell->next = NULL; | |
113 | if (prev == NULL) | |
114 | set->head[hashIdx] = newCell; | |
115 | else | |
116 | prev->next = newCell; | |
117 | set->size++; | |
118 | } | |
119 | ||
120 | void _set_delete(Set* set, void* item) | |
121 | { | |
122 | UInt hashIdx = _set_get_hindex(set, item); | |
123 | SetCell *cell = set->head[hashIdx], | |
124 | *prev = NULL; | |
125 | while (cell != NULL) | |
126 | { | |
127 | if (memcmp(cell->item, item, set->dataSize) == 0) | |
128 | { | |
129 | if (prev == NULL) | |
130 | set->head[hashIdx] = cell->next; | |
131 | else | |
132 | prev->next = cell->next; | |
133 | safe_free(cell->item); | |
134 | safe_free(cell); | |
135 | set->size--; | |
136 | break; | |
137 | } | |
138 | prev = cell; | |
139 | cell = cell->next; | |
140 | } | |
141 | } | |
142 | ||
143 | Vector* set_to_vector(Set* set) { | |
144 | Vector* v = _vector_new(set->dataSize); | |
145 | for (UInt i = 0; i < set->hashSize; i++) { | |
146 | SetCell* cell = set->head[i]; | |
147 | while (cell != NULL) { | |
148 | _vector_push(v, cell->item); | |
149 | cell = cell->next; | |
150 | } | |
151 | } | |
152 | return v; | |
153 | } | |
154 | ||
155 | void set_clear(Set* set) | |
156 | { | |
157 | for (UInt i = 0; i < set->hashSize; i++) | |
158 | { | |
159 | SetCell* cell = set->head[i]; | |
160 | while (cell != NULL) | |
161 | { | |
162 | SetCell* next = cell->next; | |
163 | safe_free(cell->item); | |
164 | safe_free(cell); | |
165 | cell = next; | |
166 | } | |
167 | set->head[i] = NULL; | |
168 | } | |
169 | set->size = 0; | |
170 | } | |
171 | ||
172 | void set_destroy(Set* set) | |
173 | { | |
174 | set_clear(set); | |
175 | safe_free(set->head); | |
176 | safe_free(set); | |
177 | } |