hash.c 3.27 KB
Newer Older
pdw's avatar
pdw committed
1 2 3 4 5
/* hash table */

#include <stdio.h>
#include <stdlib.h>
#include "hash.h"
chris's avatar
chris committed
6
#include "iftop.h"
pdw's avatar
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's avatar
chris committed
19
    p = xmalloc(sizeof *p);
pdw's avatar
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's avatar
pdw committed
47
    if (p0) {
pdw's avatar
pdw committed
48 49
        /* not first node, p0 points to previous node */
        p0->next = p->next;
pdw's avatar
pdw committed
50 51
    }
    else {
pdw's avatar
pdw committed
52 53
        /* first node on chain */
        hash_table->table[bucket] = p->next;
pdw's avatar
pdw committed
54
    }
pdw's avatar
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's avatar
pdw committed
67
    p = hash_table->table[hash_table->hash(key)];
pdw's avatar
pdw committed
68 69

    while (p && !hash_table->compare(p->key, key))  {
pdw's avatar
pdw committed
70
        p = p->next;
pdw's avatar
pdw committed
71
    }
pdw's avatar
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's avatar
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's avatar
pdw committed
127 128 129 130
/*
 * Allocate and return a hash
 */
hash_status_enum hash_initialise(hash_type* hash_table) {
chris's avatar
chris committed
131
    hash_table->table = xcalloc(hash_table->size, sizeof *hash_table->table);
pdw's avatar
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;
}