path: root/tools/lib/hash_table.h

/* $Id: hash_table.h,v 1.1 2004/03/30 16:21:26 mjw Exp $ */
/*
 * Copyright (C) 2001 - 2004 Mike Wray <mike.wray@hp.com>
 *
 * This library is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef _XEN_LIB_HASH_TABLE_H_
#define _XEN_LIB_HASH_TABLE_H_

#include "iostream.h"

typedef unsigned long Hashcode;

/** Type used to pass parameters to table functions. */
typedef union TableArg {
    unsigned long ul;
    void *ptr;
} TableArg;

/** An entry in a bucket list. */
typedef struct HTEntry {
    /** Hashcode of the entry's key. */
    Hashcode hashcode;
    /** Identifier for this entry in the table. */
    int index;
    /** The key for this entry. */
    void *key;
    /** The value in this entry. */
    void *value;
    /** The next entry in the list. */
    struct HTEntry *next;
} HTEntry;

/** A bucket in a rule table. */
typedef struct HTBucket {
    /** Number of entries in the bucket. */
    int count;
    /** First entry in the bucket (may be null). */
    HTEntry *head;
} HTBucket;

/** Default number of buckets in a hash table.
 * You want enough buckets so the lists in the buckets will typically be short.
 * It's a good idea if this is prime, since that will help to spread hashcodes
 * around the table.
 */
//#define HT_BUCKETS_N 1
//#define HT_BUCKETS_N 3
//#define HT_BUCKETS_N 7
//#define HT_BUCKETS_N 17
//#define HT_BUCKETS_N 97
//#define HT_BUCKETS_N 211
//#define HT_BUCKETS_N 401
#define HT_BUCKETS_N 1021

typedef struct HashTable HashTable;

/** Type for a function used to select table entries. */
typedef int TableTestFn(TableArg arg, HashTable *table, HTEntry *entry);

/** Type for a function to map over table entries. */
typedef int TableMapFn(TableArg arg, HashTable *table, HTEntry *entry);

/** Type for a function to free table entries. */
typedef void TableFreeFn(HashTable *table, HTEntry *entry);

/** Type for a function to hash table keys. */
typedef Hashcode TableHashFn(void *key);

/** Type for a function to test table keys for equality. */
typedef int TableEqualFn(void *key1, void *key2);

/** Type for a function to order table entries. */
typedef int TableOrderFn(HTEntry *e1, HTEntry *e2);

/** General hash table.
 * A hash table with a list in each bucket.
 * Functions can be supplied for freeing entries, hashing keys, and comparing keys.
 * These all default to 0, when default behaviour treating keys as integers is used.
 */
struct HashTable {
    /** Flag indicating whether the table has been initialised. */
    int init_done;
    /** Next value for the id field in inserted rules. */
    unsigned long next_id;
    /** Number of buckets in the bucket array. */
    int buckets_n;
    /** Array of buckets, each with its own list. */
    HTBucket *buckets;
    /** Number of entries in the table. */
    int entry_count;
    /** Function to free keys and values in entries. */
    TableFreeFn *entry_free_fn;
    /** Function to hash keys. */
    TableHashFn *key_hash_fn;
    /** Function to compare keys for equality. */
    TableEqualFn *key_equal_fn;
    /** Place for the user of the table to hang extra data. */
    void *user_data;
};

extern HashTable *HashTable_new(int bucket_n);
extern void HashTable_free(HashTable *table);
extern HTEntry * HTEntry_new(Hashcode hashcode, void *key, void *value);
extern void HTEntry_free(HTEntry *entry);
extern int HashTable_set_bucket_n(HashTable *table, int bucket_n);
extern void HashTable_clear(HashTable *table);
extern HTEntry * HashTable_add_entry(HashTable *table, Hashcode hashcode, void *key, void *value);
extern HTEntry * HashTable_get_entry(HashTable *table, void *key);
extern HTEntry * HashTable_add(HashTable *table, void *key, void *value);
extern void * HashTable_get(HashTable *table, void *key);
extern int HashTable_remove(HashTable *table, void *key);
extern HTEntry * HashTable_find_entry(HashTable *table, Hashcode hashcode,
                                      TableTestFn *test_fn, TableArg arg);
extern int HashTable_remove_entry(HashTable *table, Hashcode hashcode,
                                   TableTestFn *test_fn, TableArg arg);
//extern int HashTable_map(HashTable *table, TableMapFn *map_fn, TableArg arg);
extern void HashTable_print(HashTable *table, IOStream *out);
extern int HashTable_set_buckets_n(HashTable *table, int buckets_n);
extern int HashTable_adjust(HashTable *table, int buckets_min);
extern void pseudo_des(unsigned long *pleft, unsigned long *pright);
extern Hashcode hash_string(char *s);

extern int HashTable_order_bucket(HashTable *table, Hashcode hashcode, TableOrderFn *order);

