git.ozlabs.org Git - ccan/blob - junkcode/guerrilla_thought@gmx.de-bst/bst.h

   1 #ifndef BST_H
   2 #define BST_H
   3
   4 #define bst_declare(name, type, idx_type) struct  {     \
   5         struct {                                        \
   6                 idx_type idx;                           \
   7                 type elem;                              \
   8                 void *left;                             \
   9                 void *right;                            \
  10         } *head;                                        \
  11 } name
  12
  13 #define bst_init(name) do {     \
  14         (name).head = NULL;     \
  15 } while (0)
  16
  17 #define bst_node_type(name) typeof(*((name).head))
  18
  19 #define bst_insert(name, _elem, _idx) do {                                      \
  20         bst_node_type(name) **cur = NULL;                                       \
  21                                                                                 \
  22         for (cur = &((name).head); ;) {                                         \
  23                 assert(cur != NULL);                                            \
  24                                                                                 \
  25                 if (*cur == NULL) {                                             \
  26                         (*cur) = malloc(sizeof(bst_node_type(name)));           \
  27                         assert(*cur != NULL);                                   \
  28                         (*cur)->idx = _idx;                                     \
  29                         (*cur)->elem = _elem;                                   \
  30                         (*cur)->left = NULL;                                    \
  31                         (*cur)->right = NULL;                                   \
  32                         break;                                                  \
  33                 } else {                                                        \
  34                         assert((*cur)->idx != _idx);                            \
  35                                                                                 \
  36                         if (_idx < (*cur)->idx) {                               \
  37                                 cur = (bst_node_type(name) **)&((*cur)->left);  \
  38                         } else {                                                \
  39                                 cur = (bst_node_type(name) **)&((*cur)->right); \
  40                         }                                                       \
  41                 }                                                               \
  42         }                                                                       \
  43 } while (0)
  44
  45 #define bst_find(name, _idx, _elemp) do {                               \
  46         bst_node_type(name) *cur = NULL;                                \
  47                                                                         \
  48         assert((_elemp) != NULL);                                       \
  49                                                                         \
  50         for (cur = (name).head; cur != NULL; ) {                        \
  51                 if (cur->idx == _idx) {                                 \
  52                         break;                                          \
  53                 }                                                       \
  54                                                                         \
  55                 if (_idx < cur->idx) {                          \
  56                         cur = (bst_node_type(name) *)(cur->left);       \
  57                 } else {                                                \
  58                         cur = (bst_node_type(name) *)(cur->right);      \
  59                 }                                                       \
  60         }                                                               \
  61                                                                         \
  62         if (cur != NULL) {                                              \
  63                 *(_elemp) = ((cur)->elem);                              \
  64         } else {                                                        \
  65                 *(_elemp) = NULL;                                       \
  66         }                                                               \
  67 } while (0);
  68
  69 #if 0
  70
  71
  72
  73 else {                                  \
  74                                 cur = &((bst_node_type(name)((*cur)->right)));                          \
  75                         }                                                       \
  76                         (*cur).elem = elem;             \
  77                         (*cur).idx = idx;               \
  78                 }
  79 #endif
  80
  81 #endif /* BST_H */