list.c 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531
  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 = faux_zmalloc(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. faux_free(node);
  42. }
  43. /** @brief Gets previous list node.
  44. *
  45. * @param [in] this List node instance.
  46. * @return List node previous in list.
  47. */
  48. faux_list_node_t *faux_list_prev_node(const faux_list_node_t *node) {
  49. assert(node);
  50. if (!node)
  51. return NULL;
  52. return node->prev;
  53. }
  54. /** @brief Gets next list node.
  55. *
  56. * @param [in] this List node instance.
  57. * @return List node next in list.
  58. */
  59. faux_list_node_t *faux_list_next_node(const faux_list_node_t *node) {
  60. assert(node);
  61. if (!node)
  62. return NULL;
  63. return node->next;
  64. }
  65. /** @brief Gets user data from list node.
  66. *
  67. * @param [in] this List node instance.
  68. * @return User data stored within specified list node.
  69. */
  70. void *faux_list_data(const faux_list_node_t *node) {
  71. assert(node);
  72. if (!node)
  73. return NULL;
  74. return node->data;
  75. }
  76. /** @brief Iterate through each list node.
  77. *
  78. * On each call to this function the iterator will change its value.
  79. * Before function using the iterator must be initialised by list head node.
  80. *
  81. * @param [in,out] iter List node ptr used as an iterator.
  82. * @return List node or NULL if list elements are over.
  83. */
  84. faux_list_node_t *faux_list_each_node(faux_list_node_t **iter) {
  85. faux_list_node_t *current_node = *iter;
  86. // No assert() on current_node. NULL iterator is normal
  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. // No assert() on current_node. NULL iterator is normal
  103. if (!*iter)
  104. return NULL;
  105. current_node = faux_list_each_node(iter);
  106. return faux_list_data(current_node);
  107. }
  108. /** @brief Allocate and initialize bidirectional list.
  109. *
  110. * Prototypes for callback functions:
  111. * @code
  112. * int faux_list_compare_fn(const void *first, const void *second);
  113. * void faux_list_free_fn(void *data);
  114. * @endcode
  115. *
  116. * @param [in] compareFn Callback function to compare two user data instances
  117. * to sort list.
  118. * @param [in] freeFn Callback function to free user data.
  119. * @return Newly created bidirectional list or NULL on error.
  120. */
  121. faux_list_t *faux_list_new(faux_list_compare_fn compareFn,
  122. faux_list_free_fn freeFn) {
  123. faux_list_t *list = NULL;
  124. list = faux_zmalloc(sizeof(*list));
  125. assert(list);
  126. if (!list)
  127. return NULL;
  128. // Initialize
  129. list->head = NULL;
  130. list->tail = NULL;
  131. list->compareFn = compareFn;
  132. list->freeFn = freeFn;
  133. list->len = 0;
  134. return list;
  135. }
  136. /** @brief Free bidirectional list
  137. *
  138. * Free all nodes and user data from list and finally
  139. * free the list itself. It uses special callback
  140. * function specified by user (while faux_list_new()) to free the abstract
  141. * user data.
  142. *
  143. * @param [in] list List to free.
  144. */
  145. void faux_list_free(faux_list_t *list) {
  146. faux_list_node_t *iter = NULL;
  147. assert(list);
  148. if (!list)
  149. return;
  150. while ((iter = faux_list_head(list))) {
  151. faux_list_del(list, iter);
  152. }
  153. faux_free(list);
  154. }
  155. /** @brief Gets head of list.
  156. *
  157. * @param [in] list List.
  158. * @return List node first in list.
  159. */
  160. faux_list_node_t *faux_list_head(const faux_list_t *list) {
  161. assert(list);
  162. if (!list)
  163. return NULL;
  164. return list->head;
  165. }
  166. /** @brief Gets tail of list.
  167. *
  168. * @param [in] list List.
  169. * @return List node last in list.
  170. */
  171. faux_list_node_t *faux_list_tail(const faux_list_t *list) {
  172. assert(list);
  173. if (!list)
  174. return NULL;
  175. return list->tail;
  176. }
  177. /** @brief Gets current length of list.
  178. *
  179. * @param [in] list List.
  180. * @return Current length of list.
  181. */
  182. size_t faux_list_len(const faux_list_t *list) {
  183. assert(list);
  184. if (!list)
  185. return 0;
  186. return list->len;
  187. }
  188. /** @brief Generic static function for adding new list nodes.
  189. *
  190. * @param [in] list List to add node to.
  191. * @param [in] data User data for new list node.
  192. * @param [in] uniq - true/false Don't add entry with identical order
  193. * key (when the compareFn() returns 0)
  194. * @param [in] find - true/false Function returns list node if there is
  195. * identical entry. Or NULL if find is false.
  196. * @return Newly added list node.
  197. */
  198. static faux_list_node_t *faux_list_add_generic(faux_list_t *list, void *data,
  199. bool_t uniq, bool_t find) {
  200. faux_list_node_t *node = NULL;
  201. faux_list_node_t *iter = NULL;
  202. assert(list);
  203. assert(data);
  204. if (!list || !data)
  205. return NULL;
  206. node = faux_list_new_node(data);
  207. if (!node)
  208. return NULL;
  209. // Empty list.
  210. if (!list->head) {
  211. list->head = node;
  212. list->tail = node;
  213. list->len++;
  214. return node;
  215. }
  216. // Not sorted list. Add to the tail.
  217. if (!list->compareFn) {
  218. node->prev = list->tail;
  219. node->next = NULL;
  220. list->tail->next = node;
  221. list->tail = node;
  222. list->len++;
  223. return node;
  224. }
  225. // Sorted list.
  226. iter = list->tail;
  227. while (iter) {
  228. int res = list->compareFn(node->data, iter->data);
  229. if (uniq && (0 == res)) {
  230. faux_list_free_node(node);
  231. return (find ? iter : NULL);
  232. }
  233. if (res >= 0) {
  234. node->next = iter->next;
  235. node->prev = iter;
  236. iter->next = node;
  237. if (node->next)
  238. node->next->prev = node;
  239. break;
  240. }
  241. iter = iter->prev;
  242. }
  243. // Insert node into the list head
  244. if (!iter) {
  245. node->next = list->head;
  246. node->prev = NULL;
  247. list->head->prev = node;
  248. list->head = node;
  249. }
  250. if (!node->next)
  251. list->tail = node;
  252. list->len++;
  253. return node;
  254. }
  255. /** @brief Adds user data (not unique) to the list.
  256. *
  257. * The user data is not unique. It means that two equal user data instances
  258. * can be added to the list.
  259. *
  260. * @param [in] list List to add entry to.
  261. * @param [in] data User data.
  262. * @return Newly created list node or NULL on error.
  263. */
  264. faux_list_node_t *faux_list_add(faux_list_t *list, void *data) {
  265. return faux_list_add_generic(list, data, BOOL_FALSE, BOOL_FALSE);
  266. }
  267. /** @brief Adds user data (unique) to the list.
  268. *
  269. * The user data must be unique. It means that two equal user data instances
  270. * can not be added to the list. Function will return NULL if equal user
  271. * data is already in the list.
  272. *
  273. * @param [in] list List to add entry to.
  274. * @param [in] data User data.
  275. * @return Newly created list node or NULL on error.
  276. */
  277. faux_list_node_t *faux_list_add_uniq(faux_list_t *list, void *data) {
  278. return faux_list_add_generic(list, data, BOOL_TRUE, BOOL_FALSE);
  279. }
  280. /** @brief Adds user data (unique) to the list or return equal existent node.
  281. *
  282. * The user data must be unique in this case. Function compares list nodes
  283. * with the new one. If equal node is already in the list then function
  284. * returns this node. Else new unique node will be added to the list.
  285. *
  286. * @param [in] list List to add entry to.
  287. * @param [in] data User data.
  288. * @return Newly created list node, existent equal node or NULL on error.
  289. */
  290. faux_list_node_t *faux_list_add_find(faux_list_t *list, void *data) {
  291. return faux_list_add_generic(list, data, BOOL_TRUE, BOOL_TRUE);
  292. }
  293. /** Takes away list node from the list.
  294. *
  295. * Function removes list node from the list and returns user data
  296. * stored in this node.
  297. *
  298. * @param [in] list List to take away node from.
  299. * @param [in] node List node to take away.
  300. * @return User data from removed node or NULL on error.
  301. */
  302. void *faux_list_takeaway(faux_list_t *list, faux_list_node_t *node) {
  303. void *data = NULL;
  304. assert(list);
  305. assert(node);
  306. if (!list || !node)
  307. return NULL;
  308. if (node->prev)
  309. node->prev->next = node->next;
  310. else
  311. list->head = node->next;
  312. if (node->next)
  313. node->next->prev = node->prev;
  314. else
  315. list->tail = node->prev;
  316. list->len--;
  317. data = faux_list_data(node);
  318. faux_list_free_node(node);
  319. return data;
  320. }
  321. /** @brief Deletes list node from the list.
  322. *
  323. * Functions removes node from the list and free user data memory if
  324. * freeFn callback was defined while list creation. If freeFn callback
  325. * is not defined then function is the same as faux_list_takeaway().
  326. *
  327. * @param [in] list List to delete node from.
  328. * @param [in] node List node to delete.
  329. * @return 0 on success, < 0 on error.
  330. */
  331. int faux_list_del(faux_list_t *list, faux_list_node_t *node) {
  332. void *data = NULL;
  333. assert(list);
  334. assert(node);
  335. if (!list || !node)
  336. return -1;
  337. data = faux_list_takeaway(list, node);
  338. assert(data);
  339. if (!data) // Illegal case
  340. return -1;
  341. if (list->freeFn)
  342. list->freeFn(data);
  343. return 0;
  344. }
  345. /** @brief Search list for matching (match function).
  346. *
  347. * Function iterates through the list and executes special matching user defined
  348. * callback function matchFn for every list node. User can provide "userkey" -
  349. * the data that matchFn can use how it wants. The matchFn is arbitrary
  350. * argument. The userkey argument can be NULL. The function will immediately
  351. * return matched list node. To continue searching the saveptr argument contains
  352. * current iterator. So user can call to faux_list_match_node() for several
  353. * times and gets all matched nodes from list.
  354. *
  355. * Prototype for matchFn callback function:
  356. * @code
  357. * int faux_list_match_fn(const void *key, const void *data);
  358. * @endcode
  359. *
  360. * @param [in] list List.
  361. * @param [in] matchFn User defined matching callback function.
  362. * @param [in] userkey User defined data to use in matchFn function.
  363. * @param [in,out] saveptr Ptr to save iterator.
  364. * @return Matched list node.
  365. */
  366. faux_list_node_t *faux_list_match_node(const faux_list_t *list,
  367. faux_list_match_fn matchFn, const void *userkey,
  368. faux_list_node_t **saveptr) {
  369. faux_list_node_t *iter = NULL;
  370. assert(list);
  371. assert(matchFn);
  372. if (!list || !matchFn || !list->head)
  373. return NULL;
  374. if (saveptr)
  375. iter = *saveptr;
  376. if (!iter)
  377. iter = list->head;
  378. while (iter) {
  379. int res = 0;
  380. faux_list_node_t *node = iter;
  381. iter = faux_list_next_node(iter);
  382. if (saveptr)
  383. *saveptr = iter;
  384. res = matchFn(userkey, faux_list_data(node));
  385. if (0 == res)
  386. return node;
  387. if (res < 0) // No chances to find match
  388. return NULL;
  389. }
  390. return NULL;
  391. }
  392. /** @brief Search list for matching (match function) and returns user data.
  393. *
  394. * Same as faux_list_match_node() but returns user data structure.
  395. *
  396. * @sa faux_list_match_node()
  397. */
  398. void *faux_list_match(const faux_list_t *list, faux_list_match_fn matchFn,
  399. const void *userkey, faux_list_node_t **saveptr) {
  400. faux_list_node_t *res = faux_list_match_node(list, matchFn,
  401. userkey, saveptr);
  402. if (!res)
  403. return NULL;
  404. return faux_list_data(res);
  405. }
  406. /** @brief Search list for first matching (match function).
  407. *
  408. * Same as faux_list_match_node() but search for the fisrt matching.
  409. * Doesn't use saveptr iterator.
  410. *
  411. * @sa faux_list_match_node()
  412. */
  413. faux_list_node_t *faux_list_find_node(const faux_list_t *list,
  414. faux_list_match_fn matchFn, const void *userkey) {
  415. return faux_list_match_node(list, matchFn, userkey, NULL);
  416. }
  417. /** @brief Search list for first matching (match function) and returns user data.
  418. *
  419. * Same as faux_list_match_node() but returns user data structure and search
  420. * only for the first matching. Doesn't use saveptr iterator.
  421. *
  422. * @sa faux_list_match_node()
  423. */
  424. void *faux_list_find(const faux_list_t *list, faux_list_match_fn matchFn,
  425. const void *userkey) {
  426. return faux_list_match(list, matchFn, userkey, NULL);
  427. }