void rb() {
    printf(">> RB\n");
    rb_tree_t tree;
    rb_init(&tree, NULL);

    test_rb_t a = { 1 };
    test_rb_t b = { 2 };
    test_rb_t c = { 3 };

    rb_insert(&tree, &a.node, &test_rb_compare);
    rb_insert(&tree, &b.node, &test_rb_compare);
    rb_insert(&tree, &c.node, &test_rb_compare);

    // Display them
    rb_node_t *node = rb_head(&tree);
    while (node) {
        rb_node_t *next = rb_next(node);
        rb_node_t *prev = rb_prev(node);
        test_rb_t *c = rb_ref(node, test_rb_t, node);
        test_rb_t *n = next ? rb_ref(next, test_rb_t, node) : NULL;
        test_rb_t *p = prev ? rb_ref(prev, test_rb_t, node) : NULL;
        printf("current: %d, next: %d, prev: %d\n",
                c->number,
                n ? n->number : -1,
                p ? p->number : -1);
        node = next;
    }
}

struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node)
{
    node->left = node->right = NULL;
    node->red = false;

    if (!tree) {
        node->red = true;
        return node;
    }

    if (is_red(tree->left) && is_red(tree->right))
        color_flip(tree);

    if (node->key < tree->key)
        tree->left = rb_insert(tree->left, node);
    else
        tree->right = rb_insert(tree->right, node);

    if (is_red(tree->right))
        tree = rotate_left(tree);

    if (is_red(tree->left) && is_red(tree->left->left))
        tree = rotate_right(tree);

    return tree;
}

void insert_CLRS(NODE * t, int v)
{
	if (dbg_level == 0) {
		fprintf(stderr, "%s%d%s, ", GREEN, v, NOCOLOR);
		rb_insert(t, alloc_node(v, R));
		verify_rbtree(t->L, 0);
	} else {
		printf("%sinsert %d%s\n", GREEN, v, NOCOLOR);
		rb_insert(t, alloc_node(v, R));
		______________________________("./fig/", t, t, "inserted %d", v);
	}
}

/* If hk==NULL to register, new is attempted to be created. */
WHook *mainloop_register_hook(const char *name, WHook *hk)
{
    char *nnm;
    
    if(hk==NULL)
        return NULL;
    
    if(named_hooks==NULL){
        named_hooks=make_rb();
        if(named_hooks==NULL)
            return NULL;
    }
    
    nnm=scopy(name);
    
    if(nnm==NULL)
        return NULL;
    
    if(!rb_insert(named_hooks, nnm, hk)){
        free(nnm);
        destroy_obj((Obj*)hk);
    }
    
    return hk;
}

static void m_insert_right(MTrace * m, void * pdata){
    rb_insert(m->rb2, pdata);
    m->cnt2 += 1;
    if ((m->right_min && m->cmp_fn(pdata, m->right_min) < 0) || (!m->right_min)){
        m->right_min = pdata;
    }
}

static void m_insert_left(MTrace * m, void *pdata){
    rb_insert(m->rb1, pdata);
    m->cnt1 += 1;
    if ((m->left_max && m->cmp_fn(pdata, m->left_max) > 0) || (!m->left_max)){
        m->left_max = pdata;
    }
}

StringId stringstore_alloc_n(const char *str, uint l)
{
    Rb_node node=(Rb_node)stringstore_find_n(str, l);
    char *s;
    
    if(node!=NULL){
        node->v.ival++;
        return node;
    }
    
    if(stringstore==NULL){
        stringstore=make_rb();
        if(stringstore==NULL)
            return STRINGID_NONE;
    }
    
    s=scopyn(str, l);
    
    if(s==NULL)
        return STRINGID_NONE;
    
    node=rb_insert(stringstore, s, NULL);
    
    if(node==NULL)
        return STRINGID_NONE;
    
    node->v.ival=1;
        
    return (StringId)node;
}

BOOL vmm_ld_mapped(struct pm_task *task, UINT32 vlow, UINT32 vhigh)
{
    struct vmm_memory_region *mreg = NULL;

    // I'll only create a memory region for LD on the task..
    // I won't check collitions because this is always the first lib loaded.
    mreg = kmalloc(sizeof(struct vmm_memory_region));

    if(!mreg) return FALSE;

    if(!rb_free_value(&task->vmm_info.regions_id, &mreg->tsk_id_node.value))
	{
		kfree(mreg);
		return FALSE;
	}

    mreg->owner_task = task->id;
    mreg->next = mreg->prev = NULL;
	mreg->tsk_node.high = TRANSLATE_ADDR(vhigh, UINT32);
	mreg->tsk_node.low = TRANSLATE_ADDR(vlow, UINT32);
	mreg->flags = VMM_MEM_REGION_FLAG_NONE;
	mreg->type = VMM_MEMREGION_LIB;
    mreg->descriptor = NULL;

    ma_insert(&task->vmm_info.regions, &mreg->tsk_node);
    rb_insert(&task->vmm_info.regions_id, &mreg->tsk_id_node, FALSE);

    return TRUE;
}

