htbl.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license in the file COPYING
 * or http://www.opensource.org/licenses/CDDL-1.0.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file COPYING.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2023 Saso Kiselkov. All rights reserved.
 */
 
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
 
#include "acfutils/crc64.h"
#include "acfutils/helpers.h"
#define __INCLUDED_FROM_HTBL_C__
#include "acfutils/htbl.h"
 
typedef struct {
    list_node_t bucket_node;
    size_t      value_sz;
    union {
        void    *value;
        list_t  multi;
    };
    uint8_t     key[1]; /* variable length, depends on htbl->key_sz */
} htbl_bucket_item_t;
 
struct htbl_multi_value_s {
    void            *value;
    list_node_t     node;
    htbl_bucket_item_t  *item;
};
 
static inline uint64_t
H(const void *p, size_t l)
{
    return (crc64(p, l));
}
 
static inline void
htbl2_check_key_type(const htbl2_t REQ_PTR(htbl), size_t key_sz)
{
    ASSERT_MSG(key_sz == htbl->h.key_sz,
        "Invalid hash table operation with key_sz %x, whereas the "
        "hash table was created with key_sz %x. This most likely "
        "indicates a data type error.",
        (unsigned)key_sz, (unsigned)htbl->h.key_sz);
}
 
static inline void
htbl2_check_value_type(size_t htbl_value_sz, size_t value_sz)
{
    ASSERT_MSG(value_sz == htbl_value_sz,
        "Invalid hash table operation with value_sz %x, whereas "
        "the hash table was created with value_sz %x. This most "
        "likely indicates a data type error.",
        (unsigned)value_sz, (unsigned)htbl_value_sz);
}
 
static inline void
htbl2_check_types(const htbl2_t REQ_PTR(htbl), size_t key_sz, size_t value_sz)
{
    htbl2_check_key_type(htbl, key_sz);
    htbl2_check_value_type(htbl->value_sz, value_sz);
}
 
static void
htbl_create_impl(htbl_t *htbl, size_t tbl_sz, size_t key_sz, bool multi_value)
{
    ASSERT(htbl != NULL);
    ASSERT(key_sz != 0);
    ASSERT(tbl_sz != 0);
    ASSERT(tbl_sz <= ((size_t)1 << ((sizeof(size_t) * 8) - 1)));
 
    memset(htbl, 0, sizeof (*htbl));
    /* round table size up to nearest multiple of 2 */
    htbl->tbl_sz = P2ROUNDUP(tbl_sz);
    htbl->buckets = safe_malloc(sizeof (*htbl->buckets) * htbl->tbl_sz);
    ASSERT(htbl->buckets != NULL);
    for (size_t i = 0; i < htbl->tbl_sz; i++) {
        list_create(&htbl->buckets[i], sizeof (htbl_bucket_item_t),
            offsetof(htbl_bucket_item_t, bucket_node));
    }
    htbl->key_sz = key_sz;
    htbl->multi_value = multi_value;
}
 
void
htbl_create(htbl_t REQ_PTR(htbl), size_t tbl_sz, size_t key_sz,
    bool_t multi_value)
{
    htbl_create_impl(htbl, tbl_sz, key_sz, multi_value);
}
 
void
htbl2_create(htbl2_t REQ_PTR(htbl), size_t tbl_sz, size_t key_sz,
    size_t value_sz, bool multi_value)
{
    htbl_create_impl(&htbl->h, tbl_sz, key_sz, multi_value);
    htbl->value_sz = value_sz;
}
 
void
htbl_destroy(htbl_t REQ_PTR(htbl))
{
    ASSERT(htbl != NULL);
    ASSERT(htbl->num_values == 0);
    ASSERT(htbl->buckets != NULL);
    for (size_t i = 0; i < htbl->tbl_sz; i++)
        list_destroy(&htbl->buckets[i]);
    free(htbl->buckets);
}
 
void
htbl2_destroy(htbl2_t REQ_PTR(htbl))
{
    htbl_destroy(&htbl->h);
}
 
static void
htbl_empty_multi_item(htbl_bucket_item_t *item, void (*func)(void *, void *),
    void *arg)
{
    for (htbl_multi_value_t *mv = list_head(&item->multi); mv;
        mv = list_head(&item->multi)) {
        if (func != NULL)
            func(mv->value, arg);
        list_remove_head(&item->multi);
        free(mv);
    }
    list_destroy(&item->multi);
}
 
void
htbl_empty(htbl_t REQ_PTR(htbl), void (*func)(void *value, void *userinfo),
    void *userinfo)
{
    if (htbl->num_values == 0)
        return;
    for (size_t i = 0; i < htbl->tbl_sz; i++) {
        for (htbl_bucket_item_t *item = list_head(&htbl->buckets[i]);
            item; item = list_head(&htbl->buckets[i])) {
            if (htbl->multi_value)
                htbl_empty_multi_item(item, func, userinfo);
            else if (func != NULL)
                func(item->value, userinfo);
            list_remove_head(&htbl->buckets[i]);
            free(item);
        }
    }
    htbl->num_values = 0;
}
 
