主要是使用红黑树这种数据结构封装一个MAP容器,本来想模仿STL MAP,不过现在暂时实现,今后会改进,目前还没实现加锁这功能,不过可以支持win32和linux平台。。。
以下是源代码:
- /*
-
* file: main.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-31
-
*/
-
-
#define DEBUG
-
-
#include <stdio.h>
-
#include <time.h>
-
#include <stdlib.h>
-
#include <string.h>
-
-
#include "map.h"
-
-
#ifdef DEBUG
-
#define dump(a,s) __dump((a),(s))
-
#else
-
#define dump(a,s)
-
#endif
-
-
-
typedef struct word_info {
-
unsigned long hash_major;
-
unsigned long hash_minor;
-
char *path;
-
unsigned long line;
-
unsigned long col;
-
}word_info_t;
-
-
typedef struct priv_info {
-
unsigned long key;
-
char val[10];
-
}priv_info_t;
-
-
-
static void __dump(priv_info_t *array, size_t num)
-
{
-
int i;
-
printf("-- DUMP START -- \n");
-
for (i=0; i < num; i++)
-
{
-
printf("array[%d].key=%03d, array[%d].val=%s\n",
-
i, array[i].key, i, array[i].val);
-
}
-
printf("-- DUMP END -- \n");
-
}
-
-
#define map_info(pm) {\
-
printf("-- dump map start ... --\n"); \
-
map_dump(pm); \
-
printf("-- dump map end ... --\n"); \
-
}
-
-
#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))
-
-
#define MAX_NUM 20
-
-
int main()
-
{
-
map_t map1;
-
int key;
-
int i, j;
-
priv_info_t priv_info[MAX_NUM];
-
-
srand(time(0));
-
-
memset(priv_info, 0, sizeof(priv_info));
-
for (i=0; i<MAX_NUM; i++)
-
{
-
key = rand()%MAX_NUM;
-
priv_info[i].key = key;
-
sprintf(priv_info[i].val, "i am %d", key);
-
}
-
dump(priv_info, ARRAY_SIZE(priv_info));
-
-
map_init(&map1);
-
-
i = 0;
-
while (i < MAX_NUM)
-
{
-
struct mnode* node;
-
printf("-- %d -- \n", i);
-
node = map_find(&map1,&(priv_info[i].key), NULL);
-
if (!node) {
-
printf("->>> insert node: priv_info[%d].key=%d \n", i, priv_info[i].key);
-
map_insert_alloc(&map1, &(priv_info[i].key),
-
&priv_info[i], sizeof(priv_info[i]), NULL);
-
} else {
-
/* key not matched, so just print out */
-
printf("priv_info[%d].key=%d is exist!\n", i, priv_info[i].key);
-
for (j=0; j < MAX_NUM; j++) {
-
if(priv_info[j].key == priv_info[i].key && i!=j)
-
printf("\t|-- priv_info[%d].key=%d\n", j, priv_info[j].key);
-
}
-
}
-
map_info(&map1);
-
-
i++;
-
}
-
map_info(&map1);
-
-
printf("-----------------------------------\n");
-
for (i=0; i < MAX_NUM; i++)
-
{
-
struct mnode* node;
-
node = map_find(&map1,&i, NULL);
-
if (node){
-
map_remove_free(&map1, &i, NULL);
-
printf("--> key=%03d deleted!\n", i);
-
map_info(&map1);
-
}else{
-
printf("key=%03d not found!\n", i);
-
}
-
}
-
map_info(&map1);
-
-
map_exit(&map1);
-
return 0;
-
}
.............................................................................................
.............................................................................................
- /*
-
* file: map.h
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-31
-
*/
-
#ifndef __MAP_H__
-
#define __MAP_H__
-
-
#include <stdlib.h>
-
#include "platform.h"
-
#include "rbtree.h"
-
-
#define lock_t int
-
#define lock_init(x)
-
#define lock_exit(x)
-
-
#ifndef NULL
-
#define NULL 0
-
#endif
-
-
#define __assert(x)
-
#define __free(x) free(x)
-
#define __malloc(x) malloc(x)
-
#define __memcpy(d,s,len) memcpy((d),(s),(len))
-
-
extern struct map;
-
-
typedef int (*CMP_FUNC)(const void *d1, const void *d2);
-
-
typedef struct mnode{
-
struct rb_node node;
-
void *key;
-
void *private;
-
}mnode_t;
-
-
/*
-
typedef struct ops{
-
struct mnode*(*find)(struct map *map, void *key, CMP_FUNC cmpf);
-
int (*insert_alloc)(struct map *map, void *key,
-
void *private, size_t size, CMP_FUNC cmpf);
-
int (*remove_free)(struct map *map, void *key, CMP_FUNC cmpf);
-
int (*insert)(struct map *map, struct mnode *data, CMP_FUNC cmpf);
-
int (*remove)(struct map *map, void *key, CMP_FUNC cmpf);
-
}ops_t;
-
*/
-
-
typedef struct map{
-
struct rb_root root;
-
lock_t lock;
-
}map_t;
-
-
extern int map_init(struct map* map);
-
extern int map_exit(struct map* map);
-
-
struct mnode* __rbfind(struct map *map, void *key, CMP_FUNC cmpf);
-
int __rbinsert_alloc(struct map *map, void *key,
-
void *private, size_t size, CMP_FUNC cmpf);
-
int __rbremove_free(struct map *map, void *key, CMP_FUNC cmpf);
-
int __rbinsert(struct map *map, struct mnode *data, CMP_FUNC cmpf);
-
int __rbremove(struct map *map, void *key, CMP_FUNC cmpf);
-
-
#define map_find(map,key,cmpf) \
-
__rbfind((map),(key),(cmpf))
-
-
#define map_insert_alloc(map,key,priv,size,cmpf) \
-
__rbinsert_alloc((map),(key),(priv),(size),(cmpf))
-
-
#define map_remove_free(map,key,cmpf) \
-
__rbremove_free((map),(key),(cmpf))
-
-
#if 0
-
#define map_insert(map,data,cmpf) \
-
__rbinsert((map),(data),(cmpf))
-
#define map_remove(map,key,cmpf) \
-
__rbremove((map),(key),(cmpf))
-
#endif
-
-
-
#define map_entry(ptr, type, member) container_of(ptr, type, member)
-
-
extern struct mnode *map_first(const struct map *map);
-
extern struct mnode *map_last(const struct map *map);
-
extern struct mnode *map_next(const struct mnode *mnode);
-
extern struct mnode *map_prev(const struct mnode *mnode);
-
-
extern void map_dump(const struct map* map);
-
-
-
#endif
.............................................................................................
.............................................................................................
- /*
-
* file: map.c
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-31
-
*/
-
#define DEBUG
-
#include "map.h"
-
-
#define mnode_init(mnode) {\
-
(mnode)->node.rb_parent_color=0; \
-
(mnode)->node.rb_right=0; \
-
(mnode)->node.rb_left=0; \
-
(mnode)->key=0; \
-
(mnode)->private=0; \
-
}
-
-
-
void map_dump(const struct map* map)
-
{
-
struct mnode *mnode;
-
int cnt=0;
-
for (mnode = map_first(map); mnode; mnode = map_next(mnode))
-
printf("key=%03d%s", *(int*)mnode->key, ++cnt%10==0?"\n":" ");
-
printf("\n");
-
}
-
-
-
static int __cmp_default(long *d1, long *d2)
-
{
-
// printf("-- d1:%d, d2:%d\n", *d1, *d2);
-
if (*d1 < *d2) return -1;
-
else if (*d1 > *d2) return 1;
-
else return 0;
-
}
-
-
struct mnode* __rbfind(struct map *map, void *key, CMP_FUNC cmpf)
-
{
-
int result;
-
CMP_FUNC cmp;
-
struct mnode *data;
-
struct rb_node *node = map->root.rb_node;
-
-
__assert(map && key);
-
-
cmp = cmpf ? cmpf : __cmp_default;
-
/* printf("==> entry %s key:%d\n", __func__, *(int*)key); */
-
while (node)
-
{
-
data = container_of(node, struct mnode, node);
-
/* printf("data->key:%d VS key:%d\n", *(int*)(data->key), *(int*)key);*/
-
result = cmp(key, data->key);
-
/*printf("result=%d, node->rb_left=%p, node->rb_right=%p\n",
-
result, node->rb_left, node->rb_right);*/
-
if (result < 0)
-
node = node->rb_left;
-
else if (result > 0)
-
node = node->rb_right;
-
else
-
return data;
-
}
-
//printf("node=%p\n", node);
-
return NULL;
-
}
-
-
int __rbinsert(struct map *map, struct mnode *data, CMP_FUNC cmpf)
-
{
-
int result;
-
struct mnode *this;
-
CMP_FUNC cmp;
-
struct rb_node **new = &(map->root.rb_node), *parent = NULL;
-
-
__assert(map && data);
-
-
cmp = cmpf ? cmpf : __cmp_default;
-
-
/* Figure out where to put new node */
-
while (*new)
-
{
-
this = container_of(*new, struct mnode, node);
-
result = cmp(data->key, this->key);
-
-
parent = *new;
-
if (result < 0) new = &((*new)->rb_left);
-
else if (result > 0) new = &((*new)->rb_right);
-
else return -2;
-
}
-
/* Add new node and rebalance tree. */
-
rb_link_node(&(data->node), parent, new);
-
rb_insert_color(&(data->node), &(map->root));
-
return 0;
-
}
-
-
int __rbremove(struct map *map, void *key, CMP_FUNC cmpf)
-
{
-
struct mnode* data = __rbfind(map, key, cmpf);
-
__assert(map && key);
-
if (data)
-
rb_erase(&(data->node), &(map->root));
-
return 0;
-
}
-
-
int __rbinsert_alloc(struct map *map, void *key,
-
void *private, size_t size, CMP_FUNC cmpf)
-
{
-
struct mnode *new;
-
__assert(map && key && private);
-
new = (struct mnode*)__malloc(size+sizeof(struct mnode));
-
__assert(new);
-
mnode_init(new);
-
new->key = key;
-
new->private = new+1;
-
if (private)
-
__memcpy(new->private, private, size);
-
-
return __rbinsert(map, new, cmpf);
-
}
-
-
int __rbremove_free(struct map *map, void *key, CMP_FUNC cmpf)
-
{
-
struct mnode* data;
-
__assert(map && key);
-
data = __rbfind(map, key, cmpf);
-
/* printf("%s: key: %d\n", __func__, *(int*)(data->key)); */
-
if (data)
-
{
-
/* printf("%s: deleted!\n", __func__);*/
-
rb_erase(&(data->node), &(map->root));
-
__free(data);
-
}
-
return 0;
-
}
-
-
struct mnode *map_first(const struct map *map)
-
{
-
struct rb_node *node;
-
__assert(map);
-
node = rb_first(&(map->root));
-
if(node)
-
return map_entry(node, struct mnode, node);
-
return NULL;
-
}
-
-
struct mnode *map_last(const struct map *map)
-
{
-
struct rb_node *node;
-
__assert(map);
-
node = rb_last(&(map->root));
-
if(node)
-
return map_entry(node, struct mnode, node);
-
return NULL;
-
}
-
-
struct mnode *map_next(const struct mnode *mnode)
-
{
-
struct rb_node *node;
-
__assert(mnode);
-
node = rb_next(&(mnode->node));
-
if(node)
-
return map_entry(node, struct mnode, node);
-
return NULL;
-
}
-
-
struct mnode *map_prev(const struct mnode *mnode)
-
{
-
struct rb_node *node;
-
__assert(mnode);
-
node = rb_prev(&(mnode->node));
-
if(node)
-
return map_entry(node, struct mnode, node);
-
return NULL;
-
}
-
-
-
int map_init(struct map* map)
-
{
-
map->root.rb_node = NULL;
-
lock_init(map->lock);
-
return 0;
-
}
-
-
int map_exit(struct map* map)
-
{
-
lock_exit(map->lock);
-
return 0;
-
}
.............................................................................................
.............................................................................................
- /*
-
* file: platform.h
-
* author: vincent.cws2008@gmail.com
-
* history:
-
* initial @ 2012-01-31
-
*/
-
-
#ifndef __PLATFORM_H__
-
#define __PLATFORM_H__
-
-
#ifndef NULL
-
#define NULL 0
-
#endif
-
-
#ifndef offsetof
-
#define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
-
#endif
-
-
#ifdef WIN32
-
-
# ifndef container_of
-
# define container_of(ptr, type, member) ((type *)( (char *)ptr-offsetof(type,member)))
-
# endif
-
-
# define inline __inline
-
-
# define __attribute__(x) __declspec(align(4));
-
-
#else /* platform: UNIX or Linux */
-
-
# ifndef container_of
-
# define container_of(ptr, type, member) ({ \
-
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
-
(type *)( (char *)__mptr - offsetof(type,member) );})
-
# endif
-
-
# include
-
# include
-
-
#endif
-
-
-
-
#endif
.............................................................................................
.............................................................................................
- #Makefile
-
-
TARGET := main
-
RM := rm
-
-
CC := gcc
-
-
MK := make
-
-
SRCS := rbtree.c map.c main.c
-
-
OBJS := $(subst .c,.o,$(SRCS))
-
-
-
$(TARGET): $(OBJS)
-
$(CC) $(OBJS) -o $@
-
-
default:
-
$(MK) $(TARGET)
-
-
clean:
-
$(RM) $(OBJS) $(TARGET)
-
-
# common part
-
%.o: %.c
-
$(CC) -c $< -Wall -o $@
okay, 收工。。。
附件:
map.rar
阅读(8991) | 评论(0) | 转发(1) |