174 lines
2.1 KiB
C
174 lines
2.1 KiB
C
/**
|
|
* llist.c - a basic linked list implementation.
|
|
*
|
|
* Used for the hashtable.
|
|
*
|
|
*/
|
|
|
|
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
|
|
#include "llist.h"
|
|
|
|
/**
|
|
* Node in the linked list
|
|
*/
|
|
typedef struct LLNodeT
|
|
{
|
|
void* data;
|
|
struct LLNodeT* next;
|
|
}
|
|
LLNode;
|
|
|
|
/**
|
|
* Create a new linked list
|
|
*/
|
|
LL* ll_create(void)
|
|
{
|
|
LL* ll = malloc(sizeof(LL));
|
|
ll->entries = 0;
|
|
return ll;
|
|
}
|
|
|
|
/**
|
|
* Add item to beginning of a linked list
|
|
*/
|
|
int ll_push(LL* ll, void* data)
|
|
{
|
|
LLNode* n = malloc(sizeof(*n));
|
|
|
|
n->data = data;
|
|
|
|
// Reassign the head
|
|
n->next = ll->head;
|
|
ll->head = n;
|
|
|
|
ll->entries++;
|
|
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* Add item to end of a linked list
|
|
*/
|
|
int ll_append(LL* ll, void* data)
|
|
{
|
|
LLNode* tail = ll->head;
|
|
|
|
// Just push if there are no nodes yet
|
|
if (tail == NULL)
|
|
{
|
|
return ll_push(ll, data);
|
|
}
|
|
|
|
// Travserse list to find tail
|
|
while (tail->next != NULL)
|
|
{
|
|
tail = tail->next;
|
|
}
|
|
|
|
// Create new node and assign it as tail
|
|
LLNode* n = malloc(sizeof(LLNode));
|
|
n->data = data;
|
|
tail->next = n;
|
|
|
|
ll->entries++;
|
|
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* Get an item from the list via cb function
|
|
*/
|
|
void* ll_search(LL* ll, LLCb cb, void* arg)
|
|
{
|
|
LLNode* n = ll->head;
|
|
|
|
// Keep going until tail is reached
|
|
while (n != NULL)
|
|
{
|
|
if (cb(n->data, arg) == 0)
|
|
{
|
|
break;
|
|
}
|
|
|
|
n = n->next;
|
|
}
|
|
|
|
if (n == NULL)
|
|
{
|
|
return NULL;
|
|
}
|
|
|
|
return n->data;
|
|
}
|
|
|
|
/**
|
|
* Find and delete an entry from a linked list
|
|
*/
|
|
void* ll_delete(LL* ll, LLCb cb, void* arg)
|
|
{
|
|
LLNode* n = ll->head, *prev = NULL;
|
|
|
|
while (n != NULL)
|
|
{
|
|
if (cb(n->data, arg) == 0)
|
|
{
|
|
void* data = n->data;
|
|
|
|
// We are at the head
|
|
if (prev == NULL)
|
|
{
|
|
ll->head = n->next;
|
|
free(n);
|
|
}
|
|
else
|
|
{
|
|
prev->next = n->next;
|
|
free(n);
|
|
}
|
|
|
|
return data;
|
|
}
|
|
|
|
prev = n;
|
|
n = n->next;
|
|
}
|
|
|
|
return NULL;
|
|
}
|
|
|
|
/**
|
|
* Apply a function to every node in a linked list
|
|
*/
|
|
int ll_loop(LL* ll, LLCb cb, void* arg)
|
|
{
|
|
LLNode* n = ll->head, *next;
|
|
|
|
while (n != NULL)
|
|
{
|
|
next = n->next;
|
|
cb(n->data, arg);
|
|
n = next;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
/**
|
|
* Free a linked list
|
|
*/
|
|
void ll_free(LL* ll)
|
|
{
|
|
LLNode* n = ll->head, *next;
|
|
|
|
while (n != NULL)
|
|
{
|
|
next = n->next;
|
|
free(n);
|
|
n = next;
|
|
}
|
|
|
|
free(ll);
|
|
}
|
|
|