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 } |