Remove unused Utils/HashMap.h
Signed-off-by: Henner Zeller <h.zeller@acm.org>
diff --git a/src/Utils/HashMap.h b/src/Utils/HashMap.h
deleted file mode 100644
index cbb2635..0000000
--- a/src/Utils/HashMap.h
+++ /dev/null
@@ -1,361 +0,0 @@
-
-#ifndef HASHMAP_H
-#define HASHMAP_H
-#include <iostream>
-#include <iomanip>
-#include <exception>
-#include <mutex>
-#include <condition_variable>
-
-/*
- * wrapper for items stored in the map
- */
-template <typename K, typename V>
-class HashItem {
- public:
- HashItem(K key, V value) {
- this->key = key;
- this->value = value;
- this->nextItem = nullptr;
- }
-
- /*
- * copy constructor
- */
- HashItem(const HashItem &item) {
- this->key = item.getKey();
- this->value = item.getValue();
- this->nextItem = nullptr;
- }
-
- void setNext(HashItem<K, V> *item) { this->nextItem = item; }
-
- HashItem *getNext() { return nextItem; }
-
- K getKey() { return key; }
-
- V getValue() { return value; }
-
- void setValue(V value) { this->value = value; }
-
- private:
- K key;
- V value;
- HashItem *nextItem;
-};
-
-/*
- * template HashMap for storing items
- * default hash function HF = std::hash<K>
- */
-template <typename K, typename V, typename HF = std::hash<K>>
-class HashMap {
- public:
- /*
- * constructor
- * @mSize specifies the bucket size og the map
- */
- HashMap(std::size_t mSize) {
- // lock initialization for single thread
- std::lock_guard<std::mutex> lock(mtx);
- // if (mSize < 1)
- // throw std::exception("Number of buckets ust be greater than zero.");
-
- mapSize = mSize;
- numOfItems = 0;
- // initialize
- hMap = new HashItem<K, V> *[mapSize]();
- }
-
- /*
- * for simplicity no copy constructor
- * anyway we want test how different threads
- * use same instance of the map
- */
- // HashMap(const HashMap & hmap) = delete;
-
- /*
- * inserts item
- * replaces old value with the new one when item already exists
- * @key key of the item
- * @value value of the item
- */
- void insert(const K &key, const V &value) {
- std::lock_guard<std::mutex> lock(mtx);
- insertHelper(this->hMap, this->mapSize, numOfItems, key, value);
- condVar.notify_all();
- }
-
- /*
- * erases item with key when siúch item exists
- * @key of item to erase
- */
- void erase(const K &key) {
- std::lock_guard<std::mutex> lock(mtx);
- // calculate the bucket where item must be inserted
- std::size_t hVal = hashFunc(key) % mapSize;
- HashItem<K, V> *prev = nullptr;
- HashItem<K, V> *item = hMap[hVal];
-
- while ((item != nullptr) && (item->getKey() != key)) {
- prev = item;
- item = item->getNext();
- }
- // no item found with the given key
- if (item == nullptr) {
- return;
- } else {
- if (prev == nullptr) {
- // item found is the first item in the bucket
- hMap[hVal] = item->getNext();
- } else {
- // item found in one of the entries in the bucket
- prev->setNext(item->getNext());
- }
- delete item;
- numOfItems--;
- }
- condVar.notify_all();
- }
-
- /*
- * get element with the given key by reference
- * @key is the key of item that has to be found
- * @value is the holder where the value of item with key will be copied
- */
- bool getItem(const K &key, V &value) const {
- std::lock_guard<std::mutex> lock(mtx);
- // calculate the bucket where item must be inserted
- std::size_t hVal = hashFunc(key) % mapSize;
- HashItem<K, V> *item = hMap[hVal];
-
- while ((item != nullptr) && (item->getKey() != key)) item = item->getNext();
- // item not found
- if (item == nullptr) {
- return false;
- }
-
- value = item->getValue();
- return true;
- }
-
- /*
- * get element with the given key by reference
- * @key is the key of item that has to be found
- * shows an example of thread waitung for some condition
- * @value is the holder where the value of item with key will be copied
- */
- bool getWithWait(const K &key, V &value) {
- std::unique_lock<std::mutex> ulock(mtxForWait);
- condVar.wait(ulock, [this] { return !this->empty(); });
- // calculate the bucket where item must be inserted
- std::size_t hVal = hashFunc(key) % mapSize;
- HashItem<K, V> *item = hMap[hVal];
-
- while ((item != nullptr) && (item->getKey() != key)) item = item->getNext();
- // item not found
- if (item == nullptr) {
- return false;
- }
-
- value = item->getValue();
- return true;
- }
-
- /*
- * resizes the map
- * creates new map on heap
- * copies the elements into new map
- * @newSize specifies new bucket size
- */
- void resize(std::size_t newSize) {
- std::lock_guard<std::mutex> lock(mtx);
- if (newSize < 1)
- throw std::exception("Number of buckets must be greater than zero.");
-
- resizeHelper(newSize);
- condVar.notify_all();
- }
-
- /*
- * outputs all items of the map
- */
- void outputMap() const {
- std::lock_guard<std::mutex> lock(mtx);
- if (numOfItems == 0) {
- std::cout << "Map is empty." << std::endl << std::endl;
- return;
- }
- std::cout << "Map contains " << numOfItems << " items." << std::endl;
- for (std::size_t i = 0; i < mapSize; i++) {
- HashItem<K, V> *item = hMap[i];
- while (item != nullptr) {
- std::cout << "Bucket: " << std::setw(3) << i
- << ", key: " << std::setw(3) << item->getKey()
- << ", value:" << std::setw(3) << item->getValue()
- << std::endl;
- item = item->getNext();
- }
- }
- std::cout << std::endl;
- }
-
- /*
- * returns true when map has no items
- */
- bool empty() const {
- std::lock_guard<std::mutex> lock(mtx);
- return numOfItems == 0;
- }
-
- void clear() {
- std::lock_guard<std::mutex> lock(mtx);
- deleteMap(hMap, mapSize);
- numOfItems = 0;
- hMap = new HashItem<K, V> *[mapSize]();
- }
-
- void deleteDeep() {
- std::lock_guard<std::mutex> lock(mtx);
- deleteMapDeep(hMap, mapSize);
- numOfItems = 0;
- hMap = new HashItem<K, V> *[mapSize]();
- }
-
- /*
- * returns number of items stored in the map
- */
- std::size_t size() const {
- std::lock_guard<std::mutex> lock(mtx);
- return numOfItems;
- }
-
- /*
- * returns number of buckets
- */
- std::size_t bucket_count() const {
- std::lock_guard<std::mutex> lock(mtx);
- return mapSize;
- }
-
- /*
- * desctructor
- */
- ~HashMap() {
- std::lock_guard<std::mutex> lock(mtx);
- deleteMap(hMap, mapSize);
- }
-
- private:
- std::size_t mapSize;
- std::size_t numOfItems;
- HF hashFunc;
- HashItem<K, V> **hMap;
- mutable std::mutex mtx;
- mutable std::mutex mtxForWait;
- std::condition_variable condVar;
-
- /*
- * help method for inserting key, value item into the map hm
- * mapSize specifies the size of the map, items - the number
- * of stored items, will be incremented when insertion is completed
- * @hm HashMap
- * @mSize specifies number of buckets
- * @items holds the number of items in hm, will be incremented when insertion
- * successful
- * @key - key of item to insert
- * @value - value of item to insert
- */
- void insertHelper(HashItem<K, V> **hm, const std::size_t &mSize,
- std::size_t &items, const K &key, const V &value) {
- std::size_t hVal = hashFunc(key) % mSize;
- HashItem<K, V> *prev = nullptr;
- HashItem<K, V> *item = hm[hVal];
-
- while ((item != nullptr) && (item->getKey() != key)) {
- prev = item;
- item = item->getNext();
- }
-
- // inserting new item
- if (item == nullptr) {
- item = new HashItem<K, V>(key, value);
- items++;
- if (prev == nullptr) {
- // insert new value as first item in the bucket
- hm[hVal] = item;
- } else {
- // append new item on previous in the same bucket
- prev->setNext(item);
- }
- } else {
- // replace existing value
- item->setValue(value);
- }
- }
-
- /*
- * help method to resize the map
- * @newSize specifies new number of buckets
- */
- void resizeHelper(std::size_t newSize) {
- HashItem<K, V> **newMap = new HashItem<K, V> *[newSize]();
- std::size_t items = 0;
- for (std::size_t i = 0; i < mapSize; i++) {
- HashItem<K, V> *item = hMap[i];
- while (item != nullptr) {
- insertHelper(newMap, newSize, items, item->getKey(), item->getValue());
- item = item->getNext();
- }
- }
-
- deleteMap(hMap, mapSize);
- hMap = newMap;
- mapSize = newSize;
- numOfItems = items;
- newMap = nullptr;
- }
-
- /*
- * help function for deleting the map hm
- * @hm HashMap
- * @mSize number of buckets in hm
- */
- void deleteMap(HashItem<K, V> **hm, std::size_t mSize) {
- // delete all nodes
- for (std::size_t i = 0; i < mSize; ++i) {
- HashItem<K, V> *item = hm[i];
- while (item != nullptr) {
- HashItem<K, V> *prev = item;
- item = item->getNext();
- delete prev;
- }
- hm[i] = nullptr;
- }
- // delete the map
- delete[] hm;
- }
-
- /*
- * help function for deleting the map hm
- * @hm HashMap
- * @mSize number of buckets in hm
- */
- void deleteMapDeep(HashItem<K, V> **hm, std::size_t mSize) {
- // delete all nodes
- for (std::size_t i = 0; i < mSize; ++i) {
- HashItem<K, V> *item = hm[i];
- while (item != nullptr) {
- HashItem<K, V> *prev = item;
- item = item->getNext();
- delete prev->getValue();
- delete prev;
- }
- hm[i] = nullptr;
- }
- // delete the map
- delete[] hm;
- }
-};
-
-#endif /* HASHMAP_H */
