<file_sep>/*
 * =============================================================================
 *
 *       Filename:  rbtree_api.h
 *
 *    Description:  api for rbtree to use.
 *
 *        Created:  09/30/2019 11:39:34 PM
 *
 *         Author:  <NAME>, <EMAIL>
 *
 * =============================================================================
 */
#ifndef __RBTREE_API_H__
#define __RBTREE_API_H__

#define MK_KEY(key) ((UserKey)key)
#define MK_VALUE(value) ((UserValue)value)

typedef void * UserRbTree;
typedef void * UserKey;
typedef void * UserValue;
typedef void * UserNode;
/**
    compare function for user key
**/
typedef int (*CompareKeyFun)(UserKey key1, UserKey key2);

/**
    delete function for user value
**/
typedef void (*DeleteValueObjectFun)(UserValue userValue);

/**
    create rbtree
    compareFun: the compare function for key.
    If it is NULL, a default compare function will be used just compare key value in format of integer
    deleteValueObjFun: the function to release value object when going to destory or clean
    return: the instance for rbtree
**/
UserRbTree RbTreeCreate(CompareKeyFun compareFun, DeleteValueObjectFun deleteValueObjFun);

/**
    destory rbtree
    It will release all the memory and destory the tree instance.
**/
void RbTreeDestory(UserRbTree userRbTree);

/**
    remove all the node in rbtree
**/
void RbTreeClear(UserRbTree userRbTree);

/**
    search value in rbtree instance
    userKey: the key want to search
    pUserNode: the node that equal userKey. You can use RbTreeGetValueFromNode to get the value in the node
	return 0: find the key
	return -1: not found the key
**/
int RbTreeSearch(UserRbTree userRbTree, UserKey userKey, UserNode *pUserNode);

/**
    insert a key value pair to rbtree instance
    userKey: the key want to insert
    userValue: the value want to insert
	return 0: insert ok
	return 1: already has key
	< 0: error occure
**/
int RbTreeInsert(UserRbTree userRbTree, UserKey userKey, UserValue userValue);

/**
    remove a key value pair from rbtree instance
    node: node get from RbTreeSearch, invalid node might cause api crash
	return 0: remove ok
	< 0: error occure
**/
int RbTreeRemove(UserRbTree userRbTree, UserNode node);

/**
    get value from node
    node: node get from RbTreeSearch, invalid node might cause api crash
	return the value of the node
**/
UserValue RbTreeGetValueFromNode(UserNode node);

/**
    dump the rbtree 
**/
void RbTreeDump(UserRbTree userRbTree);

/**
    get the size of rbtree 
    return the size of rbtree
**/
int RbTreeGetSize(UserRbTree userRbTree);

/**
    get the min key of rbtree 
    return the min key of rbtree
**/
int RbTreeGetMinKey(UserRbTree userRbTree, UserKey *pUserKey);

/**
    get the max key of rbtree 
    return the max key of rbtree
**/
int RbTreeGetMaxKey(UserRbTree userRbTree, UserKey *pUserKey);

/**
    get the nodelist from the instance that key between userKeyMin and userKeyMax,
    the value will be save in userNodeList.
    userNodeList: the space to save result, the mem must be alloc out of api
    size: the count of node in userNodeList
    userKeyMin: the min userKey
    userKeyMax: the max userKey
	return >=0 the number of node save in userNodeList
	< 0: error occure
**/
int RbTreeGetNodeListBetween(UserRbTree userRbTree, UserNode *userNodeList, int size, UserKey userKeyMin, UserKey userKeyMax);

#endif
<file_sep>/*
 * =============================================================================
 *
 *       Filename:  api_test.c
 *
 *    Description:  test code for rbtree_api to use.
 *
 *        Created:  09/30/2019 11:39:34 PM
 *
 *         Author:  <NAME>, <EMAIL>
 *
 * =============================================================================
 */


#include "rbtree.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "rbtree_api.h"

static void DeleteValueObject(UserValue userValue) {
    if(userValue) {
        free(userValue);
        printf("free ok for [%p]", userValue);
    }
}

