1
0

list.c 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308
  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. return this->head;
  52. }
  53. /*--------------------------------------------------------- */
  54. inline lub_list_node_t *lub_list__get_tail(lub_list_t *this)
  55. {
  56. return this->tail;
  57. }
  58. /*--------------------------------------------------------- */
  59. static void lub_list_node_init(lub_list_node_t *this,
  60. void *data)
  61. {
  62. this->prev = this->next = NULL;
  63. this->data = data;
  64. }
  65. /*--------------------------------------------------------- */
  66. lub_list_node_t *lub_list_node_new(void *data)
  67. {
  68. lub_list_node_t *this;
  69. this = malloc(sizeof(*this));
  70. assert(this);
  71. lub_list_node_init(this, data);
  72. return this;
  73. }
  74. /*--------------------------------------------------------- */
  75. inline lub_list_node_t *lub_list_iterator_init(lub_list_t *this)
  76. {
  77. return this->head;
  78. }
  79. /*--------------------------------------------------------- */
  80. inline lub_list_node_t *lub_list_node__get_prev(lub_list_node_t *this)
  81. {
  82. return this->prev;
  83. }
  84. /*--------------------------------------------------------- */
  85. inline lub_list_node_t *lub_list_node__get_next(lub_list_node_t *this)
  86. {
  87. return this->next;
  88. }
  89. /*--------------------------------------------------------- */
  90. inline lub_list_node_t *lub_list_iterator_next(lub_list_node_t *this)
  91. {
  92. return lub_list_node__get_next(this);
  93. }
  94. /*--------------------------------------------------------- */
  95. inline lub_list_node_t *lub_list_iterator_prev(lub_list_node_t *this)
  96. {
  97. return lub_list_node__get_prev(this);
  98. }
  99. /*--------------------------------------------------------- */
  100. inline void lub_list_node_free(lub_list_node_t *this)
  101. {
  102. free(this);
  103. }
  104. /*--------------------------------------------------------- */
  105. inline void *lub_list_node__get_data(lub_list_node_t *this)
  106. {
  107. return this->data;
  108. }
  109. /*--------------------------------------------------------- */
  110. /* uniq - true/false Don't add entry with identical order
  111. * key (when the compareFn() returns 0)
  112. * find - true/false Function returns list_node if there is
  113. * identical entry. Or NULL if find is false.
  114. */
  115. static lub_list_node_t *lub_list_add_generic(lub_list_t *this, void *data,
  116. bool_t uniq, bool_t find)
  117. {
  118. lub_list_node_t *node = lub_list_node_new(data);
  119. lub_list_node_t *iter;
  120. this->len++;
  121. /* Empty list */
  122. if (!this->head) {
  123. this->head = node;
  124. this->tail = node;
  125. return node;
  126. }
  127. /* Not sorted list. Add to the tail. */
  128. if (!this->compareFn) {
  129. node->prev = this->tail;
  130. node->next = NULL;
  131. this->tail->next = node;
  132. this->tail = node;
  133. return node;
  134. }
  135. /* Sorted list */
  136. iter = this->tail;
  137. while (iter) {
  138. int res = this->compareFn(node->data, iter->data);
  139. if (uniq && (res == 0)) {
  140. this->len--; // Revert previous increment
  141. return (find ? iter : NULL);
  142. }
  143. if (res >= 0) {
  144. node->next = iter->next;
  145. node->prev = iter;
  146. iter->next = node;
  147. if (node->next)
  148. node->next->prev = node;
  149. break;
  150. }
  151. iter = iter->prev;
  152. }
  153. /* Insert node into the list head */
  154. if (!iter) {
  155. node->next = this->head;
  156. node->prev = NULL;
  157. this->head->prev = node;
  158. this->head = node;
  159. }
  160. if (!node->next)
  161. this->tail = node;
  162. return node;
  163. }
  164. /*--------------------------------------------------------- */
  165. lub_list_node_t *lub_list_add(lub_list_t *this, void *data)
  166. {
  167. return lub_list_add_generic(this, data, BOOL_FALSE, BOOL_FALSE);
  168. }
  169. /*--------------------------------------------------------- */
  170. lub_list_node_t *lub_list_add_uniq(lub_list_t *this, void *data)
  171. {
  172. return lub_list_add_generic(this, data, BOOL_TRUE, BOOL_FALSE);
  173. }
  174. /*--------------------------------------------------------- */
  175. lub_list_node_t *lub_list_find_add(lub_list_t *this, void *data)
  176. {
  177. return lub_list_add_generic(this, data, BOOL_TRUE, BOOL_TRUE);
  178. }
  179. /*--------------------------------------------------------- */
  180. void lub_list_del(lub_list_t *this, lub_list_node_t *node)
  181. {
  182. if (node->prev)
  183. node->prev->next = node->next;
  184. else
  185. this->head = node->next;
  186. if (node->next)
  187. node->next->prev = node->prev;
  188. else
  189. this->tail = node->prev;
  190. this->len--;
  191. }
  192. /*--------------------------------------------------------- */
  193. inline void lub_list_node_copy(lub_list_node_t *dst, lub_list_node_t *src)
  194. {
  195. memcpy(dst, src, sizeof(lub_list_node_t));
  196. }
  197. /*--------------------------------------------------------- */
  198. lub_list_node_t *lub_list_match_node(lub_list_t *this,
  199. lub_list_match_fn matchFn, const void *userkey,
  200. lub_list_node_t **saveptr, bool_t reverse)
  201. {
  202. lub_list_node_t *iter = NULL;
  203. if (!this || !matchFn || !this->head)
  204. return NULL;
  205. if (saveptr)
  206. iter = *saveptr;
  207. if (!iter)
  208. iter = reverse ? this->tail : this->head;
  209. while (iter) {
  210. int res;
  211. lub_list_node_t *node = iter;
  212. iter = reverse ? lub_list_node__get_prev(iter) : lub_list_node__get_next(iter);
  213. if (saveptr)
  214. *saveptr = iter;
  215. res = matchFn(userkey, lub_list_node__get_data(node));
  216. if (!res)
  217. return node;
  218. if (reverse) {
  219. if (res > 0) // No chances to find match
  220. return NULL;
  221. } else {
  222. if (res < 0) // No chances to find match
  223. return NULL;
  224. }
  225. }
  226. return NULL;
  227. }
  228. /*--------------------------------------------------------- */
  229. void *lub_list_find_node(lub_list_t *this,
  230. lub_list_match_fn matchFn, const void *userkey)
  231. {
  232. return lub_list_match_node(this, matchFn, userkey, NULL, BOOL_FALSE);
  233. }
  234. /*--------------------------------------------------------- */
  235. void *lub_list_rfind_node(lub_list_t *this,
  236. lub_list_match_fn matchFn, const void *userkey)
  237. {
  238. return lub_list_match_node(this, matchFn, userkey, NULL, BOOL_TRUE);
  239. }
  240. /*--------------------------------------------------------- */
  241. void *lub_list_match(lub_list_t *this,
  242. lub_list_match_fn matchFn, const void *userkey,
  243. lub_list_node_t **saveptr, bool_t reverse)
  244. {
  245. lub_list_node_t *res = lub_list_match_node(this, matchFn,
  246. userkey, saveptr, reverse);
  247. if (!res)
  248. return NULL;
  249. return lub_list_node__get_data(res);
  250. }
  251. /*--------------------------------------------------------- */
  252. void *lub_list_find(lub_list_t *this,
  253. lub_list_match_fn matchFn, const void *userkey)
  254. {
  255. return lub_list_match(this, matchFn, userkey, NULL, BOOL_FALSE);
  256. }
  257. /*--------------------------------------------------------- */
  258. void *lub_list_rfind(lub_list_t *this,
  259. lub_list_match_fn matchFn, const void *userkey)
  260. {
  261. return lub_list_match(this, matchFn, userkey, NULL, BOOL_TRUE);
  262. }
  263. /*--------------------------------------------------------- */
  264. inline unsigned int lub_list_len(lub_list_t *this)
  265. {
  266. return this->len;
  267. }