libdm/regex/ttree.c

   1 /*
   2  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
   3  * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
   4  *
   5  * This file is part of the device-mapper userspace tools.
   6  *
   7  * This copyrighted material is made available to anyone wishing to use,
   8  * modify, copy, or redistribute it subject to the terms and conditions
   9  * of the GNU Lesser General Public License v.2.1.
  10  *
  11  * You should have received a copy of the GNU Lesser General Public License
  12  * along with this program; if not, write to the Free Software Foundation,
  13  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  14  */
  15
  16 #include "dmlib.h"
  17 #include "ttree.h"
  18
  19 struct node {
  20         unsigned k;
  21         struct node *l, *m, *r;
  22         void *data;
  23 };
  24
  25 struct ttree {
  26         int klen;
  27         struct dm_pool *mem;
  28         struct node *root;
  29 };
  30
  31 static struct node **_lookup_single(struct node **c, unsigned int k)
  32 {
  33         while (*c) {
  34                 if (k < (*c)->k)
  35                         c = &((*c)->l);
  36
  37                 else if (k > (*c)->k)
  38                         c = &((*c)->r);
  39
  40                 else {
  41                         c = &((*c)->m);
  42                         break;
  43                 }
  44         }
  45
  46         return c;
  47 }
  48
  49 void *ttree_lookup(struct ttree *tt, unsigned *key)
  50 {
  51         struct node **c = &tt->root;
  52         int count = tt->klen;
  53
  54         while (*c && count) {
  55                 c = _lookup_single(c, *key++);
  56                 count--;
  57         }
  58
  59         return *c ? (*c)->data : NULL;
  60 }
  61
  62 static struct node *_tree_node(struct dm_pool *mem, unsigned int k)
  63 {
  64         struct node *n = dm_pool_zalloc(mem, sizeof(*n));
  65
  66         if (n)
  67                 n->k = k;
  68
  69         return n;
  70 }
  71
  72 int ttree_insert(struct ttree *tt, unsigned int *key, void *data)
  73 {
  74         struct node **c = &tt->root;
  75         int count = tt->klen;
  76         unsigned int k;
  77
  78         do {
  79                 k = *key++;
  80                 c = _lookup_single(c, k);
  81                 count--;
  82
  83         } while (*c && count);
  84
  85         if (!*c) {
  86                 count++;
  87
  88                 while (count--) {
  89                         if (!(*c = _tree_node(tt->mem, k))) {
  90                                 stack;
  91                                 return 0;
  92                         }
  93
  94                         if (count) {
  95                                 k = *key++;
  96                                 c = &((*c)->m);
  97                         }
  98                 }
  99         }
 100         (*c)->data = data;
 101
 102         return 1;
 103 }
 104
 105 struct ttree *ttree_create(struct dm_pool *mem, unsigned int klen)
 106 {
 107         struct ttree *tt;
 108
 109         if (!(tt = dm_pool_zalloc(mem, sizeof(*tt)))) {
 110                 stack;
 111                 return NULL;
 112         }
 113
 114         tt->klen = klen;
 115         tt->mem = mem;
 116         return tt;
 117 }