void doRbTreeTest()
{
    int ret, index;
    UserKey minUserKey, maxUserKey;
    UserNode userNode;
    UserRbTree userRbTree = RbTreeCreate(NULL, DeleteValueObject);
    if(userRbTree == NULL) {
        return;
    }
    RbTreeInsert(userRbTree, MK_KEY(1), MK_VALUE(strdup("1")));
    RbTreeInsert(userRbTree, MK_KEY(10), MK_VALUE(strdup("10")));
    RbTreeInsert(userRbTree, MK_KEY(5), MK_VALUE(strdup("5")));
    RbTreeInsert(userRbTree, MK_KEY(7), MK_VALUE(strdup("7")));
    RbTreeInsert(userRbTree, MK_KEY(4), MK_VALUE(strdup("4")));
    RbTreeInsert(userRbTree, MK_KEY(3), MK_VALUE(strdup("3")));
    RbTreeInsert(userRbTree, MK_KEY(9), MK_VALUE(strdup("9")));

    printf("treesize: %d\n", RbTreeGetSize(userRbTree));
    RbTreeDump(userRbTree);
    RbTreeSearch(userRbTree, MK_KEY(4), &userNode);
    RbTreeRemove(userRbTree, userNode);
    printf("after delete treesize: %d\n", RbTreeGetSize(userRbTree));
    RbTreeDump(userRbTree);
    RbTreeGetMinKey(userRbTree, &minUserKey);
    RbTreeGetMaxKey(userRbTree, &maxUserKey);
    printf("minkey:%ld, maxkey:%ld\n", (long)minUserKey, (long)maxUserKey);
    UserNode *userNodeList = malloc(sizeof(UserNode) * 3);
    ret = RbTreeGetNodeListBetween(userRbTree, userNodeList, 3, (UserKey)3, (UserKey)12);
    printf("we got size:%d\n", ret);
    for(index = 0; index < ret; index++) {
        printf("---->{%ld}\n", (long)RbTreeGetKeyFromNode(userNodeList[index]));
    }

    RbTreeClear(userRbTree);
    printf("after clear treesize: %d\n", RbTreeGetSize(userRbTree));
    RbTreeInsert(userRbTree, MK_KEY(1), MK_VALUE(strdup("1")));
    RbTreeInsert(userRbTree, MK_KEY(10), MK_VALUE(strdup("10")));
    RbTreeInsert(userRbTree, MK_KEY(5), MK_VALUE(strdup("5")));
    RbTreeInsert(userRbTree, MK_KEY(7), MK_VALUE(strdup("7")));
    RbTreeInsert(userRbTree, MK_KEY(4), MK_VALUE(strdup("4")));
    RbTreeInsert(userRbTree, MK_KEY(3), MK_VALUE(strdup("3")));
    RbTreeInsert(userRbTree, MK_KEY(9), MK_VALUE(strdup("9")));
    printf("after insert treesize: %d\n", RbTreeGetSize(userRbTree));
    ret = RbTreeGetNodeListBetween(userRbTree, userNodeList, 3, (UserKey)3, (UserKey)12);
    printf("we got size:%d\n", ret);
    for(index = 0; index < ret; index++) {
        printf("---->{%ld}\n", (long)RbTreeGetKeyFromNode(userNodeList[index]));
    }
    free(userNodeList);
    RbTreeDestory(userRbTree);
    printf("doRbTreeTest end\n");
}

int main()
{
    doRbTreeTest();
	return 0;
}


<file_sep># RbTree

A simple api for rbtree. We support insert, delete, search, query. And can be used in develop work easy
<file_sep>CC = gcc 
LD = gcc

SRCS = $(wildcard *.c)

OBJS = $(patsubst %c, %o, $(SRCS))

TARGET = RbTreeTest

.PHONY:all clean
all: $(TARGET)
$(TARGET): $(OBJS)
	$(LD) -o $@ $^

%o:%c
	$(CC) -c $^
clean:
	rm -f $(OBJS) $(TARGET)	<file_sep>/*
 * =============================================================================
 *
 *       Filename:  rbtree_api.c
 *
 *    Description:  api for rbtree to use.
 *
 *        Created:  09/30/2019 11:39:34 PM
 *
 *         Author:  <NAME>, <EMAIL>
 *
 * =============================================================================
 */

#include "rbtree.h"
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include "rbtree_api.h"
//#define DEBUG
#ifdef DEBUG
#define RECORD_MEM(isMalloc, addr) \
    do {\
        if(isMalloc) {\
            printf("malloc(%p)\n", addr);}\
        else {\
            printf("free(%p)\n", addr);}\
        }while(0)
#define API_DEBUG   printf
#else
#define RECORD_MEM(isMalloc, addr)
#define API_DEBUG(formate...) 
#endif
typedef struct UserRbTreeImpl {
	struct rb_root tree;
    int nodeNum;
    CompareKeyFun compareKeyFun;
    DeleteValueObjectFun deleteValueObjectFun;
}UserRbTreeImpl_t;

