开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 电子书籍 > VC书籍 > 查看源码
set.c
资源名称：c.rar　[点击查看]
上传用户：shmaik
上传日期：2014-06-01
资源大小：45093k
文件大小：7k
源码类别：

VC书籍

开发平台：

C/C++

set.c：源码内容
  1. static char rcsid[] = "$Id: H:/drh/idioms/book/RCS/set.doc,v 1.11 1996/06/26 23:02:01 drh Exp $";
  2. #include <limits.h>
  3. #include <stddef.h>
  4. #include "mem.h"
  5. #include "assert.h"
  6. #include "arith.h"
  7. #include "set.h"
  8. #define T Set_T
  9. struct T {
  10. int length;
  11. unsigned timestamp;
  12. int (*cmp)(const void *x, const void *y);
  13. unsigned (*hash)(const void *x);
  14. int size;
  15. struct member {
  16. struct member *link;
  17. const void *member;
  18. } **buckets;
  19. };
  20. static int cmpatom(const void *x, const void *y) {
  21. return x != y;
  22. }
  23. static unsigned hashatom(const void *x) {
  24. return (unsigned long)x>>2;
  25. }
  26. static T copy(T t, int hint) {
  27. T set;
  28. assert(t);
  29. set = Set_new(hint, t->cmp, t->hash);
  30. { int i;
  31.   struct member *q;
  32.   for (i = 0; i < t->size; i++)
  33.    for (q = t->buckets[i]; q; q = q->link)
  34. {
  35. struct member *p;
  36. const void *member = q->member;
  37. int i = (*set->hash)(member)%set->size;
  38. NEW(p);
  39. p->member = member;
  40. p->link = set->buckets[i];
  41. set->buckets[i] = p;
  42. set->length++;
  43. }
  44. }
  45. return set;
  46. }
  47. T Set_new(int hint,
  48. int cmp(const void *x, const void *y),
  49. unsigned hash(const void *x)) {
  50. T set;
  51. int i;
  52. static int primes[] = { 509, 509, 1021, 2053, 4093,
  53. 8191, 16381, 32771, 65521, INT_MAX };
  54. assert(hint >= 0);
  55. for (i = 1; primes[i] < hint; i++)
  56. ;
  57. set = ALLOC(sizeof (*set) +
  58. primes[i-1]*sizeof (set->buckets[0]));
  59. set->size = primes[i-1];
  60. set->cmp  = cmp  ?  cmp : cmpatom;
  61. set->hash = hash ? hash : hashatom;
  62. set->buckets = (struct member **)(set + 1);
  63. for (i = 0; i < set->size; i++)
  64. set->buckets[i] = NULL;
  65. set->length = 0;
  66. set->timestamp = 0;
  67. return set;
  68. }
  69. int Set_member(T set, const void *member) {
  70. int i;
  71. struct member *p;
  72. assert(set);
  73. assert(member);
  74. i = (*set->hash)(member)%set->size;
  75. for (p = set->buckets[i]; p; p = p->link)
  76. if ((*set->cmp)(member, p->member) == 0)
  77. break;
  78. return p != NULL;
  79. }
  80. void Set_put(T set, const void *member) {
  81. int i;
  82. struct member *p;
  83. assert(set);
  84. assert(member);
  85. i = (*set->hash)(member)%set->size;
  86. for (p = set->buckets[i]; p; p = p->link)
  87. if ((*set->cmp)(member, p->member) == 0)
  88. break;
  89. if (p == NULL) {
  90. NEW(p);
  91. p->member = member;
  92. p->link = set->buckets[i];
  93. set->buckets[i] = p;
  94. set->length++;
  95. } else
  96. p->member = member;
  97. set->timestamp++;
  98. }
  99. void *Set_remove(T set, const void *member) {
  100. int i;
  101. struct member **pp;
  102. assert(set);
  103. assert(member);
  104. set->timestamp++;
  105. i = (*set->hash)(member)%set->size;
  106. for (pp = &set->buckets[i]; *pp; pp = &(*pp)->link)
  107. if ((*set->cmp)(member, (*pp)->member) == 0) {
  108. struct member *p = *pp;
  109. *pp = p->link;
  110. member = p->member;
  111. FREE(p);
  112. set->length--;
  113. return (void *)member;
  114. }
  115. return NULL;
  116. }
  117. int Set_length(T set) {
  118. assert(set);
  119. return set->length;
  120. }
  121. void Set_free(T *set) {
  122. assert(set && *set);
  123. if ((*set)->length > 0) {
  124. int i;
  125. struct member *p, *q;
  126. for (i = 0; i < (*set)->size; i++)
  127. for (p = (*set)->buckets[i]; p; p = q) {
  128. q = p->link;
  129. FREE(p);
  130. }
  131. }
  132. FREE(*set);
  133. }
  134. void Set_map(T set,
  135. void apply(const void *member, void *cl), void *cl) {
  136. int i;
  137. unsigned stamp;
  138. struct member *p;
  139. assert(set);
  140. assert(apply);
  141. stamp = set->timestamp;
  142. for (i = 0; i < set->size; i++)
  143. for (p = set->buckets[i]; p; p = p->link) {
  144. apply(p->member, cl);
  145. assert(set->timestamp == stamp);
  146. }
  147. }
  148. void **Set_toArray(T set, void *end) {
  149. int i, j = 0;
  150. void **array;
  151. struct member *p;
  152. assert(set);
  153. array = ALLOC((set->length + 1)*sizeof (*array));
  154. for (i = 0; i < set->size; i++)
  155. for (p = set->buckets[i]; p; p = p->link)
  156. array[j++] = (void *)p->member;
  157. array[j] = end;
  158. return array;
  159. }
  160. T Set_union(T s, T t) {
  161. if (s == NULL) {
  162. assert(t);
  163. return copy(t, t->size);
  164. } else if (t == NULL)
  165. return copy(s, s->size);
  166. else {
  167. T set = copy(s, Arith_max(s->size, t->size));
  168. assert(s->cmp == t->cmp && s->hash == t->hash);
  169. { int i;
  170.   struct member *q;
  171.   for (i = 0; i < t->size; i++)
  172.    for (q = t->buckets[i]; q; q = q->link)
  173. Set_put(set, q->member);
  174. }
  175. return set;
  176. }
  177. }
  178. T Set_inter(T s, T t) {
  179. if (s == NULL) {
  180. assert(t);
  181. return Set_new(t->size, t->cmp, t->hash);
  182. } else if (t == NULL)
  183. return Set_new(s->size, s->cmp, s->hash);
  184. else if (s->length < t->length)
  185. return Set_inter(t, s);
  186. else {
  187. T set = Set_new(Arith_min(s->size, t->size),
  188. s->cmp, s->hash);
  189. assert(s->cmp == t->cmp && s->hash == t->hash);
  190. { int i;
  191.   struct member *q;
  192.   for (i = 0; i < t->size; i++)
  193.    for (q = t->buckets[i]; q; q = q->link)
  194. if (Set_member(s, q->member))
  195. {
  196. struct member *p;
  197. const void *member = q->member;
  198. int i = (*set->hash)(member)%set->size;
  199. NEW(p);
  200. p->member = member;
  201. p->link = set->buckets[i];
  202. set->buckets[i] = p;
  203. set->length++;
  204. }
  205. }
  206. return set;
  207. }
  208. }
  209. T Set_minus(T t, T s) {
  210. if (t == NULL){
  211. assert(s);
  212. return Set_new(s->size, s->cmp, s->hash);
  213. } else if (s == NULL)
  214. return copy(t, t->size);
  215. else {
  216. T set = Set_new(Arith_min(s->size, t->size),
  217. s->cmp, s->hash);
  218. assert(s->cmp == t->cmp && s->hash == t->hash);
  219. { int i;
  220.   struct member *q;
  221.   for (i = 0; i < t->size; i++)
  222.    for (q = t->buckets[i]; q; q = q->link)
  223. if (!Set_member(s, q->member))
  224. {
  225. struct member *p;
  226. const void *member = q->member;
  227. int i = (*set->hash)(member)%set->size;
  228. NEW(p);
  229. p->member = member;
  230. p->link = set->buckets[i];
  231. set->buckets[i] = p;
  232. set->length++;
  233. }
  234. }
  235. return set;
  236. }
  237. }
  238. T Set_diff(T s, T t) {
  239. if (s == NULL) {
  240. assert(t);
  241. return copy(t, t->size);
  242. } else if (t == NULL)
  243. return copy(s, s->size);
  244. else {
  245. T set = Set_new(Arith_min(s->size, t->size),
  246. s->cmp, s->hash);
  247. assert(s->cmp == t->cmp && s->hash == t->hash);
  248. { int i;
  249.   struct member *q;
  250.   for (i = 0; i < t->size; i++)
  251.    for (q = t->buckets[i]; q; q = q->link)
  252. if (!Set_member(s, q->member))
  253. {
  254. struct member *p;
  255. const void *member = q->member;
  256. int i = (*set->hash)(member)%set->size;
  257. NEW(p);
  258. p->member = member;
  259. p->link = set->buckets[i];
  260. set->buckets[i] = p;
  261. set->length++;
  262. }
  263. }
  264. { T u = t; t = s; s = u; }
  265. { int i;
  266.   struct member *q;
  267.   for (i = 0; i < t->size; i++)
  268.    for (q = t->buckets[i]; q; q = q->link)
  269. if (!Set_member(s, q->member))
  270. {
  271. struct member *p;
  272. const void *member = q->member;
  273. int i = (*set->hash)(member)%set->size;
  274. NEW(p);
  275. p->member = member;
  276. p->link = set->buckets[i];
  277. set->buckets[i] = p;
  278. set->length++;
  279. }
  280. }
  281. return set;
  282. }
  283. }