void
htbl2_empty(htbl2_t REQ_PTR(htbl), size_t value_sz,
    void (*func)(void *value, void *userinfo), void *userinfo)
{
    htbl2_check_value_type(htbl->value_sz, value_sz);
    htbl_empty(&htbl->h, func, userinfo);
}
 
size_t
htbl_count(const htbl_t *htbl)
{
    ASSERT(htbl != NULL);
    return (htbl->num_values);
}
 
size_t
htbl2_count(const htbl2_t *htbl)
{
    ASSERT(htbl != NULL);
    return (htbl->h.num_values);
}
 
static void
htbl_multi_value_add(htbl_t *htbl, htbl_bucket_item_t *item, void *value)
{
    htbl_multi_value_t *mv = safe_malloc(sizeof (*mv));
    ASSERT(htbl->multi_value);
    mv->value = value;
    mv->item = item;
    list_insert_head(&item->multi, mv);
    htbl->num_values++;
}
 
static void
htbl_set_impl(htbl_t REQ_PTR(htbl), const void *key, void *value,
    size_t value_sz)
{
    ASSERT(key != NULL);
 
    list_t *bucket = &htbl->buckets[H(key, htbl->key_sz) &
        (htbl->tbl_sz - 1)];
    htbl_bucket_item_t *item;
 
    ASSERT(key != NULL);
    ASSERT(value != NULL);
    for (item = list_head(bucket); item; item = list_next(bucket, item)) {
        if (memcmp(item->key, key, htbl->key_sz) == 0) {
            if (htbl->multi_value)
                htbl_multi_value_add(htbl, item, value);
            else
                item->value = value;
            return;
        }
    }
    item = safe_calloc(sizeof (*item) + htbl->key_sz - 1, 1);
    item->value_sz = value_sz;
    memcpy(item->key, key, htbl->key_sz);
    if (htbl->multi_value) {
        list_create(&item->multi, sizeof (htbl_multi_value_t),
            offsetof(htbl_multi_value_t, node));
        htbl_multi_value_add(htbl, item, value);
    } else {
        item->value = value;
    }
    list_insert_head(bucket, item);
    htbl->num_values++;
}
 
void
htbl_set(htbl_t REQ_PTR(htbl), const void *key, void *value)
{
    htbl_set_impl(htbl, key, value, SIZE_MAX);
}
 
void
htbl2_set(htbl2_t REQ_PTR(htbl), const void *key, size_t key_sz,
    void *value, size_t value_sz)
{
    htbl2_check_types(htbl, key_sz, value_sz);
    htbl_set_impl(&htbl->h, key, value, value_sz);
}
 
void
htbl_remove(htbl_t REQ_PTR(htbl), const void *key, bool_t nil_ok)
{
    ASSERT(htbl != NULL);
    ASSERT(key != NULL);
 
    list_t *bucket = &htbl->buckets[H(key, htbl->key_sz) &
        (htbl->tbl_sz - 1)];
    htbl_bucket_item_t *item;
 
    for (item = list_head(bucket); item; item = list_next(bucket, item)) {
        if (memcmp(item->key, key, htbl->key_sz) == 0) {
            list_remove(bucket, item);
            if (htbl->multi_value) {
                htbl_empty_multi_item(item, NULL, NULL);
                ASSERT3U(htbl->num_values, >=,
                    list_count(&item->multi));
                htbl->num_values -= list_count(&item->multi);
            } else {
                free(item);
                ASSERT(htbl->num_values != 0);
                htbl->num_values--;
            }
            return;
        }
    }
    ASSERT(nil_ok);
}
 
void
htbl2_remove(htbl2_t REQ_PTR(htbl), const void *key, size_t key_sz,
    bool nil_ok)
{
    htbl2_check_key_type(htbl, key_sz);
    htbl_remove(&htbl->h, key, nil_ok);
}
 
void
htbl_remove_multi(htbl_t REQ_PTR(htbl), const void *key,
    htbl_multi_value_t *list_item)
{
    ASSERT(htbl != NULL);
    ASSERT(htbl->multi_value);
    ASSERT(htbl->num_values != 0);
    ASSERT(list_item != NULL);
    ASSERT(key != NULL);
 
    htbl_bucket_item_t *item = list_item->item;
    ASSERT(item != NULL);
 
    list_remove(&item->multi, list_item);
    htbl->num_values--;
    free(list_item);
    if (list_count(&item->multi) == 0) {
        list_t *bucket =
            &htbl->buckets[H(key, htbl->key_sz) & (htbl->tbl_sz - 1)];
        list_remove(bucket, item);
        list_destroy(&item->multi);
        free(item);
    }
}
 
