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 typedef int (*HASH_FUNC)(char s);
  22
  23 class SearchNotFound {};
  24
  25 template <class T, int max> class TreeNode{
  26 public:
  27     T value;
  28     TreeNode<T, max> *tree[max];
  29
  30     TreeNode(){
  31         for (int i = 0; i < max; i++){
  32             tree[i] = NULL;
  33         }
  34     }
  35 };
  36
  37 template <class T, int max, HASH_FUNC hash_func> class SearchTree{
  38 private:
  39     TreeNode<T, max> *rootNode;
  40
  41         int getNodeSize(TreeNode<T, max> *node){
  42                 int size;
  43                 int i;
  44
  45                 size = 0;
  46                 size += sizeof(T); //Size of value
  47                 size += sizeof(void*) * max;
  48                 for (i = 0; i < max; i++){
  49                         if (node->tree[i] != NULL)
  50                                 size += getNodeSize(node->tree[i]);
  51                 }
  52
  53                 return size;
  54         }
  55 public:
  56     SearchTree(){
  57         rootNode = new TreeNode<T, max>();
  58     }
  59     int Insert(char *key, T value){
  60         int i, l, tk;
  61         TreeNode<T, max> *c;
  62
  63         c = rootNode;
  64         l = strlen(key);
  65
  66         for (i = 0; i < l; i++){
  67             tk = hash_func(key[i]);
  68
  69             if (tk > max)
  70                 printf("GOT MAX\n");
  71
  72             if (c->tree[tk] == NULL)
  73                 c->tree[tk] = new TreeNode<T, max>();
  74             c = c->tree[tk];
  75         }
  76         c->value = value;
  77         return 0;
  78     }
  79     T Lookup(char *key){
  80         int i, l, tk;
  81         TreeNode<T, max> *c;
  82
  83         c = rootNode;
  84         l = strlen(key);
  85
  86         for (i = 0; i < l; i++){
  87             tk = hash_func(key[i]);
  88             if (tk > max)
  89                 throw SearchNotFound();
  90
  91             if (tk == -1)
  92                 break;
  93
  94             if (c->tree[tk] == NULL)
  95                 throw SearchNotFound();
  96
  97             c = c->tree[tk];
  98         }
  99
 100         return c->value;
 101     }
 102
 103         int getTreeSize(){
 104                 return getNodeSize(rootNode);
 105         }
 106
 107     int HasKey(char *key){
 108         int i, l, tk;
 109         TreeNode<T, max> *c;
 110
 111         c = rootNode;
 112         for (i = 0; i < l; i++){
 113             tk = hash_func(key[i]);
 114
 115             if (tk > max)
 116                 return 0;
 117
 118             if (tk == -1)
 119                 break;
 120
 121             if (c->tree[tk] == NULL)
 122                 return 0;
 123
 124             c = c->tree[tk];
 125         }
 126
 127         return 1;
 128     }
 129
 130 };