Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 448
37c5d2fdb36b
parent 447
87b2cdd668ed
child 451
db06dda7ac4d
equal deleted inserted replaced
447:87b2cdd668ed 448:37c5d2fdb36b
107 cx_list_s base; 107 cx_list_s base;
108 cx_linked_list_node *begin; 108 cx_linked_list_node *begin;
109 cx_linked_list_node *end; 109 cx_linked_list_node *end;
110 } cx_linked_list; 110 } cx_linked_list;
111 111
112 static int cx_ll_add(cx_list_s *list, void *elem) { 112 static cx_linked_list_node *cx_ll_node_at(cx_linked_list *list, size_t index) {
113 cx_linked_list *ll = (cx_linked_list *) list;
114
115 cx_linked_list_node *node = cxMalloc(list->allocator,
116 sizeof(cx_linked_list_node) + list->itemsize);
117 if (node == NULL)
118 return 1;
119
120 memcpy(node->payload, elem, list->itemsize);
121 node->next = NULL;
122
123 if (ll->begin == NULL) {
124 ll->begin = ll->end = node;
125 } else {
126 // per contract of this linked list we know that end must be non-null
127 ll->end->next = node;
128 ll->end = node;
129 }
130 list->size++;
131
132 return 0;
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) { 113 if (index >= list->base.size) {
137 return NULL; 114 return NULL;
138 } else if (index > list->base.size / 2) { 115 } else if (index > list->base.size / 2) {
139 return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index); 116 return cx_linked_list_at(list->end, list->base.size, CX_LL_LOC_PREV, index);
140 } else { 117 } else {
141 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index); 118 return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
142 } 119 }
143 } 120 }
144 121
145 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) { 122 static int cx_ll_insert(cx_list_s *list, size_t index, void *elem) {
146 cx_linked_list *ll = (cx_linked_list *) list; 123 // out-of bounds check
147 // TODO: implement using low level API 124 if (index > list->size) return 1;
148 return 1; 125
126 // cast a linked list pointer
127 cx_linked_list *ll = (cx_linked_list *) list;
128
129 // create the new node
130 cx_linked_list_node *node = cxMalloc(list->allocator,
131 sizeof(cx_linked_list_node) + list->itemsize);
132
133 // sortir if failed
134 if (node == NULL) return 1;
135
136 // copy payload to the new node
137 memcpy(node->payload, elem, list->itemsize);
138
139 // check if this is the first node
140 if (ll->begin == NULL) {
141 node->prev = node->next = NULL;
142 ll->begin = ll->end = node;
143 } else {
144 // check if this shall be the new end node
145 if (index == list->size) {
146 ll->end->next = node;
147 node->prev = ll->end;
148 node->next = NULL;
149 ll->end = node;
150 }
151 // check if this shall be the new start node
152 else if (index == 0) {
153 ll->begin->prev = node;
154 node->next = ll->begin;
155 node->prev = NULL;
156 ll->begin = node;
157 } else {
158 // find the node at the current index
159 cx_linked_list_node *cur = cx_ll_node_at(ll, index);
160
161 // insert before that node
162 // (we know all ptr are non-null because we handled all other cases before)
163 node->next = cur;
164 node->prev = cur->prev;
165 cur->prev = node;
166 node->prev->next = node;
167 }
168 }
169
170 // increase the size and return
171 list->size++;
172 return 0;
173 }
174
175 static int cx_ll_add(cx_list_s *list, void *elem) {
176 return cx_ll_insert(list, list->size, elem);
149 } 177 }
150 178
151 static int cx_ll_remove(cx_list_s *list, size_t index) { 179 static int cx_ll_remove(cx_list_s *list, size_t index) {
152 cx_linked_list *ll = (cx_linked_list *) list; 180 cx_linked_list *ll = (cx_linked_list *) list;
153 cx_linked_list_node *node = cx_ll_node_at(ll, index); 181 cx_linked_list_node *node = cx_ll_node_at(ll, index);

Mercurial Repository: ucx

mercurial