Guest User

Untitled

a guest
Apr 4th, 2015
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.47 KB | None | 0 0
  1. // Linked implementation of an circular list with a sentinel node
  2. // Author: drs
  3.  
  4. #include <assert.h>
  5. #include <stdlib.h>
  6. #include <stdio.h>
  7. #include "clist.h"
  8.  
  9. struct node
  10. {
  11. any item;
  12. struct node * next;
  13. struct node * prev;
  14. };
  15.  
  16. struct clist_implementation
  17. {
  18. struct node * sentinel;
  19. struct node * cursor;
  20. int size;
  21. };
  22.  
  23. clist * new_clist()
  24. {
  25. clist * c = (clist *)malloc(sizeof(clist));
  26. if (c==NULL) {
  27. printf("new_clist: malloc failure.\n");
  28. exit(1);
  29. }
  30. c->size = 0;
  31. c->sentinel = (struct node *) malloc(sizeof(struct node));
  32. if (c->sentinel==NULL) {
  33. printf("new_clist(sentinel): malloc failure.\n");
  34. exit(1);
  35. }
  36. c->sentinel->item = NULL;
  37. c->sentinel->next = c->sentinel;
  38. c->sentinel->prev = c->sentinel;
  39. c->cursor = c->sentinel;
  40. return c;
  41. }
  42.  
  43. int clist_size(clist *c)
  44. {
  45. assert(c!=NULL);
  46. return c->size;
  47. }
  48.  
  49. int clist_isempty(clist *c)
  50. {
  51. assert(c!=NULL);
  52. return c->size == 0;
  53. }
  54.  
  55. void clist_goto_head(clist *c)
  56. {
  57. assert(c!=NULL);
  58. c->cursor = c->sentinel->next;
  59. }
  60.  
  61. void clist_goto_last(clist *c)
  62. {
  63. assert(c!=NULL);
  64. c->cursor = c->sentinel->prev;
  65. }
  66.  
  67. void clist_goto_next(clist *c)
  68. {
  69. assert(c!=NULL);
  70. c->cursor = c->cursor->next;
  71. }
  72.  
  73.  
  74.  
  75. void clist_goto_prev(clist *c)
  76. {
  77. assert(c!=NULL);
  78. c->cursor = c->cursor->prev;
  79. }
  80.  
  81. int clist_cursor_inlist(clist *c)
  82. {
  83. assert(c!=NULL);
  84. return c->cursor != c->sentinel;
  85. }
  86.  
  87. any clist_get_item(clist *c)
  88. {
  89. assert(c!=NULL);
  90. return (clist_cursor_inlist(c)) ? c->cursor->item : NULL;
  91. }
  92.  
  93. void clist_ins_before(clist *c, any item)
  94. {
  95. assert(c!=NULL);
  96. struct node * n = (struct node *) malloc(sizeof(struct node));
  97. if (n==NULL) {
  98. printf("clist_ins_before: malloc failure.\n");
  99. exit(1);
  100. }
  101. n->item = item;
  102. n->next = c->cursor;
  103. n->prev = c->cursor->prev;
  104. c->cursor->prev->next = n;
  105. c->cursor->prev = n;
  106. c->size++;
  107. }
  108.  
  109. void clist_ins_after(clist *c, any item)
  110. {
  111. assert(c!=NULL);
  112. struct node * n = (struct node *) malloc(sizeof(struct node));
  113. if (n==NULL) {
  114. printf("clist_ins_after: malloc failure.\n");
  115. exit(1);
  116. }
  117. n->item = item;
  118. n->prev = c->cursor;
  119. n->next = c->cursor->next;
  120. c->cursor->next->prev = n;
  121. c->cursor->next = n;
  122. c->size++;
  123. }
  124.  
  125. any clist_delete(clist *c)
  126. {
  127. any t;
  128. assert(c!=NULL);
  129. struct node * p = c->cursor;
  130. if (clist_cursor_inlist(c))
  131. {
  132. t = c->cursor->item;
  133. c->cursor = c->cursor->next;
  134. p->prev->next = p->next;
  135. p->next->prev = p->prev;
  136. free(p);
  137. c->size--;
  138. return t;
  139. }
  140. else
  141. return NULL;
  142. }
  143.  
  144. void clist_iterate(clist *c, modify f)
  145. {
  146. assert(c!=NULL);
  147. struct node * n = c->cursor;
  148. clist_goto_head(c);
  149. while (clist_cursor_inlist(c))
  150. {
  151. f(c->cursor->item);
  152. clist_goto_next(c);
  153. }
  154. c->cursor = n;
  155. }
  156.  
  157.  
  158. int clist_find(clist *c, pred p)
  159. {
  160. assert(c!=NULL);
  161. clist_goto_head(c);
  162. while (clist_cursor_inlist(c) && (!p(c->cursor->item)))
  163. clist_goto_next(c);
  164. return clist_cursor_inlist(c);
  165. }
  166.  
  167. int clist_find_next(clist *c, pred p)
  168. {
  169. assert(c!=NULL);
  170. struct node * n = c->cursor;
  171. while (clist_cursor_inlist(c) && (!p(c->cursor->item)))
  172. clist_goto_next(c);
  173. if (clist_cursor_inlist(c))
  174. return 1;
  175. else {
  176. c->cursor = n;
  177. return 0;
  178. }
  179. }
  180.  
  181. clist * clist_deep_copy(clist * c,
  182. any (* data_copy) (any d))
  183. {
  184. clist * clone = new_clist();
  185. struct node * p = c->sentinel->next;
  186. while (p != c->sentinel)
  187. {
  188. clist_ins_after(clone, data_copy(p->item));
  189. p = p->next;
  190. }
  191. return clone;
  192. }
  193.  
  194.  
  195. void clist_print(clist *c, void (* item_print)(any item))
  196. {
  197. assert(c!=NULL);
  198. // struct node * n = c->cursor;
  199. printf("CL[");
  200.  
  201. clist_iterate( c, item_print);
  202.  
  203. // clist_goto_head(c);
  204. // if (clist_cursor_inlist(c)) {
  205. // item_print(c->cursor->item);
  206. // clist_goto_next(c);
  207. // while (clist_cursor_inlist(c)) {
  208. // printf(", ");
  209. // item_print(c->cursor->item);
  210. // clist_goto_next(c);
  211. // }
  212. // }
  213. printf("]");
  214. // c->cursor = n;
  215. }
  216.  
  217.  
  218. void clist_release(clist *c)
  219. {
  220. assert(c!=NULL);
  221. free(c->sentinel);
  222. free(c);
  223. }
Advertisement
Add Comment
Please, Sign In to add comment