hash.c

   1 /* hash table */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include "hash.h"
   6 #include "iftop.h"
   7
   8 hash_status_enum hash_insert(hash_type* hash_table, void* key, void* rec) {
   9     hash_node_type *p, *p0;
  10     int bucket;
  11
  12    /************************************************
  13     *  allocate node for data and insert in table  *
  14     ************************************************/
  15
  16
  17     /* insert node at beginning of list */
  18     bucket = hash_table->hash(key);
  19     p = xmalloc(sizeof *p);
  20     p0 = hash_table->table[bucket];
  21     hash_table->table[bucket] = p;
  22     p->next = p0;
  23     p->key = hash_table->copy_key(key);
  24     p->rec = rec;
  25     return HASH_STATUS_OK;
  26 }
  27
  28 hash_status_enum hash_delete(hash_type* hash_table, void* key) {
  29     hash_node_type *p0, *p;
  30     int bucket;
  31
  32    /********************************************
  33     *  delete node containing data from table  *
  34     ********************************************/
  35
  36     /* find node */
  37     p0 = 0;
  38     bucket = hash_table->hash(key);
  39     p = hash_table->table[bucket];
  40     while (p && !hash_table->compare(p->key, key)) {
  41         p0 = p;
  42         p = p->next;
  43     }
  44     if (!p) return HASH_STATUS_KEY_NOT_FOUND;
  45
  46     /* p designates node to delete, remove it from list */
  47     if (p0) {
  48         /* not first node, p0 points to previous node */
  49         p0->next = p->next;
  50     }
  51     else {
  52         /* first node on chain */
  53         hash_table->table[bucket] = p->next;
  54     }
  55
  56     hash_table->delete_key(p->key);
  57     free (p);
  58     return HASH_STATUS_OK;
  59 }
  60
  61 hash_status_enum hash_find(hash_type* hash_table, void* key, void **rec) {
  62     hash_node_type *p;
  63
  64    /*******************************
  65     *  find node containing data  *
  66     *******************************/
  67     p = hash_table->table[hash_table->hash(key)];
  68
  69     while (p && !hash_table->compare(p->key, key))  {
  70         p = p->next;
  71     }
  72     if (!p) return HASH_STATUS_KEY_NOT_FOUND;
  73     *rec = p->rec;
  74     return HASH_STATUS_OK;
  75 }
  76
  77 hash_status_enum hash_next_item(hash_type* hash_table, hash_node_type** ppnode) {
  78     int i;
  79     if(*ppnode != NULL) {
  80         if((*ppnode)->next != NULL) {
  81             *ppnode = (*ppnode)->next;
  82             return HASH_STATUS_OK;
  83         }
  84         i = hash_table->hash((*ppnode)->key) + 1;
  85     }
  86     else {
  87         /* first node */
  88         i = 0;
  89     }
  90     while(i < hash_table->size && hash_table->table[i] == NULL) {
  91          i++;
  92     }
  93     if(i == hash_table->size) {
  94         *ppnode = NULL;
  95         return HASH_STATUS_KEY_NOT_FOUND;
  96     }
  97     *ppnode = hash_table->table[i];
  98     return HASH_STATUS_OK;
  99 }
 100
 101 void hash_delete_all(hash_type* hash_table) {
 102     int i;
 103     hash_node_type *n, *nn;
 104     for(i = 0; i < hash_table->size; i++) {
 105         n = hash_table->table[i];
 106         while(n != NULL) {
 107             nn = n->next;
 108             hash_table->delete_key(n->key);
 109             free(n);
 110             n = nn;
 111         }
 112         hash_table->table[i] = NULL;
 113     }
 114 }
 115
 116
 117 /*
 118  * Allocate and return a hash
 119  */
 120 hash_status_enum hash_initialise(hash_type* hash_table) {
 121     hash_table->table = xcalloc(hash_table->size, sizeof *hash_table->table);
 122     return HASH_STATUS_OK;
 123 }
 124
 125 hash_status_enum hash_destroy(hash_type* hash_table) {
 126     free(hash_table->table);
 127     return HASH_STATUS_OK;
 128 }
 129