原文来自：http://blog.chinaunix.net/uid-21457204-id-3063180.html

主要是使用红黑树这种数据结构封装一个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];

  67. srand(time(0));

  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));

  78. map_init(&map1);

  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);

  100. i++;
  101. }
  102. map_info(&map1);

  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);

  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;

  44. __assert(map && key);

  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;

  73. __assert(map && data);

  75. cmp = cmpf ? cmpf : __cmp_default;

  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);

  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);

  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. }

# c++
Logo
向您推荐>>Eolink开发者社区

权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区

更多推荐

深入理解 Mocha 测试框架：从零实现一个 Mocha

前言什么是自动化测试自动化测试在很多团队中都是Devops环节中很难执行起来的一个环节，主要原因在于测试代码的编写工作很难抽象，99%的场景都需要和业务强绑定，而且写测试代码的编写工作量往往比编写实际业务代码的工作量更多。在一些很多业务场景中投入产出比很低，适合写自动化测试的应该是那些中长期业务以及一些诸如组件一样的基础库。自动化测试是个比较大的概念，其中分类也比较多，比如单元测试，端对端测试，集

avatar 云原生

ELK实现containerd的容器日志采集展示【基于logging的全栈监测】

企业级ELK Stack构建介绍

avatar 云原生

(20200916 Solved)docker-compose up创建容器自动退出

问题描述如题，创建容器后自动退出了。并且docker start container无效解决方案原因是缺失了控制终端的配置，需要在docker-compose.yml中增加tty:true ，有时候这样也不行，需要再增加一个command:/bin/bash，命令不一定是这个，需要是一个不会退出的命令，然后用-d后台启动容器。Referencesdocker-compose启动容器后自动退出...

avatar 云原生