int
main(void)
{
	rbt root;
	int i;
	int key[] = { 1, 2, 4, 5, 7, 8, 11, 14, 15, 39, 29, 73, 24, 18, 18, 18, 18};
	int key2[] = {15, 14, 11, 8, 7, 5, 4, 2, 1, 18, 73, 24, 39, 29, 18, 18, 18};
	/*int key[] = {41, 38, 31, 12, 19, 8};
	int key2[] = { 8, 12, 19, 31, 38, 41};*/
	rbn nil = { BLACK, 0, NULL, NULL, NULL};
	root.nil = &nil;
	root.root = &nil;
	rbn *tmp;
	for (i = 0; i < sizeof(key2) / sizeof(int); i++) {
		tmp = malloc(sizeof(rbn));
		tmp->key = key2[i];
		rb_insert(&root, tmp);
		printf("insert:%d\n", tmp->key);
	}
	for (i = 0; i < sizeof(key) / sizeof(int); i++) {
		tmp = rb_search(root.root, key[i]);
		rb_delete(&root, tmp);
		printf("deleted:%d\n", tmp->key);
	}
	printf("\n");
	return 0;
}

/* Add a file to the list. Return the index of the item. */
int plist_add (struct plist *plist, const char *file_name)
{
	assert (plist != NULL);
	assert (plist->items != NULL);

	if (plist->allocated == plist->num) {
		plist->allocated *= 2;
		plist->items = (struct plist_item *)xrealloc (plist->items,
				sizeof(struct plist_item) * plist->allocated);
	}

	plist->items[plist->num].file = xstrdup (file_name);
	plist->items[plist->num].type = file_name ? file_type (file_name)
		: F_OTHER;
	plist->items[plist->num].deleted = 0;
	plist->items[plist->num].title_file = NULL;
	plist->items[plist->num].title_tags = NULL;
	plist->items[plist->num].tags = NULL;
	plist->items[plist->num].mtime = (file_name ? get_mtime(file_name)
			: (time_t)-1);
	plist->items[plist->num].queue_pos = 0;

	if (file_name) {
		rb_delete (plist->search_tree, file_name);
		rb_insert (plist->search_tree, (void *)(intptr_t)plist->num);
	}

	plist->num++;
	plist->not_deleted++;

	return plist->num - 1;
}

int main(int argc, char *argv[])
{
	struct rb_node sentinel;
	struct rb_tree rbtree;
	struct rb_node node[1000];
	int i, j;

	rb_init(&rbtree, &sentinel);
	srand(time(0));

	for (i = 0; i < 10; i++) {
		for (;;) {
			node[i].key = rand()%10000;
			for (j = 0; j < i; j++) {
				if (node[i].key == node[j].key)
					break;
			}
			if (j < i)
				continue;
			else
				break;
		}
		rb_insert(&rbtree, &node[i]);
	}
	for (i = 0; i < 10; i++)
		rb_delete(&rbtree, &node[i]);

	exit(0);
}

static bool
node_insert_at(struct rbtree_elem **root, struct rbtree_elem *node,
    struct rbtree_elem *new_node, rbtree_less_func *less)
{
  bool inserted;

  inserted = false;

  while (!inserted) {
    ASSERT(node!=nil);
    if (less(node, new_node)) /*(node->high < lowIP)*/ {
      if (node->right == nil) {
        node->right = new_node;
        new_node->parent = node;
        inserted = true;
      } else {
        node = node->right;
      }
    } else {
      ASSERT(is_less(new_node, node));
      if (node->left == nil) {
        node->left = new_node;
        new_node->parent = node;
        inserted = true;
      } else {
        node = node->left;
      }
    }
  }

  rb_insert(root, new_node) ;
  return true;
}

int Write(unsigned long *random_seed, param_t *params)
{
    long int_value;
    void *value;

    int_value = (get_random(random_seed) % params->size) + 1;

    // make sure we have an odd value
    int_value |= 0x0001;

    value = rb_remove(My_Tree, int_value);
    if (value == NULL)
    {
        printf("Failure to remove %ld\n", int_value);
        exit(-2);
    }

    if (!rb_insert(My_Tree, int_value, (void *)int_value) )
    {
        printf("Failure to insert %ld\n", int_value);
        exit(-3);
    }

    return 0;
}

