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.h < prev    next >
C/C++ Source or Header  |  2003-08-21  |  3KB  |  91 lines
  1. #ifndef RST_H
  2. #define RST_H
  3.  
  4. /* 
  5.  * This file is download at http://www.cosc.canterbury.ac.nz/~tad/alg/dict/
  6.  *  
  7.  * The disclaimer information of this file can be found at 
  8.  * Disclaimer
  9.  *   You agree that this repository contains non-commercially developed 
  10.  *   algorithms and that the source code and related files may contain errors.
  11.  *   In no event will the provider of this repository be held responsible 
  12.  *   for any damages resulting from the source code and related files 
  13.  *   supplied by this repository or the use thereof.  You acknowledge that 
  14.  *   you use all source code and related files supplied by this repository 
  15.  *   at you own risk. 
  16.  *
  17.  *  Tadao Takaoka, Professor at Department of Computer Science,
  18.  *  University of Canterbury, Private Bag 4800, Christchurch, New Zealand
  19.  *  maintains the above links.
  20.  */
  21.  
  22. /* Structure type definition for nodes in the radix search tree.  The
  23.  * (j+1)th bit in p->child_links indicates the kind of pointer for p->a[j].
  24.  * For example, if bit 0 is 1 then p->a[0] points to another rst_note
  25.  * structure.  Otherwise p->a[0] is NULL or points to a data item.
  26.  */
  27. typedef struct rst_node {
  28.     int child_links;
  29.     void *a[2];
  30. } rst_node_t;
  31.  
  32. /* Structure type definition for a radix search trie. */
  33. typedef struct radix_tree_root {
  34.     rst_node_t *root;
  35.     int n;
  36.     int max_b;
  37.     rst_node_t **stack;
  38.     unsigned long (* get_value)(const void *);
  39.     int *path_info;
  40. } rst_t;
  41.  
  42.  
  43. rst_t *rst_alloc(unsigned long (* get_value)(const void *), int max_b);
  44. void rst_free(rst_t *t);
  45.  
  46. void *rst_insert(rst_t *t, unsigned long index, void *item);
  47. void *rst_find(rst_t *t, unsigned long index);
  48. void *rst_delete(rst_t *t, unsigned long index);
  49.  
  50.  
  51. /* modifications */
  52.  
  53. void rst_init(rst_t *t, unsigned long (* get_value)(const void *), int max_b);
  54.  
  55. static inline void *radix_tree_lookup( struct radix_tree_root *tree, 
  56.                                        unsigned long index )
  57. {
  58.     return rst_find(tree, index);
  59. }
  60.  
  61. static inline int radix_tree_insert(struct radix_tree_root *tree, 
  62.                                     unsigned long index, void *item)
  63. {
  64.     void *ret;
  65.  
  66.     ret = rst_insert(tree, index, item);
  67.  
  68.     if ( ret == NULL ) return 0;
  69.  
  70.     return -1;
  71. }
  72.  
  73. static inline void radix_tree_delete(struct radix_tree_root *tree,
  74.                                      unsigned long index)
  75. {
  76.     rst_delete(tree, index);
  77.     return;
  78. }
  79.  
  80. static inline void init_single_radix_tree( struct radix_tree_root *tree, 
  81.                        unsigned long (* get_value)(const void *), int max_b )
  82. {
  83.     
  84.     rst_init(tree, get_value, max_b);
  85.  
  86. }
  87.  
  88. #define RADIX_MAX_BITS (24)
  89.  
  90. #endif
  91.