Mercurial > hg > ucx / file comparison

comparison: src/linked_list.c

src/linked_list.c

changeset 401
e6a8f7fb0c45
parent 400
8cd274352419
child 402
a34b93911956
equal deleted inserted replaced
400:8cd274352419 401:e6a8f7fb0c45
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE. 26 * POSSIBILITY OF SUCH DAMAGE.
27 */ 27 */
28 28
29 #include "cx/linked_list.h" 29 #include "cx/linked_list.h"
30 #include <stdint.h>
31 #include <string.h>
30 32
31 /* LOW LEVEL LINKED LIST FUNCTIONS */ 33 /* LOW LEVEL LINKED LIST FUNCTIONS */
32 34
33 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off)) 35 #define CX_LL_PTR(cur, off) ((void**)(((char*)cur)+off))
34 36
75 return 0; 77 return 0;
76 } 78 }
77 79
78 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */ 80 /* HIGH LEVEL LINKED LIST IMPLEMENTATION */
79 81
80 typedef struct cx_list_node_s cx_list_node;
81
82 struct cx_list_node_s {
83 cx_list_node *next;
84 cx_list_node *prev;
85 void *data;
86 };
87
88 typedef struct { 82 typedef struct {
89 cx_list_node *begin; 83 void *begin;
90 cx_list_node *end; 84 void *end;
91 size_t size;
92 } cx_linked_list; 85 } cx_linked_list;
93 86
94 int cx_ll_add(cx_list *list, void *elem) { 87 int cx_ll_add(cx_list *list, void *elem) {
95 cx_linked_list *listdata = list->listdata; 88 cx_linked_list *listdata = list->listdata;
96 CxAllocator allocator = list->allocator; 89 CxAllocator allocator = list->allocator;
97 90
98 struct cx_list_node_s *node = cxMalloc(allocator, sizeof(struct cx_list_node_s)); 91 /*
92 * Memory layout:
93 * next : sizeof(void*)
94 * prev : sizeof(void*)
95 * data : itemsize
96 */
97 void *node = cxMalloc(allocator,2*sizeof(void*)+list->itemsize);
99 if (node == NULL) 98 if (node == NULL)
100 return 1; 99 return 1;
101 100
102 node->next = NULL; 101 memset(node, 0, sizeof(void*));
103 node->data = elem; 102 memcpy(node+2, elem, list->itemsize);
104 103
105 int ret = cx_linked_list_add( 104 int ret = cx_linked_list_add(
106 (void **) &listdata->begin, 105 &listdata->begin,
107 (void **) &listdata->end, 106 &listdata->end,
108 offsetof(struct cx_list_node_s, next), 107 0,
109 offsetof(struct cx_list_node_s, prev), 108 sizeof(void*),
110 node 109 node
111 ); 110 );
112 if (ret == 0) { 111 if (ret == 0) {
113 listdata->size++; 112 list->size++;
114 return 0; 113 return 0;
115 } else { 114 } else {
116 return ret; 115 return ret;
117 } 116 }
118 } 117 }
133 cx_linked_list *listdata = list->listdata; 132 cx_linked_list *listdata = list->listdata;
134 // TODO: implement using low level API 133 // TODO: implement using low level API
135 return 0; 134 return 0;
136 } 135 }
137 136
138 size_t cx_ll_size(cx_list *list) {
139 cx_linked_list *listdata = list->listdata;
140 return listdata->size;
141 }
142 137
143 cx_list_class cx_linked_list_class = { 138 cx_list_class cx_linked_list_class = {
144 cx_ll_add, 139 cx_ll_add,
145 cx_ll_insert, 140 cx_ll_insert,
146 cx_ll_remove, 141 cx_ll_remove,
147 cx_ll_find, 142 cx_ll_find
148 cx_ll_size
149 }; 143 };
150 144
151 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator) { 145 CxList cxLinkedListCreate(CxAllocator allocator, CxListComparator comparator, size_t itemsize) {
152 CxList list = cxMalloc(allocator, sizeof(list)); 146 CxList list = cxMalloc(allocator, sizeof(list));
153 if (list == NULL) 147 if (list == NULL)
154 return NULL; 148 return NULL;
155 149
156 list->cl = &cx_linked_list_class; 150 list->cl = &cx_linked_list_class;
157 list->data.allocator = allocator; 151 list->data.allocator = allocator;
158 list->data.cmpfunc = comparator; 152 list->data.cmpfunc = comparator;
153 list->data.size = 0;
154 list->data.itemsize = itemsize;
155 list->data.capacity = SIZE_MAX;
159 list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list)); 156 list->data.listdata = cxCalloc(allocator, 1, sizeof(cx_linked_list));
160 if (list->data.listdata == NULL) { 157 if (list->data.listdata == NULL) {
161 cxFree(allocator, list); 158 cxFree(allocator, list);
162 return NULL; 159 return NULL;
163 } 160 }

Mercurial Repository: ucx

mercurial