comparison: src/linked_list.c
src/linked_list.c
- changeset 447
- 87b2cdd668ed
- parent 446
- 668757098b73
- child 448
- 37c5d2fdb36b
equal
deleted
inserted
replaced
| 446:668757098b73 | 447:87b2cdd668ed |
|---|---|
| 91 return 0; | 91 return 0; |
| 92 } | 92 } |
| 93 | 93 |
| 94 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ | 94 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ |
| 95 | 95 |
| 96 typedef struct { | 96 typedef struct cx_linked_list_node cx_linked_list_node; |
| 97 void *prev; | 97 struct cx_linked_list_node { |
| 98 void *next; | 98 cx_linked_list_node *prev; |
| 99 cx_linked_list_node *next; | |
| 99 char payload[]; | 100 char payload[]; |
| 100 } cx_linked_list_node; | 101 }; |
| 101 | 102 |
| 102 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) | 103 #define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev) |
| 103 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) | 104 #define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next) |
| 104 | 105 |
| 105 typedef struct { | 106 typedef struct { |
| 129 list->size++; | 130 list->size++; |
| 130 | 131 |
| 131 return 0; | 132 return 0; |
| 132 } | 133 } |
| 133 | 134 |
| 135 static cx_linked_list_node *cx_ll_node_at(cx_linked_list* list, size_t index) { | |
| 136 if (index >= list->base.size) { | |
| 137 return NULL; | |
| 138 } else if (index > list->base.size / 2) { | |
| 139 return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index); | |
| 140 } else { | |
| 141 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); | |
| 142 } | |
| 143 } | |
| 144 | |
| 134 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { | 145 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { |
| 135 cx_linked_list *ll = (cx_linked_list *) list; | 146 cx_linked_list *ll = (cx_linked_list *) list; |
| 136 // TODO: implement using low level API | 147 // TODO: implement using low level API |
| 137 return 1; | 148 return 1; |
| 138 } | 149 } |
| 139 | 150 |
| 140 static int cx_ll_remove(cx_list_s *list, size_t index) { | 151 static int cx_ll_remove(cx_list_s *list, size_t index) { |
| 141 if (index >= list->size) { | 152 cx_linked_list *ll = (cx_linked_list *) list; |
| 142 return 1; | 153 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 143 } | 154 |
| 144 cx_linked_list *ll = (cx_linked_list *) list; | 155 // out-of-bounds check |
| 145 // TODO: implement using low level API | 156 if (node == NULL) return 1; |
| 157 | |
| 158 // change left side connection | |
| 159 if (node->prev == NULL) { | |
| 160 ll->begin = node->next; | |
| 161 } else { | |
| 162 node->prev->next = node->next; | |
| 163 } | |
| 164 | |
| 165 // change right side connection | |
| 166 if (node->next == NULL) { | |
| 167 ll->end = node->prev; | |
| 168 } else { | |
| 169 node->next->prev = node->prev; | |
| 170 } | |
| 171 | |
| 172 // adjust size | |
| 173 list->size--; | |
| 174 | |
| 175 // free and return | |
| 176 cxFree(list->allocator, node); | |
| 177 | |
| 146 return 0; | 178 return 0; |
| 147 } | 179 } |
| 148 | 180 |
| 149 static void *cx_ll_at(cx_list_s *list, size_t index) { | 181 static void *cx_ll_at(cx_list_s *list, size_t index) { |
| 150 cx_linked_list *ll = (cx_linked_list *) list; | 182 cx_linked_list *ll = (cx_linked_list *) list; |
| 151 cx_linked_list_node *node; | 183 cx_linked_list_node *node = cx_ll_node_at(ll, index); |
| 152 if (index >= list->size) { | |
| 153 node = NULL; | |
| 154 } else if (index > list->size / 2) { | |
| 155 node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index); | |
| 156 } else { | |
| 157 node = cx_linked_list_at(ll->begin, 0, CX_LL_LOC_NEXT, index); | |
| 158 } | |
| 159 return node == NULL ? NULL : &node->payload; | 184 return node == NULL ? NULL : &node->payload; |
| 160 } | 185 } |
| 161 | 186 |
| 162 static size_t cx_ll_find(cx_list_s *list, void *elem) { | 187 static size_t cx_ll_find(cx_list_s *list, void *elem) { |
| 163 CxListComparator cmp = list->cmpfunc; | 188 CxListComparator cmp = list->cmpfunc; |
