A simple implementation for single-linked lists of objects allocated by Foundation's memory manager, and for last-in-first-out stacks of same.

• §1. Implementation
• §7. A function call API
• §8. A macro-ized API
• §10. LIFO stacks

§1. Implementation. Basically, there's a head structure, which points to a chain of body structures, each linking to the next. But to reduce memory manager overhead, we're going to store the first few body structures inside the head structure: that way, for a list of just a few items, only one call to the memory manager is needed.

define NO_LL_EARLY_ITEMS 32

typedef struct linked_list {
    struct linked_list_item *first_list_item;
    struct linked_list_item *last_list_item;
    int linked_list_length;
    int early_items_used;
    struct linked_list_item early_items[NO_LL_EARLY_ITEMS];
    CLASS_DEFINITION
} linked_list;

typedef struct linked_list_item {
    void *item_contents;
    struct linked_list_item *next_list_item;
} linked_list_item;

• The structure linked_list is private to this section.
• The structure linked_list_item is private to this section.

§2.

linked_list *LinkedLists::new?Usage of LinkedLists::new:
§8, §11(void) {
    linked_list *ll = CREATE(linked_list);
    LinkedLists::empty(ll);
    return ll;
}

void LinkedLists::empty(linked_list *ll) {
    ll->linked_list_length = 0;
    ll->early_items_used = 0;
    ll->first_list_item = NULL;
    ll->last_list_item = NULL;
}

§3. The following runs in constant time, i.e., performs no loops. In general we want speed rather than memory efficiency.

void LinkedLists::add?Usage of LinkedLists::add:
§6, §8, §11(linked_list *L, void *P, int to_end) {
    if (L == NULL) internal_error("null list");
    linked_list_item *item = NULL;
    if (L->early_items_used < NO_LL_EARLY_ITEMS)
        item = &(L->early_items[L->early_items_used++]);
    else
        item = CREATE(linked_list_item);
    item->item_contents = P;
    if (to_end) {
        item->next_list_item = NULL;
        if (L->last_list_item == NULL) {
            L->first_list_item = item;
            L->last_list_item = item;
        } else {
            L->last_list_item->next_list_item = item;
            L->last_list_item = item;
        }
    } else {
        item->next_list_item = L->first_list_item;
        L->first_list_item = item;
        if (L->last_list_item == NULL) L->last_list_item = item;
    }
    L->linked_list_length++;
}

§4. Because of the direction of the links, only removing from the front is quick:

void *LinkedLists::remove_from_front?Usage of LinkedLists::remove_from_front:
§5, §11(linked_list *L) {
    if (L == NULL) internal_error("null list");
    linked_list_item *front = L->first_list_item;
    if (front == NULL) internal_error("empty list can't have item 0 removed");
    L->first_list_item = front->next_list_item;
    if (L->first_list_item == NULL) L->last_list_item = NULL;
    L->linked_list_length--;
    return front->item_contents;
}

§5. It's rather slower to delete from a known position in the middle:

void *LinkedLists::delete?Usage of LinkedLists::delete:
§8(int N, linked_list *L) {
    if (L == NULL) internal_error("null list");
    if ((N < 0) || (N >= L->linked_list_length)) internal_error("index not valid");
    if (N == 0) return LinkedLists::remove_from_front(L);

    for (linked_list_item *item = L->first_list_item; item; item = item->next_list_item) {
        N--;
        if (N == 0) {
            if (L->last_list_item == item->next_list_item) L->last_list_item = item;
            void *contents_deleted = item->next_list_item->item_contents;
            item->next_list_item = item->next_list_item->next_list_item;
            L->linked_list_length--;
            return contents_deleted;
        }
    }

    internal_error("index not found");
    return NULL;
}

§6. And indeed to insert at a known position, where N being 0 means the front of the list, N being 1 means "after the first item", and so on.

void LinkedLists::insert(linked_list *L, int N, void *P) {
    if (N <= 0) LinkedLists::add(L, P, FALSE);
    else {
        linked_list_item *prev = NULL;
        for (linked_list_item *I = L->first_list_item; I; I = I->next_list_item) {
            if (N-- == 0) break;
            prev = I;
        }
        if (prev == NULL) LinkedLists::add(L, P, FALSE);
        else {
            linked_list_item *item = NULL;
            if (L->early_items_used < NO_LL_EARLY_ITEMS)
                item = &(L->early_items[L->early_items_used++]);
            else
                item = CREATE(linked_list_item);
            item->item_contents = P;

            linked_list_item *subs = prev->next_list_item;
            prev->next_list_item = item;
            item->next_list_item = subs;
            L->linked_list_length++;
        }
    }
}

§7. A function call API.

