trie.c

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

       * Now, attempt to recursively insert the new leaf into the subtrie we
       * just created
       */
      result = insert_node( (trie_pointer)new_node, walker, level, leaf );

      /*
       * If we failed, then destroy the subtrie we just spent so much time
       * creating, but not the old leaf underneath it.  Since we haven't
       * modified the old leaf, there is nothing to undo there
       */
      if (!result) {
        free(new_node);
        return 0;
      }

      /*
       * We are successful, the resulting node is exactly what the caller
       * wants
       */
      return result;
    }

    /*
     * Inserting a new leaf onto an existing subtrie.  Here, we ask the walker
     * for where the search would look, and attempt to insert the leaf there
     */
    case TRIE_SUBTRIE: {
      struct trie_subtrie *node = (struct trie_subtrie*)old_node;
      int n;

      n = extract_next( *walker );

      if (n < 0) {
        /*
         * If we ran out of key, then install this as an exact match, unless
         * there's already one there
         */
        if (node->exact_match) {
          return 0;
        }
        node->exact_match = leaf;
      } else {
        /*
         * The next set of bits is n -- recursively call insert_node to insert
         * the leaf into the n-th next_level node
         */
        assert( n < TRIE_BRANCH_FACTOR );
        if (node->next_level[n]) {
          trie_pointer next_level = insert_node( node->next_level[n],
                                   walker, level+1, leaf );
          if (!next_level) {
            return 0;
          }
          node->next_level[n] = next_level;
        } else
          node->next_level[n] = (trie_pointer)leaf;
      }
      /*
       * In either case, if we reach here, we succesfully added the leaf.
       */
      node->count += 1;
      return (trie_pointer)node;
    }
    default:
      assert(0);
      return 0;
  }
}

/*
 * trie_insert -- insert an entry into a trie
 *
 * inputs: trie -- a pointer to the trie to insert into
 *         key -- a pointer to the key to insert
 *         len_key -- the length (in bytes) of the key to insert
 *         result -- the value that trie_search should return when it finds
 *                   this entry
 *
 * outputs: nonzero on success, zero on error
 *
 * This attempts to insert the given key into the trie, so that if you
 * search for that specific key, you will find it.
 * There are two error conditions: malloc failure, and if the key already
 * exists within the trie.  On error, the trie is unchanged.
 * The trie makes a copy of the key.  When trie_insert returns, you are
 * free to reuse the memory that you used to specify the key
 */
int trie_insert(struct trie *trie, const unsigned char *key, size_t len_key,
            trie_result result) {
  if (trie) {
    trie_pointer p;
    key_walker walker;
    struct trie_leaf *leaf;

    /*
     * Attempt to allocate the leaf.  We do it here, so that the insert_node
     * routine doesn't have to worry about it
     */
    leaf = malloc( sizeof( *leaf ) );
    if (!leaf)
      return 0;
    leaf->key = malloc( len_key > 0 ? len_key : 1 );
    if (!leaf->key) {
      free(leaf);
      return 0;
    }
    memcpy( leaf->key, key, len_key );
    leaf->type = TRIE_LEAF;
    leaf->len_key = len_key;
    leaf->result = result;

    /* Initialize the walker for the key */
    initialize_walker( walker, key, len_key );

    /* Attempt to insert the leaf into root node */
    p = insert_node( trie->root, &walker, 0, leaf );

    /* If we were successful, store the updated root, and return success */
    if (p) {
      trie->root = p;
      return 1;
    }

    /* We failed for some reason, free up the now worthless leaf */
    destroy_leaf( leaf );
  }
  return 0;
}

/*
 * delete_node -- remove an entry from a node
 *
 * inputs: node -- a pointer to the pointer to the node we are modifying
 *         walker -- key walker for the key we are removing
 *         key -- a pointer to the key to delete
 *         len_key -- the length (in bytes) of the key to delete
 *
 * outputs: nonzero on success, zero on error
 *          updates *node on success, if appropriate
 *
 * This attempts to remove the given key from the node, returning the node
 * to the state as if the key had never been inserted
 * There is only one error condition: if the key was not found within the
 * node.  On error, the node is unchanged.
 */
static int delete_node( trie_pointer *node, key_walker *walker,
             const unsigned char *key, size_t len_key )
{
  /* If the pointer is NULL, then obviously the key was not a member of */
  /* this node */
  if (!*node)
    return 0;

  switch (**node) {
    /*
     * We're removing the leaf from a leaf -- this is succesful only
     * if they correspond to the same key
     */
    case TRIE_LEAF: {
      struct trie_leaf *p = (struct trie_leaf*)*node;
      if (len_key != p->len_key || 0 != memcmp( key, p->key, len_key ))
        return 0;

      /*
       * They do -- free up the leaf, and reset the pointer to NULL (now, the
       * node corresponds to no keys
       */
      destroy_leaf(p);
      *node = 0;
      return 1;
    }

    /*
     * We're removing the leaf from a subtrie -- try to remove it from the
     * approriate subnode, and then check if we need to collapse
     */
    case TRIE_SUBTRIE: {
      struct trie_subtrie *p = (struct trie_subtrie*)*node;
      int n;
      n = extract_next( *walker );
      if (n < 0) {
        /* If we run out of key, then we need to delete the exact match */
        if (p->exact_match == 0)
          return 0;

        /*
         * If there is an exact match in this node, it must correspond
         * to the key we're removing
         */
        assert( len_key == p->exact_match->len_key &&
                         0 == memcmp( key, p->exact_match->key, len_key ) );
        destroy_leaf( p->exact_match );
        p->exact_match = 0;
      } else {
        /* If the next set of output is N, delete the leaf from that subnode */
        if (!delete_node( &p->next_level[n], walker, key, len_key ))
          return 0;
      }

      /*
       * If we reach here, we have successfully removed the leaf from the node
       * Now, we need to check if we need to collapse the node into a leaf.
       * We do this if the number of keys that this node keeps track of falls
       * to one.
       */
      p->count -= 1;
      assert( p->count > 0 );
      if (p->count == 1) {
        trie_pointer leaf;
        int i;

        /*
         * We need to collapse the node.  Fortunately, we know that the
         * sublevels must also be collapsed, and so we can just scan through
         * all our children for a non-NULL subnode
         */
        leaf = (trie_pointer)p->exact_match;
        for (i=0; i<TRIE_BRANCH_FACTOR; i++)
          if (p->next_level[i]) {
            assert( leaf == 0 );
            leaf = p->next_level[i];
          }

        /* We must have found a child which must be a leaf */
        assert( leaf != 0 );
        assert( *leaf == TRIE_LEAF );

        /* We can use that leaf as the new node, free up the old subtrie */
        free(p);
        *node = leaf;
      }
      return 1;
    }

    default:
      assert(0);
      return 0;
  }
}

/*
 * trie_delete -- remove an entry from a trie
 *
 * inputs: trie -- a pointer to the trie to remove from
 *         key -- a pointer to the key to delete
 *         len_key -- the length (in bytes) of the key to delete
 *
 * outputs: nonzero on success, zero on error
 *
 * This attempts to remove the given key from the trie, so that if you
 * search for that specific key, it will not be found.
 * There is only one error condition: if the key was not found within the
 * trie.  On error, the trie is unchanged.
 */
int trie_delete( struct trie *trie, const unsigned char *key, size_t len_key )
{
  if (trie) {
    key_walker walker;

    initialize_walker( walker, key, len_key );
    return delete_node( &trie->root, &walker, key, len_key );
  }  
  return 0;
}