libpool/common/dict.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 at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * 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 at usr/src/OPENSOLARIS.LICENSE.
 * 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 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident   "%Z%%M% %I% %E% SMI"

/*
 * This file contains a basic dictionary implementation which stores
 * arbitrary key-value mappings. It is used by libpool to store
 * information about element pointers (pool_elem_t) in the kernel
 * provider implementation.
 */

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>

#include "dict.h"

/*
 * HASH_64_INIT is the same as the INIT value since it is the value
 * used by FNV (FNV1_64_INIT). More details on FNV are available at:
 *
 * http://www.isthe.com/chongo/tech/comp/fnv/index.html
 */
#define HASH_64_INIT    (0xcbf29ce484222325ULL) /* Hash initializer */

/*
 * HASH_64_PRIME is a large prime number chosen to minimize hashing
 * collisions.
 */
#define HASH_64_PRIME   (0x100000001b3ULL)  /* Large Prime */

/*
 * DICT_SIZE is chosen as it is the nearest prime to 2^9 (512). 512 is
 * chosen as it is unlikely that this dictionary will contain more
 * elements than this in normal operation. Of course overflow in each
 * bucket is acceptable, but if there is too much overflow, then
 * performance will degrade to that of a list.
 */
#define DICT_SIZE   509         /* Reasonable prime */

/*
 * Data Types
 */

/*
 * A key bucket.
 */
typedef struct dict_bucket
{
    const void      *db_key;    /* key */
    void            *db_value;  /* value */
    struct dict_bucket  *db_next;   /* next bucket */
} dict_bucket_t;

/*
 * A dictionary which holds a mapping between a key and a value.
 *  dh_change   - detects changes to the dictionary.
 *  dh_cmp      - comparison function
 *  dh_hash     - hashing function
 *  dh_buckets  - key storage
 *  dh_size     - # of buckets
 */
struct dict_hdl {
    uint64_t        dh_change;
    int         (*dh_cmp)(const void *, const void *);
    uint64_t        (*dh_hash)(const void *);
    uint64_t        dh_length;
    dict_bucket_t       **dh_buckets;
    uint64_t        dh_size;
};

/*
 * Utility functions. Mainly used for debugging
 */

#if defined(DEBUG)

static void     bit_print_32(unsigned int);
static void     bit_print_64(unsigned long long);

#endif /* DEBUG */

/*
 * Default functions for hashing and comparing if the user does not specify
 * these values when creating the dictionary.
 */
static int      cmp_addr(const void *, const void *);
static uint64_t     hash_addr(const void *);

/*
 * static functions
 */

#if defined(DEBUG)

/*
 * Print to standard out the bit representation of the supplied value
 */
void
bit_print_32(unsigned int v)
{
#pragma error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
    int i, mask = 1 << 31;
#pragma error_messages(on, E_INTEGER_OVERFLOW_DETECTED)

    for (i = 1; i <= 32; i++) {
        (void) putchar(((v & mask) == 0) ? '0' : '1');
        v <<= 1;
        if (i % 8 == 0 && i != 32)
            (void) putchar(' ');
    }
    (void) putchar('\n');
}

/*
 * Print to standard out the bit representation of the supplied value
 */
void
bit_print_64(unsigned long long v)
{
#pragma error_messages(off, E_INTEGER_OVERFLOW_DETECTED)
    long long mask = 1ll << 63;
#pragma error_messages(on, E_INTEGER_OVERFLOW_DETECTED)
    int i;

    for (i = 1; i <= 64; i++) {
        (void) putchar(((v & mask) == 0) ? '0' : '1');
        v <<= 1;
        if (i % 8 == 0 && i != 64)
            (void) putchar(' ');
    }
    (void) putchar('\n');
}


#endif /* DEBUG */

/*
 * Default comparison function which is used if no comparison function
 * is supplied when the dictionary is created. The default behaviour
 * is to compare memory address.
 */
int
cmp_addr(const void *x, const void *y)
{
    return (x != y);
}


/*
 * The default hashing function which is used if no hashing function
 * is provided when the dictionary is created. The default behaviour
 * is to use the hash_buf() function.
 */
uint64_t
hash_addr(const void *key)
{
    return (hash_buf(&key, sizeof (key)));
}


/*
 * public interface
 */

/*
 * Return a hash which is built by manipulating each byte in the
 * supplied data. The hash logic follows the approach suggested in the
 * FNV hash.
 */
uint64_t
hash_buf(const void *buf, size_t len)
{
    uchar_t *start = (uchar_t *)buf;
    uchar_t *end = start + len;
    uint64_t hash = HASH_64_INIT;

    while (start < end) {
        hash *= HASH_64_PRIME;
        hash ^= (uint64_t)*start++;
    }

    return (hash);
}


/*
 * Return a hash which is built by manipulating each byte in the
 * supplied string. The hash logic follows the approach suggested in
 * the FNV hash.
 */
