Branch data     Line data    Source code

       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                 :   41390689 : static struct node **_lookup_single(struct node **c, unsigned int k)
      32                 :            : {
      33         [ +  + ]:   41395253 :         while (*c) {
      34         [ +  + ]:   41394466 :                 if (k < (*c)->k)
      35                 :       1230 :                         c = &((*c)->l);
      36                 :            : 
      37         [ +  + ]:   41393236 :                 else if (k > (*c)->k)
      38                 :       3334 :                         c = &((*c)->r);
      39                 :            : 
      40                 :            :                 else {
      41                 :   41389902 :                         c = &((*c)->m);
      42                 :   41389902 :                         break;
      43                 :            :                 }
      44                 :            :         }
      45                 :            : 
      46                 :   41390689 :         return c;
      47                 :            : }
      48                 :            : 
      49                 :     199136 : void *ttree_lookup(struct ttree *tt, unsigned *key)
      50                 :            : {
      51                 :     199136 :         struct node **c = &tt->root;
      52                 :     199136 :         int count = tt->klen;
      53                 :            : 
      54 [ +  + ][ +  + ]:   41470342 :         while (*c && count) {
      55                 :   41271206 :                 c = _lookup_single(c, *key++);
      56                 :   41271206 :                 count--;
      57                 :            :         }
      58                 :            : 
      59         [ +  + ]:     199136 :         return *c ? (*c)->data : NULL;
      60                 :            : }
      61                 :            : 
      62                 :      44447 : static struct node *_tree_node(struct dm_pool *mem, unsigned int k)
      63                 :            : {
      64                 :      44447 :         struct node *n = dm_pool_zalloc(mem, sizeof(*n));
      65                 :            : 
      66         [ +  - ]:      44447 :         if (n)
      67                 :      44447 :                 n->k = k;
      68                 :            : 
      69                 :      44447 :         return n;
      70                 :            : }
      71                 :            : 
      72                 :        790 : int ttree_insert(struct ttree *tt, unsigned int *key, void *data)
      73                 :            : {
      74                 :        790 :         struct node **c = &tt->root;
      75                 :        790 :         int count = tt->klen;
      76                 :            :         unsigned int k;
      77                 :            : 
      78                 :            :         do {
      79                 :     119483 :                 k = *key++;
      80                 :     119483 :                 c = _lookup_single(c, k);
      81                 :     119483 :                 count--;
      82                 :            : 
      83   [ +  +  +  - ]:     119483 :         } while (*c && count);
      84                 :            : 
      85         [ +  - ]:        790 :         if (!*c) {
      86                 :        790 :                 count++;
      87                 :            : 
      88         [ +  + ]:      45237 :                 while (count--) {
      89         [ -  + ]:      44447 :                         if (!(*c = _tree_node(tt->mem, k))) {
      90         [ #  # ]:          0 :                                 stack;
      91                 :          0 :                                 return 0;
      92                 :            :                         }
      93                 :            : 
      94                 :      44447 :                         k = *key++;
      95                 :            : 
      96         [ +  + ]:      44447 :                         if (count)
      97                 :      43657 :                                 c = &((*c)->m);
      98                 :            :                 }
      99                 :            :         }
     100                 :        790 :         (*c)->data = data;
     101                 :            : 
     102                 :        790 :         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                 :            : }