LCOV - code coverage report
Current view: top level - src - hash.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 124 131 94.7 %
Date: 2024-02-24 00:00:00 Functions: 12 12 100.0 %

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

Generated by: LCOV version 1.14