list.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221
  1. #include <stdlib.h>
  2. #include <assert.h>
  3. #include <string.h>
  4. #include "private.h"
  5. /*--------------------------------------------------------- */
  6. static inline void lub_list_init(lub_list_t * this,
  7. lub_list_compare_fn compareFn)
  8. {
  9. this->head = NULL;
  10. this->tail = NULL;
  11. this->compareFn = compareFn;
  12. this->len = 0;
  13. }
  14. /*--------------------------------------------------------- */
  15. lub_list_t *lub_list_new(lub_list_compare_fn compareFn)
  16. {
  17. lub_list_t *this;
  18. this = malloc(sizeof(*this));
  19. assert(this);
  20. lub_list_init(this, compareFn);
  21. return this;
  22. }
  23. /*--------------------------------------------------------- */
  24. inline void lub_list_free(lub_list_t *this)
  25. {
  26. free(this);
  27. }
  28. /*--------------------------------------------------------- */
  29. inline lub_list_node_t *lub_list__get_head(lub_list_t *this)
  30. {
  31. return this->head;
  32. }
  33. /*--------------------------------------------------------- */
  34. inline lub_list_node_t *lub_list__get_tail(lub_list_t *this)
  35. {
  36. return this->tail;
  37. }
  38. /*--------------------------------------------------------- */
  39. static inline void lub_list_node_init(lub_list_node_t *this,
  40. void *data)
  41. {
  42. this->prev = this->next = NULL;
  43. this->data = data;
  44. }
  45. /*--------------------------------------------------------- */
  46. lub_list_node_t *lub_list_node_new(void *data)
  47. {
  48. lub_list_node_t *this;
  49. this = malloc(sizeof(*this));
  50. assert(this);
  51. lub_list_node_init(this, data);
  52. return this;
  53. }
  54. /*--------------------------------------------------------- */
  55. inline lub_list_node_t *lub_list_iterator_init(lub_list_t *this)
  56. {
  57. return this->head;
  58. }
  59. /*--------------------------------------------------------- */
  60. inline lub_list_node_t *lub_list_node__get_prev(lub_list_node_t *this)
  61. {
  62. return this->prev;
  63. }
  64. /*--------------------------------------------------------- */
  65. inline lub_list_node_t *lub_list_node__get_next(lub_list_node_t *this)
  66. {
  67. return this->next;
  68. }
  69. /*--------------------------------------------------------- */
  70. inline lub_list_node_t *lub_list_iterator_next(lub_list_node_t *this)
  71. {
  72. return lub_list_node__get_next(this);
  73. }
  74. /*--------------------------------------------------------- */
  75. inline lub_list_node_t *lub_list_iterator_prev(lub_list_node_t *this)
  76. {
  77. return lub_list_node__get_prev(this);
  78. }
  79. /*--------------------------------------------------------- */
  80. inline void lub_list_node_free(lub_list_node_t *this)
  81. {
  82. free(this);
  83. }
  84. /*--------------------------------------------------------- */
  85. inline void *lub_list_node__get_data(lub_list_node_t *this)
  86. {
  87. return this->data;
  88. }
  89. /*--------------------------------------------------------- */
  90. lub_list_node_t *lub_list_add(lub_list_t *this, void *data)
  91. {
  92. lub_list_node_t *node = lub_list_node_new(data);
  93. lub_list_node_t *iter;
  94. this->len++;
  95. /* Empty list */
  96. if (!this->head) {
  97. this->head = node;
  98. this->tail = node;
  99. return node;
  100. }
  101. /* Not sorted list. Add to the tail. */
  102. if (!this->compareFn) {
  103. node->prev = this->tail;
  104. node->next = NULL;
  105. this->tail->next = node;
  106. this->tail = node;
  107. return node;
  108. }
  109. /* Sorted list */
  110. iter = this->tail;
  111. while (iter) {
  112. if (this->compareFn(node->data, iter->data) >= 0) {
  113. node->next = iter->next;
  114. node->prev = iter;
  115. iter->next = node;
  116. if (node->next)
  117. node->next->prev = node;
  118. break;
  119. }
  120. iter = iter->prev;
  121. }
  122. /* Insert node into the list head */
  123. if (!iter) {
  124. node->next = this->head;
  125. node->prev = NULL;
  126. this->head->prev = node;
  127. this->head = node;
  128. }
  129. if (!node->next)
  130. this->tail = node;
  131. return node;
  132. }
  133. /*--------------------------------------------------------- */
  134. void lub_list_del(lub_list_t *this, lub_list_node_t *node)
  135. {
  136. if (node->prev)
  137. node->prev->next = node->next;
  138. else
  139. this->head = node->next;
  140. if (node->next)
  141. node->next->prev = node->prev;
  142. else
  143. this->tail = node->prev;
  144. this->len--;
  145. }
  146. /*--------------------------------------------------------- */
  147. inline void lub_list_node_copy(lub_list_node_t *dst, lub_list_node_t *src)
  148. {
  149. memcpy(dst, src, sizeof(lub_list_node_t));
  150. }
  151. /*--------------------------------------------------------- */
  152. lub_list_node_t *lub_list_search_node(lub_list_t *this, void *data)
  153. {
  154. lub_list_node_t *iter;
  155. int res;
  156. /* Empty list */
  157. if (!this->head)
  158. return NULL;
  159. /* Not sorted list. Can't search. */
  160. if (!this->compareFn)
  161. return NULL;
  162. /* Sorted list */
  163. iter = this->head;
  164. while (iter) {
  165. res = this->compareFn(data, iter->data);
  166. if (!res)
  167. return iter;
  168. if (res < 0)
  169. break; // No chances to find it
  170. iter = iter->next;
  171. }
  172. return NULL;
  173. }
  174. /*--------------------------------------------------------- */
  175. void *lub_list_search(lub_list_t *this, void *data)
  176. {
  177. lub_list_node_t *iter = lub_list_search_node(this, data);
  178. return iter->data;
  179. }
  180. /*--------------------------------------------------------- */
  181. inline unsigned int lub_list_len(lub_list_t *this)
  182. {
  183. return this->len;
  184. }
  185. /*--------------------------------------------------------- */