/** Control whether to use hashing based on DES or simple
 * hashing. DES hashing is `more random' but much more expensive.
 */
#define HASH_PSEUDO_DES 0

/** Hash a long using a quick and dirty linear congruential random number generator.
 *  See `Numerical Recipes in C', Chapter 7, "An Even Quicker Generator".
 *
 * @param a value to hash
 * @return hashed input
 */
static inline unsigned long lcrng_hash(unsigned long a){
    return (1664525L * a + 1013904223L);
}

/** Hash an unsigned long.
 *
 * @param a input to hash
 * @return hashcode
 */
static inline Hashcode hash_ul(unsigned long a){
#if HASH_PSEUDO_DES
    unsigned long left = a;
    unsigned long right = 0L;
    pseudo_des(&left, &right);
    return right;
#else
    a = lcrng_hash(a);
    a = lcrng_hash(a);
    return a;
#endif
}

/** Hash two unsigned longs together.
 *
 * @param a input to hash
 * @param b input to hash
 * @return hashcode
 */
static inline Hashcode hash_2ul(unsigned long a, unsigned long b){
#if HASH_PSEUDO_DES
    unsigned long left = a;
    unsigned long right = b;
    pseudo_des(&left, &right);
    return right;
#else
    a = lcrng_hash(a);
    a ^= b;
    a = lcrng_hash(a);
    return a;
#endif
}

/** Hash a hashcode and an unsigned long together.
 *
 * @param a input hashcode
 * @param b input to hash
 * @return hashcode
 */
static inline Hashcode hash_hul(Hashcode a, unsigned long b){
#if HASH_PSEUDO_DES
    unsigned long left = a;
    unsigned long right = b;
    pseudo_des(&left, &right);
    return right;
#else
    a ^= b;
    a = lcrng_hash(a);
    return a;
#endif
}

/** Macro to declare variables for HashTable_for_each() to use.
 *
 * @param entry variable that is set to entries in the table
 */
#define HashTable_for_decl(entry) \
  HashTable *_var_table; \
  HTBucket *_var_bucket; \
  HTBucket *_var_end; \
  HTEntry *_var_next; \
  HTEntry *entry

/** Macro to iterate over the entries in a hashtable.
 * Must be in a scope where HashTable_for_decl() has been used to declare
 * variables for it to use.
 * The variable 'entry' is iterated over entries in the table.
 * The code produced is syntactically a loop, so it must be followed by
 * a loop body, typically some statements in braces:
 * HashTable_for_each(entry, table){ ...loop body... }
 *
 * HashTable_for_each() and HashTable_for_decl() cannot be used for nested
 * loops as variables will clash.
 *
 * @note The simplest way to code a direct loop over the entries in a hashtable
 * is to use a loop over the buckets, with a nested loop over the entries
 * in a bucket. Using this approach in a macro means the macro contains
 * an opening brace, and calls to it must be followed by 2 braces!
 * To avoid this the code has been restructured so that it is a for loop.
 * So that statements could be used in the test expression of the for loop,
 * we have used the gcc statement expression extension ({ ... }).
 *
 * @param entry variable to iterate over the entries
 * @param table to iterate over (non-null)
 */
#define HashTable_for_each(entry, table) \
  _var_table = table; \
  _var_bucket = _var_table->buckets; \
  _var_end = _var_bucket + _var_table->buckets_n; \
  for(entry=0, _var_next=0; \
      ({ if(_var_next){ \
             entry = _var_next; \
             _var_next = entry->next; \
          } else { \
             while(_var_bucket < _var_end){ \
                 entry = _var_bucket->head; \
                 _var_bucket++; \
                 if(entry){ \
                      _var_next = entry->next; \
                      break; \
                 } \
             } \
          }; \
         entry; }); \
      entry = _var_next )

/** Map a function over the entries in a table.
 * Mapping stops when the function returns a non-zero value.
 * Uses the gcc statement expression extension ({ ... }).
 *
 * @param table to map over
 * @param fn function to apply to entries
 * @param arg first argument to call the function with
 * @return 0 if fn always returned 0, first non-zero value otherwise
 */
#define HashTable_map(table, fn, arg) \
  ({ HashTable_for_decl(_var_entry); \
    TableArg _var_arg = arg; \
    int _var_value = 0; \
    HashTable_for_each(_var_entry, table){ \
        if((_var_value = fn(_var_arg, _var_table, _var_entry))) break; \
    } \
    _var_value; })

/** Cast x to the type for a key or value in a hash table.
 * This avoids compiler warnings when using short integers
 * as keys or values (especially on 64-bit platforms).
 */
#define HKEY(x) ((void*)(unsigned long)(x))

/** Cast x from the type for a key or value in a hash table.
 * to an unsigned long. This avoids compiler warnings when using
 * short integers as keys or values (especially on 64-bit platforms).
 */
#define HVAL(x) ((unsigned long)(x))

#endif /* !_XEN_LIB_HASH_TABLE_H_ */