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, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
24 template<typename _Key, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
27 SetIterator(Linknode<_Key> *_curr, Hashset <_Key, _KeyInt, _Shift, hash_function, equals> *_set) :
33 SetIterator(SetIterator *s) : curr(s->curr),
38 /** Override: new operator */
39 void *operator new(size_t size) {
40 return ourmalloc(size);
43 /** Override: delete operator */
44 void operator delete(void *p, size_t size) {
48 /** Override: new[] operator */
49 void *operator new[](size_t size) {
50 return ourmalloc(size);
53 /** Override: delete[] operator */
54 void operator delete[](void *p, size_t size) {
81 Hashset <_Key, _KeyInt, _Shift, hash_function, equals> *set;
84 template<typename _Key, typename _KeyInt, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
87 Hashset(unsigned int initialcapacity = 16, double factor = 0.5) :
88 table(new Hashtable<_Key, Linknode<_Key> *, _KeyInt, _Shift, hash_function, equals>(initialcapacity, factor)),
94 /** @brief Hashset destructor */
96 Linknode<_Key> *tmp = list;
98 Linknode<_Key> *tmpnext = tmp->next;
105 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy() {
106 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy = new Hashset<_Key, _KeyInt, _Shift, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
107 SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
108 while (it->hasNext())
109 copy->add(it->next());
115 Linknode<_Key> *tmp = list;
116 while (tmp != NULL) {
117 Linknode<_Key> *tmpnext = tmp->next;
125 void resetAndDelete() {
126 Linknode<_Key> *tmp = list;
127 while (tmp != NULL) {
128 Linknode<_Key> *tmpnext = tmp->next;
133 table->resetAndDeleteKeys();
136 /** @brief Adds a new key to the hashset. Returns false if the key
137 * is already present. */
139 void addAll(Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *table) {
140 SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
141 while (it->hasNext())
146 /** @brief Adds a new key to the hashset. Returns false if the key
147 * is already present. */
150 Linknode<_Key> *val = table->get(key);
152 Linknode<_Key> *newnode = (Linknode<_Key> *)ourmalloc(sizeof(struct Linknode<_Key>));
153 newnode->prev = tail;
154 newnode->next = NULL;
157 tail->next = newnode;
161 table->put(key, newnode);
167 /** @brief Return random key from set. */
169 _Key getRandomElement() {
172 else if (getSize() < 6) {
173 uint count = random() % getSize();
174 Linknode<_Key> *ptr = list;
181 return table->getRandomValue()->key;
184 /** @brief Gets the original key corresponding to this one from the
185 * hashset. Returns NULL if not present. */
188 Linknode<_Key> *val = table->get(key);
199 bool contains(_Key key) {
200 return table->get(key) != NULL;
203 bool remove(_Key key) {
204 Linknode<_Key> *oldlinknode;
205 oldlinknode = table->get(key);
206 if (oldlinknode == NULL) {
211 //remove link node from the list
212 if (oldlinknode->prev == NULL)
213 list = oldlinknode->next;
215 oldlinknode->prev->next = oldlinknode->next;
216 if (oldlinknode->next != NULL)
217 oldlinknode->next->prev = oldlinknode->prev;
219 tail = oldlinknode->prev;
220 ourfree(oldlinknode);
224 unsigned int getSize() const {
225 return table->getSize();
228 bool isEmpty() const {
229 return getSize() == 0;
232 SetIterator<_Key, _KeyInt, _Shift, hash_function, equals> *iterator() {
233 return new SetIterator<_Key, _KeyInt, _Shift, hash_function, equals>(list, this);
236 /** Override: new operator */
237 void *operator new(size_t size) {
238 return ourmalloc(size);
241 /** Override: delete operator */
242 void operator delete(void *p, size_t size) {
246 /** Override: new[] operator */
247 void *operator new[](size_t size) {
248 return ourmalloc(size);
251 /** Override: delete[] operator */
252 void operator delete[](void *p, size_t size) {
256 Hashtable<_Key, Linknode<_Key> *, _KeyInt, _Shift, hash_function, equals> *table;
257 Linknode<_Key> *list;
258 Linknode<_Key> *tail;