external/gpl2/lvm2/dist/libdm/regex/ttree.c

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