wiki.burkey.co

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== linkedlist ======

A dual sided linked list structure. Used as the foundation for many other modules in ''%%libflint%%''

===== Usage =====

Create the list. The user is responsible for memory management of the ''%%List%%'' struct.

<code c>
List *list = malloc(sizeof(List));
</code>

After the tree is created, init it. The second argument on ''%%bintree_init()%%'' is an optional memory freeing function pointer with signature ''%%void (*destroy)(void *data)%%''. Use ''%%free()%%'' from the stdlib if you are creating the data with ''%%malloc()%%''. If allocation of your data is more complex, you can pass your own memory deallocation function as long as it fits the signature.

In this example, we are passing ''%%NULL%%'' because all memory will be stack allocated.

<code c>
ll_init(list, NULL);
int i = 1;
int j = 2;
int k = 4;
</code>

Next, insert data into the list. Data can be inserted from either side of a node.

<code c>
ll_ins_next(list, list->head, (void *) &i);
ll_ins_next(list, list->tail, (void *) &j);
ll_ins_next(list, list->tail, (void *) &k);
/* List is now 1 2 4 */
</code>

Lists can have a node removed by either targeting the node directly or removing a node pointed to by the head or tail of another node. The user is responsible for the memory management of the data inside the node, which is why a ''%%void*%%'' must be supplied to hold the data. Since in this example our memory is stack allocated, we don’t need to worry about freeing the ''%%void*%%'' but one must still be supplied for the function to work.

<code c>
/* List is 1 2 4 */
/* node is the 2nd node in the list with value 2 */
ListNode *node = list->head;
/* void pointer to the data inside of the node */
void *data;
ll_remove(list, node, &data);
/* List is now 1 4 */

printf("Removed: %d\n", *((int *) data));
/* Prints "2" */
</code>

Here is an alternative example using ''%%ll_remove_next()%%'' instead of ''%%ll_remove()%%''

<code c>
/* node is the 2nd node in the list with value 2 */
ListNode *node = list->head;
void *data; /* void pointer to the data inside of the node */
ll_remove_next(list, node, &data);
/* List is now 1 2 */

printf("Removed: %d\n", *((int *) data));
/* Prints "4" */
</code>

To destroy the list, first call ''%%ll_destroy()%%'' to free the nodes in the list and optionally run the destroy function against the data stored in the list. Since this example is stack allocated and we passed ''%%NULL%%'' when creating the list, no destroy function is run against the memory in the nodes. The list itself must be deleted with ''%%free()%%''

<code c>
ll_destroy(list);
free(list);
</code>

Complete example:

<code c>
List *list = malloc(sizeof(List));
ll_init(list, NULL);

int i = 1;
int j = 2;
int k = 4;

ll_ins_next(list, list->head, (void *) &i);
ll_ins_next(list, list->tail, (void *) &j);
ll_ins_next(list, list->tail, (void *) &k);

printf("List: ");
print_ll(list);

void *data;
ll_remove_next(list, list->head, &data);

printf("List: ");
print_ll(list);
printf("Removed: %d\n", *((int *) data));

ll_destroy(list);
free(list);
</code>

===== Structs =====

==== List ====

Double ended linked list struct

<code c>
typedef struct {
    size_t size;
    void (*destroy)(void *data);
    int (*match)(const void *a, const void *b);
    struct ListNode *head;
    struct ListNode *tail;
} List;
</code>

Members:

  * ''%%size%%'': How many nodes are in the list
  * ''%%destroy%%'': Optional deallocation function for member data. Use ''%%NULL%%'' if data is stack allocated
  * ''%%match%%'': Comparison function between data inside two nodes. This is not used by ''%%List%%'' itself, but is used in structures built on top of ''%%List%%''
  * ''%%head%%'': Pointer to the ''%%ListNode%%'' at the head of the list
  * ''%%tail%%'': Pointer to the ''%%ListNode%%'' at the tail of the list

==== ListNode ====

Node of the list

<code c>
typedef struct ListNode {
    void *data;
    struct ListNode *next;
    struct ListNode *prev;
} ListNode;
</code>

Members:

  * ''%%data%%'': void pointer to the member data in the node
  * ''%%next%%'': Pointer to the ''%%ListNode%%'' before this node in the list
  * ''%%prev%%'': Pointer to the ''%%ListNode%%'' after this node in the list

===== Functions =====

==== ll_init ====

Initialize the list. User is responsible for creating the initial ''%%List%%'' structure and freeing memory with ''%%ll_destroy()%%''. ''%%destroy%%'' is a deallocation function for the members of ''%%List%%'', pass ''%%NULL%%'' if the memory is stack-allocated

<code c>
void ll_init(List *list, void (*destroy)(void *data));

/* Usage */
List *list = malloc(sizeof(Stack));

// Pass NULL for stack-allocated memory
ll_init(list, NULL);

// Pass free or a custom freeing function for heap allocated memory
ll_init(list, free);
</code>

==== ll_destroy ====

Destroys the nodes inside a list and calls the deallocation funciton on the data if one was provided. Does not destroy the list itself, that is left up to the user.

<code c>
void ll_destroy(List *list);
</code>

==== ll_ins_next ====

Creates a new node containing ''%%data%%'' and inserts it after ''%%node%%''.

<code c>
int ll_ins_next(List *list, ListNode *node, const void *data);
</code>

==== ll_ins_prev ====

Creates a new node containing ''%%data%%'' and inserts it before ''%%node%%''.

<code c>
int ll_ins_prev(List *list, ListNode *node, const void *data);
</code>

==== ll_remove ====

Removes and deallocates the node pointed to by ''%%node%%''. The user is responsible for managing the contained data’s memory, as such the ''%%destroy%%'' function is **not** run by ''%%ll_remove()%%''

<code c>
int ll_remove(List *list, ListNode *node, void **data);
</code>

==== ll_remove_next ====

Removes and deallocates the node pointed to by ''%%node%%''’s ''%%tail%%'' pointer. The user is responsible for managing the contained data’s memory, as such the ''%%destroy%%'' function is **not** run by ''%%ll_remove_next()%%''

<code c>
int ll_remove_next(List *list, ListNode *node, void **data);
</code>

==== ll_remove_prev ====

Removes and deallocates the node pointed to by ''%%node%%''’s ''%%head%%'' pointer. The user is responsible for managing the contained data’s memory, as such the ''%%destroy%%'' function is **not** run by ''%%ll_remove_prev()%%''

<code c>
int ll_remove_prev(List *list, ListNode *node, void **data);
</code>

===== Macros =====

==== LL_ITER ====

A utility macro that helps with iterating over an entire list. A ''%%ListNode%%'' pointer named ''%%node%%'' is created as part of this macro and can be used to access the current node in the iteration, so be careful your own variable naming if you intend to use ''%%LL_ITER%%''.

<code c>
#define LL_ITER(list) for(ListNode *node = (list)->head; node != NULL; node = node->next)

/* Example with list of strings */
for LL_ITER(list) {
    printf("%s\n", (char *)(node->data));
}
</code>
wiki.burkey.co

User Tools

Site Tools

Page Tools