typedef struct UserNodeImpl {
	struct rb_node node;
	UserKey key;
	UserValue value;
}UserNodeImpl_t;

static int compareKeyDefault(UserKey key1, UserKey key2) {
    if(key1 > key2) {
        return 1;
    }
    else if(key1 < key2) {
        return -1;
    }
    else {
        return 0;
    }
}


UserRbTree RbTreeCreate(CompareKeyFun compareFun, DeleteValueObjectFun deleteValueObjFun) {
	UserRbTreeImpl_t *userRbTreeImpl = malloc(sizeof(UserRbTreeImpl_t));
	if(userRbTreeImpl) {
        RECORD_MEM(1, userRbTreeImpl);
		userRbTreeImpl->tree = RB_ROOT;
        if(compareFun) {
            userRbTreeImpl->compareKeyFun = compareFun;
        }
        else {
            userRbTreeImpl->compareKeyFun = compareKeyDefault;
        }
        userRbTreeImpl->deleteValueObjectFun = deleteValueObjFun;
        userRbTreeImpl->nodeNum = 0;
	}
	return userRbTreeImpl;
}

static void deleteNode(DeleteValueObjectFun deleteValueObjectFun, struct rb_node *node) {
    if(node) {
        UserNodeImpl_t *data = (UserNodeImpl_t *)node;
        API_DEBUG("going to delete node value[%p, %p]\n", deleteValueObjectFun, data->value);
        if(deleteValueObjectFun && data->value) {
           deleteValueObjectFun(data->value); 
        }
        deleteNode(deleteValueObjectFun, node->rb_left);
        deleteNode(deleteValueObjectFun, node->rb_right);
        RECORD_MEM(0, node);
        free(node);
    }
}

void RbTreeDestory(UserRbTree userRbTree) {
	UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
	if(pUserRbTreeImpl) {
        struct rb_node *node = pUserRbTreeImpl->tree.rb_node;
        deleteNode(pUserRbTreeImpl->deleteValueObjectFun, node);
        RECORD_MEM(0, pUserRbTreeImpl);
		free(pUserRbTreeImpl);
	}
}

void RbTreeClear(UserRbTree userRbTree)
{
	UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
	if(pUserRbTreeImpl) {
        struct rb_node *node = pUserRbTreeImpl->tree.rb_node;
        deleteNode(pUserRbTreeImpl->deleteValueObjectFun, node);
        pUserRbTreeImpl->tree = RB_ROOT;
        pUserRbTreeImpl->nodeNum = 0;
	}    
}

int RbTreeSearch(UserRbTree userRbTree, UserKey userKey, UserNode *pUserNode)
{
	if(userRbTree && pUserNode) {
		UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
	  	struct rb_node *node = pUserRbTreeImpl->tree.rb_node;

	  	while (node) {
	  		UserNodeImpl_t *data = (UserNodeImpl_t *)node;
			int result;

			result = pUserRbTreeImpl->compareKeyFun(userKey, data->key);

			if (result < 0)
	  			node = node->rb_left;
			else if (result > 0)
	  			node = node->rb_right;
			else {
				*pUserNode = data;
				return 0;
			}
		}
	}
	return -1;
}

int RbTreeInsert(UserRbTree userRbTree, UserKey userKey, UserValue userValue)
{
    if(userRbTree) {
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        struct rb_node **newNode = &(pUserRbTreeImpl->tree.rb_node), *parent = NULL;
        UserNodeImpl_t *rbTreeData = NULL;
      	/* Figure out where to put new node */
      	while (*newNode) {
            UserNodeImpl_t *data = (UserNodeImpl_t *)(*newNode);

      		int result = pUserRbTreeImpl->compareKeyFun(userKey, data->key);

    		parent = *newNode;
      		if (result < 0)
      			newNode = &((*newNode)->rb_left);
      		else if (result > 0)
      			newNode = &((*newNode)->rb_right);
      		else
      			return 0;
      	} 
        rbTreeData = malloc(sizeof(UserNodeImpl_t));
        if(rbTreeData == NULL) {
            return -2;
        }
        RECORD_MEM(1, rbTreeData);
        rbTreeData->key = userKey;
        rbTreeData->value = userValue;
        pUserRbTreeImpl->nodeNum++;
        
      	/* Add new node and rebalance tree. */
      	rb_link_node(&rbTreeData->node, parent, newNode);
      	rb_insert_color(&rbTreeData->node, &pUserRbTreeImpl->tree);

    	return 1;
    }

	return -1;
}

