include/libfmail/searchtree.h

   1 /*
   2 libfmail: Generic Search Tree implementation
   3
   4 Copyright (C) 2007  Carlos Daniel Ruvalcaba Valenzuela <clsdaniel@gmail.com>
   5
   6 This program is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2 of the License, or
   9 (at your option) any later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License along
  17 with this program; if not, write to the Free Software Foundation, Inc.,
  18 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  19 */
  20
  21 /* Generic Search Tree
  22  * For a given key string and value, generate
  23  * a tree that can be navigated using the key
  24  * characters to retrieve a value.
  25  *
  26  * Given the Key-Value:
  27  *  * test-20
  28  *  * key-8
  29  *  * some-10
  30  *  * same-11
  31  *   ROOT
  32  *  / | \
  33  * t  k  s
  34  * e  e  o \
  35  * s  y  m  a
  36  * t     e  m
  37  *          e
  38  * The search tree may be arranged this way, with the last
  39  * node having the value.
  40  *
  41  * Notes:
  42  *  * This algorithm is O(n), may be better than binary trees but not
  43  *    so good as hash tables, proable is in the middle between speed
  44  *    and memory usage.
  45  *  * This algorithm may consume a lot of memory, depending on the
  46  *    keys, it is recomended to use a hash function with values ranging
  47  *    from 0 to 26 for best performance.
  48  * */
  49
  50 typedef int (*HASH_FUNC)(char s);
  51
  52 /* Search failure exception */
  53 class SearchNotFound {};
  54
  55 /* Node class */
  56 template <class T, int max> class TreeNode{
  57 public:
  58     T value;
  59     TreeNode<T, max> *tree[max];
  60
  61     TreeNode(){
  62         for (int i = 0; i < max; i++){
  63             tree[i] = NULL;
  64         }
  65     }
  66     ~TreeNode(){
  67         int i;
  68         //printf("Deleting Node\n");
  69         for (i = 0; i < max; i++){
  70             if (tree[i] != NULL){
  71                 //printf("\tDeleting Child\n");
  72                 delete tree[i];
  73             }
  74         }
  75     }
  76 };
  77
  78 /* Generic search tree class
  79  * may hold T type of values, may use
  80  * max number for characters for key hashes,
  81  * may use hash_func for character key hashes */
  82 template <class T, int max, HASH_FUNC hash_func> class SearchTree{
  83 private:
  84     TreeNode<T, max> *rootNode;
  85
  86         int getNodeSize(TreeNode<T, max> *node){
  87                 int size;
  88                 int i;
  89
  90                 size = 0;
  91                 size += sizeof(T); //Size of value
  92                 size += sizeof(void*) * max;
  93                 for (i = 0; i < max; i++){
  94                         if (node->tree[i] != NULL)
  95                                 size += getNodeSize(node->tree[i]);
  96                 }
  97
  98                 return size;
  99         }
 100 public:
 101     SearchTree(){
 102         rootNode = new TreeNode<T, max>();
 103     }
 104     ~SearchTree(){
 105         delete rootNode;
 106         rootNode = NULL;
 107     }
 108     int Insert(char *key, T value){
 109         int i, l, tk;
 110         TreeNode<T, max> *c;
 111
 112                 /* Grab root node and key length*/
 113         c = rootNode;
 114         l = strlen(key);
 115
 116                 /* For each character in key insert a node */
 117         for (i = 0; i < l; i++){
 118                         /* Get the hash key character */
 119             tk = hash_func(key[i]);
 120
 121                         /* If hash key character > max allowed should fail, undefined for now */
 122             if (tk > max)
 123                 printf("GOT MAX\n");
 124
 125                         /* If next node is NULL create */
 126             if (c->tree[tk] == NULL)
 127                 c->tree[tk] = new TreeNode<T, max>();
 128             c = c->tree[tk];
 129         }
 130                 /* Once we reach the final node, set the value */
 131         c->value = value;
 132         return 0;
 133     }
 134     T Lookup(char *key){
 135         int i, l, tk;
 136         TreeNode<T, max> *c;
 137
 138         c = rootNode;
 139         l = strlen(key);
 140
 141         for (i = 0; i < l; i++){
 142             tk = hash_func(key[i]);
 143             if (tk > max)
 144                 throw SearchNotFound();
 145
 146             if (tk == -1)
 147                 break;
 148
 149             if (c->tree[tk] == NULL)
 150                 throw SearchNotFound();
 151
 152             c = c->tree[tk];
 153         }
 154
 155         return c->value;
 156     }
 157
 158         int getTreeSize(){
 159                 return getNodeSize(rootNode);
 160         }
 161
 162     int HasKey(char *key){
 163         int i, l, tk;
 164         TreeNode<T, max> *c;
 165
 166         c = rootNode;
 167         for (i = 0; i < l; i++){
 168             tk = hash_func(key[i]);
 169
 170             if (tk > max)
 171                 return 0;
 172
 173             if (tk == -1)
 174                 break;
 175
 176             if (c->tree[tk] == NULL)
 177                 return 0;
 178
 179             c = c->tree[tk];
 180         }
 181
 182         return 1;
 183     }
 184
 185 };