Chinaunix首页 | 论坛 | 博客

路漫漫vincent.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

vincent-cws

  • 博客访问： 943051
  • 博文数量： 116
  • 博客积分： 3923
  • 博客等级： 中校
  • 技术积分： 1337
  • 用 户 组： 普通用户
  • 注册时间： 2009-04-23 01:22
文章分类

全部博文（116）

文章存档

2013年（1）

2012年（17）

2011年（69）

2009年（29）

我的朋友
最近访客
推荐博文
相关博文
红黑树封装--map容器C代码实现

分类： LINUX

2012-01-31 21:05:48

主要是使用红黑树这种数据结构封装一个MAP容器，本来想模仿STL MAP，不过现在暂时实现，今后会改进，目前还没实现加锁这功能，不过可以支持win32和linux平台。。。

以下是源代码:

  1. /*
  2.  * file: main.c
  3.  * author: vincent.cws2008@gmail.com
  4.  * history:
  5.  * initial @ 2012-01-31
  6.  */

  8. #define DEBUG

  10. #include <stdio.h>
  11. #include <time.h>
  12. #include <stdlib.h>
  13. #include <string.h>

  15. #include "map.h"

  17. #ifdef DEBUG
  18. #define dump(a,s) __dump((a),(s))
  19. #else
  20. #define dump(a,s)
  21. #endif


  24. typedef struct word_info {
  25.     unsigned long hash_major;
  26.     unsigned long hash_minor;
  27.     char *path;
  28.     unsigned long line;
  29.     unsigned long col;
  30. }word_info_t;

  32. typedef struct priv_info {
  33.     unsigned long key;
  34.     char val[10];
  35. }priv_info_t;


  38. static void __dump(priv_info_t *array, size_t num)
  39. {
  40.     int i;
  41.     printf("-- DUMP START -- \n");
  42.     for (i=0; i < num; i++)
  43.     {
  44.         printf("array[%d].key=%03d, array[%d].val=%s\n",
  45.             i, array[i].key, i, array[i].val);
  46.     }
  47.     printf("-- DUMP END -- \n");
  48. }

  50. #define map_info(pm) {\
  51.     printf("-- dump map start ... --\n"); \
  52.     map_dump(pm); \
  53.     printf("-- dump map end ... --\n"); \
  54. }

  56. #define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

  58. #define MAX_NUM 20

  60. int main()
  61. {
  62.     map_t map1;
  63.     int key;
  64.     int i, j;
  65.     priv_info_t priv_info[MAX_NUM];
  66.     
  67.     srand(time(0));
  68.     
  69.     memset(priv_info, 0, sizeof(priv_info));
  70.     for (i=0; i<MAX_NUM; i++)
  71.     {
  72.         key = rand()%MAX_NUM;
  73.         priv_info[i].key = key;
  74.         sprintf(priv_info[i].val, "i am %d", key);
  75.     }
  76.     dump(priv_info, ARRAY_SIZE(priv_info));
  77.     
  78.     map_init(&map1);
  79.     
  80.     i = 0;
  81.     while (i < MAX_NUM)
  82.     {
  83.         struct mnode* node;
  84.         printf("-- %d -- \n", i);
  85.         node = map_find(&map1,&(priv_info[i].key), NULL);
  86.         if (!node) {
  87.             printf("->>> insert node: priv_info[%d].key=%d \n", i, priv_info[i].key);
  88.             map_insert_alloc(&map1, &(priv_info[i].key),
  89.                 &priv_info[i], sizeof(priv_info[i]), NULL);
  90.         } else {
  91.             /* key not matched, so just print out */
  92.             printf("priv_info[%d].key=%d is exist!\n", i, priv_info[i].key);
  93.             for (j=0; j < MAX_NUM; j++) {
  94.                 if(priv_info[j].key == priv_info[i].key && i!=j)
  95.                     printf("\t|-- priv_info[%d].key=%d\n", j, priv_info[j].key);
  96.             }
  97.         }
  98.         map_info(&map1);
  99.         
  100.         i++;
  101.     }
  102.     map_info(&map1);
  103.     
  104.     printf("-----------------------------------\n");
  105.     for (i=0; i < MAX_NUM; i++)
  106.     {
  107.         struct mnode* node;
  108.         node = map_find(&map1,&i, NULL);
  109.         if (node){
  110.             map_remove_free(&map1, &i, NULL);
  111.             printf("--> key=%03d deleted!\n", i);
  112.             map_info(&map1);
  113.         }else{
  114.             printf("key=%03d not found!\n", i);
  115.         }
  116.     }
  117.     map_info(&map1);
  118.     
  119.     map_exit(&map1);
  120.     return 0;
  121. }

