text: /*
    +----------------------------------------------------------------------+
    | Swoole                                                               |
    +----------------------------------------------------------------------+
    | This source file is subject to version 2.0 of the Apache license,    |
    | that is bundled with this package in the file LICENSE, and is        |
    | available through the world-wide-web at the following url:           |
    | http://www.apache.org/licenses/LICENSE-2.0.html                      |
    | If you did not receive a copy of the Apache2.0 license and are unable|
    | to obtain it through the world-wide-web, please send a note to       |
    | license@swoole.com so we can mail you a copy immediately.            |
    +----------------------------------------------------------------------+
    | Author: Tianfeng Han  <mikan.tenny@gmail.com>                        |
    +----------------------------------------------------------------------+
  */
  
  #ifndef _SW_RBTREE_H_INCLUDED_
  #define _SW_RBTREE_H_INCLUDED_
  
  #ifdef __cplusplus
  extern "C" {
  #endif
  
  #include <stdint.h>
  
  typedef struct swRbtree_node_s swRbtree_node;
  
  struct swRbtree_node_s
  {
      uint32_t key;
      void *value;
      swRbtree_node *left;
      swRbtree_node *right;
      swRbtree_node *parent;
      char color;
  };
  
  typedef struct swRbtree_s swRbtree;
  
  struct swRbtree_s
  {
      swRbtree_node *root;
      swRbtree_node *sentinel;
  };
  
  swRbtree* swRbtree_new();
  void swRbtree_free(swRbtree*);
  void swRbtree_insert(swRbtree *tree, uint32_t key, void *value);
  int swRbtree_delete(swRbtree *tree, uint32_t key);
  void* swRbtree_find(swRbtree *tree, uint32_t key);
  
  #define swRbtree_red(node)               ((node)->color = 1)
  #define swRbtree_black(node)             ((node)->color = 0)
  #define swRbtree_is_red(node)            ((node)->color)
  #define swRbtree_is_black(node)          (!swRbtree_is_red(node))
  #define swRbtree_copy_color(n1, n2)      (n1->color = n2->color)
  
  #define swRbtree_sentinel_init(node)      swRbtree_black(node)
  
  static inline swRbtree_node *swRbtree_min(swRbtree_node *node, swRbtree_node *sentinel)
  {
      while (node->left != sentinel)
      {
          node = node->left;
      }
      return node;
  }
  
  #ifdef __cplusplus
  }
  #endif
  
  #endif
  