I'm having trouble figuring out what's wrong with my setKey function for my priority queue. I'm using a hash table to get the position of a node in the heap from its id (a string associated with the node) in constant time. The hashtable maps the id to an index in a vector of hashItems which contains a pointer to the node. But when I try getting the index from the pointer, I get a large number which leads to a segmentation fault.
I'm fairly certain that the problem is with my hashTable class like maybe I'm not handling pointers correctly.
Here is the header file for my heap class.
#ifndef _HEAP_H
#define _HEAP_H
#include <vector>
#include <string>
#include "hash.cpp"
class heap
{
public:
//=
// heap - The constructor allocates space for the nodes of the heap
// and the mapping (hash table) based on the specified capacity
//
heap(int capacity);
//
// insert - Inserts a new node into the binary heap
//
// Inserts a node with the specified id string, key,
// and optionally a pointer. They key is used to
// determine the final position of the new node.
//
// Returns:
// 0 on success
// 1 if the heap is already filled to capacity
// 2 if a node with the given id already exists (but the heap
// is not filled to capacity)
//
int insert(const std::string &id, int key, void *pv = nullptr);
//
// setKey - set the key of the specified node to the specified value
//
// I have decided that the class should provide this member function
// instead of two separate increaseKey and decreaseKey functions.
//
// Returns:
// 0 on success
// 1 if a node with the given id does not exist
//
int setKey(const std::string &id, int key);
//node class
//an object containing an id (for the heap), a key that determines its
//position on the heap
//and also its position on the heap
class node
{
public:
node(std::string identi, int pass, void* pvData, int pos);
node() = default;
std::string id;
int key;
void *pData;
int position;
};
private:
int size;
int capacity;
std::vector<node> data;
hashTable* map;
public:
//fixes the heap after a key is changed or
//a node is inserted
void percolateUp(int posCur)
{
//index will be the current position of the node
int index = posCur;
node element = data[index];
//while we haven't reached the top of the heap
//and the key of the node is still smaller than that of its parent
while(index > 1 and element.key < data[index / 2].key)
{
//push the parent down the heap
data[index] = data[index / 2];
index = index / 2;
}
//once the heap has been corrected
//change the position of the node
element.position = index;
//set data[index] to element
data[index] = element;
}
//fixes the heap after a key is changed
void percolateDown(int posCur)
{
//index will be the current position of the node
int index = posCur;
node element = data[index];
//while we haven't reached the bottom of the heap
while(index < size + 1)
{
//if the key of the element is greater than that of its left child
if(element.key > data[index * 2].key)
{
//push the left child up the heap
data[index] = data[index*2];
//take its place on the heap
index = index *2;
}
//if the key of the element is greater than that of its right child
else if(element.key > data[index * 2 + 1].key)
{
//push the right child up the heap
data[index] = data[index*2 + 1];
//take its place on the heap
index = index *2 + 1;
}
//else, we found the right place for the node in the heap
else
{
break;
}
}
//once the heap has been corrected
//change the position of the node
element.position = index;
//set data[index] to element
data[index] = element;
}
};
#endif //_HEAP_H
Here is my implementation of the heap class:
#include "heap.h"
#include <stdio.h>
#include <stdlib.h>
//constructor for heap object
//capacity: measure of how much space in heap is left
//size: measure of how many elements (nodes) in heap
//map is a hashTable that allows for constant time access to pointers to nodes from their ids
//creates a hashTable
heap::heap(int length)
{
data.resize(length + 1);
capacity = length;
size = 0;
map = new hashTable(2*capacity);
}
//constructor for node object
//has an id which is used by the hashTable
//a key which is used to determine its position in the heap
heap::node::node(std::string identi, int pass, void* pvData, int pos)
{
id = identi;
key = pass;
pData = pvData;
position = pos;
}
//inserts into heap and adjusts based on key
int heap::insert(const std::string &id, int key, void *pv)
{
//if the heap is almost full, return 1
if (size == capacity - 1)
{
return 1;
}
//if the id is already in use, return 2
if(map -> contains(id))
{
return 2;
}
//index keeps track of index of element to be inserted
//begin by setting it to the final position in the heap
int index = size + 1;
//make a node based on the information given
node element = node(id, key, pv, index);
//set the last element in the heap to the node made
data[index] = element;
//call to percolateUp, adjusts the heap
percolateUp(index);
//make a pointer to the node
node* ptr = &element;
//insert the id, pointer pair to the map
map -> insert(id, ptr);
//increment size
size += 1;
//decrease capacity
capacity -= 1;
//return 0 on success
return 0;
}
//changes the key of a node specified by id in the heap
//and then adjusts the heap
int heap::setKey(const std::string &id, int key)
{
//if the node with that id is not in the map/heap
//return 1
if (not map -> contains(id))
{
return 1;
}
//use map to get the pointer to the node with that id
node *element = (node*)(map -> getPointer(id));
//prints out id, right now prints out just a new line
std::cout << element -> id << std::endl;
//sets key of the node to the given key
element -> key = key;
//get the current position of element and put it into index
int index = element -> position;
//doesn't give correct position. Gives 1823232313. Something's wrong here.
//do percolate up
percolateUp(index);
//then percolate down
//if percolateUp doesn't do anything, we need to percolateDown
//and if it does do something, the heap is perfectly ordered
//and percolateDown won't do anything
percolateDown(index);
//return 0 on success
return 0;
}
Here is the header file for my hashTable class:
#ifndef _HASH_H
#define _HASH_H
#include <vector>
#include <string>
class hashTable {
public:
// The constructor initializes the hash table.
// Uses getPrime to choose a prime number at least as large as
// the specified size for the initial size of the hash table.
hashTable(int size = 0);
// Insert the specified key into the hash table.
// If an optional pointer is provided,
// associate that pointer with the key.
// Returns 0 on success,
// 1 if key already exists in hash table,
// 2 if rehash fails.
int insert(const std::string &key, void *pv = nullptr);
// Check if the specified key is in the hash table.
// If so, return true; otherwise, return false.
bool contains(const std::string &key);
// Get the pointer associated with the specified key.
// If the key does not exist in the hash table, return nullptr.
// If an optional pointer to a bool is provided,
// set the bool to true if the key is in the hash table,
// and set the bool to false otherwise.
void *getPointer(const std::string &key, bool *b = nullptr);
private:
// Each item in the hash table contains:
// key - a string used as a key.
// isOccupied - if false, this entry is empty,
// and the other fields are meaningless.
// isDeleted - if true, this item has been lazily deleted.
// pv - a pointer related to the key;
// nullptr if no pointer was provided to insert.
class hashItem {
public:
std::string key = "";
bool isOccupied = false;
bool isDeleted = false;
void *pv = nullptr;
hashItem() = default;
};
int capacity; // The current capacity of the hash table.
int filled; // Number of occupied items in the table.
size_t length;
std::vector<hashItem> data; // The actual entries are here.
// The hash function.
int hash(const std::string &key);
// Return a prime number at least as large as size.
// Uses a precomputed sequence of selected prime numbers.
static unsigned int getPrime(int size);
};
#endif //_HASH_H
And finally, here's the implementation for my hashTable class
#include "hash.h"
#include <typeinfo>
#include <stdio.h>
#include <stdlib.h>
//returns a prime number depending on size required for hash table
//supports a size of up to one million
unsigned int hashTable::getPrime(int size)
{
if (size <= 10000) { return 12373;}
if (size <= 20000) {return 25867;}
if (size <= 50000) {return 51479;}
if (size <= 100000) {return 109211;}
if (size <= 200000) {return 202717;}
if (size <= 400000) {return 410299;}
if (size <= 800000) {return 803549;}
if (size <= 1600000) {return 2001101;}
return 3200983;
}
// constructor for hashTable class
//takes initial size input and makes size of table from getPrime
//sets capacity to be initially the size of the hash table
hashTable::hashTable(int size)
{
int num = getPrime(size);
length = num;
data.resize(num);
capacity = length;
filled = 0;
}
//hash function
//uses linear probing in the event of a collision
//which is where the function goes from the index
//where the initial hash sent the string to and
//goes down the table until it either finds a free space
//or it finds the hashitem with that key value
int hashTable::hash(const std::string &key)
{
int hashVal = 0;
for(char ch: key)
{
hashVal = 37*hashVal + ch;
}
int i = 0;
if (data[hashVal % length].isOccupied)
{
while( data[(hashVal + i) % length].isOccupied and
(data[(hashVal + i)% length].key).compare(key) != 0)
{
i += 1;
}
}
return (hashVal + i) % length;
}
//insert function inserts key into position given by hash function
//changes filled and capacity number
//returns 0 on success, 1 when the key has already been inserted
//and 2 if there was a memory allocation error in the rehash function
//if the loading size exceeds 0.5, it rehashes
//this means that at any given time, the hashtable only uses a 1/3 of its actual size
//which is necessary in order to decrease the likelihood of collisions
int hashTable::insert(const std::string &key, void *pv)
{
int index = hash(key);
if ((data[index].key).compare(key) == 0)
{
return 1;
}
data[index] = hashItem();
data[index].isOccupied = true;
data[index].key = key;
data[index].pv = pv;
filled += 1;
capacity -= 1;
if (filled/capacity > 0.5)
{
return 2;
}
return 0;
}
//checks if key is in hash table
bool hashTable::contains(const std::string &key)
{
return (data[hash(key)]).isOccupied and not((data[hash(key)]).isDeleted);
}
//retrieves pointer in hashItem from hashtable
//also writes to a boolean pointer whether or not key is in the table
//returns nullptr if not in the table
void* hashTable::getPointer(const std::string &key, bool *b)
{
bool con = contains(key);
b = &con;
if(not con)
{
return nullptr;
}
return data[hash(key)].pv;
}
