llist.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208
  1. /***************************************************************************
  2. * _ _ ____ _
  3. * Project ___| | | | _ \| |
  4. * / __| | | | |_) | |
  5. * | (__| |_| | _ <| |___
  6. * \___|\___/|_| \_\_____|
  7. *
  8. * Copyright (C) 1998 - 2011, Daniel Stenberg, <daniel@haxx.se>, et al.
  9. *
  10. * This software is licensed as described in the file COPYING, which
  11. * you should have received as part of this distribution. The terms
  12. * are also available at http://curl.haxx.se/docs/copyright.html.
  13. *
  14. * You may opt to use, copy, modify, merge, publish, distribute and/or sell
  15. * copies of the Software, and permit persons to whom the Software is
  16. * furnished to do so, under the terms of the COPYING file.
  17. *
  18. * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  19. * KIND, either express or implied.
  20. *
  21. ***************************************************************************/
  22. #include "setup.h"
  23. #include "llist.h"
  24. #include "curl_memory.h"
  25. /* this must be the last include file */
  26. #include "memdebug.h"
  27. /*
  28. * @unittest: 1300
  29. */
  30. static void
  31. llist_init(struct curl_llist *l, curl_llist_dtor dtor)
  32. {
  33. l->size = 0;
  34. l->dtor = dtor;
  35. l->head = NULL;
  36. l->tail = NULL;
  37. }
  38. struct curl_llist *
  39. Curl_llist_alloc(curl_llist_dtor dtor)
  40. {
  41. struct curl_llist *list;
  42. list = malloc(sizeof(struct curl_llist));
  43. if(NULL == list)
  44. return NULL;
  45. llist_init(list, dtor);
  46. return list;
  47. }
  48. /*
  49. * Curl_llist_insert_next()
  50. *
  51. * Inserts a new list element after the given one 'e'. If the given existing
  52. * entry is NULL and the list already has elements, the new one will be
  53. * inserted first in the list.
  54. *
  55. * Returns: 1 on success and 0 on failure.
  56. *
  57. * @unittest: 1300
  58. */
  59. int
  60. Curl_llist_insert_next(struct curl_llist *list, struct curl_llist_element *e,
  61. const void *p)
  62. {
  63. struct curl_llist_element *ne = malloc(sizeof(struct curl_llist_element));
  64. if(!ne)
  65. return 0;
  66. ne->ptr = (void *) p;
  67. if(list->size == 0) {
  68. list->head = ne;
  69. list->head->prev = NULL;
  70. list->head->next = NULL;
  71. list->tail = ne;
  72. }
  73. else {
  74. /* if 'e' is NULL here, we insert the new element first in the list */
  75. ne->next = e?e->next:list->head;
  76. ne->prev = e;
  77. if(!e) {
  78. list->head->prev = ne;
  79. list->head = ne;
  80. }
  81. else if(e->next) {
  82. e->next->prev = ne;
  83. }
  84. else {
  85. list->tail = ne;
  86. }
  87. if(e)
  88. e->next = ne;
  89. }
  90. ++list->size;
  91. return 1;
  92. }
  93. /*
  94. * @unittest: 1300
  95. */
  96. int
  97. Curl_llist_remove(struct curl_llist *list, struct curl_llist_element *e,
  98. void *user)
  99. {
  100. if(e == NULL || list->size == 0)
  101. return 1;
  102. if(e == list->head) {
  103. list->head = e->next;
  104. if(list->head == NULL)
  105. list->tail = NULL;
  106. else
  107. e->next->prev = NULL;
  108. }
  109. else {
  110. e->prev->next = e->next;
  111. if(!e->next)
  112. list->tail = e->prev;
  113. else
  114. e->next->prev = e->prev;
  115. }
  116. list->dtor(user, e->ptr);
  117. free(e);
  118. --list->size;
  119. return 1;
  120. }
  121. void
  122. Curl_llist_destroy(struct curl_llist *list, void *user)
  123. {
  124. if(list) {
  125. while(list->size > 0)
  126. Curl_llist_remove(list, list->tail, user);
  127. free(list);
  128. }
  129. }
  130. size_t
  131. Curl_llist_count(struct curl_llist *list)
  132. {
  133. return list->size;
  134. }
  135. /*
  136. * @unittest: 1300
  137. */
  138. int Curl_llist_move(struct curl_llist *list, struct curl_llist_element *e,
  139. struct curl_llist *to_list,
  140. struct curl_llist_element *to_e)
  141. {
  142. /* Remove element from list */
  143. if(e == NULL || list->size == 0)
  144. return 0;
  145. if(e == list->head) {
  146. list->head = e->next;
  147. if(list->head == NULL)
  148. list->tail = NULL;
  149. else
  150. e->next->prev = NULL;
  151. }
  152. else {
  153. e->prev->next = e->next;
  154. if(!e->next)
  155. list->tail = e->prev;
  156. else
  157. e->next->prev = e->prev;
  158. }
  159. --list->size;
  160. /* Add element to to_list after to_e */
  161. if(to_list->size == 0) {
  162. to_list->head = e;
  163. to_list->head->prev = NULL;
  164. to_list->head->next = NULL;
  165. to_list->tail = e;
  166. }
  167. else {
  168. e->next = to_e->next;
  169. e->prev = to_e;
  170. if(to_e->next) {
  171. to_e->next->prev = e;
  172. }
  173. else {
  174. to_list->tail = e;
  175. }
  176. to_e->next = e;
  177. }
  178. ++to_list->size;
  179. return 1;
  180. }