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