int RbTreeRemove(UserRbTree userRbTree, UserNode node)
{
    if(userRbTree && node) {
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        UserNodeImpl_t * pUserNodeImpl = (UserNodeImpl_t *)node;
        rb_erase(&pUserNodeImpl->node, &pUserRbTreeImpl->tree);
        RECORD_MEM(0, pUserNodeImpl);
        free(pUserNodeImpl);
        pUserRbTreeImpl->nodeNum--;
    }

    return 0;
}

UserValue RbTreeGetValueFromNode(UserNode node)
{
    UserNodeImpl_t * pUserNodeImpl = (UserNodeImpl_t *)node;
    return pUserNodeImpl->value;
}

UserKey RbTreeGetKeyFromNode(UserNode node) 
{
    UserNodeImpl_t * pUserNodeImpl = (UserNodeImpl_t *)node;
    return pUserNodeImpl->key;    
}

int RbTreeGetSize(UserRbTree userRbTree) {
    if(userRbTree) {
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        return pUserRbTreeImpl->nodeNum;
    }
    return 0;
}

void RbTreeDump(UserRbTree userRbTree) {
    if(userRbTree) {
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        struct rb_node *node;
        for (node = rb_first(&pUserRbTreeImpl->tree); node; node = rb_next(node)) {
            
            printf("key = %ld\n", (long)((UserNodeImpl_t *)node)->key);

        }

    }
    
}

int RbTreeGetMinKey(UserRbTree userRbTree, UserKey *pUserKey)
{
    if(userRbTree) {
        UserNodeImpl_t * pUserNodeImpl = NULL;
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        struct rb_node *node = pUserRbTreeImpl->tree.rb_node;
        if(node) {
            while (node->rb_left) {
                node = node->rb_left;
            }
            pUserNodeImpl = (UserNodeImpl_t *)node;
            *pUserKey = pUserNodeImpl->key;
            return 0;
        }
        else {
            return -1;
        }
    }
    return -2;
}

int RbTreeGetMaxKey(UserRbTree userRbTree, UserKey *pUserKey)
{
    if(userRbTree) {
        UserNodeImpl_t * pUserNodeImpl = NULL;
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        struct rb_node *node = pUserRbTreeImpl->tree.rb_node;
        if(node) {
            while (node->rb_right) {
                node = node->rb_right;
            }
            pUserNodeImpl = (UserNodeImpl_t *)node;
            *pUserKey = pUserNodeImpl->key;
            return 0;
        }
        else {
            return -1;
        }
    }
    return -2;

}

int RbTreeGetNodeListBetween(UserRbTree userRbTree, UserNode *userNodeList, int size, UserKey userKeyMin, UserKey userKeyMax)
{
    if(userRbTree && userNodeList && size > 0) {
        UserRbTreeImpl_t *pUserRbTreeImpl = userRbTree;
        struct rb_node **newNode = &(pUserRbTreeImpl->tree.rb_node), *parent = NULL;
        UserNodeImpl_t *rbTreeData = NULL;
        int result = -2;
        int curSize = 0;
      	/* Figure out where to put new node */
      	while (*newNode) {
            UserNodeImpl_t *data = (UserNodeImpl_t *)(*newNode);

      		result = pUserRbTreeImpl->compareKeyFun(userKeyMin, data->key);
            parent = *newNode;

    		rbTreeData = (UserNodeImpl_t *)(*newNode);
            API_DEBUG("####rbTreeData-->key:%ld, result:%d\n", (long)rbTreeData->key, result);
      		if (result <= 0) {
      			newNode = &((*newNode)->rb_left);
                
            }
      		else if (result > 0) {
      			newNode = &((*newNode)->rb_right);

            }  
      	} 
        if(parent) {
            if(result <= 0) {
                
            }
            else {
                parent = rb_next(parent);
            }
        }
        else {
            parent = rb_first(&pUserRbTreeImpl->tree);
        }

        struct rb_node *node;
        for (node = parent; node; node = rb_next(node)) {
            result = pUserRbTreeImpl->compareKeyFun(userKeyMax, ((UserNodeImpl_t *)node)->key);
            
            if(result >= 0) {
                API_DEBUG("====>key = %ld, result:%d\n", (long)((UserNodeImpl_t *)node)->key, result);
                if(curSize < size) {
                    userNodeList[curSize] = (UserNode)node;
                    curSize++;
                }
                else {
                    break;
                }
            }
            else {
                break;
            }

        }
        return curSize;

    }
    return -1;
}
