kxld_dict.c   [plain text]

/*
 * Copyright (c) 2007-2008 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 * 
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */
#include <string.h>
#include <sys/types.h>

#define DEBUG_ASSERT_COMPONENT_NAME_STRING "kxld"
#include <AssertMacros.h>

#include "kxld_dict.h"
#include "kxld_util.h"

/*******************************************************************************
* Types and macros
*******************************************************************************/

/* Ratio of num_entries:num_buckets that will cause a resize */
#define RESIZE_NUMER 7
#define RESIZE_DENOM 10
#define RESIZE_THRESHOLD(x) (((x)*RESIZE_NUMER) / RESIZE_DENOM)
#define MIN_BUCKETS(x) (((x)*RESIZE_DENOM) / RESIZE_NUMER) 

/* Selected for good scaling qualities when resizing dictionary
 * ... see: http://www.concentric.net/~ttwang/tech/hashsize.htm
 */
#define DEFAULT_DICT_SIZE 89

typedef struct dict_entry DictEntry;

typedef enum {
    EMPTY = 0,
    USED = 1,
    DELETED = 2
} DictEntryState;

struct dict_entry {
    const void *key;
    void *value;
    DictEntryState state;
};

/*******************************************************************************
* Function prototypes
*******************************************************************************/

static kern_return_t get_locate_index(const KXLDDict *dict, const void *key, 
    u_int *idx);
static kern_return_t get_insert_index(const KXLDDict *dict, const void *key, 
    u_int *idx);
static kern_return_t resize_dict(KXLDDict *dict);

