nexmon – Rev 1

?pathlinks?

Blame – Last modification – View Log – Download

/*
 * Copyright 2008-2009 Katholieke Universiteit Leuven
 *
 * Use of this software is governed by the GNU LGPLv2.1 license
 *
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
 */

#include <stdlib.h>
#include <strings.h>
#include <isl/hash.h>
#include <isl/ctx.h>

uint32_t isl_hash_string(uint32_t hash, const char *s)
{
        for (; *s; s++)
                isl_hash_byte(hash, *s);
        return hash;
}

uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
{
        int i;
        const char *s = p;
        for (i = 0; i < len; ++i)
                isl_hash_byte(hash, s[i]);
        return hash;
}

static unsigned int round_up(unsigned int v)
{
        int old_v = v;

        while (v) {
                old_v = v;
                v ^= v & -v;
        }
        return old_v << 1;
}

int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
                        int min_size)
{
        size_t size;

        if (!table)
                return -1;

        if (min_size < 2)
                min_size = 2;
        table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
        table->n = 0;

        size = 1 << table->bits;
        table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
                                          size);
        if (!table->entries)
                return -1;

        return 0;
}

static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table,
                        int (*eq)(const void *entry, const void *val))
{
        size_t old_size, size;
        struct isl_hash_table_entry *entries;
        uint32_t h;

        entries = table->entries;
        old_size = 1 << table->bits;
        size = 2 * old_size;
        table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
                                          size);
        if (!table->entries) {
                table->entries = entries;
                return -1;
        }

        table->bits++;

        for (h = 0; h < old_size; ++h) {
                struct isl_hash_table_entry *entry;

                if (!entries[h].data)
                        continue;

                entry = isl_hash_table_find(ctx, table, entries[h].hash,
                                            eq, entries[h].data, 1);
                if (!entry) {
                        table->bits--;
                        free(table->entries);
                        table->entries = entries;
                        return -1;
                }

                *entry = entries[h];
        }

        free(entries);

        return 0;
}

struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
{
        struct isl_hash_table *table = NULL;

        table = isl_alloc_type(ctx, struct isl_hash_table);
        if (isl_hash_table_init(ctx, table, min_size))
                goto error;
        return table;
error:
        isl_hash_table_free(ctx, table);
        return NULL;
}

void isl_hash_table_clear(struct isl_hash_table *table)
{
        if (!table)
                return;
        free(table->entries);
}

void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
{
        if (!table)
                return;
        isl_hash_table_clear(table);
        free(table);
}

struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
                                struct isl_hash_table *table,
                                uint32_t key_hash,
                                int (*eq)(const void *entry, const void *val),
                                const void *val, int reserve)
{
        size_t size;
        uint32_t h, key_bits;

        key_bits = isl_hash_bits(key_hash, table->bits);
        size = 1 << table->bits;
        for (h = key_bits; table->entries[h].data; h = (h+1) % size)
                if (table->entries[h].hash == key_hash &&
                    eq(table->entries[h].data, val))
                        return &table->entries[h];

        if (!reserve)
                return NULL;

        if (4 * table->n >= 3 * size) {
                if (grow_table(ctx, table, eq) < 0)
                        return NULL;
                return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
        }

        table->n++;
        table->entries[h].hash = key_hash;

        return &table->entries[h];
}

int isl_hash_table_foreach(struct isl_ctx *ctx,
                                struct isl_hash_table *table,
                                int (*fn)(void **entry, void *user), void *user)
{
        size_t size;
        uint32_t h;

        size = 1 << table->bits;
        for (h = 0; h < size; ++ h)
                if (table->entries[h].data &&
                    fn(&table->entries[h].data, user) < 0)
                        return -1;
        
        return 0;
}

void isl_hash_table_remove(struct isl_ctx *ctx,
                                struct isl_hash_table *table,
                                struct isl_hash_table_entry *entry)
{
        int h, h2;
        size_t size;

        if (!table || !entry)
                return;

        size = 1 << table->bits;
        h = entry - table->entries;
        isl_assert(ctx, h >= 0 && h < size, return);

        for (h2 = h+1; table->entries[h2 % size].data; h2++) {
                uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
                                                table->bits);
                uint32_t offset = (size + bits - (h+1)) % size;
                if (offset <= h2 - (h+1))
                        continue;
                *entry = table->entries[h2 % size];
                h = h2;
                entry = &table->entries[h % size];
        }

        entry->hash = 0;
        entry->data = NULL;
        table->n--;
}