import less(1)

[unleashed/tickless.git] / usr / src / lib / 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");
                }
        }
}