Line data    Source code

       1             : /* hash.c
       2             : ** strophe XMPP client library -- hash table implementation
       3             : **
       4             : ** Copyright (C) 2005-2009 Collecta, Inc.
       5             : **
       6             : **  This software is provided AS-IS with no warranty, either express
       7             : **  or implied.
       8             : **
       9             : **  This program is dual licensed under the MIT and GPLv3 licenses.
      10             : */
      11             : 
      12             : /** @file
      13             :  *  Hash tables.
      14             :  */
      15             : 
      16             : #include <stdlib.h>
      17             : #include <string.h>
      18             : 
      19             : #include "strophe.h"
      20             : #include "common.h"
      21             : #include "hash.h"
      22             : 
      23             : /* private types */
      24             : typedef struct _hashentry_t hashentry_t;
      25             : 
      26             : struct _hashentry_t {
      27             :     hashentry_t *next;
      28             :     char *key;
      29             :     void *value;
      30             : };
      31             : 
      32             : struct _hash_t {
      33             :     unsigned int ref;
      34             :     xmpp_ctx_t *ctx;
      35             :     hash_free_func free;
      36             :     int length;
      37             :     int num_keys;
      38             :     hashentry_t **entries;
      39             : };
      40             : 
      41             : struct _hash_iterator_t {
      42             :     unsigned int ref;
      43             :     hash_t *table;
      44             :     hashentry_t *entry;
      45             :     int index;
      46             : };
      47             : 
      48             : /** allocate and initialize a new hash table */
      49          38 : hash_t *hash_new(xmpp_ctx_t *ctx, int size, hash_free_func free_func)
      50             : {
      51          38 :     hash_t *result = NULL;
      52             : 
      53          38 :     result = strophe_alloc(ctx, sizeof(hash_t));
      54          38 :     if (result != NULL) {
      55          38 :         result->entries = strophe_alloc(ctx, size * sizeof(hashentry_t *));
      56          38 :         if (result->entries == NULL) {
      57           0 :             strophe_free(ctx, result);
      58           0 :             return NULL;
      59             :         }
      60          38 :         memset(result->entries, 0, size * sizeof(hashentry_t *));
      61          38 :         result->length = size;
      62             : 
      63          38 :         result->ctx = ctx;
      64          38 :         result->free = free_func;
      65          38 :         result->num_keys = 0;
      66             :         /* give the caller a reference */
      67          38 :         result->ref = 1;
      68             :     }
      69             : 
      70             :     return result;
      71             : }
      72             : 
      73             : /** obtain a new reference to an existing hash table */
      74          32 : hash_t *hash_clone(hash_t *table)
      75             : {
      76          32 :     table->ref++;
      77          32 :     return table;
      78             : }
      79             : 
      80             : /** release a hash table that is no longer needed */
      81          70 : void hash_release(hash_t *table)
      82             : {
      83          70 :     xmpp_ctx_t *ctx = table->ctx;
      84          70 :     hashentry_t *entry, *next;
      85          70 :     int i;
      86             : 
      87          70 :     if (table->ref > 1)
      88          32 :         table->ref--;
      89             :     else {
      90         534 :         for (i = 0; i < table->length; i++) {
      91         496 :             entry = table->entries[i];
      92         541 :             while (entry != NULL) {
      93          45 :                 next = entry->next;
      94          45 :                 strophe_free(ctx, entry->key);
      95          45 :                 if (table->free)
      96          45 :                     table->free(ctx, entry->value);
      97          45 :                 strophe_free(ctx, entry);
      98          45 :                 entry = next;
      99             :             }
     100             :         }
     101          38 :         strophe_free(ctx, table->entries);
     102          38 :         strophe_free(ctx, table);
     103             :     }
     104          70 : }
     105             : 
     106             : /** hash a key for our table lookup */
     107         164 : static int _hash_key(hash_t *table, const char *key)
     108             : {
     109         164 :     unsigned hash = 0;
     110         164 :     unsigned shift = 0;
     111         164 :     const unsigned char *c = (const unsigned char *)key;
     112             : 
     113         871 :     while (*c != 0) {
     114             :         /* assume 32 bit ints */
     115         707 :         hash ^= ((unsigned)*c++ << shift);
     116         707 :         shift += 8;
     117         707 :         if (shift > 24)
     118         134 :             shift = 0;
     119             :     }
     120         164 :     return hash % (unsigned)table->length;
     121             : }
     122             : 
     123         113 : hashentry_t *_hash_entry_find(hash_t *table, const char *key)
     124             : {
     125         113 :     hashentry_t *entry;
     126         113 :     int table_index = _hash_key(table, key);
     127             : 
     128             :     /* look up the hash entry */
     129         113 :     entry = table->entries[table_index];
     130         127 :     while (entry != NULL) {
     131             :         /* traverse the linked list looking for the key */
     132          78 :         if (!strcmp(key, entry->key)) {
     133             :             /* match */
     134             :             break;
     135             :         }
     136          14 :         entry = entry->next;
     137             :     }
     138         113 :     return entry;
     139             : }
     140             : 
     141             : /** add a key, value pair to a hash table.
     142             :  *  each key can appear only once; the value of any
     143             :  *  identical key will be replaced
     144             :  */
     145          48 : int hash_add(hash_t *table, const char *key, void *data)
     146             : {
     147          48 :     xmpp_ctx_t *ctx = table->ctx;
     148          48 :     hashentry_t *entry = NULL;
     149          48 :     int table_index = _hash_key(table, key);
     150             : 
     151             :     /* find and replace existing entry, if any */
     152          48 :     entry = _hash_entry_find(table, key);
     153             : 
     154          48 :     if (entry == NULL) {
     155             :         /* allocate and fill a new entry */
     156          47 :         entry = strophe_alloc(ctx, sizeof(hashentry_t));
     157          47 :         if (!entry)
     158             :             return -1;
     159          47 :         entry->key = strophe_strdup(ctx, key);
     160          47 :         if (!entry->key) {
     161           0 :             strophe_free(ctx, entry);
     162           0 :             return -1;
     163             :         }
     164             :         /* insert ourselves in the linked list */
     165          47 :         entry->next = table->entries[table_index];
     166          47 :         table->entries[table_index] = entry;
     167          47 :         table->num_keys++;
     168             :     } else {
     169           1 :         if (table->free)
     170           1 :             table->free(ctx, entry->value);
     171             :     }
     172             : 
     173          48 :     entry->value = data;
     174             : 
     175          48 :     return 0;
     176             : }
     177             : 
     178             : /** look up a key in a hash table */
     179          65 : void *hash_get(hash_t *table, const char *key)
     180             : {
     181          65 :     hashentry_t *entry;
     182             : 
     183          65 :     entry = _hash_entry_find(table, key);
     184          65 :     return entry == NULL ? NULL : entry->value;
     185             : }
     186             : 
     187             : /** delete a key from a hash table */
     188           3 : int hash_drop(hash_t *table, const char *key)
     189             : {
     190           3 :     xmpp_ctx_t *ctx = table->ctx;
     191           3 :     hashentry_t *entry, *prev;
     192           3 :     int table_index = _hash_key(table, key);
     193             : 
     194             :     /* look up the hash entry */
     195           3 :     entry = table->entries[table_index];
     196           3 :     prev = NULL;
     197           3 :     while (entry != NULL) {
     198             :         /* traverse the linked list looking for the key */
     199           2 :         if (!strcmp(key, entry->key)) {
     200             :             /* match, remove the entry */
     201           2 :             strophe_free(ctx, entry->key);
     202           2 :             if (table->free)
     203           2 :                 table->free(ctx, entry->value);
     204           2 :             if (prev == NULL) {
     205           2 :                 table->entries[table_index] = entry->next;
     206             :             } else {
     207           0 :                 prev->next = entry->next;
     208             :             }
     209           2 :             strophe_free(ctx, entry);
     210           2 :             table->num_keys--;
     211           2 :             return 0;
     212             :         }
     213           0 :         prev = entry;
     214           0 :         entry = entry->next;
     215             :     }
     216             :     /* no match */
     217             :     return -1;
     218             : }
     219             : 
     220          14 : int hash_num_keys(hash_t *table)
     221             : {
     222          14 :     return table->num_keys;
     223             : }
     224             : 
     225             : /** allocate and initialize a new iterator */
     226          32 : hash_iterator_t *hash_iter_new(hash_t *table)
     227             : {
     228          32 :     xmpp_ctx_t *ctx = table->ctx;
     229          32 :     hash_iterator_t *iter;
     230             : 
     231          32 :     iter = strophe_alloc(ctx, sizeof(*iter));
     232          32 :     if (iter != NULL) {
     233          32 :         iter->ref = 1;
     234          32 :         iter->table = hash_clone(table);
     235          32 :         iter->entry = NULL;
     236          32 :         iter->index = -1;
     237             :     }
     238             : 
     239          32 :     return iter;
     240             : }
     241             : 
     242             : /** release an iterator that is no longer needed */
     243          32 : void hash_iter_release(hash_iterator_t *iter)
     244             : {
     245          32 :     xmpp_ctx_t *ctx = iter->table->ctx;
     246             : 
     247          32 :     iter->ref--;
     248             : 
     249          32 :     if (iter->ref == 0) { // ref is unsigned!!!
     250          32 :         hash_release(iter->table);
     251          32 :         strophe_free(ctx, iter);
     252             :     }
     253          32 : }
     254             : 
     255             : /** return the next hash table key from the iterator.
     256             :     the returned key should not be freed */
     257          58 : const char *hash_iter_next(hash_iterator_t *iter)
     258             : {
     259          58 :     hash_t *table = iter->table;
     260          58 :     hashentry_t *entry = iter->entry;
     261          58 :     int i;
     262             : 
     263             :     /* advance until we find the next entry */
     264          58 :     if (entry != NULL)
     265          26 :         entry = entry->next;
     266          26 :     if (entry == NULL) {
     267             :         /* we're off the end of list, search for a new entry */
     268          54 :         i = iter->index + 1;
     269         672 :         while (i < iter->table->length) {
     270         640 :             entry = table->entries[i];
     271         640 :             if (entry != NULL) {
     272          22 :                 iter->index = i;
     273          22 :                 break;
     274             :             }
     275         618 :             i++;
     276             :         }
     277             :     }
     278             : 
     279          54 :     if (entry == NULL) {
     280             :         /* no more keys! */
     281             :         return NULL;
     282             :     }
     283             : 
     284             :     /* remember our current match */
     285          26 :     iter->entry = entry;
     286          26 :     return entry->key;
     287             : }