List Library

Dynamic array/list implementation in x86-64 Assembly with C interface

by JD McIntosh

Features

• Generic list of same size elements
• Dynamic growth
• Forward & backward iteration
• Fast indexed access (list_at)
• Binary search capable after sorting (list_find)
• Two deletion modes:
  • list_delete – finds & removes by key (requires sorted list)
  • list_remove – removes by direct pointer
• Custom comparison & cleanup callbacks
• Very lightweight memory footprint

Requirements

• Linux (x86-64)
• NASM (Netwide Assembler)
• GCC
• Make
• bash

Quick Start

Build everything (library + demo)

cd List-main
sh ./list_make.sh

Run the demonstration program

cd demo
./go_demo.sh

Configuration (list.asm)

You can tune the growth strategy by changing this value:

LIST_COUNT      EQU     16

Basic Usage Example

#include "list.h"

typedef struct {
    int id;
    char name[32];
} Person;

int compare_by_id(const void* a, const void* b) {
    return ((Person*)a)->id - ((Person*)b)->id;
}

int main(void)
{
    list_t* people = list_alloc();
    if (!people) return 1;

    if (list_init(people, sizeof(Person)) != 0) {
        list_free(people);
        return 1;
    }

    Person p1 = { .id = 42, .name = "Alice" };
    Person p2 = { .id =  7, .name = "Bob"   };
    Person p3 = { .id = 19, .name = "Carol" };

    list_add(people, &p1);
    list_add(people, &p2);
    list_add(people, &p3);

    // Sort for binary search & ordered delete
    list_sort(people, compare_by_id);

    // Find & delete by key
    Person key = { .id = 7 };
    list_delete(people, &key, compare_by_id, NULL);

    // Iteration example
    Person* p;
    for (p = list_begin(people); p; p = list_next(people)) {
        printf("ID: %d  Name: %s\n", p->id, p->name);
    }

    list_free(people);
    return 0;
}

---

List Library API

The List Library stores objects of the same size that can be: sorted and searched; deleted from the list; and iterated through, forward or backward.

void * list_alloc();

list_alloc() allocates a list structure on the Heap. Returns an address on success, or NULL on failure.

---

int list_add (list_t *list, void const *object);

list_add() adds contents of object to the list. Returns 0 on success, or -1 on failure. NOTE: A slot is allocated in the list and the contents of object are copied into that slot. Adding to a list amounts to copying the contents of an object into the next available slot in a list.

---

void * list_at (list_t *list, size_t const index);

list_at() returns the address of a list member at index in a list, or NULL on failure (for instance, index out-of-bounds).

---

void * list_begin (list_t *list);

list_begin() initializes the list iterator and returns the address of the first member in a list or NULL if list is empty.

---

size_t list_count (list_t const *list);

list_count() returns the number of objects in a list.

---

void * list_curr (list_t *list);

list_curr() returns the address to the current list member during iteration.

---

int list_delete (list_t *list, void const *key,
    int (*find_cb) (void const *key, void const *mbr),
    void (*delete_cb) (void *mbr));

list_delete() attempts to delete a list member with a matching key. Returns 0 on success, or -1 on failure. NOTE: All list members after the deleted member are shifted (left) one slot to fill the gap left by a deleted member.

find_cb() is a user supplied function. This function must return an integer less-than, equal-to, or greater-than zero if parameter key is less-than, equal-to, or greater-than the key of parameter mbr.

delete_cb() is a user supplied function. NOTE: This parameter can be NULL. This function is passed the list member prior to the deletion of the list member. This function allows the user access to a list member to deal with any resources (file/socket descriptor, Heap memory, etc.) or data in same.

NOTE: list_sort() must be called prior to using list_delete(). If a list can not be sorted then list_remove() can be used to remove a list member.

---

void * list_end (list_t *);

list_end() initializes the list iterator and returns the address of the last member in a list or NULL if a list is empty.

---

void * list_find (list_t const *list, void const *key,
    int (*find_cb) (void const *key, void const *mbr));

list_find() returns the first member in a list with a matching key, or NULL if no match is found.

find_cb() is a user supplied function. This function must return an integer less-than, equal-to, or greater-than zero if parameter key is less-than, equal-to, or greater-than the key of parameter mbr.

---

void list_free(list_t *list);

list_free() deallocates a list structure from the Heap.

---

int list_init (list_t *list, size_t const size);

size of the objects that will be stored in the list.

list_init() must be called on a list before a list can be used.

---

void * list_next (list_t *list);

list_next() increments the list iterator and returns the address of the next object in a list, or NULL when no successor exists. NOTE: list_begin() must be called prior to calling this function.

---

size_t list_object_size (list_t *list);

list_object_size() returns the size that was passed to list_init().

---

void * list_pred (list_t *list);

list_pred() returns the address of the predecessor to the current member in a list, or NULL when no predecessor exists. NOTE: list_end() must be called prior to calling this function.

---

void * list_prev (list_t *list);

list_prev() decrements the list iterator and returns the address of the previous object in a list, or NULL when no predecessor exists. NOTE: list_end() must be called prior to calling this function.

---

void list_remove (list_t *list, void const *mbrber, void (*delete_cb) (void *));

list_remove() removes the list member pointed to by parameter member. Calls delete_cb (if not NULL) prior to removing the list member. NOTE: the address passed in parameter member must point to a list member or list_remove() will do nothing.

---

size_t list_slot_size (list_t *list);

list_slot_size() returns the size of a slot in parament list.

---

void list_sort (list_t *list, int (*sort_cb) (void const *mbr1, void const *mbr2));

sort_cb() is a user supplied function. Both parameters point to list members being compared. This function must return an integer less-than, equal-to, or greater-than zero if the key of parameter mbr1 is less-than, equal-to, or greater-than the key of parameter mbr2. If two members compare as equal, their order in the sorted array is undefined.

list_sort() sorts a list in ascending order according to a comparison function pointed to by sort_cb.

---

void * list_succ (list_t *list);

list_succ() returns the address of the successor to the current member in a list, or NULL when no successor exists. NOTE: list_begin() must be called prior to calling this function.

---

void list_term (list_t *list);

list_term() terminates a list.

---