Home | History | Annotate | Line # | Download | only in datastruct 
      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 }
    140