1 /* $NetBSD: ttree.c,v 1.1.1.1 2008/12/22 00:18:37 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 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 } 120