1                 : /*
       2                 :  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.  
       3                 :  * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
       4                 :  *
       5                 :  * This file is part of the device-mapper userspace tools.
       6                 :  *
       7                 :  * This copyrighted material is made available to anyone wishing to use,
       8                 :  * modify, copy, or redistribute it subject to the terms and conditions
       9                 :  * of the GNU Lesser General Public License v.2.1.
      10                 :  *
      11                 :  * You should have received a copy of the GNU Lesser General Public License
      12                 :  * along with this program; if not, write to the Free Software Foundation,
      13                 :  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      14                 :  */
      15                 : 
      16                 : #include "dmlib.h"
      17                 : #include "ttree.h"
      18                 : 
      19                 : struct node {
      20                 :         unsigned k;
      21                 :         struct node *l, *m, *r;
      22                 :         void *data;
      23                 : };
      24                 : 
      25                 : struct ttree {
      26                 :         int klen;
      27                 :         struct dm_pool *mem;
      28                 :         struct node *root;
      29                 : };
      30                 : 
      31        41339775 : static struct node **_lookup_single(struct node **c, unsigned int k)
      32                 : {
      33        82683398 :         while (*c) {
      34        41342888 :                 if (k < (*c)->k)
      35            1170 :                         c = &((*c)->l);
      36                 : 
      37        41341718 :                 else if (k > (*c)->k)
      38            2678 :                         c = &((*c)->r);
      39                 : 
      40                 :                 else {
      41        41339040 :                         c = &((*c)->m);
      42        41339040 :                         break;
      43                 :                 }
      44                 :         }
      45                 : 
      46        41339775 :         return c;
      47                 : }
      48                 : 
      49          185928 : void *ttree_lookup(struct ttree *tt, unsigned *key)
      50                 : {
      51          185928 :         struct node **c = &tt->root;
      52          185928 :         int count = tt->klen;
      53                 : 
      54        41592306 :         while (*c && count) {
      55        41220450 :                 c = _lookup_single(c, *key++);
      56        41220450 :                 count--;
      57                 :         }
      58                 : 
      59          185928 :         return *c ? (*c)->data : NULL;
      60                 : }
      61                 : 
      62           44349 : static struct node *_tree_node(struct dm_pool *mem, unsigned int k)
      63                 : {
      64           44349 :         struct node *n = dm_pool_zalloc(mem, sizeof(*n));
      65                 : 
      66           44349 :         if (n)
      67           44349 :                 n->k = k;
      68                 : 
      69           44349 :         return n;
      70                 : }
      71                 : 
      72             738 : int ttree_insert(struct ttree *tt, unsigned int *key, void *data)
      73                 : {
      74             738 :         struct node **c = &tt->root;
      75             738 :         int count = tt->klen;
      76                 :         unsigned int k;
      77                 : 
      78                 :         do {
      79          119325 :                 k = *key++;
      80          119325 :                 c = _lookup_single(c, k);
      81          119325 :                 count--;
      82                 : 
      83          119325 :         } while (*c && count);
      84                 : 
      85             738 :         if (!*c) {
      86             738 :                 count++;
      87                 : 
      88           45825 :                 while (count--) {
      89           44349 :                         if (!(*c = _tree_node(tt->mem, k))) {
      90               0 :                                 stack;
      91               0 :                                 return 0;
      92                 :                         }
      93                 : 
      94           44349 :                         k = *key++;
      95                 : 
      96           44349 :                         if (count)
      97           43611 :                                 c = &((*c)->m);
      98                 :                 }
      99                 :         }
     100             738 :         (*c)->data = data;
     101                 : 
     102             738 :         return 1;
     103                 : }
     104                 : 
     105               3 : struct ttree *ttree_create(struct dm_pool *mem, unsigned int klen)
     106                 : {
     107                 :         struct ttree *tt;
     108                 : 
     109               3 :         if (!(tt = dm_pool_zalloc(mem, sizeof(*tt)))) {
     110               0 :                 stack;
     111               0 :                 return NULL;
     112                 :         }
     113                 : 
     114               3 :         tt->klen = klen;
     115               3 :         tt->mem = mem;
     116               3 :         return tt;
     117                 : }