trie.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "trie_internal.h"

/*
 * trie_create -- create a new trie
 *
 * inputs: none
 *
 * outputs: a pointer to the new trie, or NULL on error
 *
 * This attempts to dynamically allocate a new trie, initializes it to
 * empty, and returns a pointer to it.
 */
struct trie *trie_create(void)
{
  struct trie *trie = malloc( sizeof(*trie ) );

  if (trie) {
    trie->root = 0;
  }
  return trie;
}

/*
 * destroy_leaf -- deallocate a leaf
 *
 * inputs: a pointer to the leaf to free
 *
 * outputs: none
 *
 * This frees up all memory associated with the leaf.  Calling it with
 * NULL is legitimite
 */
static void destroy_leaf(struct trie_leaf *leaf)
{
  if (leaf) {
    free(leaf->key);
    free(leaf);
  }
}

/*
 * destroy_node -- deallocate a node of any type
 *
 * inputs: a pointer to the node to free
 *
 * outputs: none
 *
 * This frees up all memory associated with the node.  Calling it with
 * NULL is legitimite
 */
static void destroy_node(trie_pointer node)
{
  if (node == 0)
    return;

  switch (*node) {
    case TRIE_LEAF: {
      /* If it's a leaf, we have a dedicated routine to free it */
      struct trie_leaf *p = (struct trie_leaf*)node;
      destroy_leaf(p);
      break;
    }
    case TRIE_SUBTRIE: {
      /*
       * If it's a subtrie, we need to free the exact_match (if any) and
       * its children before we free up the memory taken by the structure
       * itself
       */
      struct trie_subtrie *p = (struct trie_subtrie*)node;
      int i;
      destroy_leaf(p->exact_match);
      for (i=0; i<TRIE_BRANCH_FACTOR; i++)
        destroy_node(p->next_level[i]);
      free(p);
      break;
    }
    default: assert(0);
  }
}

/*
 * trie_destroy -- destroy a trie
 *
 * inputs: a pointer to the trie to free
 *
 * outputs: none
 *
 * This frees up all memory associated with the trie.  If any keys were
 * inserted into the trie, any memory associated with those are freed as
 * well.
 * Once this returns, it is no longer legitimite to refer to the trie
 */
void trie_destroy(struct trie *trie)
{
  if (trie) {
    destroy_node(trie->root);
    free(trie);
  }
}

/*
 * compare_leaf -- check a leaf to see if it matches the key we are
 *                 searching for
 *
 * inputs: a pointer to the leaf to compare
 *         the key and its length we are searching for
 *
 * outputs: the result of the search
 *
 * This does the final check for a search on this key.  It assumes that the
 * trie walk has ensured that this leaf is the only possible match.  This
 * checks this leaf to see if it is a match, and returns what the search
 * should return, either the result if this is a match, or NULL if it isn't
 */
static trie_result compare_leaf( const struct trie_leaf *leaf,
                                  const unsigned char *key, size_t len_key )
{
  if (!leaf || len_key != leaf->len_key ||
      0 != memcmp( key, leaf->key, len_key)) {
    return 0;
  } else
    return leaf->result;
}

/*
 * trie_search -- search the trie for an entry
 *
 * inputs: trie -- a pointer to the trie to search
 *         key -- a pointer to the key to look for
 *         len_key -- the length (in bytes) of the key to look for
 *
 * outputs: the result of the key, or NULL if the key was not found
 *
 * This searches for the given key through the trie.  If that key has been
 * successfully inserted, and has not been removed since, this will return
 * the trie_result that was specified during the insert.
 */