void
htbl2_remove_multi(htbl2_t REQ_PTR(htbl), const void *key, size_t key_sz,
    htbl2_multi_value_t *list_item)
{
    htbl2_check_key_type(htbl, key_sz);
    htbl_remove_multi(&htbl->h, key, list_item);
}
 
static htbl_bucket_item_t *
htbl_lookup_common(const htbl_t *htbl, const void *key)
{
    ASSERT(htbl != NULL);
    ASSERT(key != NULL);
 
    list_t *bucket = &htbl->buckets[H(key, htbl->key_sz) &
        (htbl->tbl_sz - 1)];
    htbl_bucket_item_t *item;
 
    for (item = list_head(bucket); item; item = list_next(bucket, item)) {
        if (memcmp(item->key, key, htbl->key_sz) == 0)
            return (item);
    }
    return (NULL);
}
 
void *
htbl_lookup(const htbl_t REQ_PTR(htbl), const void *key)
{
    htbl_bucket_item_t *item;
    ASSERT(!htbl->multi_value);
    item = htbl_lookup_common(htbl, key);
    return (item != NULL ? item->value : NULL);
}
 
void *
htbl2_lookup(const htbl2_t REQ_PTR(htbl), const void *key,
    size_t key_sz, size_t value_sz)
{
    htbl2_check_types(htbl, key_sz, value_sz);
    return (htbl_lookup(&htbl->h, key));
}
 
const list_t *
htbl_lookup_multi(const htbl_t REQ_PTR(htbl), const void *key)
{
    htbl_bucket_item_t *item;
    ASSERT(htbl->multi_value);
    item = htbl_lookup_common(htbl, key);
    return (item != NULL ? &item->multi : NULL);
}
 
const list_t *
htbl2_lookup_multi(const htbl2_t REQ_PTR(htbl), const void *key,
    size_t key_sz)
{
    htbl2_check_key_type(htbl, key_sz);
    return (htbl_lookup_multi(&htbl->h, key));
}
 
void
htbl_foreach(const htbl_t *htbl,
    void (*func)(const void *key, void *value, void *userinfo), void *userinfo)
{
    ASSERT(htbl != NULL);
    ASSERT(func != NULL);
    for (size_t i = 0; i < htbl->tbl_sz; i++) {
        list_t *bucket = &htbl->buckets[i];
        for (const htbl_bucket_item_t *item = list_head(bucket),
            *next_item = NULL; item; item = next_item) {
            /*
             * To support current value removal in the callback,
             * retrieve the next pointer right now.
             */
            next_item = list_next(bucket, item);
            if (htbl->multi_value) {
                const list_t *ml = &item->multi;
                for (htbl_multi_value_t *mv = list_head(ml),
                    *mv_next = NULL; mv != NULL; mv = mv_next) {
                    mv_next = list_next(ml, mv);
                    func(item->key, mv->value, userinfo);
                }
            } else {
                func(item->key, item->value, userinfo);
            }
        }
    }
}
 
void
htbl2_foreach(const htbl2_t REQ_PTR(htbl),
    size_t key_sz, size_t value_sz,
    void (*func)(const void *key, void *value, void *userinfo), void *userinfo)
{
    htbl2_check_types(htbl, key_sz, value_sz);
    htbl_foreach(&htbl->h, func, userinfo);
}
 
void *
htbl_value_multi(const htbl_multi_value_t *mv)
{
    ASSERT(mv != NULL);
    // To check against accidentally crossing over from htbl2_t
    htbl2_check_value_type(mv->item->value_sz, SIZE_MAX);
    return (mv->value);
}
 
void *
htbl2_value_multi(const htbl2_multi_value_t *mv, size_t value_sz)
{
    ASSERT(mv != NULL);
    htbl2_check_value_type(mv->item->value_sz, value_sz);
    return (mv->value);
}
 
char *
htbl_dump(const htbl_t *htbl, bool_t printable_keys)
{
    char    *result = NULL;
    size_t  result_sz = 0;
 
    append_format(&result, &result_sz, "(%lu){\n",
        (long unsigned)htbl->num_values);
    for (size_t i = 0; i < htbl->tbl_sz; i++) {
        list_t *bucket = &htbl->buckets[i];
        append_format(&result, &result_sz, "  [%lu] =",
            (long unsigned)i);
        if (list_head(bucket) == NULL)
            append_format(&result, &result_sz, " <empty>");
        for (const htbl_bucket_item_t *item = list_head(bucket); item;
            item = list_next(bucket, item)) {
            if (printable_keys) {
                append_format(&result, &result_sz, " (%s) ",
                    item->key);
            } else {
                append_format(&result, &result_sz, " (#BIN)");
            }
        }
        append_format(&result, &result_sz, "\n");
    }
    append_format(&result, &result_sz, "}");
 
    return (result);
}