lib/datastruct/btree.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 LVM2.
   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 "lib.h"
  17 #include "btree.h"
  18
  19 struct node {
  20         uint32_t key;
  21         struct node *l, *r, *p;
  22
  23         void *data;
  24 };
  25
  26 struct btree {
  27         struct dm_pool *mem;
  28         struct node *root;
  29 };
  30
  31 struct btree *btree_create(struct dm_pool *mem)
  32 {
  33         struct btree *t = dm_pool_alloc(mem, sizeof(*t));
  34
  35         if (t) {
  36                 t->mem = mem;
  37                 t->root = NULL;
  38         }
  39
  40         return t;
  41 }
  42
  43 /*
  44  * Shuffle the bits in a key, to try and remove
  45  * any ordering.
  46  */
  47 static uint32_t _shuffle(uint32_t k)
  48 {
  49 #if 1
  50         return ((k & 0xff) << 24 |
  51                 (k & 0xff00) << 8 |
  52                 (k & 0xff0000) >> 8 | (k & 0xff000000) >> 24);
  53 #else
  54         return k;
  55 #endif
  56 }
  57
  58 static struct node **_lookup(struct node *const *c, uint32_t key,
  59                              struct node **p)
  60 {
  61         *p = NULL;
  62         while (*c) {
  63                 *p = *c;
  64                 if ((*c)->key == key)
  65                         break;
  66
  67                 if (key < (*c)->key)
  68                         c = &(*c)->l;
  69
  70                 else
  71                         c = &(*c)->r;
  72         }
  73
  74         return (struct node **)c;
  75 }
  76
  77 void *btree_lookup(const struct btree *t, uint32_t k)
  78 {
  79         uint32_t key = _shuffle(k);
  80         struct node *p, **c = _lookup(&t->root, key, &p);
  81         return (*c) ? (*c)->data : NULL;
  82 }
  83
  84 int btree_insert(struct btree *t, uint32_t k, void *data)
  85 {
  86         uint32_t key = _shuffle(k);
  87         struct node *p, **c = _lookup(&t->root, key, &p), *n;
  88
  89         if (!*c) {
  90                 if (!(n = dm_pool_alloc(t->mem, sizeof(*n))))
  91                         return_0;
  92
  93                 n->key = key;
  94                 n->data = data;
  95                 n->l = n->r = NULL;
  96                 n->p = p;
  97
  98                 *c = n;
  99         }
 100
 101         return 1;
 102 }
 103
 104 void *btree_get_data(const struct btree_iter *it)
 105 {
 106         return ((const struct node *) it)->data;
 107 }
 108
 109 static struct node *_left(struct node *n)
 110 {
 111         while (n->l)
 112                 n = n->l;
 113         return n;
 114 }
 115
 116 struct btree_iter *btree_first(const struct btree *t)
 117 {
 118         if (!t->root)
 119                 return NULL;
 120
 121         return (struct btree_iter *) _left(t->root);
 122 }
 123
 124 struct btree_iter *btree_next(const struct btree_iter *it)
 125 {
 126         struct node *n = (struct node *) it;
 127         uint32_t k = n->key;
 128
 129         if (n->r)
 130                 return (struct btree_iter *) _left(n->r);
 131
 132         do
 133                 n = n->p;
 134         while (n && k > n->key);
 135
 136         return (struct btree_iter *) n;
 137 }