Blame view

pdw committed
1 2 3 4 5
/* hash table */

#include <stdio.h>
#include <stdlib.h>
#include "hash.h"
chris committed
6
#include "iftop.h"
pdw committed
7 8 9 10 11 12 13 14 15 16 17 18

hash_status_enum hash_insert(hash_type* hash_table, void* key, void* rec) {
    hash_node_type *p, *p0;
    int bucket;

   /************************************************
    *  allocate node for data and insert in table  *
    ************************************************/


    /* insert node at beginning of list */
    bucket = hash_table->hash(key);
chris committed
19
    p = xmalloc(sizeof *p);
pdw committed
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
    p0 = hash_table->table[bucket];
    hash_table->table[bucket] = p;
    p->next = p0;
    p->key = hash_table->copy_key(key);
    p->rec = rec;
    return HASH_STATUS_OK;
}

hash_status_enum hash_delete(hash_type* hash_table, void* key) {
    hash_node_type *p0, *p;
    int bucket;

   /********************************************
    *  delete node containing data from table  *
    ********************************************/

    /* find node */
    p0 = 0;
    bucket = hash_table->hash(key);
    p = hash_table->table[bucket];
    while (p && !hash_table->compare(p->key, key)) {
        p0 = p;
        p = p->next;
    }
    if (!p) return HASH_STATUS_KEY_NOT_FOUND;

    /* p designates node to delete, remove it from list */
pdw committed
47
    if (p0) {
pdw committed
48 49
        /* not first node, p0 points to previous node */
        p0->next = p->next;
pdw committed
50 51
    }
    else {
pdw committed
52 53
        /* first node on chain */
        hash_table->table[bucket] = p->next;
pdw committed
54
    }
pdw committed
55 56 57 58 59 60 61 62 63 64 65 66

    hash_table->delete_key(p->key);
    free (p);
    return HASH_STATUS_OK;
}

hash_status_enum hash_find(hash_type* hash_table, void* key, void **rec) {
    hash_node_type *p;

   /*******************************
    *  find node containing data  *
    *******************************/
pdw committed
67
    p = hash_table->table[hash_table->hash(key)];
pdw committed
68 69

    while (p && !hash_table->compare(p->key, key))  {
pdw committed
70
        p = p->next;
pdw committed
71
    }
pdw committed
72 73 74 75 76 77 78
    if (!p) return HASH_STATUS_KEY_NOT_FOUND;
    *rec = p->rec;
    return HASH_STATUS_OK;
}

hash_status_enum hash_next_item(hash_type* hash_table, hash_node_type** ppnode) {
    int i;
79 80 81 82 83

    if (hash_table == 0) {
      return HASH_STATUS_KEY_NOT_FOUND;
    }

pdw committed
84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
    if(*ppnode != NULL) {
        if((*ppnode)->next != NULL) {
            *ppnode = (*ppnode)->next;
            return HASH_STATUS_OK;
        }
        i = hash_table->hash((*ppnode)->key) + 1;
    }
    else {
        /* first node */
        i = 0;
    }
    while(i < hash_table->size && hash_table->table[i] == NULL) {
         i++; 
    }
    if(i == hash_table->size) {
        *ppnode = NULL;
        return HASH_STATUS_KEY_NOT_FOUND;
    }
    *ppnode = hash_table->table[i];
    return HASH_STATUS_OK;
}

106 107 108
void hash_delete_all(hash_type* hash_table) {
    int i;
    hash_node_type *n, *nn;
109 110 111 112 113

    if(hash_table == 0) {
      return;
    }

114 115 116 117 118 119 120 121 122 123 124 125 126
    for(i = 0; i < hash_table->size; i++) {
        n = hash_table->table[i];
        while(n != NULL) {
            nn = n->next;
            hash_table->delete_key(n->key);
            free(n);
            n = nn;
        }
        hash_table->table[i] = NULL;
    }
}


pdw committed
127 128 129 130
/*
 * Allocate and return a hash
 */
hash_status_enum hash_initialise(hash_type* hash_table) {
chris committed
131
    hash_table->table = xcalloc(hash_table->size, sizeof *hash_table->table);
pdw committed
132 133 134 135 136 137 138 139
    return HASH_STATUS_OK;
}

hash_status_enum hash_destroy(hash_type* hash_table) {
    free(hash_table->table);
    return HASH_STATUS_OK;
}