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

全部博文(116)

文章存档

2013年(1)

2012年(17)

2011年(69)

2009年(29)

分类: 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.  */

  7. #define DEBUG

  8. #include <stdio.h>
  9. #include <time.h>
  10. #include <stdlib.h>
  11. #include <string.h>

  12. #include "map.h"

  13. #ifdef DEBUG
  14. #define dump(a,s) __dump((a),(s))
  15. #else
  16. #define dump(a,s)
  17. #endif


  18. typedef struct word_info {
  19.     unsigned long hash_major;
  20.     unsigned long hash_minor;
  21.     char *path;
  22.     unsigned long line;
  23.     unsigned long col;
  24. }word_info_t;

  25. typedef struct priv_info {
  26.     unsigned long key;
  27.     char val[10];
  28. }priv_info_t;


  29. static void __dump(priv_info_t *array, size_t num)
  30. {
  31.     int i;
  32.     printf("-- DUMP START -- \n");
  33.     for (i=0; i < num; i++)
  34.     {
  35.         printf("array[%d].key=%03d, array[%d].val=%s\n",
  36.             i, array[i].key, i, array[i].val);
  37.     }
  38.     printf("-- DUMP END -- \n");
  39. }

  40. #define map_info(pm) {\
  41.     printf("-- dump map start ... --\n"); \
  42.     map_dump(pm); \
  43.     printf("-- dump map end ... --\n"); \
  44. }

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

  46. #define MAX_NUM 20

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

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


  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__

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

  12. #define lock_t int
  13. #define lock_init(x)
  14. #define lock_exit(x)

  15. #ifndef NULL
  16. #define NULL 0
  17. #endif

  18. #define __assert(x)
  19. #define __free(x) free(x)
  20. #define __malloc(x) malloc(x)
  21. #define __memcpy(d,s,len) memcpy((d),(s),(len))

  22. extern struct map;

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

  24. typedef struct mnode{
  25.   struct rb_node node;
  26.   void *key;
  27.   void *private;
  28. }mnode_t;

  29. /*
  30. typedef struct ops{
  31.   struct mnode*(*find)(struct map *map, void *key, CMP_FUNC cmpf);
  32.   int (*insert_alloc)(struct map *map, void *key,
  33.                       void *private, size_t size, CMP_FUNC cmpf);
  34.   int (*remove_free)(struct map *map, void *key, CMP_FUNC cmpf);
  35.   int (*insert)(struct map *map, struct mnode *data, CMP_FUNC cmpf);
  36.   int (*remove)(struct map *map, void *key, CMP_FUNC cmpf);
  37. }ops_t;
  38. */

  39. typedef struct map{
  40.   struct rb_root root;
  41.   lock_t lock;
  42. }map_t;

  43. extern int map_init(struct map* map);
  44. extern int map_exit(struct map* map);

  45. struct mnode* __rbfind(struct map *map, void *key, CMP_FUNC cmpf);
  46. int __rbinsert_alloc(struct map *map, void *key,
  47.                      void *private, size_t size, CMP_FUNC cmpf);
  48. int __rbremove_free(struct map *map, void *key, CMP_FUNC cmpf);
  49. int __rbinsert(struct map *map, struct mnode *data, CMP_FUNC cmpf);
  50. int __rbremove(struct map *map, void *key, CMP_FUNC cmpf);

  51. #define map_find(map,key,cmpf) \
  52.   __rbfind((map),(key),(cmpf))

  53. #define map_insert_alloc(map,key,priv,size,cmpf) \
  54.   __rbinsert_alloc((map),(key),(priv),(size),(cmpf))

  55. #define map_remove_free(map,key,cmpf) \
  56.   __rbremove_free((map),(key),(cmpf))

  57. #if 0
  58. #define map_insert(map,data,cmpf) \
  59.   __rbinsert((map),(data),(cmpf))
  60. #define map_remove(map,key,cmpf) \
  61.   __rbremove((map),(key),(cmpf))
  62. #endif


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

  64. extern struct mnode *map_first(const struct map *map);
  65. extern struct mnode *map_last(const struct map *map);
  66. extern struct mnode *map_next(const struct mnode *mnode);
  67. extern struct mnode *map_prev(const struct mnode *mnode);

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


  69. #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"

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


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


  24. static int __cmp_default(long *d1, long *d2)
  25. {
  26.     // printf("-- d1:%d, d2:%d\n", *d1, *d2);
  27.     if (*d1 < *d2) return -1;
  28.     else if (*d1 > *d2) return 1;
  29.     else return 0;
  30. }

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

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

  86. int __rbremove(struct map *map, void *key, CMP_FUNC cmpf)
  87. {
  88.     struct mnode* data = __rbfind(map, key, cmpf);
  89.     __assert(map && key);
  90.     if (data)
  91.         rb_erase(&(data->node), &(map->root));
  92.     return 0;
  93. }

  94. int __rbinsert_alloc(struct map *map, void *key,
  95.                      void *private, size_t size, CMP_FUNC cmpf)
  96. {
  97.     struct mnode *new;
  98.     __assert(map && key && private);
  99.     new = (struct mnode*)__malloc(size+sizeof(struct mnode));
  100.     __assert(new);
  101.     mnode_init(new);
  102.     new->key = key;
  103.     new->private = new+1;
  104.     if (private)
  105.         __memcpy(new->private, private, size);
  106.     
  107.     return __rbinsert(map, new, cmpf);
  108. }

  109. int __rbremove_free(struct map *map, void *key, CMP_FUNC cmpf)
  110. {
  111.     struct mnode* data;
  112.     __assert(map && key);
  113.     data = __rbfind(map, key, cmpf);
  114.     /* printf("%s: key: %d\n", __func__, *(int*)(data->key)); */
  115.     if (data)
  116.     {
  117.         /* printf("%s: deleted!\n", __func__);*/
  118.         rb_erase(&(data->node), &(map->root));
  119.         __free(data);
  120.     }
  121.     return 0;
  122. }

  123. struct mnode *map_first(const struct map *map)
  124. {
  125.     struct rb_node *node;
  126.     __assert(map);
  127.     node = rb_first(&(map->root));
  128.     if(node)
  129.         return map_entry(node, struct mnode, node);
  130.     return NULL;
  131. }

  132. struct mnode *map_last(const struct map *map)
  133. {
  134.     struct rb_node *node;
  135.     __assert(map);
  136.     node = rb_last(&(map->root));
  137.     if(node)
  138.         return map_entry(node, struct mnode, node);
  139.     return NULL;
  140. }

  141. struct mnode *map_next(const struct mnode *mnode)
  142. {
  143.     struct rb_node *node;
  144.     __assert(mnode);
  145.     node = rb_next(&(mnode->node));
  146.     if(node)
  147.         return map_entry(node, struct mnode, node);
  148.     return NULL;
  149. }

  150. struct mnode *map_prev(const struct mnode *mnode)
  151. {
  152.     struct rb_node *node;
  153.     __assert(mnode);
  154.     node = rb_prev(&(mnode->node));
  155.     if(node)
  156.         return map_entry(node, struct mnode, node);
  157.     return NULL;
  158. }


  159. int map_init(struct map* map)
  160. {
  161.     map->root.rb_node = NULL;
  162.     lock_init(map->lock);
  163.     return 0;
  164. }

  165. int map_exit(struct map* map)
  166. {
  167.     lock_exit(map->lock);
  168.     return 0;
  169. }
.............................................................................................
.............................................................................................

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

  7. #ifndef __PLATFORM_H__
  8. #define __PLATFORM_H__

  9. #ifndef NULL
  10. #define NULL 0
  11. #endif

  12. #ifndef offsetof
  13. #define offsetof(TYPE,MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
  14. #endif

  15. #ifdef WIN32

  16. # ifndef container_of
  17. # define container_of(ptr, type, member) ((type *)( (char *)ptr-offsetof(type,member)))
  18. # endif

  19. # define inline __inline

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

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

  22. # ifndef container_of
  23. # define container_of(ptr, type, member) ({ \
  24. const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  25. (type *)( (char *)__mptr - offsetof(type,member) );})
  26. # endif

  27. # include
  28. # include

  29. #endif



  30. #endif

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

  1. #Makefile

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

  4. CC := gcc

  5. MK := make

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

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


  8. $(TARGET): $(OBJS)
  9. $(CC) $(OBJS) -o $@

  10. default:
  11. $(MK) $(TARGET)

  12. clean:
  13. $(RM) $(OBJS) $(TARGET)

  14. # common part
  15. %.o: %.c
  16. $(CC) -c $< -Wall -o $@


okay, 收工。。。

附件:
 map.rar  

阅读(8995) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~