"Fossies" - the Fresh Open Source Software Archive

Member "xorriso-1.5.4/libisofs/util_htable.c" (30 Jan 2021, 8616 Bytes) of package /linux/misc/xorriso-1.5.4.pl02.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "util_htable.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2  * Copyright (c) 2007 Vreixo Formoso
    3  * Copyright (c) 2014 Thomas Schmitt
    4  * 
    5  * This file is part of the libisofs project; you can redistribute it and/or 
    6  * modify it under the terms of the GNU General Public License version 2 
    7  * or later as published by the Free Software Foundation. 
    8  * See COPYING file for details.
    9  */
   10 
   11 #ifdef HAVE_CONFIG_H
   12 #include "../config.h"
   13 #endif
   14 
   15 #include "util.h"
   16 #include "libisofs.h"
   17 
   18 #include <stdlib.h>
   19 #include <string.h>
   20 
   21 /*
   22  * Hash table implementation
   23  */
   24 
   25 struct iso_hnode
   26 {
   27     void *key;
   28     void *data;
   29     
   30     /** next node for chaining */
   31     struct iso_hnode *next;
   32 };
   33 
   34 struct iso_htable
   35 {
   36     struct iso_hnode **table;
   37 
   38     size_t size; /**< number of items in table */
   39     size_t cap; /**< number of slots in table */
   40     
   41     hash_funtion_t hash;
   42     compare_function_t compare;
   43 };
   44 
   45 static
   46 struct iso_hnode *iso_hnode_new(void *key, void *data)
   47 {
   48     struct iso_hnode *node = malloc(sizeof(struct iso_hnode));
   49     if (node == NULL)
   50         return NULL;
   51     
   52     node->data = data;
   53     node->key = key;
   54     node->next = NULL;
   55     return node;
   56 }
   57 
   58 /**
   59  * Put an element in a Hash Table. The element will be identified by
   60  * the given key, that you should use to retrieve the element again.
   61  * 
   62  * This function allow duplicates, i.e., two items with the same key. In those
   63  * cases, the value returned by iso_htable_get() is undefined. If you don't
   64  * want to allow duplicates, use iso_htable_put() instead;
   65  * 
   66  * Both the key and data pointers will be stored internally, so you should
   67  * free the objects they point to. Use iso_htable_remove() to delete an 
   68  * element from the table.
   69  */
   70 int iso_htable_add(IsoHTable *table, void *key, void *data)
   71 {
   72     struct iso_hnode *node;
   73     struct iso_hnode *new;
   74     unsigned int hash;
   75     
   76     if (table == NULL || key == NULL) {
   77         return ISO_NULL_POINTER;
   78     }
   79     
   80     new = iso_hnode_new(key, data);
   81     if (new == NULL) {
   82         return ISO_OUT_OF_MEM;
   83     }
   84     
   85     hash = table->hash(key) % table->cap;
   86     node = table->table[hash];
   87 
   88     table->size++;
   89     new->next = node;
   90     table->table[hash] = new;
   91     return ISO_SUCCESS;
   92 }
   93 
   94 /**
   95  * Like iso_htable_add(), but this doesn't allow dulpicates.
   96  * 
   97  * @return
   98  *     1 success, 0 if an item with the same key already exists, < 0 error
   99  */
  100 int iso_htable_put(IsoHTable *table, void *key, void *data)
  101 {
  102     struct iso_hnode *node;
  103     struct iso_hnode *new;
  104     unsigned int hash;
  105     
  106     if (table == NULL || key == NULL) {
  107         return ISO_NULL_POINTER;
  108     }
  109     
  110     hash = table->hash(key) % table->cap;
  111     node = table->table[hash];
  112 
  113     while (node) {
  114         if (!table->compare(key, node->key)) {
  115             return 0;
  116         }
  117         node = node->next;
  118     }   
  119     
  120     new = iso_hnode_new(key, data);
  121     if (new == NULL) {
  122         return ISO_OUT_OF_MEM;
  123     }
  124     
  125     table->size++;
  126     new->next = table->table[hash];
  127     table->table[hash] = new;
  128     return ISO_SUCCESS;
  129 }
  130 
  131 /**
  132  * Retrieve an element from the given table. 
  133  * 
  134  * @param table
  135  *     Hash table
  136  * @param key
  137  *     Key of the element that will be removed
  138  * @param data
  139  *     Will be filled with the element found. Remains untouched if no
  140  *     element with the given key is found.
  141  * @return
  142  *      1 if found, 0 if not, < 0 on error
  143  */
  144 int iso_htable_get(IsoHTable *table, void *key, void **data)
  145 {
  146     struct iso_hnode *node;
  147     unsigned int hash;
  148     
  149     if (table == NULL || key == NULL) {
  150         return ISO_NULL_POINTER;
  151     }
  152     
  153     hash = table->hash(key) % table->cap;
  154     node = table->table[hash];
  155     while (node) {
  156         if (!table->compare(key, node->key)) {
  157             if (data) {
  158                 *data = node->data;
  159             }
  160             return 1;
  161         }
  162         node = node->next;
  163     }
  164     return 0;
  165 }
  166 
  167 /**
  168  * Remove an item with the given key from the table. In tables that allow 
  169  * duplicates, it is undefined the element that will be deleted.
  170  * 
  171  * @param table
  172  *     Hash table
  173  * @param key
  174  *     Key of the element that will be removed
  175  * @param free_data
  176  *     Function that will be called passing as parameters both the key and 
  177  *     the element that will be deleted. The user can use it to free the
  178  *     element. You can pass NULL if you don't want to delete the item itself.
  179  * @return
  180  *     1 success, 0 no element exists with the given key, < 0 error
  181  */
  182 int iso_htable_remove(IsoHTable *table, void *key, hfree_data_t free_data)
  183 {
  184     struct iso_hnode *node, *prev;
  185     unsigned int hash;
  186     
  187     if (table == NULL || key == NULL) {
  188         return ISO_NULL_POINTER;
  189     }
  190     
  191     hash = table->hash(key) % table->cap;
  192     node = table->table[hash];
  193     prev = NULL;
  194     while (node) {
  195         if (!table->compare(key, node->key)) {
  196             if (free_data)
  197                 free_data(node->key, node->data);
  198             if (prev) {
  199                 prev->next = node->next;
  200             } else {
  201                 table->table[hash] = node->next;
  202             }
  203             free(node);
  204             table->size--;
  205             return 1;
  206         }
  207         prev = node;
  208         node = node->next;
  209     }
  210     return 0;
  211 }
  212 
  213 /**
  214  * Like remove, but instead of checking for key equality using the compare
  215  * function, it just compare the key pointers. If the table allows duplicates,
  216  * and you provide different keys (i.e. different pointers) to elements 
  217  * with same key (i.e. same content), this function ensure the exact element
  218  * is removed. 
  219  * 
  220  * It has the problem that you must provide the same key pointer, and not just
  221  * a key whose contents are equal. Moreover, if you use the same key (same
  222  * pointer) to identify several objects, what of those are removed is 
  223  * undefined.
  224  * 
  225  * @param table
  226  *     Hash table
  227  * @param key
  228  *     Key of the element that will be removed
  229  * @param free_data
  230  *     Function that will be called passing as parameters both the key and 
  231  *     the element that will be deleted. The user can use it to free the
  232  *     element. You can pass NULL if you don't want to delete the item itself.
  233  * @return
  234  *     1 success, 0 no element exists with the given key, < 0 error
  235  */
  236 int iso_htable_remove_ptr(IsoHTable *table, void *key, hfree_data_t free_data)
  237 {
  238     struct iso_hnode *node, *prev;
  239     unsigned int hash;
  240     
  241     if (table == NULL || key == NULL) {
  242         return ISO_NULL_POINTER;
  243     }
  244     
  245     hash = table->hash(key) % table->cap;
  246     node = table->table[hash];
  247     prev = NULL;
  248     while (node) {
  249         if (key == node->key) {
  250             if (free_data)
  251                 free_data(node->key, node->data);
  252             if (prev) {
  253                 prev->next = node->next;
  254             } else {
  255                 table->table[hash] = node->next;
  256             }
  257             free(node);
  258             table->size--;
  259             return 1;
  260         }
  261         prev = node;
  262         node = node->next;
  263     }
  264     return 0;
  265 }
  266 
  267 /**
  268  * Hash function suitable for keys that are char strings.
  269  */
  270 unsigned int iso_str_hash(const void *key)
  271 {
  272     int i, len;
  273     const char *p = key;
  274     unsigned int h = 2166136261u;
  275 
  276     len = strlen(p);
  277     for (i = 0; i < len; i++)
  278         h = (h * 16777619 ) ^ p[i];
  279 
  280     return h;
  281 }
  282 
  283 /**
  284  * Destroy the given hash table.
  285  * 
  286  * Note that you're responsible to actually destroy the elements by providing
  287  * a valid free_data function. You can pass NULL if you only want to delete
  288  * the hash structure.
  289  */
  290 void iso_htable_destroy(IsoHTable *table, hfree_data_t free_data)
  291 {
  292     size_t i;
  293     struct iso_hnode *node, *tmp;
  294     
  295     if (table == NULL) {
  296         return;
  297     }
  298     
  299     for (i = 0; i < table->cap; ++i) {
  300         node = table->table[i];
  301         while (node) {
  302             tmp = node->next;
  303             if (free_data)
  304                 free_data(node->key, node->data);
  305             free(node);
  306             node = tmp;
  307         }
  308     }
  309     free(table->table);
  310     free(table);
  311 }
  312 
  313 /**
  314  * Create a new hash table.
  315  * 
  316  * @param size
  317  *     Number of slots in table.
  318  * @param hash
  319  *     Function used to generate
  320  */
  321 int iso_htable_create(size_t size, hash_funtion_t hash, 
  322                       compare_function_t compare, IsoHTable **table)
  323 {
  324     IsoHTable *t;
  325     
  326     if (size <= 0)
  327         return ISO_WRONG_ARG_VALUE;
  328     if (table == NULL)
  329         return ISO_NULL_POINTER;
  330     
  331     t = malloc(sizeof(IsoHTable));
  332     if (t == NULL) {
  333         return ISO_OUT_OF_MEM;
  334     }
  335     t->table = calloc(size, sizeof(void*));
  336     if (t->table == NULL) {
  337         free(t);
  338         return ISO_OUT_OF_MEM;
  339     }
  340     t->cap = size;
  341     t->size = 0;
  342     t->hash = hash;
  343     t->compare = compare;
  344 
  345     *table = t;
  346     return ISO_SUCCESS;
  347 }