hash.c

xorp源码hg

  } else {
    node = _new_HashNode(hash, name, code, fn, data, del_fn);
    if(!node)
      return NULL;
  };
/*
 * Install the node at the head of the hash-bucket list.
 */
  node->next = bucket->head;
  bucket->head = node;
  bucket->count++;
  return &node->symbol;
}

/*.......................................................................
 * Remove and delete a given hash-table entry.
 *
 * Input:
 *  hash   HashTable *  The hash table to find the symbol in.
 *  name  const char *  The name of the entry.
 * Output:
 *  return  HashNode *  The deleted hash node (always NULL).
 */
Symbol *_del_HashSymbol(HashTable *hash, const char *name)
{
  if(hash && name) {
    HashBucket *bucket = _find_HashBucket(hash, name);
    HashNode *prev;   /* The node preceding the located node */
    HashNode *node = _find_HashNode(hash, bucket, name, &prev);
/*
 * Node found?
 */
    if(node) {
/*
 * Remove the node from the bucket list.
 */
      if(prev) {
	prev->next = node->next;
      } else {
	bucket->head = node->next;
      };
/*
 * Record the loss of a node.
 */
      bucket->count--;
/*
 * Delete the node.
 */
      (void) _del_HashNode(hash, node);
    };
  };
  return NULL;
}

/*.......................................................................
 * Look up a symbol in the hash table.
 *
 * Input:
 *  hash   HashTable *   The table to look up the string in.
 *  name  const char *   The name of the symbol to look up.
 * Output:
 *  return    Symbol *   The located hash-table symbol, or NULL if not
 *                       found.
 */
Symbol *_find_HashSymbol(HashTable *hash, const char *name)
{
  HashBucket *bucket;  /* The hash-table bucket associated with name[] */
  HashNode *node;      /* The hash-table node of the requested symbol */
/*
 * Check arguments.
 */
  if(!hash)
    return NULL;
/*
 * Nothing to lookup?
 */
  if(!name)
    return NULL;
/*
 * Hash the name to a hash-table bucket.
 */
  bucket = _find_HashBucket(hash, name);
/*
 * Find the bucket entry that exactly matches the name.
 */
  node = _find_HashNode(hash, bucket, name, NULL);
  if(!node)
    return NULL;
  return &node->symbol;
}

/*.......................................................................
 * Private function used to allocate a hash-table node.
 * The caller is responsible for checking that the specified symbol
 * is unique and for installing the returned entry in the table.
 *
 * Input:
 *  hash     HashTable *  The table to allocate the node for.
 *  name    const char *  The name of the new entry.
 *  code           int    A user-supplied context code.
 *  fn  void (*)(void)    A user-supplied function pointer.
 *  data          void *  A user-supplied data pointer.
 *  del_fn  SYM_DEL_FN(*) An optional 'data' destructor function.
 * Output:
 *  return    HashNode *  The new node, or NULL on error.
 */
static HashNode *_new_HashNode(HashTable *hash, const char *name, int code,
			      void (*fn)(void), void *data, SYM_DEL_FN(*del_fn))
{
  HashNode *node;  /* The new node */
/*
 * Allocate the new node from the free list.
 */
  node = (HashNode *) _new_FreeListNode(hash->mem->node_memory);
  if(!node)
    return NULL;
/*
 * Before attempting any operation that might fail, initialize the
 * contents of 'node' at least up to the point at which it can be
 * safely passed to _del_HashNode().
 */
  node->symbol.name = NULL;
  node->symbol.code = code;
  node->symbol.fn = fn;
  node->symbol.data = data;
  node->symbol.del_fn = del_fn;
  node->next = NULL;
/*
 * Allocate a copy of 'name'.
 */
  node->symbol.name = _new_StringMemString(hash->mem->string_memory,
					  strlen(name) + 1);
  if(!node->symbol.name)
    return _del_HashNode(hash, node);
/*
 * If character-case is insignificant in the current table, convert the
 * name to lower case while copying it.
 */
  if(hash->case_sensitive) {
    strcpy(node->symbol.name, name);
  } else {
    const char *src = name;
    char *dst = node->symbol.name;
    for( ; *src; src++,dst++)
      *dst = tolower((int)(unsigned char) *src);
    *dst = '\0';
  };
  return node;
}

/*.......................................................................
 * Private function used to delete a hash-table node.
 * The node must have been removed from its list before calling this
 * function.
 *
 * Input:
 *  hash   HashTable *  The table for which the node was originally
 *                      allocated.
 *  node    HashNode *  The node to be deleted.
 * Output:
 *  return  HashNode *  The deleted node (always NULL).
 */
static HashNode *_del_HashNode(HashTable *hash, HashNode *node)
{
  if(node) {
    node->symbol.name = _del_StringMemString(hash->mem->string_memory,
					    node->symbol.name);
/*
 * Call the user-supplied data-destructor if provided.
 */
    if(node->symbol.data && node->symbol.del_fn)
      node->symbol.data = node->symbol.del_fn(hash->app_data,
					      node->symbol.code,
					      node->symbol.data);
/*
 * Return the node to the free-list.
 */
    node->next = NULL;
    node = (HashNode *) _del_FreeListNode(hash->mem->node_memory, node);
  };
  return NULL;
}

/*.......................................................................
 * Private function to locate the hash bucket associated with a given
 * name.
 *
 * This uses a hash-function described in the dragon-book
 * ("Compilers - Principles, Techniques and Tools", by Aho, Sethi and
 *  Ullman; pub. Adison Wesley) page 435.
 *
 * Input:
 *  hash    HashTable *   The table to look up the string in.
 *  name   const char *   The name of the symbol to look up.
 * Output:
 *  return HashBucket *   The located hash-bucket.
 */
