Having Trouble Debugging Setkey Function in Priority Queue

  c++, debugging, hashtable, heap, priority-queue

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.

Here’s the code I’m using to debug my heap class:

// 
// This program allows the user to manipulate a binary heap.
// The program only inserts string ids with with associated keys
// into the heap. The heap class, however, is capable of storing
// arbitrary pointers along with each heap item.
//

#include <iostream>
#include <string>
#include <cstdlib>

#include "heap.cpp"

using namespace std;

// Read an integer from standard input; if a non-integer is in the
// buffer, the state is fixed and the user is re-prompted;
// either way, the remainder of the buffer is cleared
void getInteger(string message, int &ref)
{
  bool inputGood = false;
  while (!inputGood) {
    inputGood = true;

    cout << message;
    cin >> ref;

    if (!cin) {
      // Non-integer in input buffer, get out of "fail" state
      cin.clear();
      inputGood = false;
    }
    while (cin.get() != 'n'); // clear buffer
  }
}

int main()
{
  int capacity = 0;
  int option;
  string stringTmp;
  int key, id;
  int retVal;

  // Have user choose capacity for binary heap
  getInteger("Choose a capacity for the binary heap: ", capacity);

  // Create the heap
  heap myHeap1(capacity);

  while (1) {
    cout << "nOptions:n";
    cout << "1 - Insert a new item into the binary heapn";
    cout << "2 - Set the key of a specified itemn";
    cout << "3 - Delete a specified itemn";
    cout << "4 - Perform a deleteMinn";
    cout << "5 - Quitn";

    // Have the user choose an option
    getInteger("Choose an option: ", option);
    switch(option) {

    case 1:
      // Get data to insert into heap from the user and insert it

      cout << "Enter an id string (to insert): ";
      getline(cin, stringTmp);

      getInteger("Enter an associated integer key: ", key);

      retVal = myHeap1.insert(stringTmp, key);

      cout << "nCall to 'insert' returned: " << retVal << "n";

      cout << "nFirst Element:" << myHeap1.peak() << "n";

      break;

    case 2:
      // Get id string and new key from user and change the key

      cout << "Enter an id string (to change its key): ";
      getline(cin, stringTmp);

      getInteger("Enter an associated integer key: ", key);

      retVal = myHeap1.setKey(stringTmp, key);
      cout << "nCall to 'setKey' returned: " << retVal << "n";

      break;

    case 3:
      // Get id string from user and delete it from the heap

      cout << "Enter an id string (to delete): ";
      getline(cin, stringTmp);

      retVal = myHeap1.remove(stringTmp, &key);
      cout << "nCall to 'delete' returned: " << retVal << "n";

      if (retVal == 0) {
    cout << "nDeleted item with string id "" << stringTmp
         << "" and key " << key << "n";
      }

      break;

    case 4:
      // Perform the deleteMin operation on the heap

      retVal = myHeap1.deleteMin(&stringTmp, &key);
      cout << "nCall to 'deleteMin' returned: " << retVal << "n";

      if (retVal == 0) {
    cout << "nDeleted item with string id "" << stringTmp
         << "" and key " << key << "n";
      }

      break;

    case 5:
      cout << "nGoodbye!n";
      exit(0);

    default:
      cerr << "Error, that input is not valid!n";
      exit (1);
    }
  }

  cerr << "Error, we should never get here!n";
  exit (1);
}

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);

  //
  // deleteMin - return the data associated with the smallest key
  //             and delete that node from the binary heap
  //
  // If pId is supplied (i.e., it is not nullptr), write to that address
  // the id of the node being deleted. If pKey is supplied, write to
  // that address the key of the node being deleted. If ppData is
  // supplied, write to that address the associated void pointer.
  //
  // Returns:
  //   0 on success
  //   1 if the heap is empty
  //
  int deleteMin(std::string *pId = nullptr, int *pKey = nullptr, void *ppData = nullptr);

  //
  // remove - delete the node with the specified id from the binary heap
  //
  // If pKey is supplied, write to that address the key of the node
  // being deleted. If ppData is supplied, write to that address the
  // associated void pointer.
  //
  // Returns:
  //   0 on success
  //   1 if a node with the given id does not exist
  //
  int remove(const std::string &id, int *pKey = nullptr, void *ppData = nullptr);


