contrib/lvm2/dist/lib/datastruct/btree.c

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