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, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
17 template<typename _Key, typename _Val, typename _KeyInt = uintptr_t, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
20 SetIterator(Hashlistnode<_Key, _Val> *_curr, Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *_table) :
26 /** Override: new operator */
27 void *operator new(size_t size) {
28 return ourmalloc(size);
31 /** Override: delete operator */
32 void operator delete(void *p, size_t size) {
36 /** Override: new[] operator */
37 void *operator new[](size_t size) {
38 return ourmalloc(size);
41 /** Override: delete[] operator */
42 void operator delete[](void *p, size_t size) {
67 Hashlistnode<_Key,_Val> *curr;
68 Hashlistnode<_Key, _Val> *last;
69 Hashtable <_Key, _Val, _KeyInt, _Shift, hash_function, equals> *table;
72 template<typename _Key, typename _KeyInt = uintptr_t, int _Shift = 0, unsigned int (*hash_function)(_Key) = defaultHashFunction<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = defaultEquals<_Key> >
75 Hashset(unsigned int initialcapacity = 16, double factor = 0.5) :
76 table(new Hashtable<_Key, _Key, _KeyInt, _Shift, hash_function, equals>(initialcapacity, factor))
80 /** @brief Hashset destructor */
85 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy() {
86 Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *copy = new Hashset<_Key, _KeyInt, _Shift, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
87 SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
89 copy->add(it->next());
98 /** @brief Adds a new key to the hashset. Returns false if the key
99 * is already present. */
101 void addAll(Hashset<_Key, _KeyInt, _Shift, hash_function, equals> *table) {
102 SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *it = iterator();
103 while (it->hasNext())
108 /** @brief Adds a new key to the hashset. Returns false if the key
109 * is already present. */
112 if (!table->contains(key)) {
113 table->put(key, key);
119 /** @brief Gets the original key corresponding to this one from the
120 * hashset. Returns NULL if not present. */
123 return table->get(key);
127 return table->list->key;
130 bool contains(_Key key) {
131 return table->contains(key);
134 bool remove(_Key key) {
135 if (!table->contains(key))
141 unsigned int size() const {
142 return table->size();
145 bool isEmpty() const {
149 SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *iterator() {
150 return new SetIterator<_Key, _Key, _KeyInt, _Shift, hash_function, equals>(table->list, table);
153 /** Override: new operator */
154 void *operator new(size_t size) {
155 return ourmalloc(size);
158 /** Override: delete operator */
159 void operator delete(void *p, size_t size) {
163 /** Override: new[] operator */
164 void *operator new[](size_t size) {
165 return ourmalloc(size);
168 /** Override: delete[] operator */
169 void operator delete[](void *p, size_t size) {
173 Hashtable<_Key, _Key, _KeyInt, _Shift, hash_function, equals> *table;
176 template<typename _Key, typename _Val, typename _KeyInt, int _Shift, unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
177 SetIterator<_Key, _Val,_KeyInt, _Shift, hash_function, equals> *getKeyIterator(Hashtable<_Key,_Val,_KeyInt,_Shift,hash_function,equals> *table) {
178 return new SetIterator<_Key, _Val, _KeyInt, _Shift, hash_function, equals>(table->list, table);