25 #ifndef DOXYGEN_SHOULD_SKIP_THIS 27 template<
class T>
struct CSetNode
53 CSet(int32_t size=41, int32_t reserved=128,
bool tracable=
true)
58 use_sg_mallocs=tracable;
61 hash_array=SG_CALLOC(CSetNode<T>*, size);
63 hash_array=(CSetNode<T>**) calloc(size,
sizeof(CSetNode<T>*));
65 for (int32_t i=0; i<size; i++)
78 for(int32_t i=0; i<array->get_num_elements(); i++)
80 if (array->get_element(i)!=NULL)
83 SG_FREE(array->get_element(i));
85 free(array->get_element(i));
101 virtual const char*
get_name()
const {
return "Set"; }
107 void add(
const T& element)
109 int32_t index=hash(element);
110 if (chain_search(index, element)==NULL)
112 insert_key(index, element);
123 int32_t index=hash(element);
124 if (chain_search(index, element)!=NULL)
134 void remove(
const T& element)
136 int32_t index=hash(element);
137 CSetNode<T>* result=chain_search(index, element);
141 delete_key(index, result);
153 int32_t index=hash(element);
154 CSetNode<T>* result=chain_search(index, element);
157 return result->index;
177 return array->get_num_elements();
189 if (array->get_element(index)!=NULL)
190 return &(array->get_element(index)->element);
203 return array->get_element(index);
209 return array->get_array();
216 int32_t hash(
const T& element)
218 return CHash::MurmurHash3((uint8_t*)(&element),
sizeof(element), 0xDEADBEEF) % hash_size;
222 bool is_free(CSetNode<T>*
node)
224 if (node->free==
true)
231 CSetNode<T>* chain_search(int32_t index,
const T& element)
233 if (hash_array[index]==NULL)
239 CSetNode<T>* current=hash_array[index];
243 if (current->element==element)
246 current=current->right;
248 }
while (current!=NULL);
255 void insert_key(int32_t index,
const T& element)
260 if ((free_index>=array->get_num_elements()) || (array->get_element(free_index)==NULL))
264 new_node=SG_CALLOC(CSetNode<T>, 1);
266 new_node=(CSetNode<T>*) calloc(1,
sizeof(CSetNode<T>));
268 array->append_element(new_node);
270 new_index=free_index;
275 new_node=array->get_element(free_index);
278 new_index=free_index;
279 free_index=new_node->index;
282 new_node->index=new_index;
283 new_node->free=
false;
284 new_node->element=element;
286 new_node->right=NULL;
289 if (hash_array[index]==NULL)
296 new_node->right=hash_array[index];
303 void delete_key(int32_t index, CSetNode<T>* node)
310 if (node->right!=NULL)
311 node->right->left = node->left;
313 if (node->left!=NULL)
314 node->left->right = node->right;
316 hash_array[index] = node->right;
320 node->index=free_index;
bool contains(const T &element)
int32_t index_of(const T &element)
node< P > new_node(const P &p)
DynArray< CSetNode< T > * > * array
int32_t get_array_size() const
CSetNode< T > ** get_array()
CSet(int32_t size=41, int32_t reserved=128, bool tracable=true)
static uint32_t MurmurHash3(uint8_t *data, int32_t len, uint32_t seed)
Class SGObject is the base class of all shogun objects.
the class CSet, a set based on the hash-table. w: http://en.wikipedia.org/wiki/Hash_table ...
CSetNode< T > ** hash_array
Template Dynamic array class that creates an array that can be used like a list or an array...
CSetNode< T > * get_node_ptr(int32_t index)
T * get_element_ptr(int32_t index)
all of classes and functions are contained in the shogun namespace
int32_t get_num_elements() const
void add(const T &element)
virtual const char * get_name() const