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
  80     if (hash_table == 0) {
  81       return HASH_STATUS_KEY_NOT_FOUND;
  82     }
  83
  84     if(*ppnode != NULL) {
  85         if((*ppnode)->next != NULL) {
  86             *ppnode = (*ppnode)->next;
  87             return HASH_STATUS_OK;
  88         }
  89         i = hash_table->hash((*ppnode)->key) + 1;
  90     }
  91     else {
  92         /* first node */
  93         i = 0;
  94     }
  95     while(i < hash_table->size && hash_table->table[i] == NULL) {
  96          i++;
  97     }
  98     if(i == hash_table->size) {
  99         *ppnode = NULL;
 100         return HASH_STATUS_KEY_NOT_FOUND;
 101     }
 102     *ppnode = hash_table->table[i];
 103     return HASH_STATUS_OK;
 104 }
 105
 106 void hash_delete_all(hash_type* hash_table) {
 107     int i;
 108     hash_node_type *n, *nn;
 109
 110     if(hash_table == 0) {
 111       return;
 112     }
 113
 114     for(i = 0; i < hash_table->size; i++) {
 115         n = hash_table->table[i];
 116         while(n != NULL) {
 117             nn = n->next;
 118             hash_table->delete_key(n->key);
 119             free(n);
 120             n = nn;
 121         }
 122         hash_table->table[i] = NULL;
 123     }
 124 }
 125
 126
 127 /*
 128  * Allocate and return a hash
 129  */
 130 hash_status_enum hash_initialise(hash_type* hash_table) {
 131     hash_table->table = xcalloc(hash_table->size, sizeof *hash_table->table);
 132     return HASH_STATUS_OK;
 133 }
 134
 135 hash_status_enum hash_destroy(hash_type* hash_table) {
 136     free(hash_table->table);
 137     return HASH_STATUS_OK;
 138 }
 139