home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume28 / librb / part01 / rb.h < prev    next >
C/C++ Source or Header  |  1992-02-23  |  2KB  |  67 lines
  1. typedef struct {
  2.   unsigned red : 1 ;
  3.   unsigned internal : 1 ;
  4.   unsigned left : 1 ;
  5.   unsigned root : 1 ;
  6.   unsigned head : 1 ;
  7. } status;
  8.  
  9. typedef struct rb_node {
  10.   union {
  11.     struct {
  12.       struct rb_node *flink;
  13.       struct rb_node *blink;
  14.     } list;
  15.     struct {
  16.       struct rb_node *left;
  17.       struct rb_node *right;
  18.     } child;
  19.   } c;
  20.   union {
  21.     struct rb_node *parent;
  22.     struct rb_node *root;
  23.   } p;
  24.   status s;
  25.   union {
  26.     int ikey;
  27.     char *key;
  28.     struct rb_node *lext;
  29.   } k;
  30.   union {
  31.     char *val;
  32.     struct rb_node *rext;
  33.   } v;
  34. } *Rb_node;
  35.  
  36. extern Rb_node make_rb();
  37. extern Rb_node rb_insert_b(/* node, char *key, char *value */);
  38.  
  39. extern Rb_node rb_find_key(/* tree, char *key */);
  40. extern Rb_node rb_find_ikey(/* tree, int ikey */);
  41. extern Rb_node rb_find_gkey(/* tree, char *key, cmpfxn */);
  42.  
  43. extern Rb_node rb_find_key_n(/* tree, char *key, int *found */);
  44. extern Rb_node rb_find_ikey_n(/* tree, int ikey, int *found */);
  45. extern Rb_node rb_find_gkey_n(/* tree, char *key, cmpfxn, int *found */);
  46. extern rb_delete_node(/* node */);
  47. extern rb_free_tree(/* node */);  /* Deletes and frees an entire tree */
  48. extern char *rb_val(/* node */);  /* Returns node->v.val (this is to shut
  49.                      lint up */
  50.  
  51. #define rb_insert_a(n, k, v) rb_insert_b(n->c.list.flink, k, v)
  52. #define rb_insert(t, k, v) rb_insert_b(rb_find_key(t, k), k, v)
  53. #define rb_inserti(t, k, v) rb_insert_b(rb_find_ikey(t, k), (char *) k, v)
  54. #define rb_insertg(t, k, v, f) rb_insert_b(rb_find_gkey(t, k, f), k, v)
  55. #define rb_first(n) (n->c.list.flink)
  56. #define rb_last(n) (n->c.list.blink)
  57. #define rb_next(n) (n->c.list.flink)
  58. #define rb_prev(n) (n->c.list.blink)
  59. #define rb_empty(t) (t->c.list.flink == t)
  60. #ifndef nil
  61. #define nil(t) (t)
  62. #endif
  63.  
  64. #define rb_traverse(ptr, lst) \
  65.   for(ptr = rb_first(lst); ptr != nil(lst); ptr = rb_next(ptr))
  66.  
  67.