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