home *** CD-ROM | disk | FTP | other *** search
/ ftp.parl.clemson.edu / 2015-02-07.ftp.parl.clemson.edu.tar / ftp.parl.clemson.edu / pub / pvfs2 / orangefs-2.8.3-20110323.tar.gz / orangefs-2.8.3-20110323.tar / orangefs / src / io / buffer / radix.c < prev    next >
C/C++ Source or Header  |  2005-10-25  |  9KB  |  327 lines
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include "radix.h"
  4.  
  5. /*
  6.  * This file is download at http://www.cosc.canterbury.ac.nz/~tad/alg/dict/
  7.  *  
  8.  * The disclaimer information of this file can be found at 
  9.  * Disclaimer
  10.  *   You agree that this repository contains non-commercially developed
  11.  *   algorithms and that the source code and related files may contain errors.
  12.  *   In no event will the provider of this repository be held responsible
  13.  *   for any damages resulting from the source code and related files
  14.  *   supplied by this repository or the use thereof.  You acknowledge that
  15.  *   you use all source code and related files supplied by this repository
  16.  *   at you own risk.
  17.  *
  18.  *  Tadao Takaoka, Professor, at Department of Computer Science,
  19.  *  University of Canterbury, Private Bag 4800, Christchurch, New Zealand
  20.  *  maintains the above links.
  21.  */
  22.  
  23.  
  24. /* Modifications made by Jiesheng Wu are as follows:
  25.  * (1) bug fixes in rst_delete;
  26.  * (2) use "unsigned long index" as the search key.
  27.  * TODO: (1) to remove malloc and free in insert and free 
  28.  * as much as possible.
  29.  *      (2) This is not an efficient implementation. 
  30.  */
  31.  
  32.  
  33. /* Prototypes for functions only visible within this file. */
  34. void rst_free_dfs(rst_node_t *p);
  35.  
  36. /* rst_alloc() - Allocates space for a radix search tree and returns a
  37.  * pointer to it. 
  38.  */
  39. rst_t *rst_alloc(unsigned long (* get_value)(const void *), int max_b)
  40. {
  41.     rst_t *t;
  42.     rst_node_t *r;
  43.     
  44.     t = malloc(sizeof(rst_t));
  45.     r = t->root = malloc(sizeof(rst_node_t));
  46.     r->child_links = 0;
  47.     r->a[0] = r->a[1] = NULL;
  48.     t->n = 0;
  49.     t->max_b = max_b;
  50.     t->stack = malloc(max_b * sizeof(rst_node_t *));
  51.     t->path_info = malloc(max_b * sizeof(int));
  52.     t->get_value = get_value;
  53.  
  54.     return t;
  55. }
  56.  
  57. /* rst_free() - Frees space used by the radix search trie pointed to by t.
  58.  */
  59. void rst_free(rst_t *t) {
  60.     rst_free_dfs(t->root);
  61.     free(t);
  62. }
  63.  
  64. void rst_free_dfs(rst_node_t *p) {
  65.     if(p->child_links & 1) rst_free_dfs(p->a[0]);
  66.     if(p->child_links & 2) rst_free_dfs(p->a[1]);
  67.     free(p);
  68. }
  69.  
  70.  
  71. /* rst_insert() - Inserts an item into the radix search tree pointed 
  72.  * to by t, according to its key.  The key of an item in the radix
  73.  * search tree must be unique among items in the tree.  If an item with
  74.  * the same key already exists in the tree, a pointer to that item is 
  75.  * returned. 
  76.  * Otherwise, NULL is returned, indicating insertion was successful.
  77.  */
  78. void *rst_insert(rst_t *t, unsigned long key, void *item)
  79. {
  80.     unsigned long key2;
  81.     unsigned int j, mask, stop_mask;
  82.     int i;
  83.     rst_node_t *x, *p;
  84.     void *item2;
  85.  
  86.     //fprintf(stderr, "rst_insert: key=%ld, item=%p\n", key, item);
  87.  
  88.     mask = 1 << (i = t->max_b - 1);
  89.     
  90.     /* Locate the insertion position. */
  91.     p = t->root;    
  92.     for(;;) {
  93.     /* Traverse left or right branch, depending on the current key bit, j.
  94.      * If the branch does not exist, then the insertion position has
  95.      * been located.  Note that the (j+1)th bit in p->child_links
  96.      * indicates the kind of pointer for p->a[j].
  97.      */
  98.     j = (key & mask) >> i;
  99.     if(!(p->child_links & (j+1))) break;
  100.     p = p->a[j];
  101.  
  102.     /* Move to the next bit. */
  103.     mask >>= 1;
  104.     i--;
  105.     }
  106.  
  107.     if((item2 = p->a[j])) {
  108.     /* Check that the same item does not already exist in the tree. */
  109.     key2 = t->get_value(item2);
  110.     if(key2 == key) {
  111.         fprintf(stderr, "rst_insert: error, key2=key=%ld (item=%p, exist=%p)\n", key, item, item2);
  112.         return p->a[j];  /* Insert failed. */
  113.         }
  114.  
  115.     /* Create new nodes as necessary, in order to distinguish the key of
  116.      * the inserted item from the key of the existing item.
  117.      * The variable stop_mask is used for determining where the 
  118.      * bits of the two mkeys differ.
  119.      */
  120.     stop_mask = key ^ key2;  /* Exclusive OR */
  121.     x = malloc(sizeof(rst_node_t));
  122.     p->a[j] = x;
  123.     p->child_links = p->child_links | (j+1);  /* Set bit j. */
  124.     for(;;) {
  125.         p = x;
  126.         
  127.         /* Move to the next bit. */
  128.         mask >>= 1;
  129.         i--;
  130.         j = (key & mask) >> i;
  131.  
  132.         /* If the current bit value is different in key and key2, then
  133.          * no more new nodes need to be created.
  134.          */
  135.         if(mask & stop_mask) break;
  136.  
  137.         x = malloc(sizeof(rst_node_t));
  138.         p->a[j] = x;
  139.         p->a[!j] = NULL;
  140.         p->child_links = (j+1);  /* Only bit j is set. */
  141.     }
  142.  
  143.     p->a[j] = item;
  144.     p->a[!j] = item2;
  145.         p->child_links = 0;
  146.     }
  147.     else {
  148.     p->a[j] = item;
  149.     }
  150.  
  151.     t->n++;
  152.  
  153.     return NULL;
  154. }
  155.  
  156.  
  157. /* rst_find() - Find an item in the radix search tree with the same key as
  158.  * the item pointed to by `key_item'.  Returns a pointer to the item found, or
  159.  * NULL if no item was found.
  160.  */
  161. void *rst_find(rst_t *t, unsigned long index) 
  162. {
  163.     unsigned int j, mask;
  164.     int i;
  165.     rst_node_t *p;
  166.  
  167.     mask = 1 << (i = t->max_b - 1);
  168.     
  169.     /* Search for the item with key `key'. */
  170.     p = t->root;
  171.     for(;;) {
  172.     /* Traverse left or right branch, depending on the current bit. */
  173.     j = (index & mask) >> i;
  174.     if(!(p->child_links & (j+1))) break;
  175.     p = p->a[j];
  176.  
  177.     /* Move to the next bit. */
  178.     mask >>= 1;
  179.     i--;
  180.     }
  181.  
  182.     if(!p->a[j] || t->get_value(p->a[j]) != index ) return NULL;
  183.     
  184.     return p->a[j];
  185. }
  186.  
  187.  
  188. /* rst_find() - Find an item in the radix search trie with the same key as
  189.  * the item pointed to by `key_item'.  Returns a pointer to the item found, or
  190.  * NULL if no item was found.
  191.  */
  192. static void *rst_find_min(rst_t *t) __attribute__((unused));
  193. static void *rst_find_min(rst_t *t)
  194. {
  195.     unsigned int j;
  196.     rst_node_t *p;
  197.  
  198.     p = t->root;
  199.     for(;;) {
  200.     j = p->a[0] ? 0 : 1;
  201.     if(!(p->child_links & (j+1))) break;
  202.     p = p->a[j];
  203.     }
  204.  
  205.     return p->a[j];
  206. }
  207.  
  208.  
  209.  
  210. /* rst_delete() - Delete the first item found in the radix search trie with
  211.  * the same key as the item pointed to by `key_item'.  Returns a pointer to the
  212.  * deleted item, and NULL if no item was found.
  213.  */
  214. void *rst_delete(rst_t *t, unsigned long key) 
  215. {
  216.     rst_node_t *p;
  217.     unsigned int mask, i, j;
  218.     rst_node_t **stack;
  219.     int *path_info, tos;
  220.     void *y, *return_item;
  221.  
  222.     //fprintf(stderr, "------rst_delete: key=%ld\n", key);
  223.     
  224.     mask = 1 << (i = t->max_b - 1);
  225.     stack = t->stack;
  226.     path_info = t->path_info;
  227.     tos = 0;
  228.     
  229.     /* Search for the item with key `key'. */
  230.     p = t->root;
  231.     for(;;) {
  232.     
  233.     /* Traverse left or right branch, depending on the current bit. */
  234.     j = (key & mask) >> i;
  235.     stack[tos] = p;
  236.     path_info[tos] = j;
  237.     tos++;
  238.     if(!(p->child_links & (j+1))) break;
  239.     p = p->a[j];
  240.  
  241.     /* Move to the next bit. */
  242.     mask >>= 1;
  243.     i--;
  244.     }
  245.  
  246.     /* The delete operation fails if the tree contains no items, or no mathcing
  247.      * item was found.
  248.      */
  249.     if(!p->a[j] || t->get_value(p->a[j]) != key) return NULL;
  250.     return_item = p->a[j];
  251.  
  252.     /* Currently p->a[j] points to the item which is to be removed.  After
  253.      * removing the deleted item, the parent node must also be deleted if its
  254.      * other child pointer is NULL.  This deletion can propagate up to the next
  255.      * level.
  256.      */
  257.     tos--;
  258.     for(;;) {
  259.     if(tos == 0) {  /* Special case: deleteing a child of the root node. */
  260.         p->a[j] = NULL;
  261.         p->child_links = p->child_links & ~(j+1);  /* Clear bit j. */
  262.         return return_item;
  263.     }
  264.     
  265.         if(p->a[!j]) break;
  266.     
  267.     free(p);
  268.         p = stack[--tos];
  269.     j = path_info[tos];
  270.     }
  271.     
  272.     /* For the current node, p, the child pointer p->a[!j] is not NULL.
  273.      * If p->a[!j] points to a node, we set p->a[j] to NULL.  Otherwise if
  274.      * p->a[!j] points to an item, we keep a pointer to the item, and
  275.      * continue to delete parent nodes if thier other child pointer is NULL.
  276.      */
  277.     if(p->child_links & (!j+1)) {  /* p->a[!j] points to a node. */
  278.         p->a[j] = NULL;
  279.     }
  280.     else {  /* p->a[!j] points to an item. */
  281.  
  282.         /* Delete p, and parent nodes for which the other child pointer is
  283.      * NULL.
  284.      */
  285.         y = p->a[!j];
  286.         do {
  287.         free(p);
  288.             p = stack[--tos];
  289.         j = path_info[tos];
  290.         if(p->a[!j]) break;
  291.         } while(tos != 0);
  292.  
  293.         /* For the current node, p, p->a[!j] is not NULL.  We assign item y to
  294.      * p->a[j].
  295.      */
  296.     p->a[j] = y;
  297.     }
  298.     p->child_links = p->child_links & ~(j+1);  /* Clear bit j. */
  299.  
  300.     return return_item;
  301. }
  302.  
  303.  
  304. /* new functions */
  305. void rst_init(rst_t *t, unsigned long (* get_value)(const void *), int max_b)
  306. {
  307.     rst_node_t *r;
  308.      
  309.     r = t->root = malloc(sizeof(rst_node_t));
  310.     r->child_links = 0;
  311.     r->a[0] = r->a[1] = NULL;
  312.     t->n = 0;
  313.     t->max_b = max_b; 
  314.     t->stack = malloc(max_b * sizeof(rst_node_t *));
  315.     t->path_info = malloc(max_b * sizeof(int));
  316.     t->get_value = get_value;
  317.  
  318.     return;
  319. }
  320.  
  321. static void rst_finalize(rst_t *t) __attribute__((unused));
  322. static void rst_finalize(rst_t *t) 
  323. {
  324.     rst_free_dfs(t->root);
  325. }
  326.  
  327.