1
0

list.c 9.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423
  1. /** @file list.c
  2. * @brief Implementation of a bidirectional list.
  3. *
  4. * Bidirectional List stores special structures (nodes) as its elements.
  5. * Nodes are linked to each other. Node stores abstract user data (i.e. void *).
  6. *
  7. * List can be sorted or unsorted. To sort list user provides special callback
  8. * function to compare two nodes. The list will be sorted
  9. * due to this function return value that indicates "less than",
  10. * "equal", "greater than". Additionally user may provide another callback
  11. * function to free user defined data on list freeing.
  12. */
  13. #include <stdlib.h>
  14. #include <assert.h>
  15. #include <string.h>
  16. #include "private.h"
  17. #include "faux/list.h"
  18. /** @brief Allocates and initializes new list node instance.
  19. *
  20. * @param [in] data User defined data to store within node.
  21. * @return Newly created list node instance or NULL on error.
  22. */
  23. static faux_list_node_t *faux_list_new_node(void *data) {
  24. faux_list_node_t *node = NULL;
  25. node = malloc(sizeof(*node));
  26. assert(node);
  27. if (!node)
  28. return NULL;
  29. // Initialize
  30. node->prev = NULL;
  31. node->next = NULL;
  32. node->data = data;
  33. return node;
  34. }
  35. /** @brief Free list node instance.
  36. *
  37. * @param [in] node List node instance.
  38. */
  39. static void faux_list_free_node(faux_list_node_t *node) {
  40. assert(node);
  41. if (node)
  42. free(node);
  43. }
  44. /** @brief Gets previous list node.
  45. *
  46. * @param [in] this List node instance.
  47. * @return List node previous in list.
  48. */
  49. faux_list_node_t *faux_list_prev_node(const faux_list_node_t *node) {
  50. assert(node);
  51. if (!node)
  52. return NULL;
  53. return node->prev;
  54. }
  55. /** @brief Gets next list node.
  56. *
  57. * @param [in] this List node instance.
  58. * @return List node next in list.
  59. */
  60. faux_list_node_t *faux_list_next_node(const faux_list_node_t *node) {
  61. assert(node);
  62. if (!node)
  63. return NULL;
  64. return node->next;
  65. }
  66. /** @brief Gets user data from list node.
  67. *
  68. * @param [in] this List node instance.
  69. * @return User data stored within specified list node.
  70. */
  71. void *faux_list_data(const faux_list_node_t *node) {
  72. assert(node);
  73. if (!node)
  74. return NULL;
  75. return node->data;
  76. }
  77. /** @brief Iterate through each list node.
  78. *
  79. * On each call to this function the iterator will change its value.
  80. * Before function using the iterator must be initialised by list head node.
  81. *
  82. * @param [in,out] iter List node ptr used as an iterator.
  83. * @return List node or NULL if list elements are over.
  84. */
  85. faux_list_node_t *faux_list_each_node(faux_list_node_t **iter) {
  86. faux_list_node_t *current_node = *iter;
  87. if (!current_node)
  88. return NULL;
  89. *iter = faux_list_next_node(current_node);
  90. return current_node;
  91. }
  92. /** @brief Iterate through each list node and returns user data.
  93. *
  94. * On each call to this function the iterator will change its value.
  95. * Before function using the iterator must be initialised by list head node.
  96. *
  97. * @param [in,out] iter List node ptr used as an iterator.
  98. * @return User data or NULL if list elements are over.
  99. */
  100. void *faux_list_each(faux_list_node_t **iter) {
  101. faux_list_node_t *current_node = NULL;
  102. if (!*iter)
  103. return NULL;
  104. current_node = faux_list_each_node(iter);
  105. return faux_list_data(current_node);
  106. }
  107. /** @brief Allocate and initialize bidirectional list.
  108. *
  109. * @param [in] compareFn Callback function to compare two user data instances
  110. * to sort list.
  111. * @param [in] freeFn Callback function to free user data.
  112. * @return Newly created bidirectional list or NULL on error.
  113. */
  114. faux_list_t *faux_list_new(faux_list_compare_fn compareFn,
  115. faux_list_free_fn freeFn) {
  116. faux_list_t *list;
  117. list = malloc(sizeof(*list));
  118. assert(list);
  119. if (!list)
  120. return NULL;
  121. // Initialize
  122. list->head = NULL;
  123. list->tail = NULL;
  124. list->compareFn = compareFn;
  125. list->freeFn = freeFn;
  126. list->len = 0;
  127. return list;
  128. }
  129. /** @brief Free bidirectional list
  130. *
  131. * Free all nodes and user data from list and finally
  132. * free the list itself. It uses special callback
  133. * function specified by user (while faux_list_new()) to free the abstract
  134. * user data.
  135. *
  136. * @param [in] list List to free.
  137. */
  138. void faux_list_free(faux_list_t *list) {
  139. faux_list_node_t *iter = NULL;
  140. assert(list);
  141. if (!list)
  142. return;
  143. while ((iter = faux_list_head(list))) {
  144. faux_list_del(list, iter);
  145. }
  146. free(list);
  147. }
  148. /** @brief Gets head of list.
  149. *
  150. * @param [in] list List.
  151. * @return List node first in list.
  152. */
  153. faux_list_node_t *faux_list_head(const faux_list_t *list) {
  154. assert(list);
  155. if (!list)
  156. return NULL;
  157. return list->head;
  158. }
  159. /** @brief Gets tail of list.
  160. *
  161. * @param [in] list List.
  162. * @return List node last in list.
  163. */
  164. faux_list_node_t *faux_list_tail(const faux_list_t *list) {
  165. assert(list);
  166. if (!list)
  167. return NULL;
  168. return list->tail;
  169. }
  170. /** @brief Gets current length of list.
  171. *
  172. * @param [in] list List.
  173. * @return Current length of list.
  174. */
  175. size_t faux_list_len(const faux_list_t *list) {
  176. assert(list);
  177. if (!list)
  178. return 0;
  179. return list->len;
  180. }
  181. /** @brief Generic static function for adding new list nodes.
  182. *
  183. * @param [in] list List to add node to.
  184. * @param [in] data User data for new list node.
  185. * @param [in] uniq - true/false Don't add entry with identical order
  186. * key (when the compareFn() returns 0)
  187. * @param [in] find - true/false Function returns list node if there is
  188. * identical entry. Or NULL if find is false.
  189. * @return Newly added list node.
  190. */
  191. static faux_list_node_t *faux_list_add_generic(faux_list_t *list, void *data,
  192. bool_t uniq, bool_t find) {
  193. faux_list_node_t *node = NULL;
  194. faux_list_node_t *iter = NULL;
  195. assert(list);
  196. assert(data);
  197. if (!list || !data)
  198. return NULL;
  199. node = faux_list_new_node(data);
  200. if (!node)
  201. return NULL;
  202. // Empty list.
  203. if (!list->head) {
  204. list->head = node;
  205. list->tail = node;
  206. list->len++;
  207. return node;
  208. }
  209. // Not sorted list. Add to the tail.
  210. if (!list->compareFn) {
  211. node->prev = list->tail;
  212. node->next = NULL;
  213. list->tail->next = node;
  214. list->tail = node;
  215. list->len++;
  216. return node;
  217. }
  218. // Sorted list.
  219. iter = list->tail;
  220. while (iter) {
  221. int res = list->compareFn(node->data, iter->data);
  222. if (uniq && (res == 0)) {
  223. faux_list_free_node(node);
  224. return (find ? iter : NULL);
  225. }
  226. if (res >= 0) {
  227. node->next = iter->next;
  228. node->prev = iter;
  229. iter->next = node;
  230. if (node->next)
  231. node->next->prev = node;
  232. break;
  233. }
  234. iter = iter->prev;
  235. }
  236. // Insert node into the list head
  237. if (!iter) {
  238. node->next = list->head;
  239. node->prev = NULL;
  240. list->head->prev = node;
  241. list->head = node;
  242. }
  243. if (!node->next)
  244. list->tail = node;
  245. list->len++;
  246. return node;
  247. }
  248. /*--------------------------------------------------------- */
  249. faux_list_node_t *faux_list_add(faux_list_t *this, void *data) {
  250. return faux_list_add_generic(this, data, BOOL_FALSE, BOOL_FALSE);
  251. }
  252. /*--------------------------------------------------------- */
  253. faux_list_node_t *faux_list_add_uniq(faux_list_t *this, void *data) {
  254. return faux_list_add_generic(this, data, BOOL_TRUE, BOOL_FALSE);
  255. }
  256. /*--------------------------------------------------------- */
  257. faux_list_node_t *faux_list_find_add(faux_list_t *this, void *data) {
  258. return faux_list_add_generic(this, data, BOOL_TRUE, BOOL_TRUE);
  259. }
  260. void *faux_list_takeaway(faux_list_t *list, faux_list_node_t *node) {
  261. void *data = NULL;
  262. assert(list);
  263. assert(node);
  264. if (!list || !node)
  265. return NULL;
  266. if (node->prev)
  267. node->prev->next = node->next;
  268. else
  269. list->head = node->next;
  270. if (node->next)
  271. node->next->prev = node->prev;
  272. else
  273. list->tail = node->prev;
  274. list->len--;
  275. data = faux_list_data(node);
  276. faux_list_free_node(node);
  277. return data;
  278. }
  279. /*--------------------------------------------------------- */
  280. void faux_list_del(faux_list_t *list, faux_list_node_t *node) {
  281. void *data = NULL;
  282. assert(list);
  283. assert(node);
  284. if (!list || !node)
  285. return;
  286. data = faux_list_takeaway(list, node);
  287. if (list->freeFn)
  288. list->freeFn(data);
  289. }
  290. /*--------------------------------------------------------- */
  291. faux_list_node_t *faux_list_match_node(faux_list_t *this,
  292. faux_list_match_fn matchFn, const void *userkey,
  293. faux_list_node_t **saveptr) {
  294. faux_list_node_t *iter = NULL;
  295. if (!this || !matchFn || !this->head)
  296. return NULL;
  297. if (saveptr)
  298. iter = *saveptr;
  299. if (!iter)
  300. iter = this->head;
  301. while (iter) {
  302. int res;
  303. faux_list_node_t *node = iter;
  304. iter = faux_list_next_node(iter);
  305. if (saveptr)
  306. *saveptr = iter;
  307. res = matchFn(userkey, faux_list_data(node));
  308. if (!res)
  309. return node;
  310. if (res < 0) // No chances to find match
  311. return NULL;
  312. }
  313. return NULL;
  314. }
  315. /*--------------------------------------------------------- */
  316. faux_list_node_t *faux_list_find_node(faux_list_t *this,
  317. faux_list_match_fn matchFn, const void *userkey) {
  318. return faux_list_match_node(this, matchFn, userkey, NULL);
  319. }
  320. /*--------------------------------------------------------- */
  321. void *faux_list_match(faux_list_t *this,
  322. faux_list_match_fn matchFn, const void *userkey,
  323. faux_list_node_t **saveptr) {
  324. faux_list_node_t *res =
  325. faux_list_match_node(this, matchFn, userkey, saveptr);
  326. if (!res)
  327. return NULL;
  328. return faux_list_data(res);
  329. }
  330. /*--------------------------------------------------------- */
  331. void *faux_list_find(faux_list_t *this,
  332. faux_list_match_fn matchFn, const void *userkey) {
  333. return faux_list_match(this, matchFn, userkey, NULL);
  334. }