-
Link list library
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();
}
-
One thing, you don't check either you successfully allocated memmory, it's always good to check...
Code:
char *str = malloc(5);
if(str != NULL)
//use the memmory
-
>One thing, you don't check either you successfully allocated memmory
Where? In the code I posted I only used dynamic allocation in two places:
Code:
Iterator item = Malloc(sizeof (*item));
item->data = Malloc(sizeof (int));
Check the definition of Malloc, it does check the return of the standard malloc function and acts accordingly if it fails. :) I'll probably rename Malloc to something more obvious like ItemAllocate or CheckedMalloc, I've been meaning to do that.
-
Code:
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;
}
I don't know why you need to do this.
If its for convience thats ok i guess.
But instead of this:
if (mem == 0)
i would do this:
if (mem == NULL)
Just a suggestion for portability and failsafe.
Also having it exit like that creates the risk of memory leaks when the program crashes.
Assuming you would use malloc more than once, if it crashes later on, all previously allocated blocks are not freed. A solution to this would to assign another function to atexit() to free all pointers, if you use this for lists it would be horribly excrutiating to type all this in, so you might want to have Malloc track all allocations.
I know Malloc wasn't the big point of this program, but I know things like that tend to become habits.
-
>I don't know why you need to do this.
It removes clutter in the program.
>Just a suggestion for portability and failsafe.
0 is always acceptable as a null pointer, NULL is just a convenient notation. Both are completely portable and safe, not to mention equivalent. ;)
>Also having it exit like that creates the risk of memory leaks when the program crashes.
No risk about it, if any allocations succeeded then there's a memory leak on failure. However, for such a simple test program I didn't bother to add bulletproof error recovery. Naturally any realistic program should do so despite the fact that any decent operating system would reclaim all memory when the program terminates.
>A solution to this would to assign another function to atexit() to free all pointers
Not a good solution since the function passed to atexit would require the list to be declared at the top lexical level (ie. global). I avoid global variables whenever possible except when they can safely be declared with file scope. My test program assumes that this isn't possible or is impractical as a general case.
An alternative is to use malloc as normal, then a check function that takes the list as well as newly allocated memory and checks the memory for NULL. If it is NULL, malloc failed and the list is released before an error is printed and the program aborted:
Code:
void CheckAlloc(void* mem, Iterator list)
{
if (mem == 0)
{
/* Allocation failed, clean up and bail */
ListWalk(ListFirst(list), release);
fprintf(stderr, "Fatal error: Out of memory\n");
exit(EXIT_FAILURE);
}
}
Code:
Iterator item = malloc(sizeof (*item));
CheckAlloc(item, list);
item->data = malloc(sizeof (int));
CheckAlloc(item->data, list);
But this gets into areas that relate to the client code, which the library knows nothing about nor should it care.
