list.c 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699
  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. {
  25. faux_list_node_t *node = NULL;
  26. node = faux_zmalloc(sizeof(*node));
  27. assert(node);
  28. if (!node)
  29. return NULL;
  30. // Initialize
  31. node->prev = NULL;
  32. node->next = NULL;
  33. node->data = data;
  34. return node;
  35. }
  36. /** @brief Free list node instance.
  37. *
  38. * @param [in] node List node instance.
  39. */
  40. static void faux_list_free_node(faux_list_node_t *node)
  41. {
  42. faux_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. {
  51. assert(node);
  52. if (!node)
  53. return NULL;
  54. return node->prev;
  55. }
  56. /** @brief Gets next list node.
  57. *
  58. * @param [in] this List node instance.
  59. * @return List node next in list.
  60. */
  61. faux_list_node_t *faux_list_next_node(const faux_list_node_t *node)
  62. {
  63. assert(node);
  64. if (!node)
  65. return NULL;
  66. return node->next;
  67. }
  68. /** @brief Gets user data from list node.
  69. *
  70. * @param [in] this List node instance.
  71. * @return User data stored within specified list node.
  72. */
  73. void *faux_list_data(const faux_list_node_t *node)
  74. {
  75. assert(node);
  76. if (!node)
  77. return NULL;
  78. return node->data;
  79. }
  80. /** @brief Iterate through each list node.
  81. *
  82. * On each call to this function the iterator will change its value.
  83. * Before function using the iterator must be initialised by list head node.
  84. *
  85. * @param [in,out] iter List node ptr used as an iterator.
  86. * @return List node or NULL if list elements are over.
  87. */
  88. faux_list_node_t *faux_list_each_node(faux_list_node_t **iter)
  89. {
  90. faux_list_node_t *current_node = *iter;
  91. // No assert() on current_node. NULL iterator is normal
  92. if (!current_node)
  93. return NULL;
  94. *iter = faux_list_next_node(current_node);
  95. return current_node;
  96. }
  97. /** @brief Iterate through each list node. Reverse order.
  98. *
  99. * On each call to this function the iterator will change its value.
  100. * Before function using the iterator must be initialised by list tail node.
  101. *
  102. * @param [in,out] iter List node ptr used as an iterator.
  103. * @return List node or NULL if list elements are over.
  104. */
  105. faux_list_node_t *faux_list_eachr_node(faux_list_node_t **iter)
  106. {
  107. faux_list_node_t *current_node = *iter;
  108. // No assert() on current_node. NULL iterator is normal
  109. if (!current_node)
  110. return NULL;
  111. *iter = faux_list_prev_node(current_node);
  112. return current_node;
  113. }
  114. /** @brief Iterate through each list node and returns user data.
  115. *
  116. * On each call to this function the iterator will change its value.
  117. * Before function using the iterator must be initialised by list head node.
  118. *
  119. * @param [in,out] iter List node ptr used as an iterator.
  120. * @return User data or NULL if list elements are over.
  121. */
  122. void *faux_list_each(faux_list_node_t **iter)
  123. {
  124. faux_list_node_t *current_node = NULL;
  125. // No assert() on current_node. NULL iterator is normal
  126. if (!*iter)
  127. return NULL;
  128. current_node = faux_list_each_node(iter);
  129. return faux_list_data(current_node);
  130. }
  131. /** @brief Iterate (reverse order) through each list node and returns user data.
  132. *
  133. * On each call to this function the iterator will change its value.
  134. * Before function using the iterator must be initialised by list head node.
  135. *
  136. * @param [in,out] iter List node ptr used as an iterator.
  137. * @return User data or NULL if list elements are over.
  138. */
  139. void *faux_list_eachr(faux_list_node_t **iter)
  140. {
  141. faux_list_node_t *current_node = NULL;
  142. // No assert() on current_node. NULL iterator is normal
  143. if (!*iter)
  144. return NULL;
  145. current_node = faux_list_eachr_node(iter);
  146. return faux_list_data(current_node);
  147. }
  148. /** @brief Allocate and initialize bidirectional list.
  149. *
  150. * Prototypes for callback functions:
  151. * @code
  152. * int (*faux_list_cmp_fn)(const void *new_item, const void *list_item);
  153. * void faux_list_free_fn(void *data);
  154. * @endcode
  155. *
  156. * @param [in] sorted If list is sorted - FAUX_LIST_SORTED, unsorted - FAUX_LIST_UNSORTED.
  157. * @param [in] unique If list entry is unique - FAUX_LIST_UNIQUE, else - FAUX_LIST_NONUNIQUE.
  158. * @param [in] compareFn Callback function to compare two user data instances
  159. * to sort list.
  160. * @param [in] freeFn Callback function to free user data.
  161. * @return Newly created bidirectional list or NULL on error.
  162. */
  163. faux_list_t *faux_list_new(faux_list_sorted_e sorted, faux_list_unique_e unique,
  164. faux_list_cmp_fn cmpFn, faux_list_kcmp_fn kcmpFn,
  165. faux_list_free_fn freeFn)
  166. {
  167. faux_list_t *list = NULL;
  168. // Sorted list must have cmpFn
  169. if (sorted && !cmpFn)
  170. return NULL;
  171. // Unique list must have cmpFn
  172. if (unique && !cmpFn)
  173. return NULL;
  174. list = faux_zmalloc(sizeof(*list));
  175. assert(list);
  176. if (!list)
  177. return NULL;
  178. // Initialize
  179. list->head = NULL;
  180. list->tail = NULL;
  181. list->sorted = sorted;
  182. list->unique = unique;
  183. list->cmpFn = cmpFn;
  184. list->kcmpFn = kcmpFn;
  185. list->freeFn = freeFn;
  186. list->len = 0;
  187. return list;
  188. }
  189. /** @brief Delete all entries from list
  190. *
  191. * Removes and frees all list entries.
  192. *
  193. * @param [in] list List to empty.
  194. * @return Number of deleted entries or < 0 on error.
  195. */
  196. ssize_t faux_list_del_all(faux_list_t *list)
  197. {
  198. faux_list_node_t *iter = NULL;
  199. ssize_t num = 0;
  200. if (!list)
  201. return -1;
  202. while ((iter = faux_list_head(list))) {
  203. faux_list_del(list, iter);
  204. num++;
  205. }
  206. return num;
  207. }
  208. /** @brief Free bidirectional list
  209. *
  210. * Free all nodes and user data from list and finally
  211. * free the list itself. It uses special callback
  212. * function specified by user (while faux_list_new()) to free the abstract
  213. * user data.
  214. *
  215. * @param [in] list List to free.
  216. */
  217. void faux_list_free(faux_list_t *list)
  218. {
  219. faux_list_del_all(list);
  220. faux_free(list);
  221. }
  222. /** @brief Gets head of list.
  223. *
  224. * @param [in] list List.
  225. * @return List node first in list.
  226. */
  227. faux_list_node_t *faux_list_head(const faux_list_t *list)
  228. {
  229. assert(list);
  230. if (!list)
  231. return NULL;
  232. return list->head;
  233. }
  234. /** @brief Gets tail of list.
  235. *
  236. * @param [in] list List.
  237. * @return List node last in list.
  238. */
  239. faux_list_node_t *faux_list_tail(const faux_list_t *list)
  240. {
  241. assert(list);
  242. if (!list)
  243. return NULL;
  244. return list->tail;
  245. }
  246. /** @brief Gets current length of list.
  247. *
  248. * @param [in] list List.
  249. * @return Current length of list.
  250. */
  251. size_t faux_list_len(const faux_list_t *list)
  252. {
  253. assert(list);
  254. if (!list)
  255. return 0;
  256. return list->len;
  257. }
  258. /** @brief Generic static function for adding new list nodes.
  259. *
  260. * @param [in] list List to add node to.
  261. * @param [in] data User data for new list node.
  262. * key (when the cmpFn() returns 0)
  263. * @param [in] find - true/false Function returns list node if there is
  264. * identical entry. Or NULL if find is false.
  265. * @return Newly added list node.
  266. */
  267. static faux_list_node_t *faux_list_add_generic(
  268. faux_list_t *list, void *data, bool_t find)
  269. {
  270. faux_list_node_t *node = NULL;
  271. faux_list_node_t *iter = NULL;
  272. assert(list);
  273. assert(data);
  274. if (!list || !data)
  275. return NULL;
  276. node = faux_list_new_node(data);
  277. if (!node)
  278. return NULL;
  279. // Empty list
  280. if (!list->head) {
  281. list->head = node;
  282. list->tail = node;
  283. list->len++;
  284. return node;
  285. }
  286. // Non-sorted: Insert to tail
  287. if (!list->sorted) {
  288. // Unique: Search through whole list
  289. if (list->unique) {
  290. iter = list->tail;
  291. while (iter) {
  292. int res = list->cmpFn(node->data, iter->data);
  293. if (0 == res) { // Already in list
  294. faux_list_free_node(node);
  295. return (find ? iter : NULL);
  296. }
  297. iter = iter->prev;
  298. }
  299. }
  300. // Add entry to the tail
  301. node->prev = list->tail;
  302. node->next = NULL;
  303. if (list->tail)
  304. list->tail->next = node;
  305. list->tail = node;
  306. list->len++;
  307. return node;
  308. }
  309. // Sorted: Insert from tail
  310. iter = list->tail;
  311. while (iter) {
  312. int res = list->cmpFn(node->data, iter->data);
  313. // Unique: Already exists
  314. if (list->unique && (0 == res)) {
  315. faux_list_free_node(node);
  316. return (find ? iter : NULL);
  317. }
  318. // Non-unique: Entry will be inserted after existent one
  319. if (res >= 0) {
  320. node->next = iter->next;
  321. node->prev = iter;
  322. iter->next = node;
  323. if (node->next)
  324. node->next->prev = node;
  325. break;
  326. }
  327. iter = iter->prev;
  328. }
  329. // Insert node into the list head
  330. if (!iter) {
  331. node->next = list->head;
  332. node->prev = NULL;
  333. list->head->prev = node;
  334. list->head = node;
  335. }
  336. if (!node->next)
  337. list->tail = node;
  338. list->len++;
  339. return node;
  340. }
  341. /** @brief Adds user data to the list.
  342. *
  343. * The user data is not unique. It means that two equal user data instances
  344. * can be added to the list.
  345. *
  346. * @param [in] list List to add entry to.
  347. * @param [in] data User data.
  348. * @return Newly created list node or NULL on error.
  349. */
  350. faux_list_node_t *faux_list_add(faux_list_t *list, void *data)
  351. {
  352. return faux_list_add_generic(list, data, BOOL_FALSE);
  353. }
  354. /** @brief Adds user data (unique) to the list or return equal existent node.
  355. *
  356. * The user data must be unique in this case. Function compares list nodes
  357. * with the new one. If equal node is already in the list then function
  358. * returns this node. Else new unique node will be added to the list.
  359. *
  360. * @param [in] list List to add entry to.
  361. * @param [in] data User data.
  362. * @return Newly created list node, existent equal node or NULL on error.
  363. */
  364. faux_list_node_t *faux_list_add_find(faux_list_t *list, void *data)
  365. {
  366. assert(list);
  367. if (!list)
  368. return NULL;
  369. // Function add_find has no meaning for non-unique list. What is the
  370. // function behaviour? It found entry. Must it return existent entry or
  371. // add new non-unique entry?
  372. if (!list->unique)
  373. return NULL;
  374. return faux_list_add_generic(list, data, BOOL_TRUE);
  375. }
  376. /** Takes away list node from the list.
  377. *
  378. * Function removes list node from the list and returns user data
  379. * stored in this node.
  380. *
  381. * @param [in] list List to take away node from.
  382. * @param [in] node List node to take away.
  383. * @return User data from removed node or NULL on error.
  384. */
  385. void *faux_list_takeaway(faux_list_t *list, faux_list_node_t *node)
  386. {
  387. void *data = NULL;
  388. assert(list);
  389. assert(node);
  390. if (!list || !node)
  391. return NULL;
  392. if (node->prev)
  393. node->prev->next = node->next;
  394. else
  395. list->head = node->next;
  396. if (node->next)
  397. node->next->prev = node->prev;
  398. else
  399. list->tail = node->prev;
  400. list->len--;
  401. data = faux_list_data(node);
  402. faux_list_free_node(node);
  403. return data;
  404. }
  405. /** @brief Deletes list node from the list.
  406. *
  407. * Functions removes node from the list and free user data memory if
  408. * freeFn callback was defined while list creation. If freeFn callback
  409. * is not defined then function is the same as faux_list_takeaway().
  410. *
  411. * @param [in] list List to delete node from.
  412. * @param [in] node List node to delete.
  413. * @return BOOL_TRUE - success, BOOL_FALSE on error.
  414. */
  415. bool_t faux_list_del(faux_list_t *list, faux_list_node_t *node)
  416. {
  417. void *data = NULL;
  418. assert(list);
  419. assert(node);
  420. if (!list || !node)
  421. return BOOL_FALSE;
  422. data = faux_list_takeaway(list, node);
  423. assert(data);
  424. if (!data) // Illegal case
  425. return BOOL_FALSE;
  426. if (list->freeFn)
  427. list->freeFn(data);
  428. return BOOL_TRUE;
  429. }
  430. /** @brief Deletes list node from the list by user key.
  431. *
  432. * @sa faux_list_del()
  433. * @param [in] list List to delete node from.
  434. * @param [in] node User key to find node to delete.
  435. * @return BOOL_TRUE - success, BOOL_FALSE on error.
  436. */
  437. bool_t faux_list_kdel(faux_list_t *list, const void *userkey)
  438. {
  439. faux_list_node_t *node = NULL;
  440. assert(list);
  441. assert(userkey);
  442. if (!list || !userkey)
  443. return BOOL_FALSE;
  444. node = faux_list_kfind_node(list, userkey);
  445. if (!node)
  446. return BOOL_FALSE; // Not found
  447. return faux_list_del(list, node);
  448. }
  449. /** @brief Search list for matching (match function).
  450. *
  451. * Function iterates through the list and executes special matching user defined
  452. * callback function matchFn for every list node. User can provide "userkey" -
  453. * the data that matchFn can use how it wants. The matchFn is arbitrary
  454. * argument. The userkey argument can be NULL. The function will immediately
  455. * return matched list node. To continue searching the saveptr argument contains
  456. * current iterator. So user can call to faux_list_match_node() for several
  457. * times and gets all matched nodes from list.
  458. *
  459. * Prototype for matchFn callback function:
  460. * @code
  461. * int (*faux_list_kcmp_fn)(const void *key, const void *list_item);
  462. * @endcode
  463. *
  464. * @param [in] list List.
  465. * @param [in] matchFn User defined matching callback function.
  466. * @param [in] userkey User defined data to use in matchFn function.
  467. * @param [in,out] saveptr Ptr to save iterator.
  468. * @return Matched list node.
  469. */
  470. faux_list_node_t *faux_list_match_node(const faux_list_t *list,
  471. faux_list_kcmp_fn matchFn, const void *userkey,
  472. faux_list_node_t **saveptr)
  473. {
  474. faux_list_node_t *iter = NULL;
  475. assert(list);
  476. assert(matchFn);
  477. if (!list || !matchFn || !list->head)
  478. return NULL;
  479. if (saveptr)
  480. iter = *saveptr;
  481. if (!iter)
  482. iter = list->head;
  483. while (iter) {
  484. int res = 0;
  485. faux_list_node_t *node = iter;
  486. iter = faux_list_next_node(node);
  487. if (saveptr)
  488. *saveptr = iter;
  489. res = matchFn(userkey, faux_list_data(node));
  490. if (0 == res)
  491. return node;
  492. if (list->sorted && (res < 0)) // No chances to find match
  493. return NULL;
  494. }
  495. return NULL;
  496. }
  497. /** @brief Search list for matching (key cmp function).
  498. *
  499. * Same as faux_list_match_node() but uses userkey compare function defined
  500. * while faux_list_new() function call.
  501. *
  502. * @sa faux_list_match_node()
  503. */
  504. faux_list_node_t *faux_list_kmatch_node(const faux_list_t *list,
  505. const void *userkey, faux_list_node_t **saveptr)
  506. {
  507. assert(list);
  508. if (!list)
  509. return NULL;
  510. return faux_list_match_node(list, list->kcmpFn, userkey, saveptr);
  511. }
  512. /** @brief Search list for matching (match function) and returns user data.
  513. *
  514. * Same as faux_list_match_node() but returns user data structure.
  515. *
  516. * @sa faux_list_match_node()
  517. */
  518. void *faux_list_match(const faux_list_t *list, faux_list_kcmp_fn matchFn,
  519. const void *userkey, faux_list_node_t **saveptr)
  520. {
  521. faux_list_node_t *res =
  522. faux_list_match_node(list, matchFn, userkey, saveptr);
  523. if (!res)
  524. return NULL;
  525. return faux_list_data(res);
  526. }
  527. /** @brief Search list for matching (key cmp function) and returns user data.
  528. *
  529. * Same as faux_list_match() but uses userkey compare function defined
  530. * while faux_list_new() function call.
  531. *
  532. * @sa faux_list_match_node()
  533. */
  534. void *faux_list_kmatch(const faux_list_t *list, const void *userkey,
  535. faux_list_node_t **saveptr)
  536. {
  537. assert(list);
  538. if (!list)
  539. return NULL;
  540. return faux_list_match(list, list->kcmpFn, userkey, saveptr);
  541. }
  542. /** @brief Search list for first matching (match function).
  543. *
  544. * Same as faux_list_match_node() but search for the fisrt matching.
  545. * Doesn't use saveptr iterator.
  546. *
  547. * @sa faux_list_match_node()
  548. */
  549. faux_list_node_t *faux_list_find_node(const faux_list_t *list,
  550. faux_list_kcmp_fn matchFn, const void *userkey)
  551. {
  552. return faux_list_match_node(list, matchFn, userkey, NULL);
  553. }
  554. /** @brief Search list for first matching (key cmp function).
  555. *
  556. * Same as faux_list_find_node() but uses userkey compare function defined
  557. * while faux_list_new() function call.
  558. *
  559. * @sa faux_list_match_node()
  560. */
  561. faux_list_node_t *faux_list_kfind_node(const faux_list_t *list,
  562. const void *userkey)
  563. {
  564. return faux_list_find_node(list, list->kcmpFn, userkey);
  565. }
  566. /** @brief Search list for first matching (match function) and returns user data.
  567. *
  568. * Same as faux_list_match_node() but returns user data structure and search
  569. * only for the first matching. Doesn't use saveptr iterator.
  570. *
  571. * @sa faux_list_match_node()
  572. */
  573. void *faux_list_find(const faux_list_t *list, faux_list_kcmp_fn matchFn,
  574. const void *userkey)
  575. {
  576. return faux_list_match(list, matchFn, userkey, NULL);
  577. }
  578. /** @brief Search list for first matching (key cmp function). Returns user data.
  579. *
  580. * Same as faux_list_find() but uses userkey compare function defined
  581. * while faux_list_new() function call.
  582. *
  583. * @sa faux_list_match_node()
  584. */
  585. void *faux_list_kfind(const faux_list_t *list,
  586. const void *userkey)
  587. {
  588. return faux_list_find(list, list->kcmpFn, userkey);
  589. }