.............................................................................................
.............................................................................................


  1. /*
  2.  * file: map.h
  3.  * author: vincent.cws2008@gmail.com
  4.  * history:
  5.  * initial @ 2012-01-31
  6.  */
  7. #ifndef __MAP_H__
  8. #define __MAP_H__

  10. #include <stdlib.h>
  11. #include "platform.h"
  12. #include "rbtree.h"

  14. #define lock_t int
  15. #define lock_init(x)
  16. #define lock_exit(x)

  18. #ifndef NULL
  19. #define NULL 0
  20. #endif

  22. #define __assert(x)
  23. #define __free(x) free(x)
  24. #define __malloc(x) malloc(x)
  25. #define __memcpy(d,s,len) memcpy((d),(s),(len))

  27. extern struct map;

  29. typedef int (*CMP_FUNC)(const void *d1, const void *d2);

  31. typedef struct mnode{
  32.   struct rb_node node;
  33.   void *key;
  34.   void *private;
  35. }mnode_t;

  37. /*
  38. typedef struct ops{
  39.   struct mnode*(*find)(struct map *map, void *key, CMP_FUNC cmpf);
  40.   int (*insert_alloc)(struct map *map, void *key,
  41.                       void *private, size_t size, CMP_FUNC cmpf);
  42.   int (*remove_free)(struct map *map, void *key, CMP_FUNC cmpf);
  43.   int (*insert)(struct map *map, struct mnode *data, CMP_FUNC cmpf);
  44.   int (*remove)(struct map *map, void *key, CMP_FUNC cmpf);
  45. }ops_t;
  46. */

  48. typedef struct map{
  49.   struct rb_root root;
  50.   lock_t lock;
  51. }map_t;

  53. extern int map_init(struct map* map);
  54. extern int map_exit(struct map* map);

  56. struct mnode* __rbfind(struct map *map, void *key, CMP_FUNC cmpf);
  57. int __rbinsert_alloc(struct map *map, void *key,
  58.                      void *private, size_t size, CMP_FUNC cmpf);
  59. int __rbremove_free(struct map *map, void *key, CMP_FUNC cmpf);
  60. int __rbinsert(struct map *map, struct mnode *data, CMP_FUNC cmpf);
  61. int __rbremove(struct map *map, void *key, CMP_FUNC cmpf);

  63. #define map_find(map,key,cmpf) \
  64.   __rbfind((map),(key),(cmpf))

  66. #define map_insert_alloc(map,key,priv,size,cmpf) \
  67.   __rbinsert_alloc((map),(key),(priv),(size),(cmpf))

  69. #define map_remove_free(map,key,cmpf) \
  70.   __rbremove_free((map),(key),(cmpf))

  72. #if 0
  73. #define map_insert(map,data,cmpf) \
  74.   __rbinsert((map),(data),(cmpf))
  75. #define map_remove(map,key,cmpf) \
  76.   __rbremove((map),(key),(cmpf))
  77. #endif


  80. #define map_entry(ptr, type, member) container_of(ptr, type, member)

  82. extern struct mnode *map_first(const struct map *map);
  83. extern struct mnode *map_last(const struct map *map);
  84. extern struct mnode *map_next(const struct mnode *mnode);
  85. extern struct mnode *map_prev(const struct mnode *mnode);

  87. extern void map_dump(const struct map* map);


  90. #endif
