Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 439
9a5adedd6de6
parent 438
cd3069757010
child 440
003aa0a78e1e
equal deleted inserted replaced
438:cd3069757010 439:9a5adedd6de6
97 void *prev; 97 void *prev;
98 void *next; 98 void *next;
99 char payload[]; 99 char payload[];
100 }; 100 };
101 101
102 #define CX_LL_LOC_PREV offsetof(struct cx_linked_list_node, prev)
103 #define CX_LL_LOC_NEXT offsetof(struct cx_linked_list_node, next)
104
102 typedef struct { 105 typedef struct {
103 cx_list_s base; 106 cx_list_s base;
104 void *begin; 107 void *begin;
105 void *end; 108 void *end;
106 ptrdiff_t loc_prev; 109 ptrdiff_t loc_prev;
118 node->next = node->prev = NULL; 121 node->next = node->prev = NULL;
119 memcpy(node->payload, elem, list->itemsize); 122 memcpy(node->payload, elem, list->itemsize);
120 123
121 int ret = cx_linked_list_add( 124 int ret = cx_linked_list_add(
122 &ll->begin, &ll->end, 125 &ll->begin, &ll->end,
123 offsetof(struct cx_linked_list_node, prev), 126 CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
124 offsetof(struct cx_linked_list_node, next),
125 node 127 node
126 ); 128 );
127 if (ret == 0) { 129 if (ret == 0) {
128 list->size++; 130 list->size++;
129 return 0; 131 return 0;
143 return 1; 145 return 1;
144 } 146 }
145 cx_linked_list *ll = (cx_linked_list *) list; 147 cx_linked_list *ll = (cx_linked_list *) list;
146 // TODO: implement using low level API 148 // TODO: implement using low level API
147 return 0; 149 return 0;
150 }
151
152 static void *cx_ll_at(cx_list_s *list, size_t index) {
153 cx_linked_list *ll = (cx_linked_list *) list;
154 struct cx_linked_list_node *node;
155 if (index > list->size / 2) {
156 node = cx_linked_list_at(ll->begin, 0, CX_LL_LOC_NEXT, index);
157 } else {
158 node = cx_linked_list_at(ll->end, list->size, CX_LL_LOC_PREV, index);
159 }
160 return &node->payload;
148 } 161 }
149 162
150 static size_t cx_ll_find(cx_list_s *list, void *elem) { 163 static size_t cx_ll_find(cx_list_s *list, void *elem) {
151 CxListComparator cmp = list->cmpfunc; 164 CxListComparator cmp = list->cmpfunc;
152 cx_linked_list *ll = (cx_linked_list *) list; 165 cx_linked_list *ll = (cx_linked_list *) list;
162 } 175 }
163 return index; 176 return index;
164 } 177 }
165 178
166 static void *cx_ll_last(cx_list_s *list) { 179 static void *cx_ll_last(cx_list_s *list) {
167 cx_linked_list *linkedList = (cx_linked_list *) list; 180 cx_linked_list *ll = (cx_linked_list *) list;
168 struct cx_linked_list_node *last = cx_linked_list_last( 181 struct cx_linked_list_node *last = cx_linked_list_last(NULL, &ll->end, CX_LL_LOC_NEXT);
169 NULL, &linkedList->end, offsetof(struct cx_linked_list_node, next));
170 return &last->payload; 182 return &last->payload;
171 } 183 }
172 184
173 cx_list_class cx_linked_list_class = { 185 cx_list_class cx_linked_list_class = {
174 cx_ll_add, 186 cx_ll_add,
175 cx_ll_insert, 187 cx_ll_insert,
176 cx_ll_remove, 188 cx_ll_remove,
189 cx_ll_at,
177 cx_ll_find, 190 cx_ll_find,
178 cx_ll_last 191 cx_ll_last
179 }; 192 };
180 193
181 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) { 194 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t item_size) {
188 list->base.cmpfunc = comparator; 201 list->base.cmpfunc = comparator;
189 list->base.itemsize = item_size; 202 list->base.itemsize = item_size;
190 list->base.capacity = SIZE_MAX; 203 list->base.capacity = SIZE_MAX;
191 204
192 list->begin = NULL; 205 list->begin = NULL;
193 list->loc_prev = offsetof(struct cx_linked_list_node, prev); 206 list->loc_prev = CX_LL_LOC_PREV;
194 list->loc_next = offsetof(struct cx_linked_list_node, next); 207 list->loc_next = CX_LL_LOC_NEXT;
195 208
196 CxList result = (CxList) list; 209 CxList result = (CxList) list;
197 cxLinkedListRecalculateSize(result); 210 cxLinkedListRecalculateSize(result);
198 return result; 211 return result;
199 } 212 }

Mercurial Repository: ucx

mercurial