uint64_t
hash_str(const char *str)
{
    uchar_t *p = (uchar_t *)str;
    uint64_t hash = HASH_64_INIT;

    while (*p) {
        hash *= HASH_64_PRIME;
        hash ^= (uint64_t)*p++;
    }

    return (hash);
}

/*
 * Return the number of keys held in the supplied dictionary.
 */
uint64_t
dict_length(dict_hdl_t *hdl)
{
    return (hdl->dh_length);
}

/*
 * Free the supplied dictionary and all it's associated resource.
 */
void
dict_free(dict_hdl_t **hdl)
{
    if ((*hdl)->dh_length > 0) {
        uint64_t i;
        for (i = 0; i < (*hdl)->dh_size; i++) {
            dict_bucket_t *this, *next;
            for (this = (*hdl)->dh_buckets[i]; this != NULL;
                this = next) {
                next = this->db_next;
                free(this);
            }
        }
    }
    free((*hdl)->dh_buckets);
    free((*hdl));
    *hdl = NULL;
}

/*
 * Create a new dictionary using the supplied comparison and hashing
 * functions. If none are supplied then the defaults are used.
 */
dict_hdl_t *
dict_new(int (*cmp)(const void *, const void *),
    uint64_t (*hash)(const void *))
{
    dict_hdl_t *hdl;

    if ((hdl = calloc(1, sizeof (dict_hdl_t))) == NULL)
        return (NULL);
    hdl->dh_size = DICT_SIZE;
    if ((hdl->dh_buckets = calloc(hdl->dh_size, sizeof (dict_bucket_t *)))
        == NULL) {
        free(hdl);
        return (NULL);
    }
    hdl->dh_cmp = cmp ? cmp : cmp_addr;
    hdl->dh_hash = hash ? hash : hash_addr;
    return (hdl);
}

/*
 * Get a value from the hash. Null is returned if the key cannot be
 * found.
 */
void *
dict_get(dict_hdl_t *hdl, const void *key)
{
    uint64_t i;
    dict_bucket_t *bucket;

    i = (*hdl->dh_hash)(key)%hdl->dh_size;
    for (bucket = hdl->dh_buckets[i]; bucket != NULL;
        bucket = bucket->db_next)
        if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
            break;
    return (bucket ? bucket->db_value : NULL);
}

/*
 * Put an entry into the hash. Null is returned if this key was not
 * already present, otherwise the previous value is returned.
 */
void *
dict_put(dict_hdl_t *hdl, const void *key, void *value)
{
    uint64_t i;
    dict_bucket_t *bucket;
    void *prev = NULL;

    i = (*hdl->dh_hash)(key)%hdl->dh_size;
    for (bucket = hdl->dh_buckets[i]; bucket != NULL;
        bucket = bucket->db_next)
        if ((*hdl->dh_cmp)(key, bucket->db_key) == 0)
            break;
    if (bucket) {
        prev = bucket->db_value;
    } else {
        bucket = malloc(sizeof (dict_bucket_t));
        bucket->db_key = key;
        bucket->db_next = hdl->dh_buckets[i];
        hdl->dh_buckets[i] = bucket;
        hdl->dh_length++;
    }
    hdl->dh_change++;
    bucket->db_value = value;
    return (prev);
}

/*
 * Remove the key/value from the dictionary. The value is returned if
 * the key is found. NULL is returned if the key cannot be located.
 */
void *
dict_remove(dict_hdl_t *hdl, const void *key)
{
    uint64_t i;
    dict_bucket_t   **pbucket;

    hdl->dh_change++;
    i = (*hdl->dh_hash)(key)%hdl->dh_size;

    for (pbucket = &hdl->dh_buckets[i]; *pbucket != NULL;
        pbucket = &(*pbucket)->db_next) {
        if ((*hdl->dh_cmp)(key, (*pbucket)->db_key) == 0) {
            dict_bucket_t *bucket = *pbucket;
            void *value = bucket->db_value;

            *pbucket = bucket->db_next;
            free(bucket);
            hdl->dh_length--;
            return (value);
        }
    }
    return (NULL);
}

/*
 * For all entries in the dictionary call the user supplied function
 * (apply) with the key, value and user supplied data. If the
 * dictionary is modifed while this function is executing, then the
 * function will fail with an assertion about table modifcation.
 */
void
dict_map(dict_hdl_t *hdl, void (*apply)(const void *, void **, void *),
    void *cl)
{
    uint64_t i;
    dict_bucket_t *bucket = NULL;
    uint64_t change_stamp = hdl->dh_change;

    for (i = 0; i < hdl->dh_size; i++) {
        for (bucket = hdl->dh_buckets[i]; bucket != NULL;
            bucket = bucket->db_next) {
            apply(bucket->db_key, &bucket->db_value, cl);
            if (hdl->dh_change != change_stamp)
                assert(!"table modified illegally");
        }
    }
}