7 void _set_init(Set
* set
, size_t dataSize
, size_t hashSize
,
8 UInt (*getHash
)(void*, size_t))
10 set
->hashSize
= hashSize
;
11 set
->dataSize
= dataSize
;
12 set
->head
= safe_malloc(hashSize
* sizeof(SetCell
*));
13 for (UInt i
= 0; i
< hashSize
; i
++)
16 set
->getHash
= getHash
; //may be NULL
19 Set
* _set_new(size_t dataSize
, size_t hashSize
, UInt (*getHash
)(void*, size_t))
21 Set
* set
= (Set
*) safe_malloc(sizeof(Set
));
22 _set_init(set
, dataSize
, hashSize
, getHash
);
26 Set
* set_copy(Set
* set
)
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
++)
32 SetCell
*cell
= set
->head
[i
],
33 *cellCopy
= setCopy
->head
[i
],
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
;
46 if (cellCopy
!= NULL
) cellCopy
->next
= NULL
;
51 bool set_empty(Set
* set
)
53 return (set
->size
== 0);
56 UInt
set_size(Set
* set
)
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
)
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
;
74 // Get hash index from key [internal usage]
75 UInt
_set_get_hindex(Set
* set
, void* key
)
77 if (set
->getHash
== NULL
)
78 return _set_compute_hash(key
, set
->dataSize
, set
->hashSize
);
79 return set
->getHash(key
, set
->hashSize
);
82 bool set_has(Set
* set
, void* item
)
84 UInt hashIdx
= _set_get_hindex(set
, item
);
85 SetCell
* cell
= set
->head
[hashIdx
];
88 if (memcmp(cell
->item
, item
, set
->dataSize
) == 0)
95 void _set_add(Set
* set
, void* item
)
97 UInt hashIdx
= _set_get_hindex(set
, item
);
98 SetCell
*cell
= set
->head
[hashIdx
],
102 if (memcmp(cell
->item
, item
, set
->dataSize
) == 0)
103 // Already here: nothing to do
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
;
114 set
->head
[hashIdx
] = newCell
;
116 prev
->next
= newCell
;
120 void _set_delete(Set
* set
, void* item
)
122 UInt hashIdx
= _set_get_hindex(set
, item
);
123 SetCell
*cell
= set
->head
[hashIdx
],
127 if (memcmp(cell
->item
, item
, set
->dataSize
) == 0)
130 set
->head
[hashIdx
] = cell
->next
;
132 prev
->next
= cell
->next
;
133 safe_free(cell
->item
);
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
);
155 void set_clear(Set
* set
)
157 for (UInt i
= 0; i
< set
->hashSize
; i
++)
159 SetCell
* cell
= set
->head
[i
];
162 SetCell
* next
= cell
->next
;
163 safe_free(cell
->item
);
172 void set_destroy(Set
* set
)
175 safe_free(set
->head
);