1 /* Copyright (c) 2015 Regents of the University of California
3 * Author: Brian Demsky <bdemsky@uci.edu>
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU General Public License
7 * version 2 as published by the Free Software Foundation.
12 #include "hashtable.h"
14 template<typename _Key>
21 template<typename _Key, typename _KeyInt, int _Shift, void *
22 (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function
23 )(_Key), bool (*equals)(_Key, _Key)>
26 template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
29 HSIterator(LinkNode<_Key> *_curr, HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * _set) :
35 /** Override: new operator */
36 void * operator new(size_t size) {
40 /** Override: delete operator */
41 void operator delete(void *p, size_t size) {
45 /** Override: new[] operator */
46 void * operator new[](size_t size) {
50 /** Override: delete[] operator */
51 void operator delete[](void *p, size_t size) {
78 HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * set;
81 template<typename _Key, typename _KeyInt, int _Shift = 0, void * (*_malloc)(size_t) = snapshot_malloc, void * (*_calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
84 HashSet(unsigned int initialcapacity = 16, double factor = 0.5) :
85 table(new HashTable<_Key, LinkNode<_Key> *, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(initialcapacity, factor)),
91 /** @brief Hashset destructor */
93 LinkNode<_Key> *tmp=list;
95 LinkNode<_Key> *tmpnext=tmp->next;
102 HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * copy() {
103 HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> *copy=new HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
104 HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * it=iterator();
106 copy->add(it->next());
112 LinkNode<_Key> *tmp=list;
114 LinkNode<_Key> *tmpnext=tmp->next;
122 /** @brief Adds a new key to the hashset. Returns false if the key
123 * is already present. */
126 LinkNode<_Key> * val=table->get(key);
128 LinkNode<_Key> * newnode=(LinkNode<_Key> *)_malloc(sizeof(struct LinkNode<_Key>));
137 table->put(key, newnode);
143 /** @brief Gets the original key corresponding to this one from the
144 * hashset. Returns NULL if not present. */
147 LinkNode<_Key> * val=table->get(key);
158 bool contains(_Key key) {
159 return table->get(key)!=NULL;
162 bool remove(_Key key) {
163 LinkNode<_Key> * oldlinknode;
164 oldlinknode=table->get(key);
165 if (oldlinknode==NULL) {
170 //remove link node from the list
171 if (oldlinknode->prev==NULL)
172 list=oldlinknode->next;
174 oldlinknode->prev->next=oldlinknode->next;
175 if (oldlinknode->next!=NULL)
176 oldlinknode->next->prev=oldlinknode->prev;
178 tail=oldlinknode->prev;
183 unsigned int getSize() {
184 return table->getSize();
193 HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * iterator() {
194 return new HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(list, this);
197 /** Override: new operator */
198 void * operator new(size_t size) {
199 return _malloc(size);
202 /** Override: delete operator */
203 void operator delete(void *p, size_t size) {
207 /** Override: new[] operator */
208 void * operator new[](size_t size) {
209 return _malloc(size);
212 /** Override: delete[] operator */
213 void operator delete[](void *p, size_t size) {
217 HashTable<_Key, LinkNode<_Key>*, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * table;
218 LinkNode<_Key> *list;
219 LinkNode<_Key> *tail;