list.c 4.3 KB

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