/*******************************************************************************
*******************************************************************************/
kern_return_t
kxld_dict_init(KXLDDict * dict, kxld_dict_hash hash, kxld_dict_cmp cmp, 
    u_int num_entries) 
{
    kern_return_t rval = KERN_FAILURE;
    u_int min_buckets = MIN_BUCKETS(num_entries);
    u_int num_buckets = DEFAULT_DICT_SIZE;
    
    check(dict);
    check(hash);
    check(cmp);
    
    /* We want the number of allocated buckets to be at least twice that of the 
     * number to be inserted.
     */
    while (min_buckets > num_buckets) {
        num_buckets *= 2;
        num_buckets++;
    }
    
    /* Allocate enough buckets for the anticipated number of entries */
    rval = kxld_array_init(&dict->buckets, sizeof(DictEntry), num_buckets);
    require_noerr(rval, finish);
    
    /* Initialize */
    dict->hash = hash;
    dict->cmp = cmp;
    dict->num_entries = 0;
    dict->resize_threshold = RESIZE_THRESHOLD(num_buckets);
    
    rval = KERN_SUCCESS;
    
finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
void
kxld_dict_clear(KXLDDict *dict)
{
    check(dict);

    dict->hash = NULL;
    dict->cmp = NULL;
    dict->num_entries = 0;
    dict->resize_threshold = 0;
    kxld_array_clear(&dict->buckets);
    kxld_array_clear(&dict->resize_buckets);
}

/*******************************************************************************
*******************************************************************************/
void
kxld_dict_iterator_init(KXLDDictIterator *iter, const KXLDDict *dict)
{
    check(iter);
    check(dict);

    iter->idx = 0;
    iter->dict = dict;
}

/*******************************************************************************
*******************************************************************************/
void
kxld_dict_deinit(KXLDDict *dict)
{
    check(dict);
    
    kxld_array_deinit(&dict->buckets);
    kxld_array_deinit(&dict->resize_buckets);
}

/*******************************************************************************
*******************************************************************************/
u_int
kxld_dict_get_num_entries(const KXLDDict *dict)
{
    check(dict);

    return dict->num_entries;
}

/*******************************************************************************
*******************************************************************************/
void *
kxld_dict_find(const KXLDDict *dict, const void *key)
{
    kern_return_t rval = KERN_FAILURE;
    DictEntry *entry = NULL;
    u_int idx = 0;
   
    check(dict);
    check(key);
   
    rval = get_locate_index(dict, key, &idx);
    if (rval) return NULL; 

    entry = kxld_array_get_item(&dict->buckets, idx);
    
    return entry->value;
}

/*******************************************************************************
* This dictionary uses linear probing, which means that when there is a
* collision, we just walk along the buckets until a free bucket shows up.
* A consequence of this is that when looking up an item, items that lie between
* its hash value and its actual bucket may have been deleted since it was
* inserted.  Thus, we should only stop a lookup when we've wrapped around the
* dictionary or encountered an EMPTY bucket.
********************************************************************************/
static kern_return_t
get_locate_index(const KXLDDict *dict, const void *key, u_int *_idx)
{
    kern_return_t rval = KERN_FAILURE;
    DictEntry *entry = NULL;
    u_int base, idx;

    base = idx = dict->hash(dict, key);
    
    /* Iterate until we match the key, wrap, or hit an empty bucket */
    entry = kxld_array_get_item(&dict->buckets, idx);
    while (!dict->cmp(entry->key, key)) {
        if (entry->state == EMPTY) goto finish;

        idx = (idx + 1) % dict->buckets.nitems;
        if (idx == base) goto finish;

        entry = kxld_array_get_item(&dict->buckets, idx);
    }

    check(idx < dict->buckets.nitems);

    *_idx = idx;
    rval = KERN_SUCCESS;

finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
kern_return_t
kxld_dict_insert(KXLDDict *dict, const void *key, void *value)
{
    kern_return_t rval = KERN_FAILURE;
    DictEntry *entry = NULL;
    u_int idx = 0;
    
    check(dict);
    check(key);
    check(value);
    
    /* Resize if we are greater than the capacity threshold.
     * Note: this is expensive, but the dictionary can be sized correctly at
     * construction to avoid ever having to do this.
     */
    while (dict->num_entries > dict->resize_threshold) { 
        rval = resize_dict(dict); 
        require_noerr(rval, finish);
    }
    
    /* If this function returns FULL after we've already resized appropriately
     * something is very wrong and we should return an error.
     */
    rval = get_insert_index(dict, key, &idx);
    require_noerr(rval, finish);
    
    /* Insert the new key-value pair into the bucket, but only count it as a 
     * new entry if we are not overwriting an existing entry.
     */
    entry = kxld_array_get_item(&dict->buckets, idx);
    if (entry->state != USED) {
        dict->num_entries++;
        entry->key = key;
        entry->state = USED;
    }
    entry->value = value;

    rval = KERN_SUCCESS;
    
finish:
    return rval;
}

/*******************************************************************************
* Increases the hash table's capacity by 2N+1.  Uses dictionary API.  Not
* fast; just correct.
*******************************************************************************/
static kern_return_t
resize_dict(KXLDDict *dict)
{
    kern_return_t rval = KERN_FAILURE;
    KXLDArray tmparray;
    DictEntry *entry = NULL;
    u_int nbuckets = (dict->buckets.nitems * 2 + 1);
    u_int i = 0;

    check(dict);

    /* Initialize a new set of buckets to hold more entries */
    rval = kxld_array_init(&dict->resize_buckets, sizeof(DictEntry), nbuckets);
    require_noerr(rval, finish);

    /* Swap the new buckets with the old buckets */
    tmparray = dict->buckets;
    dict->buckets = dict->resize_buckets;
    dict->resize_buckets = tmparray; 

    /* Reset dictionary parameters */
    dict->num_entries = 0;
    dict->resize_threshold = RESIZE_THRESHOLD(dict->buckets.nitems);

    /* Rehash all of the entries */
    for (i = 0; i < dict->resize_buckets.nitems; ++i) {
        entry = kxld_array_get_item(&dict->resize_buckets, i);
        if (entry->state == USED) {
            rval = kxld_dict_insert(dict, entry->key, entry->value);
            require_noerr(rval, finish);
        }
    }

    /* Clear the old buckets */
    kxld_array_clear(&dict->resize_buckets);

    rval = KERN_SUCCESS;
    
finish:
    return rval;
}

/*******************************************************************************
* Simple function to find the first empty cell
*******************************************************************************/
static kern_return_t
get_insert_index(const KXLDDict *dict, const void *key, u_int *r_index)
{
    kern_return_t rval = KERN_FAILURE;
    DictEntry *entry = NULL;
    u_int base, idx;

    base = idx = dict->hash(dict, key);
    
    /* Iterate through the buckets until we find an EMPTY bucket, a DELETED
     * bucket, or a key match.
     */
    entry = kxld_array_get_item(&dict->buckets, idx);
    while (entry->state == USED && !dict->cmp(entry->key, key)) {
        idx = (idx + 1) % dict->buckets.nitems;
        require_action(base != idx, finish, rval=KERN_FAILURE);
        entry = kxld_array_get_item(&dict->buckets, idx);
    }
    
    *r_index = idx;
    rval = KERN_SUCCESS;
    
finish:
    return rval;
}

/*******************************************************************************
*******************************************************************************/
void
kxld_dict_remove(KXLDDict *dict, const void *key, void **value)
{
    kern_return_t rval = KERN_FAILURE;
    DictEntry *entry = NULL;
    u_int idx = 0;
   
    check(dict);
    check(key);
    
    /* Find the item */
    rval = get_locate_index(dict, key, &idx);
    if (rval) {
        if (value) *value = NULL;
        return;
    }

    entry = kxld_array_get_item(&dict->buckets, idx);

    /* Save the value if requested */    
    if (value) *value = entry->value;

    /* Delete the item from the dictionary */
    entry->key = NULL;
    entry->value = NULL;
    entry->state = DELETED;
    dict->num_entries--;
}

/*******************************************************************************
*******************************************************************************/
void 
kxld_dict_iterator_get_next(KXLDDictIterator *iter, const void **key, 
    void **value)
{
    DictEntry *entry = NULL;

    check(iter);
    check(key);
    check(value);

    *key = NULL;
    *value = NULL;

    /* Walk over the dictionary looking for USED buckets */
    for (; iter->idx < iter->dict->buckets.nitems; ++(iter->idx)) {
        entry = kxld_array_get_item(&iter->dict->buckets, iter->idx);
        if (entry->state == USED) {
            *key = entry->key;
            *value = entry->value;
            ++(iter->idx);
            break;
        }
    }
}

/*******************************************************************************
*******************************************************************************/
void 
kxld_dict_iterator_reset(KXLDDictIterator *iter)
{
    iter->idx = 0;
}

/*******************************************************************************
* This is Daniel Bernstein's hash algorithm from comp.lang.c
* It's fast and distributes well.  Returns an idx into the symbol hash table.
* NOTE: Will not check for a valid pointer - performance
*******************************************************************************/
u_int
kxld_dict_string_hash(const KXLDDict *dict, const void *_key) 
{
    const char *key = _key;
    u_int c = 0;
    u_int hash_val = 5381;

    check(dict);
    check(_key);

    while ((c = *key++)) {
        /* hash(i) = hash(i-1) *33 ^ name[i] */
        hash_val = ((hash_val << 5) + hash_val) ^ c;    
    }
    
    return (hash_val % dict->buckets.nitems);
}

u_int
kxld_dict_uint32_hash(const KXLDDict *dict, const void *_key)
{
    uint32_t key = *(const uint32_t *) _key;

    check(_key);

    return (u_int) (key % dict->buckets.nitems);
}

u_int
kxld_dict_kxldaddr_hash(const KXLDDict *dict, const void *_key)
{
    kxld_addr_t key = *(const kxld_addr_t *) _key;

    check(_key);

    return (u_int) (key % dict->buckets.nitems);
}

u_int
kxld_dict_string_cmp(const void *key1, const void *key2)
{
    return streq(key1, key2);
}

u_int
kxld_dict_uint32_cmp(const void *key1, const void *key2)
{
    const uint32_t *a = key1;
    const uint32_t *b = key2;

    return (a && b && (*a == *b));
}

u_int
kxld_dict_kxldaddr_cmp(const void *key1, const void *key2)
{
    const kxld_addr_t *a = key1;
    const kxld_addr_t *b = key2;

    return (a && b && (*a == *b));
}