Mercurial > hg > ucx / changeset

--- a/src/cx/linked_list.h	Mon Sep 08 22:48:48 2025 +0200
+++ b/src/cx/linked_list.h	Tue Sep 09 22:30:18 2025 +0200
@@ -44,6 +44,38 @@
 #endif
 
 /**
+ * Meta data for a linked list.
+ */
+typedef struct cx_linked_list_s {
+    /** Base members. */
+    struct cx_list_s base;
+    /**
+     * Location of the prev pointer (mandatory).
+     */
+    off_t loc_prev;
+    /**
+     * Location of the next pointer (mandatory).
+     */
+    off_t loc_next;
+    /**
+     * Location of the payload (mandatory).
+     */
+    off_t loc_data;
+    /**
+     * Additional bytes to allocate @em behind the payload (e.g. for metadata).
+     */
+    size_t extra_data_len;
+    /**
+     * Pointer to the first node.
+     */
+    void *begin;
+    /**
+     * Pointer to the last node.
+     */
+    void *end;
+} cx_linked_list;
+
+/**
  * Allocates a linked list for storing elements with @p elem_size bytes each.
  *
  * If @p elem_size is #CX_STORE_POINTERS, the created list stores pointers instead of

--- a/src/kv_list.c	Mon Sep 08 22:48:48 2025 +0200
+++ b/src/kv_list.c	Tue Sep 09 22:30:18 2025 +0200
@@ -40,15 +40,8 @@
     cx_kv_list *list;
 };
 
-/** The list aspect (must have the same layout as the normal linked list). */
-struct cx_kv_list_list_s {
-    struct cx_list_s list_base;
-    void *begin;
-    void *end;
-};
-
 struct cx_kv_list_s {
-    struct cx_kv_list_list_s list;
+    struct cx_linked_list_s list;
     /** The lookup map - stores pointers to the nodes. */
     struct cx_kv_list_map_s *map;
     const cx_list_class *list_methods;
@@ -82,7 +75,7 @@
     const cx_kv_list *kv_list = list_ptr;
     // the elem called with a map destructor is a pointer to the node
     // we need to deref the elem accordingly
-    void *elem = kv_list->list.list_base.collection.store_pointer ? *(void**)node_data : node_data;
+    void *elem = kv_list->list.base.collection.store_pointer ? *(void**)node_data : node_data;
     if (kv_list->list_destr) {
         kv_list->list_destr(elem);
     }
@@ -100,15 +93,15 @@
 static void cx_kv_list_update_destructors(cx_kv_list *list) {
     // we copy the destructors to our custom fields and register
     // an own destructor function which invokes all these
-    if (list->list.list_base.collection.simple_destructor != NULL) {
-        list->list_destr = list->list.list_base.collection.simple_destructor;
-        list->list.list_base.collection.simple_destructor = NULL;
+    if (list->list.base.collection.simple_destructor != NULL) {
+        list->list_destr = list->list.base.collection.simple_destructor;
+        list->list.base.collection.simple_destructor = NULL;
     }
-    if (list->list.list_base.collection.advanced_destructor != cx_kv_list_destructor_wrapper_list) {
-        list->list_destr2 = list->list.list_base.collection.advanced_destructor;
-        list->list_destr_data = list->list.list_base.collection.destructor_data;
-        list->list.list_base.collection.advanced_destructor = cx_kv_list_destructor_wrapper_list;
-        list->list.list_base.collection.destructor_data = list;
+    if (list->list.base.collection.advanced_destructor != cx_kv_list_destructor_wrapper_list) {
+        list->list_destr2 = list->list.base.collection.advanced_destructor;
+        list->list_destr_data = list->list.base.collection.destructor_data;
+        list->list.base.collection.advanced_destructor = cx_kv_list_destructor_wrapper_list;
+        list->list.base.collection.destructor_data = list;
     }
     if (list->map->map_base.base.collection.simple_destructor != NULL) {
         list->map_destr = list->map->map_base.base.collection.simple_destructor;
@@ -126,8 +119,10 @@
     cx_kv_list *kv_list = (cx_kv_list*)list;
     // patch the destructors
     cx_kv_list_update_destructors(kv_list);
-    // free the map first
+    // free the map first, but skip the destructors of the map
+    cxDefineAdvancedDestructor(&kv_list->map->map_base.base, NULL, NULL);
     kv_list->map_methods->deallocate(&kv_list->map->map_base.base);
+    // then free the list, now the destructors may be called
     kv_list->list_methods->deallocate(list);
 }
 
@@ -196,7 +191,7 @@
     // clear the list
     kv_list->list_methods->clear(list);
     // then clear the map
-    cxMapClear(&kv_list->map->map_base.base);
+    kv_list->map_methods->clear(&kv_list->map->map_base.base);
 }
 
 static int cx_kvl_swap(
@@ -250,7 +245,7 @@
 static void cx_kvl_map_deallocate(struct cx_map_s *map) {
     cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
     kv_list->map_methods->deallocate(map);
-    kv_list->list_methods->deallocate(&kv_list->list.list_base);
+    kv_list->list_methods->deallocate(&kv_list->list.base);
 }
 
 static void cx_kvl_map_clear(struct cx_map_s *map) {
@@ -263,10 +258,10 @@
 static void *cx_kvl_map_put(CxMap *map, CxHashKey key, void *value) {
     cx_kv_list *kv_list = ((struct cx_kv_list_map_s*)map)->list;
     // insert the data into the list first (assume that insertion destroys the sorted property)
-    kv_list->list.list_base.collection.sorted = false;
+    kv_list->list.base.collection.sorted = false;
     // TODO: use the same trick as above to increase the element size temporarily to add the key to the data
     void *node_data = kv_list->list_methods->insert_element(
-        &kv_list->list.list_base, kv_list->list.list_base.collection.size, value);
+        &kv_list->list.base, kv_list->list.base.collection.size, value);
     if (node_data == NULL) return NULL; // LCOV_EXCL_LINE
     // then insert the key into the map, referring to the node data
     // TODO: check if we still get a correct pointer when the list is storing pointers
@@ -294,29 +289,29 @@
     if (targetbuf == NULL) {
         // patch the destructors and invoke them through the wrapper
         cx_kv_list_update_destructors(kv_list);
-        cx_invoke_advanced_destructor(&kv_list->list.list_base, node_data);
+        cx_invoke_advanced_destructor(&kv_list->list.base, node_data);
     } else {
         // copy the element to the target buffer
-        memcpy(targetbuf, node_data, kv_list->list.list_base.collection.elem_size);
+        memcpy(targetbuf, node_data, kv_list->list.base.collection.elem_size);
     }
 
     // calculate the address of the node
-    void *node_ptr = (char*)node_data - 2*sizeof(void*);
+    void *node_ptr = (char*)node_data - kv_list->list.loc_data;
 
     // unlink the node
     cx_linked_list_remove(
         &kv_list->list.begin,
         &kv_list->list.end,
-        0,
-        sizeof(void*),
+        kv_list->list.loc_prev,
+        kv_list->list.loc_next,
         node_ptr
     );
 
     // decrement the list's size
-    kv_list->list.list_base.collection.size--;
+    kv_list->list.base.collection.size--;
 
     // deallocate the node
-    cxFree(kv_list->list.list_base.collection.allocator, node_ptr);
+    cxFree(kv_list->list.base.collection.allocator, node_ptr);
 
     return 0;
 }
@@ -364,6 +359,8 @@
     // create a normal linked list and a normal hash map, first
     CxList *list = cxLinkedListCreate(allocator, comparator, elem_size);
     if (list == NULL) return NULL; // LCOV_EXCL_LINE
+    cx_linked_list *ll = (cx_linked_list*)list;
+    ll->extra_data_len = sizeof(CxHashKey);
     CxMap *map = cxHashMapCreate(allocator, CX_STORE_POINTERS, 0);
     if (map == NULL) { // LCOV_EXCL_START
         cxListFree(list);
@@ -421,7 +418,7 @@
 }
 
 CxList *cxKvListAsList(CxMap *map) {
-    return &((struct cx_kv_list_map_s*)map)->list->list.list_base;
+    return &((struct cx_kv_list_map_s*)map)->list->list.base;
 }
 
 CxMap *cxKvListAsMap(CxList *list) {
@@ -429,7 +426,16 @@
 }
 
 int cx_kv_list_set_key(CxList *list, size_t index, CxHashKey key) {
-    return -1;
+    cx_kv_list *kv_list = (cx_kv_list*)list;
+    char *node_data = kv_list->list_methods->at(list, index);
+    char *loc_key = node_data + list->collection.elem_size;
+    memcpy(loc_key, &key, sizeof(key));
+
+    // TODO: what happens when we are _replacing_ an existing key?
+    kv_list->map_methods->put(&kv_list->map->map_base.base, key, node_data);
+    // TODO: what happens if the map cocks up and returns NULL?
+
+    return 0;
 }
 
 int cx_kv_list_remove_key(CxList *list, size_t index, CxHashKey key) {

--- a/src/linked_list.c	Mon Sep 08 22:48:48 2025 +0200
+++ b/src/linked_list.c	Tue Sep 09 22:30:18 2025 +0200
@@ -564,65 +564,46 @@
 
 // HIGH LEVEL LINKED LIST IMPLEMENTATION
 
-typedef struct cx_linked_list_node cx_linked_list_node;
-// IMPORTANT: the layout must stay exactly like this, because kv_list.c uses that!
-struct cx_linked_list_node {
-    cx_linked_list_node *prev;
-    cx_linked_list_node *next;
-    char payload[];
-};
-
-#define CX_LL_LOC_PREV offsetof(cx_linked_list_node, prev)
-#define CX_LL_LOC_NEXT offsetof(cx_linked_list_node, next)
-#define CX_LL_LOC_DATA offsetof(cx_linked_list_node, payload)
-
-typedef struct {
-    struct cx_list_s base;
-    cx_linked_list_node *begin;
-    cx_linked_list_node *end;
-} cx_linked_list;
-
-static cx_linked_list_node *cx_ll_node_at(
+static void *cx_ll_node_at(
         const cx_linked_list *list,
         size_t index
 ) {
     if (index >= list->base.collection.size) {
         return NULL;
     } else if (index > list->base.collection.size / 2) {
-        return cx_linked_list_at(list->end, list->base.collection.size - 1, CX_LL_LOC_PREV, index);
+        return cx_linked_list_at(list->end, list->base.collection.size - 1, list->loc_prev, index);
     } else {
-        return cx_linked_list_at(list->begin, 0, CX_LL_LOC_NEXT, index);
+        return cx_linked_list_at(list->begin, 0, list->loc_next, index);
     }
 }
 
-static cx_linked_list_node *cx_ll_malloc_node(const struct cx_list_s *list) {
-    return cxMalloc(list->collection.allocator,
-                    sizeof(cx_linked_list_node) + list->collection.elem_size);
+static void *cx_ll_malloc_node(const cx_linked_list *list) {
+    return cxZalloc(list->base.collection.allocator,
+                    list->loc_data + list->base.collection.elem_size + list->extra_data_len);
 }
 
 static int cx_ll_insert_at(
         struct cx_list_s *list,
-        cx_linked_list_node *node,
+        void *node,
         const void *elem
 ) {
+    cx_linked_list *ll = (cx_linked_list *) list;
 
     // create the new new_node
-    cx_linked_list_node *new_node = cx_ll_malloc_node(list);
+    void *new_node = cx_ll_malloc_node(ll);
 
     // sortir if failed
     if (new_node == NULL) return 1;
 
-    // initialize new new_node
-    new_node->prev = new_node->next = NULL;
+    // copy the data
     if (elem != NULL) {
-        memcpy(new_node->payload, elem, list->collection.elem_size);
+        memcpy((char*)new_node + ll->loc_data, elem, list->collection.elem_size);
     }
 
     // insert
-    cx_linked_list *ll = (cx_linked_list *) list;
     cx_linked_list_insert_chain(
-            (void **) &ll->begin, (void **) &ll->end,
-            CX_LL_LOC_PREV, CX_LL_LOC_NEXT,
+            &ll->begin, &ll->end,
+            ll->loc_prev, ll->loc_next,
             node, new_node, new_node
     );
 
@@ -641,7 +622,7 @@
     if (index > list->collection.size || n == 0) return 0;
 
     // find position efficiently
-    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
+    void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
 
     // perform first insert
     if (0 != cx_ll_insert_at(list, node, array)) return 1;
@@ -650,14 +631,15 @@
     if (n == 1) return 1;
 
     // we now know exactly where we are
-    node = node == NULL ? ((cx_linked_list *) list)->begin : node->next;
+    cx_linked_list *ll = (cx_linked_list *) list;
+    node = node == NULL ? ((cx_linked_list *) list)->begin : CX_LL_PTR(node, ll->loc_next);
 
     // we can add the remaining nodes and immediately advance to the inserted node
     const char *source = array;
     for (size_t i = 1; i < n; i++) {
         source += list->collection.elem_size;
         if (0 != cx_ll_insert_at(list, node, source)) return i;
-        node = node->next;
+        node = CX_LL_PTR(node, ll->loc_next);
     }
     return n;
 }
@@ -671,25 +653,28 @@
     if (index > list->collection.size) return NULL;
 
     // find position efficiently
-    cx_linked_list_node *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
+    void *node = index == 0 ? NULL : cx_ll_node_at((cx_linked_list *) list, index - 1);
 
     // perform first insert
     if (cx_ll_insert_at(list, node, element)) return NULL;
 
     // return a pointer to the data of the inserted node
+    cx_linked_list *ll = (cx_linked_list *) list;
     if (node == NULL) {
-        return ((cx_linked_list *) list)->begin->payload;
+        return (char*)(ll->begin) + ll->loc_data;
     } else {
-        return node->next->payload;
+        char *next = CX_LL_PTR(node, ll->loc_next);
+        return next + ll->loc_data;
     }
 }
 
 static _Thread_local cx_compare_func cx_ll_insert_sorted_cmp_func;
+static _Thread_local off_t cx_ll_insert_sorted_loc_data;
 
 static int cx_ll_insert_sorted_cmp_helper(const void *l, const void *r) {
-    const cx_linked_list_node *left = l;
-    const cx_linked_list_node *right = r;
-    return cx_ll_insert_sorted_cmp_func(left->payload, right->payload);
+    const char *left = (const char*)l + cx_ll_insert_sorted_loc_data;
+    const char *right = (const char*)r + cx_ll_insert_sorted_loc_data;
+    return cx_ll_insert_sorted_cmp_func(left, right);
 }
 
 static size_t cx_ll_insert_sorted(
@@ -697,40 +682,40 @@
         const void *array,
         size_t n
 ) {
+    cx_linked_list *ll = (cx_linked_list *) list;
+
     // special case
     if (n == 0) return 0;
 
     // create a new chain of nodes
-    cx_linked_list_node *chain = cx_ll_malloc_node(list);
+    void *chain = cx_ll_malloc_node(ll);
     if (chain == NULL) return 0;
 
-    memcpy(chain->payload, array, list->collection.elem_size);
-    chain->prev = NULL;
-    chain->next = NULL;
+    memcpy((char*)chain + ll->loc_data, array, list->collection.elem_size);
 
     // add all elements from the array to that chain
-    cx_linked_list_node *prev = chain;
+    void *prev = chain;
     const char *src = array;
     size_t inserted = 1;
     for (; inserted < n; inserted++) {
-        cx_linked_list_node *next = cx_ll_malloc_node(list);
+        void *next = cx_ll_malloc_node(ll);
         if (next == NULL) break;
         src += list->collection.elem_size;
-        memcpy(next->payload, src, list->collection.elem_size);
-        prev->next = next;
-        next->prev = prev;
+        memcpy((char*)next + ll->loc_data, src, list->collection.elem_size);
+        CX_LL_PTR(prev, ll->loc_next) = next;
+        CX_LL_PTR(next, ll->loc_prev) = prev;
         prev = next;
     }
-    prev->next = NULL;
+    CX_LL_PTR(prev, ll->loc_next) = NULL;
 
     // invoke the low level function
-    cx_linked_list *ll = (cx_linked_list *) list;
     cx_ll_insert_sorted_cmp_func = list->collection.cmpfunc;
+    cx_ll_insert_sorted_loc_data = ll->loc_data;
     cx_linked_list_insert_sorted_chain(
-            (void **) &ll->begin,
-            (void **) &ll->end,
-            CX_LL_LOC_PREV,
-            CX_LL_LOC_NEXT,
+            &ll->begin,
+            &ll->end,
+            ll->loc_prev,
+            ll->loc_next,
             chain,
             cx_ll_insert_sorted_cmp_helper
     );
@@ -748,7 +733,7 @@
         void *targetbuf
 ) {
     cx_linked_list *ll = (cx_linked_list *) list;
-    cx_linked_list_node *node = cx_ll_node_at(ll, index);
+    void *node = cx_ll_node_at(ll, index);
 
     // out-of-bounds check
     if (node == NULL) return 0;
@@ -757,8 +742,8 @@
     size_t removed = cx_linked_list_remove_chain(
             (void **) &ll->begin,
             (void **) &ll->end,
-            CX_LL_LOC_PREV,
-            CX_LL_LOC_NEXT,
+            ll->loc_prev,
+            ll->loc_next,
             node,
             num
     );
@@ -768,28 +753,28 @@
 
     // copy or destroy the removed chain
     if (targetbuf == NULL) {
-        cx_linked_list_node *n = node;
+        char *n = node;
         for (size_t i = 0; i < removed; i++) {
             // element destruction
-            cx_invoke_destructor(list, n->payload);
+            cx_invoke_destructor(list, n + ll->loc_data);
 
             // free the node and advance
-            void *next = n->next;
+            void *next = CX_LL_PTR(n, ll->loc_next);
             cxFree(list->collection.allocator, n);
             n = next;
         }
     } else {
         char *dest = targetbuf;
-        cx_linked_list_node *n = node;
+        char *n = node;
         for (size_t i = 0; i < removed; i++) {
             // copy payload
-            memcpy(dest, n->payload, list->collection.elem_size);
+            memcpy(dest, n + ll->loc_data, list->collection.elem_size);
 
             // advance target buffer
             dest += list->collection.elem_size;
 
             // free the node and advance
-            void *next = n->next;
+            void *next = CX_LL_PTR(n, ll->loc_next);
             cxFree(list->collection.allocator, n);
             n = next;
         }
@@ -802,10 +787,10 @@
     if (list->collection.size == 0) return;
 
     cx_linked_list *ll = (cx_linked_list *) list;
-    cx_linked_list_node *node = ll->begin;
+    char *node = ll->begin;
     while (node != NULL) {
-        cx_invoke_destructor(list, node->payload);
-        cx_linked_list_node *next = node->next;
+        cx_invoke_destructor(list, node + ll->loc_data);
+        void *next = CX_LL_PTR(node, ll->loc_next);
         cxFree(list->collection.allocator, node);
         node = next;
     }
@@ -832,14 +817,14 @@
         left = j;
         right = i;
     }
-    cx_linked_list_node *nleft = NULL, *nright = NULL;
+    void *nleft = NULL, *nright = NULL;
     if (left < mid && right < mid) {
         // case 1: both items left from mid
         nleft = cx_ll_node_at(ll, left);
         assert(nleft != NULL);
         nright = nleft;
         for (size_t c = left; c < right; c++) {
-            nright = nright->next;
+            nright = CX_LL_PTR(nright, ll->loc_next);
         }
     } else if (left >= mid && right >= mid) {
         // case 2: both items right from mid
@@ -847,7 +832,7 @@
         assert(nright != NULL);
         nleft = nright;
         for (size_t c = right; c > left; c--) {
-            nleft = nleft->prev;
+            nleft = CX_LL_PTR(nleft, ll->loc_prev);
         }
     } else {
         // case 3: one item left, one item right
@@ -873,12 +858,12 @@
             if (closest == left) {
                 nright = nleft;
                 for (size_t c = left; c < right; c++) {
-                    nright = nright->next;
+                    nright = CX_LL_PTR(nright, ll->loc_next);
                 }
             } else {
                 nleft = nright;
                 for (size_t c = right; c > left; c--) {
-                    nleft = nleft->prev;
+                    nleft = CX_LL_PTR(nleft, ll->loc_prev);
                 }
             }
         } else {
@@ -891,33 +876,33 @@
         }
     }
 
-    cx_linked_list_node *prev = nleft->prev;
-    cx_linked_list_node *next = nright->next;
-    cx_linked_list_node *midstart = nleft->next;
-    cx_linked_list_node *midend = nright->prev;
+    void *prev = CX_LL_PTR(nleft, ll->loc_prev);
+    void *next = CX_LL_PTR(nright, ll->loc_next);
+    void *midstart = CX_LL_PTR(nleft, ll->loc_next);
+    void *midend = CX_LL_PTR(nright, ll->loc_prev);
 
     if (prev == NULL) {
         ll->begin = nright;
     } else {
-        prev->next = nright;
+        CX_LL_PTR(prev, ll->loc_next) = nright;
     }
-    nright->prev = prev;
+    CX_LL_PTR(nright, ll->loc_prev) = prev;
     if (midstart == nright) {
         // special case: both nodes are adjacent
-        nright->next = nleft;
-        nleft->prev = nright;
+        CX_LL_PTR(nright, ll->loc_next) = nleft;
+        CX_LL_PTR(nleft, ll->loc_prev) = nright;
     } else {
         // likely case: a chain is between the two nodes
-        nright->next = midstart;
-        midstart->prev = nright;
-        midend->next = nleft;
-        nleft->prev = midend;
+        CX_LL_PTR(nright, ll->loc_next) = midstart;
+        CX_LL_PTR(midstart, ll->loc_prev) = nright;
+        CX_LL_PTR(midend, ll->loc_next) = nleft;
+        CX_LL_PTR(nleft, ll->loc_prev) = midend;
     }
-    nleft->next = next;
+    CX_LL_PTR(nleft, ll->loc_next) = next;
     if (next == NULL) {
         ll->end = nleft;
     } else {
-        next->prev = nleft;
+        CX_LL_PTR(next, ll->loc_prev) = nleft;
     }
 
     return 0;
@@ -928,8 +913,8 @@
         size_t index
 ) {
     cx_linked_list *ll = (cx_linked_list *) list;
-    cx_linked_list_node *node = cx_ll_node_at(ll, index);
-    return node == NULL ? NULL : node->payload;
+    char *node = cx_ll_node_at(ll, index);
+    return node == NULL ? NULL : node + ll->loc_data;
 }
 
 static size_t cx_ll_find_remove(
@@ -940,10 +925,10 @@
     if (list->collection.size == 0) return 0;
 
     size_t index;
-    cx_linked_list *ll = ((cx_linked_list *) list);
-    cx_linked_list_node *node = cx_linked_list_find(
+    cx_linked_list *ll = (cx_linked_list *) list;
+    char *node = cx_linked_list_find(
             ll->begin,
-            CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+            ll->loc_next, ll->loc_data,
             list->collection.cmpfunc, elem,
             &index
     );
@@ -951,9 +936,9 @@
         return list->collection.size;
     }
     if (remove) {
-        cx_invoke_destructor(list, node->payload);
-        cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
-                              CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+        cx_invoke_destructor(list, node + ll->loc_data);
+        cx_linked_list_remove(&ll->begin, &ll->end,
+                              ll->loc_prev, ll->loc_next, node);
         list->collection.size--;
         cxFree(list->collection.allocator, node);
     }
@@ -962,14 +947,14 @@
 
 static void cx_ll_sort(struct cx_list_s *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
-    cx_linked_list_sort((void **) &ll->begin, (void **) &ll->end,
-                        CX_LL_LOC_PREV, CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+    cx_linked_list_sort(&ll->begin, &ll->end,
+                        ll->loc_prev, ll->loc_next, ll->loc_data,
                         list->collection.cmpfunc);
 }
 
 static void cx_ll_reverse(struct cx_list_s *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
-    cx_linked_list_reverse((void **) &ll->begin, (void **) &ll->end, CX_LL_LOC_PREV, CX_LL_LOC_NEXT);
+    cx_linked_list_reverse(&ll->begin, &ll->end, ll->loc_prev, ll->loc_next);
 }
 
 static int cx_ll_compare(
@@ -978,8 +963,10 @@
 ) {
     cx_linked_list *left = (cx_linked_list *) list;
     cx_linked_list *right = (cx_linked_list *) other;
+    assert(left->loc_next == right->loc_next);
+    assert(left->loc_data == right->loc_data);
     return cx_linked_list_compare(left->begin, right->begin,
-                                  CX_LL_LOC_NEXT, CX_LL_LOC_DATA,
+                                  left->loc_next, left->loc_data,
                                   list->collection.cmpfunc);
 }
 
@@ -994,17 +981,18 @@
         iter->base.remove = false;
         struct cx_list_s *list = iter->src_handle.m;
         cx_linked_list *ll = iter->src_handle.m;
-        cx_linked_list_node *node = iter->elem_handle;
-        iter->elem_handle = node->next;
-        cx_invoke_destructor(list, node->payload);
-        cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
-                              CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+        char *node = iter->elem_handle;
+        iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
+        cx_invoke_destructor(list, node + ll->loc_data);
+        cx_linked_list_remove(&ll->begin, &ll->end,
+                              ll->loc_prev, ll->loc_next, node);
         list->collection.size--;
         cxFree(list->collection.allocator, node);
     } else {
+        const cx_linked_list *ll = iter->src_handle.c;
         iter->index++;
-        cx_linked_list_node *node = iter->elem_handle;
-        iter->elem_handle = node->next;
+        void *node = iter->elem_handle;
+        iter->elem_handle = CX_LL_PTR(node, ll->loc_next);
     }
 }
 
@@ -1014,25 +1002,27 @@
         iter->base.remove = false;
         struct cx_list_s *list = iter->src_handle.m;
         cx_linked_list *ll = iter->src_handle.m;
-        cx_linked_list_node *node = iter->elem_handle;
-        iter->elem_handle = node->prev;
+        char *node = iter->elem_handle;
+        iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
         iter->index--;
-        cx_invoke_destructor(list, node->payload);
-        cx_linked_list_remove((void **) &ll->begin, (void **) &ll->end,
-                              CX_LL_LOC_PREV, CX_LL_LOC_NEXT, node);
+        cx_invoke_destructor(list, node + ll->loc_data);
+        cx_linked_list_remove(&ll->begin, &ll->end,
+                              ll->loc_prev, ll->loc_next, node);
         list->collection.size--;
         cxFree(list->collection.allocator, node);
     } else {
+        const cx_linked_list *ll = iter->src_handle.c;
         iter->index--;
-        cx_linked_list_node *node = iter->elem_handle;
-        iter->elem_handle = node->prev;
+        char *node = iter->elem_handle;
+        iter->elem_handle = CX_LL_PTR(node, ll->loc_prev);
     }
 }
 
 static void *cx_ll_iter_current(const void *it) {
     const struct cx_iterator_s *iter = it;
-    cx_linked_list_node *node = iter->elem_handle;
-    return node->payload;
+    const cx_linked_list *ll = iter->src_handle.c;
+    char *node = iter->elem_handle;
+    return node + ll->loc_data;
 }
 
 static CxIterator cx_ll_iterator(
@@ -1060,10 +1050,11 @@
         int prepend
 ) {
     struct cx_list_s *list = iter->src_handle.m;
-    cx_linked_list_node *node = iter->elem_handle;
+    cx_linked_list *ll = iter->src_handle.m;
+    void *node = iter->elem_handle;
     if (node != NULL) {
         assert(prepend >= 0 && prepend <= 1);
-        cx_linked_list_node *choice[2] = {node, node->prev};
+        void *choice[2] = {node, CX_LL_PTR(node, ll->loc_prev)};
         int result = cx_ll_insert_at(list, choice[prepend], elem);
         if (result == 0) {
             iter->elem_count++;
@@ -1085,10 +1076,10 @@
 static void cx_ll_destructor(CxList *list) {
     cx_linked_list *ll = (cx_linked_list *) list;
 
-    cx_linked_list_node *node = ll->begin;
+    char *node = ll->begin;
     while (node) {
-        cx_invoke_destructor(list, node->payload);
-        void *next = node->next;
+        cx_invoke_destructor(list, node + ll->loc_data);
+        void *next = CX_LL_PTR(node, ll->loc_next);
         cxFree(list->collection.allocator, node);
         node = next;
     }
@@ -1124,6 +1115,10 @@
 
     cx_linked_list *list = cxCalloc(allocator, 1, sizeof(cx_linked_list));
     if (list == NULL) return NULL;
+    list->extra_data_len = 0;
+    list->loc_prev = 0;
+    list->loc_next = sizeof(void*);
+    list->loc_data = sizeof(void*)*2;
     cx_list_init((CxList*)list, &cx_linked_list_class,
             allocator, comparator, elem_size);