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

            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           26 :     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           54 :     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 2.0-1