1
0

list.c 7.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294
  1. #include <stdlib.h>
  2. #include <assert.h>
  3. #include <string.h>
  4. #include "private.h"
  5. /*--------------------------------------------------------- */
  6. static void lub_list_init(lub_list_t *this,
  7. lub_list_compare_fn compareFn,
  8. lub_list_free_fn freeFn)
  9. {
  10. this->head = NULL;
  11. this->tail = NULL;
  12. this->compareFn = compareFn;
  13. this->freeFn = freeFn;
  14. this->len = 0;
  15. }
  16. /*--------------------------------------------------------- */
  17. lub_list_t *lub_list_new(lub_list_compare_fn compareFn,
  18. lub_list_free_fn freeFn)
  19. {
  20. lub_list_t *this;
  21. this = malloc(sizeof(*this));
  22. assert(this);
  23. lub_list_init(this, compareFn, freeFn);
  24. return this;
  25. }
  26. /*--------------------------------------------------------- */
  27. inline void lub_list_free(lub_list_t *this)
  28. {
  29. free(this);
  30. }
  31. /*--------------------------------------------------------- */
  32. /* Free all nodes and data from list and finally
  33. * free the list itself. It uses special callback
  34. * function specified by user to free the abstract
  35. * data.
  36. */
  37. void lub_list_free_all(lub_list_t *this)
  38. {
  39. lub_list_node_t *iter;
  40. while ((iter = lub_list__get_head(this))) {
  41. lub_list_del(this, iter);
  42. if (this->freeFn)
  43. this->freeFn(lub_list_node__get_data(iter));
  44. lub_list_node_free(iter);
  45. }
  46. lub_list_free(this);
  47. }
  48. /*--------------------------------------------------------- */
  49. inline lub_list_node_t *lub_list__get_head(lub_list_t *this)
  50. {
  51. assert(this);
  52. if (!this)
  53. return NULL;
  54. return this->head;
  55. }
  56. /*--------------------------------------------------------- */
  57. inline lub_list_node_t *lub_list__get_tail(lub_list_t *this)
  58. {
  59. return this->tail;
  60. }
  61. /*--------------------------------------------------------- */
  62. static void lub_list_node_init(lub_list_node_t *this,
  63. void *data)
  64. {
  65. this->prev = this->next = NULL;
  66. this->data = data;
  67. }
  68. /*--------------------------------------------------------- */
  69. lub_list_node_t *lub_list_node_new(void *data)
  70. {
  71. lub_list_node_t *this;
  72. this = malloc(sizeof(*this));
  73. assert(this);
  74. lub_list_node_init(this, data);
  75. return this;
  76. }
  77. /*--------------------------------------------------------- */
  78. inline lub_list_node_t *lub_list_iterator_init(lub_list_t *this)
  79. {
  80. return this->head;
  81. }
  82. /*--------------------------------------------------------- */
  83. inline lub_list_node_t *lub_list_node__get_prev(lub_list_node_t *this)
  84. {
  85. return this->prev;
  86. }
  87. /*--------------------------------------------------------- */
  88. inline lub_list_node_t *lub_list_node__get_next(lub_list_node_t *this)
  89. {
  90. return this->next;
  91. }
  92. /*--------------------------------------------------------- */
  93. inline lub_list_node_t *lub_list_iterator_next(lub_list_node_t *this)
  94. {
  95. return lub_list_node__get_next(this);
  96. }
  97. /*--------------------------------------------------------- */
  98. inline lub_list_node_t *lub_list_iterator_prev(lub_list_node_t *this)
  99. {
  100. return lub_list_node__get_prev(this);
  101. }
  102. /*--------------------------------------------------------- */
  103. inline void lub_list_node_free(lub_list_node_t *this)
  104. {
  105. free(this);
  106. }
  107. /*--------------------------------------------------------- */
  108. inline void *lub_list_node__get_data(lub_list_node_t *this)
  109. {
  110. return this->data;
  111. }
  112. /*--------------------------------------------------------- */
  113. /* uniq - true/false Don't add entry with identical order
  114. * key (when the compareFn() returns 0)
  115. * find - true/false Function returns list_node if there is
  116. * identical entry. Or NULL if find is false.
  117. */
  118. static lub_list_node_t *lub_list_add_generic(lub_list_t *this, void *data,
  119. bool_t uniq, bool_t find)
  120. {
  121. lub_list_node_t *node = lub_list_node_new(data);
  122. lub_list_node_t *iter;
  123. this->len++;
  124. /* Empty list */
  125. if (!this->head) {
  126. this->head = node;
  127. this->tail = node;
  128. return node;
  129. }
  130. /* Not sorted list. Add to the tail. */
  131. if (!this->compareFn) {
  132. node->prev = this->tail;
  133. node->next = NULL;
  134. this->tail->next = node;
  135. this->tail = node;
  136. return node;
  137. }
  138. /* Sorted list */
  139. iter = this->tail;
  140. while (iter) {
  141. int res = this->compareFn(node->data, iter->data);
  142. if (uniq && (res == 0)) {
  143. this->len--; // Revert previous increment
  144. lub_list_node_free(node);
  145. return (find ? iter : NULL);
  146. }
  147. if (res >= 0) {
  148. node->next = iter->next;
  149. node->prev = iter;
  150. iter->next = node;
  151. if (node->next)
  152. node->next->prev = node;
  153. break;
  154. }
  155. iter = iter->prev;
  156. }
  157. /* Insert node into the list head */
  158. if (!iter) {
  159. node->next = this->head;
  160. node->prev = NULL;
  161. this->head->prev = node;
  162. this->head = node;
  163. }
  164. if (!node->next)
  165. this->tail = node;
  166. return node;
  167. }
  168. /*--------------------------------------------------------- */
  169. lub_list_node_t *lub_list_add(lub_list_t *this, void *data)
  170. {
  171. return lub_list_add_generic(this, data, BOOL_FALSE, BOOL_FALSE);
  172. }
  173. /*--------------------------------------------------------- */
  174. lub_list_node_t *lub_list_add_uniq(lub_list_t *this, void *data)
  175. {
  176. return lub_list_add_generic(this, data, BOOL_TRUE, BOOL_FALSE);
  177. }
  178. /*--------------------------------------------------------- */
  179. lub_list_node_t *lub_list_find_add(lub_list_t *this, void *data)
  180. {
  181. return lub_list_add_generic(this, data, BOOL_TRUE, BOOL_TRUE);
  182. }
  183. /*--------------------------------------------------------- */
  184. void lub_list_del(lub_list_t *this, lub_list_node_t *node)
  185. {
  186. if (node->prev)
  187. node->prev->next = node->next;
  188. else
  189. this->head = node->next;
  190. if (node->next)
  191. node->next->prev = node->prev;
  192. else
  193. this->tail = node->prev;
  194. node->prev = NULL;
  195. node->next = NULL;
  196. this->len--;
  197. }
  198. /*--------------------------------------------------------- */
  199. inline void lub_list_node_copy(lub_list_node_t *dst, lub_list_node_t *src)
  200. {
  201. memcpy(dst, src, sizeof(lub_list_node_t));
  202. }
  203. /*--------------------------------------------------------- */
  204. lub_list_node_t *lub_list_match_node(lub_list_t *this,
  205. lub_list_match_fn matchFn, const void *userkey,
  206. lub_list_node_t **saveptr)
  207. {
  208. lub_list_node_t *iter = NULL;
  209. if (!this || !matchFn || !this->head)
  210. return NULL;
  211. if (saveptr)
  212. iter = *saveptr;
  213. if (!iter)
  214. iter = this->head;
  215. while (iter) {
  216. int res;
  217. lub_list_node_t *node = iter;
  218. iter = lub_list_node__get_next(iter);
  219. if (saveptr)
  220. *saveptr = iter;
  221. res = matchFn(userkey, lub_list_node__get_data(node));
  222. if (!res)
  223. return node;
  224. if (res < 0) // No chances to find match
  225. return NULL;
  226. }
  227. return NULL;
  228. }
  229. /*--------------------------------------------------------- */
  230. void *lub_list_find_node(lub_list_t *this,
  231. lub_list_match_fn matchFn, const void *userkey)
  232. {
  233. return lub_list_match_node(this, matchFn, userkey, NULL);
  234. }
  235. /*--------------------------------------------------------- */
  236. void *lub_list_match(lub_list_t *this,
  237. lub_list_match_fn matchFn, const void *userkey,
  238. lub_list_node_t **saveptr)
  239. {
  240. lub_list_node_t *res = lub_list_match_node(this, matchFn, userkey, saveptr);
  241. if (!res)
  242. return NULL;
  243. return lub_list_node__get_data(res);
  244. }
  245. /*--------------------------------------------------------- */
  246. void *lub_list_find(lub_list_t *this,
  247. lub_list_match_fn matchFn, const void *userkey)
  248. {
  249. return lub_list_match(this, matchFn, userkey, NULL);
  250. }
  251. /*--------------------------------------------------------- */
  252. inline unsigned int lub_list_len(lub_list_t *this)
  253. {
  254. return this->len;
  255. }