trie.h 6.07 KB
Newer Older
1 2 3 4

#ifndef TRIE_H_TRIE_1
#define TRIE_H_TRIE_1

5
/*#define KERNEL */
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#ifdef KERNEL

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/module.h>
#include <sys/proc.h>
#include <sys/buf.h>
#include <sys/malloc.h>
#include <sys/namei.h>
#include <sys/conf.h>
#include <sys/stat.h>
#include <sys/sysctl.h>
#include <sys/disklabel.h>
#include <ufs/ffs/fs.h>
#include <sys/devicestat.h>
#include <sys/fcntl.h>
#include <sys/vnode.h>

#else

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

#endif

/*--------------
  WARNING!!!!
  --------------
  The insertion functions are currently not transactional.*/

38
/* Do not change the typdefs for TrieKey and TrieValue */
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
typedef unsigned int TrieKey;
TrieKey getDefaultTrieKey(void);

typedef int TrieValue;
TrieValue getDefaultTrieValue(void);

/* pick one */
enum
{
    BITS_PER_LEVEL = 1
/* Don't pick the below options at this time. I'm assuming the first
   one for reasons of simplification, and because it provides the most
   compression. */
/*  BITS_PER_LEVEL = 2  */
/*  BITS_PER_LEVEL = 4  */
};

enum
{
    CHILD_COUNT = (1 << BITS_PER_LEVEL),
    TOTAL_BITS = sizeof(TrieKey) * 8,
    LEVEL_MASK = 0xffffffff >> (TOTAL_BITS - BITS_PER_LEVEL),
    TOTAL_LEVELS = TOTAL_BITS / BITS_PER_LEVEL
};

64 65 66 67 68 69
typedef enum OverlapTag
{
    FREE_OVERLAP,
    DEFAULT_OVERLAP
} OverlapT;

70 71 72 73 74 75 76 77
typedef struct TrieNodeTag
{
    char depth;
    char maxDepth;
    short isLeaf;
    TrieKey key;
    TrieValue value;
    struct TrieNodeTag * next;
78
    struct TrieNodeTag * prev;
79 80 81 82 83 84 85 86 87 88 89
/* Don't touch these */
    struct TrieNodeTag * parent;
    struct TrieNodeTag * child[CHILD_COUNT];
} TrieNode;

typedef void * FirstPtrT;
typedef void * SecondPtrT;
typedef void * ThirdPtrT;

typedef int (*BlockAllocateFunction)(int);
typedef int (*BlockFreeFunction)(int, int);
90 91
typedef int (*BlockCopyFunction)(FirstPtrT, SecondPtrT,
                                 TrieKey source, TrieValue dest, int size, int direction);
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144

typedef struct
{
    TrieNode root;
    BlockAllocateFunction blockAlloc;
    BlockFreeFunction blockFree;
    BlockCopyFunction blockCopy;
    FirstPtrT first;
    SecondPtrT second;
    ThirdPtrT third;
    TrieNode * tail;
} Trie;

typedef TrieNode * TrieIterator;

/* Call init before doing anything else. Send a pointer to a valid Trie *
   So it can allocate and setup a Trie for you and point your
   pointer to it.
   Returns 1 on success, 0 on failure */
int TrieInit(Trie ** trieOutPtr, BlockAllocateFunction blockAlloc,
             BlockFreeFunction blockFree, BlockCopyFunction blockCopy);

/* Call cleanup before exiting. Destroys the Trie. */
void TrieCleanup(Trie * triePtr);

/* Output the structure of the tree to stderr */
void logTrieStructure(Trie * triePtr);

/* Initialize an iterator based on a trie. Starts at the beginning.
   Send a pointer to a valid TrieIterator * so an iterator can be
   allocated.
   Returns 1 on success, 0 on failure */
int TrieIteratorInit(Trie * triePtr, TrieIterator * iterator);
void TrieIteratorCleanup(TrieIterator * iterator);

/* Move the TrieIterator to the next position. */
void TrieIteratorAdvance(TrieIterator * iterator);

/* Checks to see if the iterator points to a valid node.
   If the iterator is valid, this returns 1, otherwise 0. */
int TrieIteratorIsValid(TrieIterator iterator);

/* Inserts every key in [key, key+size) and skips any of these
   keys which are already inserted. This is transactional. If any insert
   fails, they all fail.
   Returns the number of keys actually inserted (non-skipped inserts).
   Returns <0 on failure */
int TrieInsertWeak(Trie * triePtr, TrieKey key, int size, FirstPtrT first,
                   SecondPtrT second, ThirdPtrT third);

/* Inserts every key in [key, key+size) and overwrites any of these
   keys which are already inserted. This inserts 'value' at key, 'value+1'
   at key+1, etc. up to size. This is transactional. If any of the inserts
145 146
   fail, they all fail. overlap determines whether blockFree is called
   when an insert overlaps an existing block.
147 148
   Returns the number of new keys inserted (non-overwrite inserts).
   Returns <0 on failure. */
149 150
int TrieInsertStrong(Trie * triePtr, TrieKey key, int size, TrieValue value,
                     OverlapT overlap);
151 152 153 154

/* This is not transactional.
   The return value determines whether it succeeded or not.
   1 for success, 0 for failure. */
155
int merge(Trie * dest, Trie * source, OverlapT overlap);
156 157 158 159 160 161

/* This is not transactional. */
void freeAllBlocks(Trie * trie);

int depthToSize(int num);

162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
static void TrieNodeInit(TrieNode * node);
static void TrieNodeCleanup(TrieNode * node);
static int extract(char inDepth, TrieKey key);
static void logStructure(TrieNode * current, int tableSize, int isYoungest);

/* Change the leaf property on a TrieNode. */
static void setLeaf(TrieNode * current);
static void clearLeaf(TrieNode * current);

/* Returns 1 if the node is a leaf, 0 otherwise. */
static int isLeaf(TrieNode * current);
static int isBranch(TrieNode * current);

static int roundDownToPow2(int num);
static int sizeToDepth(int num);
static int getBlockSize(TrieKey key, int size);
static int insertWeak(Trie * triePtr, TrieNode * node, TrieKey key,
                      int maxDepth);
static int insertStrong(Trie * triePtr, TrieNode * node, TrieKey key,
                        int maxDepth, TrieValue value, OverlapT overlap);
static int addChild(Trie * triePtr, TrieNode * parent, TrieKey key,
                    int maxDepth, TrieValue value);
static int replace(Trie * triePtr, TrieNode * node, TrieKey key,
                   int maxDepth, TrieValue value, OverlapT overlap);
static void freeChildren(Trie * triePtr, TrieNode * node, OverlapT overlap);
static int strongOverlap(Trie * triePtr, TrieNode * node, TrieKey key,
                         int maxDepth, TrieValue value, OverlapT overlap);
static int weakOverlap(Trie * triePtr, TrieNode * node, TrieKey key,
                       int maxDepth);
static TrieNode * search(TrieNode * node, TrieKey key, int maxDepth);
static TrieNode * pushDown(Trie * triePtr, TrieNode * node);
static void addToList(Trie * triePtr, TrieNode * node);
static void removeFromList(Trie * triePtr, TrieNode * node);

196
#endif