I'm writing a link list library for fun and future use when I can't use C++ and STL. I'm not fond of void pointers, but oh well. Anyway, have I forgotten something big besides a list sort? I'm going to add that when I have time. Here's the header:
Code:
#ifndef ListHeader_H
#define ListHeader_H
typedef struct LinkNode* Iterator;
struct LinkNode {
Iterator prev;
Iterator next;
void* data;
};
/*
* Iterator functions
*/
Iterator ListFirst (Iterator current);
Iterator ListLast (Iterator current);
Iterator ListPrevious(Iterator current);
Iterator ListNext (Iterator current);
Iterator ListEnd (void);
void* ListContent (Iterator current);
Iterator ListAddFront(Iterator current, Iterator item);
Iterator ListAddBack (Iterator current, Iterator item);
Iterator ListRemove (Iterator current);
void ListWalk (Iterator start, void (*action)(Iterator item));
void ListRWalk (Iterator start, void (*action)(Iterator item));
Iterator ListSearch (Iterator start, Iterator find, int (*compare)(const Iterator a, const Iterator b));
#endif
And a quickie test of the simpler features, I've tested them all and haven't found any bugs yet:
Code:
#include <stdio.h>
#include <stdlib.h>
#include "List.h"
void print(Iterator item)
{
printf("%d=>", *(int*)ListContent(item));
}
void release(Iterator item)
{
free(item);
}
void* Malloc(size_t size)
{
void* mem = malloc(size);
if (mem == 0)
{
fprintf(stderr, "Fatal error: Out of memory\n");
exit(EXIT_FAILURE);
}
return mem;
}
int main(void)
{
Iterator list = 0;
int i;
for (i = 0; i < 10; i++)
{
Iterator item = Malloc(sizeof (*item));
item->data = Malloc(sizeof (int));
*(int*)item->data = i;
item->next = item->prev = 0;
list = ListAddBack(ListLast(list), item);
}
ListWalk(ListFirst(list), print);
printf("\n");
ListRWalk(ListLast(list), print);
printf("\n");
ListWalk(ListFirst(list), release);
return 0;
}
<!-- What follows isn't relevant to the question --!>
Here's the implementation file also if anybody wants to critique it. I don't expect anybody to do so, but it never hurts to put it up just in case.
Code:
#include <stdlib.h>
#include "List.h"
Iterator ListFirst(Iterator current)
{
while (current != ListEnd() && current->prev != ListEnd())
current = ListPrevious(current);
return current;
}
Iterator ListLast(Iterator current)
{
while (current != ListEnd() && current->next != ListEnd())
current = ListNext(current);
return current;
}
Iterator ListPrevious(Iterator current)
{
return (current != ListEnd()) ? current->prev : current;
}
Iterator ListNext(Iterator current)
{
return (current != ListEnd()) ? current->next : current;
}
Iterator ListEnd(void)
{
return 0;
}
void* ListContent(Iterator current)
{
return (current != ListEnd()) ? current->data : 0;
}
Iterator ListAddFront(Iterator current, Iterator item)
{
if (current == ListEnd())
return item;
item->prev = current->prev;
item->next = current;
if (current->prev != ListEnd())
current->prev->next = item;
current->prev = item;
return item;
}
Iterator ListAddBack(Iterator current, Iterator item)
{
if (current == ListEnd())
return item;
item->prev = current;
item->next = current->next;
if (current->next != ListEnd())
current->next->prev = item;
current->next = item;
return item;
}
Iterator ListRemove(Iterator current)
{
Iterator save;
if (current == ListEnd())
return current;
save = (current->prev != ListEnd()) ? current->prev : current->next;
if (current->prev != ListEnd())
current->prev->next = current->next;
if (current->next != ListEnd())
current->next->prev = current->prev;
current->prev = ListEnd();
current->next = ListEnd();
free(current);
return save;
}
void ListWalk(Iterator start, void (*action)(Iterator item))
{
Iterator it;
Iterator forward;
for (it = start; it != ListEnd(); it = forward)
{
forward = ListNext(it);
action(it);
}
}
void ListRWalk(Iterator start, void (*action)(Iterator item))
{
Iterator it;
Iterator forward;
for (it = start; it != ListEnd(); it = forward)
{
forward = ListPrevious(it);
action(it);
}
}
Iterator ListSearch(Iterator start, Iterator find, int (*compare)(const Iterator a, const Iterator b))
{
Iterator it;
for (it = start; it != ListEnd(); it = ListNext(it))
{
if (compare(it, find))
return it;
}
return ListEnd();
}