hash.c

xorp源码hg

/*
 * Copyright (c) 2000, 2001 by Martin C. Shepherd.
 * 
 * All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, and/or sell copies of the Software, and to permit persons
 * to whom the Software is furnished to do so, provided that the above
 * copyright notice(s) and this permission notice appear in all copies of
 * the Software and that both the above copyright notice(s) and this
 * permission notice appear in supporting documentation.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
 * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
 * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
 * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
 * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 * 
 * Except as contained in this notice, the name of a copyright holder
 * shall not be used in advertising or otherwise to promote the sale, use
 * or other dealings in this Software without prior written authorization
 * of the copyright holder.
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#include "hash.h"
#include "strngmem.h"
#include "freelist.h"

/*
 * The following container object contains free-lists to be used
 * for allocation of HashTable containers and nodes.
 */
struct HashMemory {
  FreeList *hash_memory;    /* HashTable free-list */
  FreeList *node_memory;    /* HashNode free-list */
  StringMem *string_memory; /* Memory used to allocate hash strings */
};

/*
 * Define a hash symbol-table entry.
 * See symbol.h for the definition of the Symbol container type.
 */
typedef struct HashNode HashNode;
struct HashNode {
  Symbol symbol;       /* The symbol stored in the hash-entry */
  HashNode *next;      /* The next hash-table entry in a bucket list */
};

/*
 * Each hash-table bucket contains a linked list of entries that
 * hash to the same bucket.
 */
typedef struct {
  HashNode *head;   /* The head of the bucket hash-node list */
  int count;        /* The number of entries in the list */
} HashBucket;

/*
 * Set the max length of the error-reporting string. There is no point
 * in this being longer than the width of a typical terminal window.
 * In composing error messages, I have assumed that this number is
 * at least 80, so you don't decrease it below this number.
 */
#define ERRLEN 200

/*
 * A hash-table consists of 'size' hash buckets.
 * Note that the HashTable typedef for this struct is contained in hash.h.
 */
struct HashTable {
  char errmsg[ERRLEN+1];/* Error-report buffer */
  HashMemory *mem;      /* HashTable free-list */
  int internal_mem;     /* True if 'mem' was allocated by _new_HashTable() */
  int case_sensitive;   /* True if case is significant in lookup keys */
  int size;             /* The number of hash buckets */
  HashBucket *bucket;   /* An array of 'size' hash buckets */
  int (*keycmp)(const char *, const char *); /* Key comparison function */
  void *app_data;       /* Application-provided data */
  HASH_DEL_FN(*del_fn); /* Application-provided 'app_data' destructor */
};

static HashNode *_del_HashNode(HashTable *hash, HashNode *node);
static HashNode *_new_HashNode(HashTable *hash, const char *name, int code,
		      void (*fn)(void), void *data, SYM_DEL_FN(*del_fn));
static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket,
				const char *name, HashNode **prev);
static HashBucket *_find_HashBucket(HashTable *hash, const char *name);
static int _ht_lower_strcmp(const char *node_key, const char *look_key);
static int _ht_strcmp(const char *node_key, const char *look_key);

/*.......................................................................
 * Allocate a free-list for use in allocating hash tables and their nodes.
 *
 * Input:
 *  list_count    int    The number of HashTable containers per free-list
 *                       block.
 *  node_count    int    The number of HashTable nodes per free-list block.
 * Output:
 *  return HashMemory *  The new free-list for use in allocating hash tables
 *                       and their nodes.
 */
HashMemory *_new_HashMemory(int hash_count, int node_count)
{
  HashMemory *mem;
/*
 * Allocate the free-list container.
 */
  mem = (HashMemory *) malloc(sizeof(HashMemory));
  if(!mem) {
    fprintf(stderr, "_new_HashMemory: Insufficient memory.\n");
    return NULL;
  };
/*
 * Initialize the container at least up to the point at which it can
 * safely be passed to _del_HashMemory().
 */
  mem->hash_memory = NULL;
  mem->node_memory = NULL;
  mem->string_memory = NULL;
/*
 * Allocate the two free-lists.
 */
  mem->hash_memory = _new_FreeList("_new_HashMemory", sizeof(HashTable),
				  hash_count);
  if(!mem->hash_memory)
    return _del_HashMemory(mem, 1);
  mem->node_memory = _new_FreeList("_new_HashMemory", sizeof(HashNode),
				  node_count);
  if(!mem->node_memory)
    return _del_HashMemory(mem, 1);
  mem->string_memory = _new_StringMem("_new_HashMemory", 64);
  if(!mem->string_memory)
    return _del_HashMemory(mem, 1);
/*
 * Return the free-list container.
 */
  return mem;
}