trie_result trie_search(const struct trie *trie, const unsigned char *key, size_t len_key)
{
  trie_pointer node;
  key_walker walker;
  const struct trie_leaf *leaf;

  if (trie == 0)
    return 0;

  /*
   * The general strategy is to extact bits from the key, and use those
   * bits to guide us down the trie, and we continue the walk until either
   * we hit something other than a TRIE_SUBTRIE (which means we hit a NULL or
   * a leaf, and so there is at most one possible match), or we run out of key,
   * in which case we look at the current nodes exact_match
   */
  initialize_walker(walker, key, len_key);
  node = trie->root;
  for (;;) {
    const struct trie_subtrie *q;
    int n;

    /* If we hit a NULL, there obviously isn't a match */
    if (!node) {
      return 0;
    }
    /* If we hit something other than a TRIE_SUBTRIE, we have limited the */
    /* possible matches down to one */
    if (*node != TRIE_SUBTRIE)
      break;

    q = (const struct trie_subtrie*)node;
    n = extract_next(walker);
    if (n < 0) {
      /* We ran out of key -- see if the node has an exact_match value */
      /* that we match on */
      return compare_leaf( q->exact_match, key, len_key );
    } else {
      /* Index down the next level based on the next bits of the key */
      assert( n < TRIE_BRANCH_FACTOR );
      node = q->next_level[n];
    }
  }

  /* If hit a leaf -- check to see if that leaf is what we are looking for */
  assert( *node == TRIE_LEAF );
  leaf = (const struct trie_leaf*)node;
  return compare_leaf( leaf, key, len_key );
}

/*
 * insert_node -- insert an entry into a node
 *
 * inputs: old_node -- a pointer to the node we are inserting into
 *         walker -- a pointer to the key walker for the key we are inserting
 *         level -- the depth in the trie of the node we are inserting into
 *                  (the root node is depty 0, the nodes immediately beneath
 *                  that are depth 1, etc)
 *         leaf -- pointer to the leaf to insert
 *
 * outputs: pointer to the new node if leaf successfully inserted, NULL on
 *          error
 *
 * This attempts to insert the given key into a node.
 * There are two error conditions: malloc failure, and if the key already
 * exists within the trie.
 * On success, the returned pointer should be used to reference the revised
 * node, the old pointer and the pointer to the leaf should be forgotten.  On
 * error, the node is unchanged, and the old pointer should continue to be used
 *
 * Having the old pointer be NULL is supported, and is interpreted to mean
 * that you are inserting the leaf into a node that does not correspond to
 * any keys
 */
static trie_pointer insert_node( trie_pointer old_node, key_walker *walker, int level,
                                               struct trie_leaf *leaf )
{
  /*
   * If the old pointer is NULL, then the leaf is the appropriate value for
   * the new node
   */
  if (!old_node) {
    return (trie_pointer)leaf;
  }
  switch (*old_node) {
    /*
     * Inserting a new leaf onto an existing leaf.  The strategy here is to
     * expand the old leaf into a full node, and then recursively call
     * insert_node to insert the new leaf into it
     */
    case TRIE_LEAF: {
      struct trie_subtrie *new_node;
      struct trie_leaf *previous_leaf = (struct trie_leaf*)old_node;
      trie_pointer result;
      int i, n;

      /*
       * Create a new subtrie, and attach the old leaf into it.  Note that,
       * since we aren't certain that the insert won't fail later, we need
       * to be sure we don't do any irrecoverable changes quite yet
       */
      new_node = malloc( sizeof( *new_node ));
      if (!new_node) return 0;

      new_node->type = TRIE_SUBTRIE;
      new_node->exact_match = 0;
      for (i=0; i<TRIE_BRANCH_FACTOR; i++)
        new_node->next_level[i] = 0;

      /*
       * Figure out exactly where in the node the old leaf would go
       */
      n = extract_at_offset( previous_leaf->key, previous_leaf->len_key,
                                                                   level );
      if (n < 0) {
        /* The previous key doesn't extend any farther, put it in the
        /* exact_match spot */
        new_node->exact_match = previous_leaf;
      } else {
        /* Place the previous leaf in the appropriate spot in the subtrie */
        assert( n < TRIE_BRANCH_FACTOR );
        new_node->next_level[n] = (trie_pointer)previous_leaf;
      }
      new_node->count = 1;

      /*