.............................................................................................
.............................................................................................

  1. /*
  2.  * file: map.c
  3.  * author: vincent.cws2008@gmail.com
  4.  * history:
  5.  * initial @ 2012-01-31
  6.  */
  7. #define DEBUG
  8. #include "map.h"

  10. #define mnode_init(mnode) {\
  11.     (mnode)->node.rb_parent_color=0; \
  12.     (mnode)->node.rb_right=0; \
  13.     (mnode)->node.rb_left=0; \
  14.     (mnode)->key=0; \
  15.     (mnode)->private=0; \
  16. }


  19. void map_dump(const struct map* map)
  20. {
  21.     struct mnode *mnode;
  22.     int cnt=0;
  23.     for (mnode = map_first(map); mnode; mnode = map_next(mnode))
  24.         printf("key=%03d%s", *(int*)mnode->key, ++cnt%10==0?"\n":" ");
  25.     printf("\n");
  26. }


  29. static int __cmp_default(long *d1, long *d2)
  30. {
  31.     // printf("-- d1:%d, d2:%d\n", *d1, *d2);
  32.     if (*d1 < *d2) return -1;
  33.     else if (*d1 > *d2) return 1;
  34.     else return 0;
  35. }

  37. struct mnode* __rbfind(struct map *map, void *key, CMP_FUNC cmpf)
  38. {
  39.     int result;
  40.     CMP_FUNC cmp;
  41.     struct mnode *data;
  42.     struct rb_node *node = map->root.rb_node;
  43.     
  44.     __assert(map && key);
  45.     
  46.     cmp = cmpf ? cmpf : __cmp_default;
  47.     /* printf("==> entry %s key:%d\n", __func__, *(int*)key); */
  48.     while (node)
  49.     {
  50.         data = container_of(node, struct mnode, node);
  51.         /* printf("data->key:%d VS key:%d\n", *(int*)(data->key), *(int*)key);*/
  52.         result = cmp(key, data->key);
  53.         /*printf("result=%d, node->rb_left=%p, node->rb_right=%p\n",
  54.         result, node->rb_left, node->rb_right);*/
  55.         if (result < 0)
  56.             node = node->rb_left;
  57.         else if (result > 0)
  58.             node = node->rb_right;
  59.         else
  60.             return data;
  61.     }
  62.     //printf("node=%p\n", node);
  63.     return NULL;
  64. }

  66. int __rbinsert(struct map *map, struct mnode *data, CMP_FUNC cmpf)
  67. {
  68.     int result;
  69.     struct mnode *this;
  70.     CMP_FUNC cmp;
  71.     struct rb_node **new = &(map->root.rb_node), *parent = NULL;
  72.     
  73.     __assert(map && data);
  74.     
  75.     cmp = cmpf ? cmpf : __cmp_default;
  76.     
  77.     /* Figure out where to put new node */
  78.     while (*new)
  79.     {
  80.         this = container_of(*new, struct mnode, node);
  81.         result = cmp(data->key, this->key);
  82.         
  83.         parent = *new;
  84.         if (result < 0) new = &((*new)->rb_left);
  85.         else if (result > 0) new = &((*new)->rb_right);
  86.         else return -2;
  87.     }
  88.     /* Add new node and rebalance tree. */
  89.     rb_link_node(&(data->node), parent, new);
  90.     rb_insert_color(&(data->node), &(map->root));
  91.     return 0;
  92. }

  94. int __rbremove(struct map *map, void *key, CMP_FUNC cmpf)
  95. {
  96.     struct mnode* data = __rbfind(map, key, cmpf);
  97.     __assert(map && key);
  98.     if (data)
  99.         rb_erase(&(data->node), &(map->root));
  100.     return 0;
  101. }

  103. int __rbinsert_alloc(struct map *map, void *key,
  104.                      void *private, size_t size, CMP_FUNC cmpf)
  105. {
  106.     struct mnode *new;
  107.     __assert(map && key && private);
  108.     new = (struct mnode*)__malloc(size+sizeof(struct mnode));
  109.     __assert(new);
  110.     mnode_init(new);
  111.     new->key = key;
  112.     new->private = new+1;
  113.     if (private)
  114.         __memcpy(new->private, private, size);
  115.     
  116.     return __rbinsert(map, new, cmpf);
  117. }

  119. int __rbremove_free(struct map *map, void *key, CMP_FUNC cmpf)
  120. {
  121.     struct mnode* data;
  122.     __assert(map && key);
  123.     data = __rbfind(map, key, cmpf);
  124.     /* printf("%s: key: %d\n", __func__, *(int*)(data->key)); */
  125.     if (data)
  126.     {
  127.         /* printf("%s: deleted!\n", __func__);*/
  128.         rb_erase(&(data->node), &(map->root));
  129.         __free(data);
  130.     }
  131.     return 0;
  132. }

  134. struct mnode *map_first(const struct map *map)
  135. {
  136.     struct rb_node *node;
  137.     __assert(map);
  138.     node = rb_first(&(map->root));
  139.     if(node)
  140.         return map_entry(node, struct mnode, node);
  141.     return NULL;
  142. }

  144. struct mnode *map_last(const struct map *map)
  145. {
  146.     struct rb_node *node;
  147.     __assert(map);
  148.     node = rb_last(&(map->root));
  149.     if(node)
  150.         return map_entry(node, struct mnode, node);
  151.     return NULL;
  152. }

  154. struct mnode *map_next(const struct mnode *mnode)
  155. {
  156.     struct rb_node *node;
  157.     __assert(mnode);
  158.     node = rb_next(&(mnode->node));
  159.     if(node)
  160.         return map_entry(node, struct mnode, node);
  161.     return NULL;
  162. }

  164. struct mnode *map_prev(const struct mnode *mnode)
  165. {
  166.     struct rb_node *node;
  167.     __assert(mnode);
  168.     node = rb_prev(&(mnode->node));
  169.     if(node)
  170.         return map_entry(node, struct mnode, node);
  171.     return NULL;
  172. }


  175. int map_init(struct map* map)
  176. {
  177.     map->root.rb_node = NULL;
  178.     lock_init(map->lock);
  179.     return 0;
  180. }

  182. int map_exit(struct map* map)
  183. {
  184.     lock_exit(map->lock);
  185.     return 0;
  186. }
