29ba947e48244f55e73bf21e9089b5eba59dfb05
[cgds.git] / src / Set.c
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)
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
53 bool set_empty(Set* set)
54 {
55 return (set->size == 0);
56 }
57
58 UInt 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())
65 UInt _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]
77 UInt _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
84 bool 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
97 void _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
122 void _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
145 Vector* 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
157 void 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
174 void set_destroy(Set* set)
175 {
176 set_clear(set);
177 safe_free(set->head);
178 safe_free(set);
179 }