//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;
  }

  
    int getPos(node *pn);
  std::string peak();
};

#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);
    //incremenet 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;
}

//deletes the root node of the heap
//by setting its key to INT_MAX
//percolating down and then popping it off the heap

int heap::deleteMin(std::string *pId, int *pKey, void *ppData)
{
    //if the heap is empty, return 1
    if(size == 0)
    {
        return 1;
    }
    std::string id = data[1].id;

    //if they're not nullpointers
    //write to the pointers the information on the root node
    if(pId != nullptr)
    {
        pId = &(data[1].id);
    }
    if(pKey != nullptr)
    {
        pKey = &(data[1].key);
    }
    if(ppData != nullptr)
    {
        ppData = &(data[1].pData);
    }
    //call to setKey
    setKey(data[1].id, INT_MAX);
    //remove that id from the map
    map -> remove(id);
    //pop it off the heap
    data.pop_back();
    return 0;
}

//remove
//basically the same as deleteMin but more general
//since their functionalities are so similar, I could probably
//just do a call on remove in deleteMin instead
int heap::remove(const std::string &id, int *pKey, void *ppData)
{
    if(size == 0)
    {
        return 1;
    }
    if(pKey != nullptr)
    {
        pKey = &(data[1].key);
    }
    if(ppData != nullptr)
    {
        ppData = &(data[1].pData);
    }
    setKey(id, INT_MAX);
    map -> remove(id);
    data.pop_back();
    return 0;
}


//this is for debugging purposes
//i used this to test the insert function
//which seems to work fine
std::string heap::peak()
{
    std::string elements = "";
    for(int i = 0; i < size; i++)
    {
        elements += std::to_string(data[i + 1].key) + ", ";
    }
    return elements;
}

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);

  // Set the pointer associated with the specified key.
  // Returns 0 on success,
  // 1 if the key does not exist in the hash table.
  int setPointer(const std::string &key, void *pv);

  // Delete the item with the specified key.
  // Returns true on success,
  // false if the specified key is not in the hash table.
  bool remove(const std::string &key);
 
 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);

  // Search for an item with the specified key.
  // Return the position if found, -1 otherwise.
  int findPos(const std::string &key);

  // The rehash function; makes the hash table bigger.
  // Returns true on success, false if memory allocation fails.
  bool rehash();

  // 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)
    {
        if (not rehash())
        {
            return 2;
        }
    }
    return 0;
}

//multiplies the size of the table by 2
//resizes it based on getPrime of new size
//uses a try catch block on the portion where
//the table is resized
//returns false if memory allocation error occurs
//true if successful
bool hashTable::rehash()
{
    int m = data.size();

    std::vector<hashItem> temp(data);
    //make temporary vector to contain key values
    //temp.resize(m);
    //temp = data;
    //get new size of hashtable
    int size = getPrime(m*2);
    //clear the contents of the hashtable
    data.clear();
    //try to double the size of the hashtable
    try
    {
        data.resize(size);
    }
    //catch any potential memory allocation error
    catch (std::bad_alloc)
    {
        return false;
    }
    //set capacity to size and filled to 0
    capacity = size;
    filled = 0;
    length = size;
    //insert the key into the resized and empty hashtable
    for(int i= 0; i < m; i++)
    {
        //only add in items that weren't deleted
        if(not temp[i].isDeleted)
        {
            insert(temp[i].key);
            setPointer(key, temp[i].pv);
        }
    }
    //deallocate memory from the temporary vector
    std::vector<hashItem>().swap(temp);
    return true;
}

//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;
}

//sets pointer of hashItem associated with the key
//to input
int hashTable::setPointer(const std::string &key, void *pv)
 {
    if(not contains(key))
    {
        return 1;
    }
    data[hash(key)].pv = pv;
    return 0;
 }

//removes an item from a hashtable
 //via lazy deletion
bool hashTable::remove(const std::string &key)
{
    if(not contains(key))
    {
        return false;
    }
    data[hash(key)].isDeleted = true;
    return true;
}

Source: Windows Questions C++

LEAVE A COMMENT