.............................................................................................
.............................................................................................

  1. /*
  2. * file: platform.h
  3. * author: vincent.cws2008@gmail.com
  4. * history:
  5. * initial @ 2012-01-31
  6. */

  8. #ifndef __PLATFORM_H__
  9. #define __PLATFORM_H__

  11. #ifndef NULL
  12. #define NULL 0
  13. #endif

  15. #ifndef offsetof
  16. #define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  17. #endif

  19. #ifdef WIN32

  21. # ifndef container_of
  22. # define container_of(ptr, type, member) ((type *)( (char *)ptr-offsetof(type,member)))
  23. # endif

  25. # define inline __inline

  27. # define __attribute__(x) __declspec(align(4));

  29. #else /* platform: UNIX or Linux */

  31. # ifndef container_of
  32. # define container_of(ptr, type, member) ({ \
  33. const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  34. (type *)( (char *)__mptr - offsetof(type,member) );})
  35. # endif

  37. # include
  38. # include

  40. #endif



  44. #endif

.............................................................................................
.............................................................................................

  1. #Makefile

  3. TARGET := main
  4. RM := rm

  6. CC := gcc

  8. MK := make

  10. SRCS := rbtree.c map.c main.c

  12. OBJS := $(subst .c,.o,$(SRCS))


  15. $(TARGET): $(OBJS)
  16. $(CC) $(OBJS) -o $@

  18. default:
  19. $(MK) $(TARGET)

  21. clean:
  22. $(RM) $(OBJS) $(TARGET)

  24. # common part
  25. %.o: %.c
  26. $(CC) -c $< -Wall -o $@


okay, 收工。。。

附件：
 map.rar  

阅读(8923) | 评论(0) | 转发(1) |
0

上一篇：【转】关于C语言中数据结构的内存对齐问题

下一篇：求质素（素数）

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6