int LinkedLists::len?Usage of LinkedLists::len:
§11
Time - §7
JSON - §29, §36
Epub Ebooks - §7.3(linked_list *L) {
    return L?(L->linked_list_length):0;
}
linked_list_item *LinkedLists::first?Usage of LinkedLists::first:
§8
Version Numbers - §8(linked_list *L) {
    return L?(L->first_list_item):NULL;
}
void *LinkedLists::entry?Usage of LinkedLists::entry:
§8(int N, linked_list *L) {
    if ((N < 0) || (L == NULL) || (N >= L->linked_list_length)) return NULL;
    for (linked_list_item *I = L->first_list_item; I; I = I->next_list_item)
        if (N-- == 0)
            return I->item_contents;
    return NULL;
}
void LinkedLists::set_entry(int N, linked_list *L, void *P) {
    if ((N < 0) || (L == NULL) || (N >= L->linked_list_length)) return;
    for (linked_list_item *I = L->first_list_item; I; I = I->next_list_item)
        if (N-- == 0) {
            I->item_contents = P; return;
        }
}
linked_list_item *LinkedLists::last?Usage of LinkedLists::last:
§8(linked_list *L) {
    return L?(L->last_list_item):NULL;
}
linked_list_item *LinkedLists::next?Usage of LinkedLists::next:
§8
Version Numbers - §8(linked_list_item *I) {
    return I?(I->next_list_item):NULL;
}
void *LinkedLists::content?Usage of LinkedLists::content:
§8
Version Numbers - §8(linked_list_item *I) {
    return I?(I->item_contents):NULL;
}

§8. A macro-ized API. These intentionally hide the implementation. The difference between FIRST_IN_LINKED_LIST and FIRST_ITEM_IN_LINKED_LIST is that one returns the first structure in the list, and the other returns the first linked_list_item chunk in the list. From the latter you can make the former using CONTENT_IN_ITEM, but not vice versa. The same object may be listed in many different lists, so if all you have is the object, you don't know its place in the list.

define NEW_LINKED_LIST(T)
    (LinkedLists::new())
define FIRST_ITEM_IN_LINKED_LIST(T, L)
    (LinkedLists::first(L))
define ENTRY_IN_LINKED_LIST(N, T, L)
    ((T *) (LinkedLists::entry(N, L)))
define DELETE_FROM_LINKED_LIST(N, T, L)
    ((T *) (LinkedLists::delete(N, L)))
define LAST_ITEM_IN_LINKED_LIST(T, L)
    (LinkedLists::last(L))
define NEXT_ITEM_IN_LINKED_LIST(I, T)
    (LinkedLists::next(I))
define CONTENT_IN_ITEM(I, T)
    ((T *) (LinkedLists::content(I)))
define ADD_TO_LINKED_LIST(I, T, L)
    LinkedLists::add(L, (void *) (I), TRUE)
define FIRST_IN_LINKED_LIST(T, L)
    ((T *) (LinkedLists::content(LinkedLists::first(L))))
define LAST_IN_LINKED_LIST(T, L)
    ((T *) (LinkedLists::content(LinkedLists::last(L))))

§9. The following macro requires slight care to use: the list L needs to be calculable without side-effects. There's no such worry over P or T, since they're just identifier names: the loop variable and the type name respectively.

Note that the loop variable P must already be defined. Inside the loop body, a new variable will also then exist, P_item, to refer to the item which points to P. This allows us to iterate despite the comments above.

define LOOP_OVER_LINKED_LIST(P, T, L)
    for (linked_list_item *P##_item = (P = FIRST_IN_LINKED_LIST(T, L), FIRST_ITEM_IN_LINKED_LIST(T, L));
        P##_item;
        P##_item = (P = CONTENT_IN_ITEM(NEXT_ITEM_IN_LINKED_LIST(P##_item, T), T), NEXT_ITEM_IN_LINKED_LIST(P##_item, T)))

§10. LIFO stacks. The above gives us an almost free implementation of LIFO, last-in-first-out, stacks, where we represent a stack as a linked list whose first entry is at the front. To push an item, we add it at the front; to pull, we remove the front item.

We provide an abstract type name for these stacks, even though they're the exact same structure. For reasons to do with the way typedef works in C, it is awkward to typedef the two names together, so we'll simply use the preprocessor:

define lifo_stack linked_list

§11. Otherwise, it's macros all the way:

define NEW_LIFO_STACK(T)
    (LinkedLists::new())
define PUSH_TO_LIFO_STACK(I, T, L)
    LinkedLists::add((L), (void *) (I), FALSE)
define PULL_FROM_LIFO_STACK(T, L)
    ((T *) LinkedLists::remove_from_front(L))
define POP_LIFO_STACK(T, L)
    (LinkedLists::remove_from_front(L))
define TOP_OF_LIFO_STACK(T, L)
    FIRST_IN_LINKED_LIST(T, L)
define LIFO_STACK_EMPTY(T, L)
    ((LinkedLists::len(L) == 0)?TRUE:FALSE)
define LOOP_DOWN_LIFO_STACK(P, T, L)
    LOOP_OVER_LINKED_LIST(P, T, L)