int main() {
    RB_TREE root = NULL;
    RB_TYPE rbt;
    int v,i;

    rb_type_create( &rbt, sizeof(VNODE), 0, cmp, NULL, NULL );

    srand(2);
    for( i=0; i<1000; i++ ) {
	v = rand();
	//v = 1000000-i;
	rb_insert( &rbt, &root, &v );
	}
    rb_assert(&rbt,root);

    printf( "Tree has %d elements\n", rb_size(&root) );

    srand(2);
    for( i=0; i<1000; i++ ) {
	v = rand();
	//v = 1000000-i;
	rb_remove( &rbt, &root, &v );
	}
    rb_assert(&rbt,root);
    printf( "Tree has %d elements\n", rb_size(&root) );

    rb_free(&rbt,&root);

    return 0;
    }

int register_event_prio(int fd, event_handler_t h, void *data, int prio)
{
	int ret;
	struct epoll_event ev;
	struct event_info *ei;

	ei = xzalloc(sizeof(*ei));
	ei->fd = fd;
	ei->handler = h;
	ei->data = data;
	ei->prio = prio;

	memset(&ev, 0, sizeof(ev));
	ev.events = EPOLLIN;
	ev.data.ptr = ei;

	ret = epoll_ctl(efd, EPOLL_CTL_ADD, fd, &ev);
	if (ret) {
		sd_err("failed to add epoll event for fd %d: %m", fd);
		free(ei);
	} else
		rb_insert(&events_tree, ei, rb, event_cmp);

	return ret;
}

void *rb_put(struct rb_tree *t, void *key, void *value)
{
  struct rb_tree_node *n = rb_insert(t, key);
  void *old_value = n->value;
  n->value = value;
  return old_value;
}

void *LCUIMM_Alloc( size_t size, unsigned int class_id )
{
	rb_node_t *node;
	mem_data_t mem_data;

	mem_data.mem_info.class_id = class_id;
	/* 查找该类别的结点 */
	node = rb_search( global_mem_class_info.root,
			&mem_data, RB_DATA_TYLE_INFO );
	/* 如果不存在，则用默认类别的结点 */
	if( node == NULL ) {
		mem_data.mem_info.class_id = 0;
		node = rb_search( global_mem_class_info.root,
				&mem_data, RB_DATA_TYLE_INFO );
		/* 如果默认类别的结点不存在，则说明出问题了 */
		if( node == NULL ) {
			abort();
		}
	}
	/* 分配内存空间，并记录它 */
	mem_data.mem_blk.mem_addr = malloc( size );
	/* 分配失败则返回NULL */
	if( mem_data.mem_blk.mem_addr == NULL ) {
		return NULL;
	}
	mem_data.mem_blk.mem_size = size;
	/* 累计该类别的总内存空间大小 */
	node->mem_data.mem_info.total_size += size;
	/* 插入该内存的信息 */
	rb_insert( &global_mem_data, &mem_data, RB_DATA_TYPE_ADDR );
	return mem_data.mem_blk.mem_addr;
}

/* Swap the first item on the playlist with the item with file fname. */
void plist_swap_first_fname (struct plist *plist, const char *fname)
{
	int i;

	assert (plist != NULL);
	assert (fname != NULL);

	i = plist_find_fname (plist, fname);

	if (i != -1 && i != 0) {
		rb_delete (plist->search_tree, fname);
		rb_delete (plist->search_tree, plist->items[0].file);
		plist_swap (plist, 0, i);
		rb_insert (plist->search_tree, NULL);
		rb_insert (plist->search_tree, (void *)(intptr_t)i);
	}
}

static void add_suggestion(rb_tree *suggs, string word){
  if(!(rb_lookup(suggs, &word))){
    DEBUG_PRINTF("adding suggestion %.*s\n", (int)word.len, word.str);
    string *ptr = xmalloc(sizeof(string) + word.sz);
    ptr->sz = word.sz; ptr->mem = (((void*)ptr)+sizeof(string));
    memcpy(ptr->mem, word.mem, word.sz);
    rb_insert(suggs, ptr);
  }
}

// insert_vma_rb - insert vma in rb tree according vma->start_addr
static inline void
insert_vma_rb(rb_tree *tree, struct vma_struct *vma, struct vma_struct **vma_prevp) {
    rb_node *node = &(vma->rb_link), *prev;
    rb_insert(tree, node);
    if (vma_prevp != NULL) {
        prev = rb_node_prev(tree, node);
        *vma_prevp = (prev != NULL) ? rbn2vma(prev, rb_link) : NULL;
    }
}