/*.......................................................................
 * Delete a HashTable free-list. An error will be displayed if the list is
 * still in use and the deletion will be aborted.
 *
 * Input:
 *  mem    HashMemory *  The free-list container to be deleted.
 *  force         int    If force==0 then _del_HashMemory() will complain
 *                        and refuse to delete the free-list if any
 *                        of nodes have not been returned to the free-list.
 *                       If force!=0 then _del_HashMemory() will not check
 *                        whether any nodes are still in use and will
 *                        always delete the list.
 * Output:
 *  return HashMemory *  Always NULL (even if the memory could not be
 *                       deleted).
 */
HashMemory *_del_HashMemory(HashMemory *mem, int force)
{
  const char *caller = "_del_HashMemory";
  if(mem) {
    if(!force && (_busy_FreeListNodes(mem->hash_memory) > 0 ||
		  _busy_FreeListNodes(mem->node_memory) > 0)) {
      fprintf(stderr, "%s: Free-list in use.\n", caller);
      return NULL;
    };
    mem->hash_memory = _del_FreeList(caller, mem->hash_memory, force);
    mem->node_memory = _del_FreeList(caller, mem->node_memory, force);
    mem->string_memory = _del_StringMem(caller, mem->string_memory, force);
    free(mem);
  };
  return NULL;
}

/*.......................................................................
 * Create a new hash table.
 *
 * Input:
 *  mem       HashMemory *  An optional free-list for use in allocating
 *                          HashTable containers and nodes. See explanation
 *                          in hash.h. If you are going to allocate more
 *                          than one hash table, then it will be more
 *                          efficient to allocate a single free-list for
 *                          all of them than to force each hash table
 *                          to allocate its own private free-list.
 *  size             int    The size of the hash table. Best performance
 *                          will be acheived if this is a prime number.
 *  hcase       HashCase    Specify how symbol case is considered when
 *                          looking up symbols, from:
 *                           IGNORE_CASE - Upper and lower case versions
 *                                         of a letter are treated as
 *                                         being identical.
 *                           HONOUR_CASE - Upper and lower case versions
 *                                         of a letter are treated as
 *                                         being distinct.
 *                          characters in a lookup name is significant.
 *  app_data        void *  Optional application data to be registered
 *                          to the table. This is presented to user
 *                          provided SYM_DEL_FN() symbol destructors along
 *                          with the symbol data.
 *  del_fn() HASH_DEL_FN(*) If you want app_data to be free'd when the
 *                          hash-table is destroyed, register a suitable
 *                          destructor function here.
 * Output:
 *  return HashTable *  The new hash table, or NULL on error.
 */
