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) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
27 HSIterator(LinkNode<_Key> *_curr, HashSet <_Key, _KeyInt, _Shift, hash_function, equals> * _set) :
33 /** Override: new operator */
34 void * operator new(size_t size) {
35 return ourmalloc(size);
38 /** Override: delete operator */
39 void operator delete(void *p, size_t size) {
43 /** Override: new[] operator */
44 void * operator new[](size_t size) {
45 return ourmalloc(size);
48 /** Override: delete[] operator */
49 void operator delete[](void *p, size_t size) {
76 HashSet <_Key, _KeyInt, _Shift, hash_function, equals> * set;
79 template<typename _Key, typename _KeyInt, int _Shift = 0, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
82 HashSet(unsigned int initialcapacity = 16, double factor = 0.5) :
83 table(new HashTable<_Key, LinkNode<_Key> *, _KeyInt, _Shift, hash_function, equals>(initialcapacity, factor)),
89 /** @brief Hashset destructor */
91 LinkNode<_Key> *tmp=list;
93 LinkNode<_Key> *tmpnext=tmp->next;
100 HashSet<_Key, _KeyInt, _Shift, hash_function, equals> * copy() {
101 HashSet<_Key, _KeyInt, _Shift, hash_function, equals> *copy=new HashSet<_Key, _KeyInt, _Shift, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
102 HSIterator<_Key, _KeyInt, _Shift, hash_function, equals> * it=iterator();
104 copy->add(it->next());
110 LinkNode<_Key> *tmp=list;
112 LinkNode<_Key> *tmpnext=tmp->next;
120 /** @brief Adds a new key to the hashset. Returns false if the key
121 * is already present. */
123 void addAll(HashSet<_Key, _KeyInt, _Shift, hash_function, equals> * table) {
124 HSIterator<_Key, _KeyInt, _Shift, hash_function, equals> * it=iterator();
130 /** @brief Adds a new key to the hashset. Returns false if the key
131 * is already present. */
134 LinkNode<_Key> * val=table->get(key);
136 LinkNode<_Key> * newnode=(LinkNode<_Key> *)ourmalloc(sizeof(struct LinkNode<_Key>));
145 table->put(key, newnode);
151 /** @brief Gets the original key corresponding to this one from the
152 * hashset. Returns NULL if not present. */
155 LinkNode<_Key> * val=table->get(key);
166 bool contains(_Key key) {
167 return table->get(key)!=NULL;
170 bool remove(_Key key) {
171 LinkNode<_Key> * oldlinknode;
172 oldlinknode=table->get(key);
173 if (oldlinknode==NULL) {
178 //remove link node from the list
179 if (oldlinknode->prev==NULL)
180 list=oldlinknode->next;
182 oldlinknode->prev->next=oldlinknode->next;
183 if (oldlinknode->next!=NULL)
184 oldlinknode->next->prev=oldlinknode->prev;
186 tail=oldlinknode->prev;
187 ourfree(oldlinknode);
191 unsigned int getSize() {
192 return table->getSize();
199 HSIterator<_Key, _KeyInt, _Shift, hash_function, equals> * iterator() {
200 return new HSIterator<_Key, _KeyInt, _Shift, hash_function, equals>(list, this);
203 /** Override: new operator */
204 void * operator new(size_t size) {
205 return ourmalloc(size);
208 /** Override: delete operator */
209 void operator delete(void *p, size_t size) {
213 /** Override: new[] operator */
214 void * operator new[](size_t size) {
215 return ourmalloc(size);
218 /** Override: delete[] operator */
219 void operator delete[](void *p, size_t size) {
223 HashTable<_Key, LinkNode<_Key>*, _KeyInt, _Shift, hash_function, equals> * table;
224 LinkNode<_Key> *list;
225 LinkNode<_Key> *tail;