htable.c

Go to the documentation of this file.

/*
 * Copyright 2004, Regents of the University of Minnesota
 *
 * This file contains routines for manipulating a direct-access hash table
 *
 * Started 3/22/04
 * George
 *
 */
 
#include <GKlib.h>
 
/******************************************************************************
* This function creates the hash-table
*******************************************************************************/
gk_HTable_t *HTable_Create(int nelements)
{
  gk_HTable_t *htable;
 
  htable            = gk_malloc(sizeof(gk_HTable_t), "HTable_Create: htable");
  htable->harray    = gk_ikvmalloc(nelements, "HTable_Create: harray");
  htable->nelements = nelements;
 
  HTable_Reset(htable);
 
  return htable;
}
 
 
/******************************************************************************
* This function resets the data-structures associated with the hash-table
*******************************************************************************/
void HTable_Reset(gk_HTable_t *htable)
{
  int i;
 
  for (i=0; i<htable->nelements; i++)
    htable->harray[i].key = HTABLE_EMPTY;
  htable->htsize = 0;
 
}
 
/******************************************************************************
* This function resizes the hash-table
*******************************************************************************/
void HTable_Resize(gk_HTable_t *htable, int nelements)
{
  int i, old_nelements;
  gk_ikv_t *old_harray;
 
  old_nelements = htable->nelements;
  old_harray = htable->harray;
 
  /* prepare larger hash */
  htable->nelements = nelements;
  htable->htsize = 0;
  htable->harray = gk_ikvmalloc(nelements, "HTable_Resize: harray");
  for (i=0; i<nelements; i++)
    htable->harray[i].key = HTABLE_EMPTY;
 
  /* reassign the values */
  for (i=0; i<old_nelements; i++)
    if (old_harray[i].key != HTABLE_EMPTY)
       HTable_Insert(htable, old_harray[i].key, old_harray[i].val);
 
  /* remove old harray */
  gk_free((void **)&old_harray, LTERM);
}
 
 
/******************************************************************************
* This function inserts a key-value pair in the array
*******************************************************************************/
void HTable_Insert(gk_HTable_t *htable, int key, int val)
{
  int i, first;
 
  if (htable->htsize > htable->nelements/2)
    HTable_Resize(htable, 2*htable->nelements);
 
  first = HTable_HFunction(htable->nelements, key);
 
  for (i=first; i<htable->nelements; i++) {
    if (htable->harray[i].key == HTABLE_EMPTY || htable->harray[i].key == HTABLE_DELETED) {
      htable->harray[i].key = key;
      htable->harray[i].val = val;
      htable->htsize++;
      return;
    }
  }
 
  for (i=0; i<first; i++) {
    if (htable->harray[i].key == HTABLE_EMPTY || htable->harray[i].key == HTABLE_DELETED) {
      htable->harray[i].key = key;
      htable->harray[i].val = val;
      htable->htsize++;
      return;
    }
  }
 
}
 
 
/******************************************************************************
* This function deletes key from the htable
*******************************************************************************/
void HTable_Delete(gk_HTable_t *htable, int key)
{
  int i, first;
 
  first = HTable_HFunction(htable->nelements, key);
 
  for (i=first; i<htable->nelements; i++) {
    if (htable->harray[i].key == key) {
      htable->harray[i].key = HTABLE_DELETED;
      htable->htsize--;
      return;
    }
  }
 
  for (i=0; i<first; i++) {
    if (htable->harray[i].key == key) {
      htable->harray[i].key = HTABLE_DELETED;
      htable->htsize--;
      return;
    }
  }
 
}
 
 
/******************************************************************************
* This function returns the data associated with the key in the hastable
*******************************************************************************/
int HTable_Search(gk_HTable_t *htable, int key)
{
  int i, first;
 
  first = HTable_HFunction(htable->nelements, key);
 
  for (i=first; i<htable->nelements; i++) {
    if (htable->harray[i].key == key) 
      return htable->harray[i].val;
    else if (htable->harray[i].key == HTABLE_EMPTY)
      return -1;
  }
 
  for (i=0; i<first; i++) {
    if (htable->harray[i].key == key) 
      return htable->harray[i].val;
    else if (htable->harray[i].key == HTABLE_EMPTY)
      return -1;
  }
 
  return -1;
}
 
 
/******************************************************************************
* This function returns the next key/val
*******************************************************************************/
int HTable_GetNext(gk_HTable_t *htable, int key, int *r_val, int type)
{
  int i;
  static int first, last;
 
  if (type == HTABLE_FIRST)
    first = last = HTable_HFunction(htable->nelements, key);
 
  if (first > last) {
    for (i=first; i<htable->nelements; i++) {
      if (htable->harray[i].key == key) {
        *r_val = htable->harray[i].val;
        first = i+1;
        return 1;
      }
      else if (htable->harray[i].key == HTABLE_EMPTY)
        return -1;
    }
    first = 0;
  }
 
  for (i=first; i<last; i++) {
    if (htable->harray[i].key == key) {
      *r_val = htable->harray[i].val;
      first = i+1;
      return 1;
    }
    else if (htable->harray[i].key == HTABLE_EMPTY)
      return -1;
  }
 
  return -1;
}
 
 
/******************************************************************************
* This function returns the data associated with the key in the hastable
*******************************************************************************/
int HTable_SearchAndDelete(gk_HTable_t *htable, int key)
{
  int i, first;
 
  first = HTable_HFunction(htable->nelements, key);
 
  for (i=first; i<htable->nelements; i++) {
    if (htable->harray[i].key == key) {
      htable->harray[i].key = HTABLE_DELETED;
      htable->htsize--;
      return htable->harray[i].val;
    }
    else if (htable->harray[i].key == HTABLE_EMPTY)
      gk_errexit(SIGERR, "HTable_SearchAndDelete: Failed to find the key!\n");
  }
 
  for (i=0; i<first; i++) {
    if (htable->harray[i].key == key) {
      htable->harray[i].key = HTABLE_DELETED;
      htable->htsize--;
      return htable->harray[i].val;
    }
    else if (htable->harray[i].key == HTABLE_EMPTY)
      gk_errexit(SIGERR, "HTable_SearchAndDelete: Failed to find the key!\n");
  }
 
  return -1;
 
}
 
 
 
/******************************************************************************
* This function destroys the data structures associated with the hash-table
*******************************************************************************/
void HTable_Destroy(gk_HTable_t *htable)
{
  gk_free((void **)&htable->harray, &htable, LTERM);
}
 
 
/******************************************************************************
* This is the hash-function. Based on multiplication
*******************************************************************************/
int HTable_HFunction(int nelements, int key)
{
  return (int)(key%nelements);
}