HashTable *_new_HashTable(HashMemory *mem, int size, HashCase hcase,
			 void *app_data, HASH_DEL_FN(*del_fn))
{
  HashTable *hash;         /* The table to be returned */
  int allocate_mem = !mem; /* True if mem should be internally allocated */
  int i;
/*
 * Check arguments.
 */
  if(size <= 0) {
    fprintf(stderr, "_new_HashTable: Illegal table size (%d).\n", size);
    return NULL;
  };
/*
 * Allocate an internal free-list?
 */
  if(allocate_mem) {
    mem = _new_HashMemory(1, 100);
    if(!mem)
      return NULL;
  };
/*
 * Allocate the container.
 */
  hash = (HashTable *) _new_FreeListNode(mem->hash_memory);
  if(!hash) {
    fprintf(stderr, "_new_HashTable: Insufficient memory.\n");
    if(allocate_mem)
      mem = _del_HashMemory(mem, 1);
    return NULL;
  };
/*
 * Before attempting any operation that might fail, initialize
 * the container at least up to the point at which it can safely
 * be passed to _del_HashTable().
 */
  hash->errmsg[0] = '\0';
  hash->mem = mem;
  hash->internal_mem = allocate_mem;
  hash->case_sensitive = hcase==HONOUR_CASE;
  hash->size = size;
  hash->bucket = NULL;
  hash->keycmp = hash->case_sensitive ? _ht_strcmp : _ht_lower_strcmp;
  hash->app_data = app_data;
  hash->del_fn = del_fn;
/*
 * Allocate the array of 'size' hash buckets.
 */
  hash->bucket = (HashBucket *) malloc(sizeof(HashBucket) * size);
  if(!hash->bucket) {
    fprintf(stderr, "_new_HashTable: Insufficient memory for %d buckets.\n",
	    size);
    return _del_HashTable(hash);
  };
/*
 * Initialize the bucket array.
 */
  for(i=0; i<size; i++) {
    HashBucket *b = hash->bucket + i;
    b->head = NULL;
    b->count = 0;
  };
/*
 * The table is ready for use - albeit currently empty.
 */
  return hash;
}

/*.......................................................................
 * Delete a hash-table.
 *
 * Input:
 *  hash   HashTable *  The hash table to be deleted.
 * Output:
 *  return HashTable *  The deleted hash table (always NULL).
 */
HashTable *_del_HashTable(HashTable *hash)
{
  if(hash) {
/*
 * Clear and delete the bucket array.
 */
    if(hash->bucket) {
      _clear_HashTable(hash);
      free(hash->bucket);
      hash->bucket = NULL;
    };
/*
 * Delete application data.
 */
    if(hash->del_fn)
      hash->del_fn(hash->app_data);
/*
 * If the hash table was allocated from an internal free-list, delete
 * it and the hash table by deleting the free-list. Otherwise just
 * return the hash-table to the external free-list.
 */
    if(hash->internal_mem)
      _del_HashMemory(hash->mem, 1);
    else
      hash = (HashTable *) _del_FreeListNode(hash->mem->hash_memory, hash);
  };
  return NULL;
}

/*.......................................................................
 * Create and install a new entry in a hash table. If an entry with the
 * same name already exists, replace its contents with the new data.
 *
 * Input:
 *  hash   HashTable *  The hash table to insert the symbol into.
 *  name  const char *  The name to tag the entry with.
 *  code         int    An application-specific code to be stored in
 *                      the entry.
 *  fn  void (*)(void)  An application-specific function to be stored
 *                      in the entry.
 *  data        void *  An application-specific pointer to data to be
 *                      associated with the entry, or NULL if not
 *                      relevant.
 *  del_fn SYM_DEL_FN(*) An optional destructor function. When the
 *                      symbol is deleted this function will be called
 *                      with the 'code' and 'data' arguments given
 *                      above. Any application data that was registered
 *                      to the table via the app_data argument of
 *                      _new_HashTable() will also be passed.
 * Output:
 *  return  HashNode *  The new entry, or NULL if there was insufficient
 *                      memory or the arguments were invalid.
 */
Symbol *_new_HashSymbol(HashTable *hash, const char *name, int code,
			void (*fn)(void), void *data, SYM_DEL_FN(*del_fn))
{
  HashBucket *bucket;  /* The hash-bucket associated with the name */
  HashNode *node;      /* The new node */
/*
 * Check arguments.
 */
  if(!hash || !name)
    return NULL;
/*
 * Get the hash bucket of the specified name.
 */
  bucket = _find_HashBucket(hash, name);
/*
 * See if a node with the same name already exists.
 */
  node = _find_HashNode(hash, bucket, name, NULL);
/*
 * If found, delete its contents by calling the user-supplied
 * destructor function, if provided.
 */
  if(node) {
    if(node->symbol.data && node->symbol.del_fn) {
      node->symbol.data = node->symbol.del_fn(hash->app_data, node->symbol.code,
					      node->symbol.data);
    };
/*
 * Allocate a new node if necessary.
 */