static HashBucket *_find_HashBucket(HashTable *hash, const char *name)
{
  unsigned const char *kp;
  unsigned long h = 0L;
  if(hash->case_sensitive) {
    for(kp=(unsigned const char *) name; *kp; kp++)
      h = 65599UL * h + *kp;  /* 65599 is a prime close to 2^16 */
  } else {
    for(kp=(unsigned const char *) name; *kp; kp++)
      h = 65599UL * h + tolower((int)*kp);  /* 65599 is a prime close to 2^16 */
  };
  return hash->bucket + (h % hash->size);
}

/*.......................................................................
 * Search for a given name in the entries of a given bucket.
 *
 * Input:
 *  hash     HashTable *  The hash-table being searched.
 *  bucket  HashBucket *  The bucket to search (use _find_HashBucket()).
 *  name    const char *  The name to search for.
 * Output:
 *  prev      HashNode ** If prev!=NULL then the pointer to the node
 *                        preceding the located node in the list will
 *                        be recorded in *prev. This will be NULL either
 *                        if the name is not found or the located node is
 *                        at the head of the list of entries.
 * return     HashNode *  The located hash-table node, or NULL if not
 *                        found.
 */
static HashNode *_find_HashNode(HashTable *hash, HashBucket *bucket,
			       const char *name, HashNode **prev)
{
  HashNode *last;  /* The previously searched node */
  HashNode *node;  /* The node that is being searched */
/*
 * Search the list for a node containing the specified name.
 */
  for(last=NULL, node=bucket->head;
      node && hash->keycmp(node->symbol.name, name)!=0;
      last = node, node=node->next)
    ;
  if(prev)
    *prev = node ? last : NULL;
  return node;
}

/*.......................................................................
 * When hash->case_sensitive is zero this function is called
 * in place of strcmp(). In such cases the hash-table names are stored
 * as lower-case versions of the original strings so this function
 * performs the comparison against lower-case copies of the characters
 * of the string being compared.
 *
 * Input:
 *  node_key   const char *  The lower-case hash-node key being compared
 *                           against.
 *  look_key   const char *  The lookup key.
 * Output:
 *  return            int    <0 if node_key < look_key.
 *                            0 if node_key == look_key.
 *                           >0 if node_key > look_key.
 */
static int _ht_lower_strcmp(const char *node_key, const char *look_key)
{
  int cn;  /* The latest character from node_key[] */
  int cl;  /* The latest character from look_key[] */
  do {
    cn = *node_key++;
    cl = *look_key++;
  } while(cn && cn==tolower((int)(unsigned char) cl));
  return cn - tolower((int)(unsigned char) cl);
}

/*.......................................................................
 * This is a wrapper around strcmp for comparing hash-keys in a case
 * sensitive manner. The reason for having this wrapper, instead of using
 * strcmp() directly, is to make some C++ compilers happy. The problem
 * is that when the library is compiled with a C++ compiler, the
 * declaration of the comparison function is a C++ declaration, whereas
 * strcmp() is a pure C function and thus although it appears to have the
 * same declaration, the compiler disagrees.
 *
 * Input:
 *  node_key   char *  The lower-case hash-node key being compared against.
 *  look_key   char *  The lookup key.
 * Output:
 *  return      int    <0 if node_key < look_key.
 *                      0 if node_key == look_key.
 *                     >0 if node_key > look_key.
 */
static int _ht_strcmp(const char *node_key, const char *look_key)
{
  return strcmp(node_key, look_key);
}

/*.......................................................................
 * Empty a hash-table by deleting all of its entries.
 *
 * Input:
 *  hash    HashTable *  The hash table to clear.
 * Output:
 *  return        int    0 - OK.
 *                       1 - Invalid arguments.
 */
int _clear_HashTable(HashTable *hash)
{
  int i;
/*
 * Check the arguments.
 */
  if(!hash)
    return 1;
/*
 * Clear the contents of the bucket array.
 */
  for(i=0; i<hash->size; i++) {
    HashBucket *bucket = hash->bucket + i;
/*
 * Delete the list of active hash nodes from the bucket.
 */
    HashNode *node = bucket->head;
    while(node) {
      HashNode *next = node->next;
      (void) _del_HashNode(hash, node);
      node = next;
    };
/*
 * Mark the bucket as empty.
 */
    bucket->head = NULL;
    bucket->count = 0;
  };
  return 0;
}

/*.......................................................................
 * Execute a given function on each entry of a hash table, returning
 * before completion if the the specified function returns non-zero.
 *
 * Input:
 *  hash       HashTable *    The table to traverse.
 *  scan_fn HASH_SCAN_FN(*)   The function to call.
 *  context         void *    Optional caller-specific context data
 *                            to be passed to scan_fn().
 * Output:
 *  return           int      0 - OK.
 *                            1 - Either the arguments were invalid, or
 *                                scan_fn() returned non-zero at some
 *                                point.
 */
int _scan_HashTable(HashTable *hash, HASH_SCAN_FN(*scan_fn), void *context)
{
  int i;
/*
 * Check the arguments.
 */
  if(!hash || !scan_fn)
    return 1;
/*
 * Iterate through the buckets of the table.
 */
  for(i=0; i<hash->size; i++) {
    HashBucket *bucket = hash->bucket + i;
    HashNode *node;
/*
 * Iterate through the list of symbols that fall into bucket i,
 * passing each one to the caller-specified function.
 */
    for(node=bucket->head; node; node=node->next) {
      if(scan_fn(&node->symbol, context))
	return 1;
    };
  };
  return 0;
}