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