1
0

list.c 3.8 KB

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