gkos Linked List API
The linked list api that I talked about some weeks ago.I will try to keep it simple, but this was not optimized.
There are 2 files: llapi.h, libllapi.c.
The first you will include in your application as:
#include "llapi.h"The secont you will use to make an archive.
Do as follow:
gcc -c libllapi.c
ar -rcs libllapi.a libllapi.o
Before to use your list you need to declare and
initialize it.
llist mylist;
init_llist (&mylist);
Ok, now you have a ready to use list, but, what you
may put inside it? The answer is nodes, of course.
Nodes are declared as an struct containing three members:
- a key for you search it latter
- a data field with BUFSIZ bytes
- a pointer to next node
node *nodebuf;
char data[BUFSIZ];
note: The data buffer need to have BUFSIZ length because the init_node() will try to copy BUFSIZ bytes to node data member. If data buffer has less than BUFSIZ bytes you will recieve a segment fault error at run time, since init_node() will try to dereference an array beyond its boundaries.
You can initialize a node as
nodebuf = init_node ("KeyName", data);
Or you can initialize it by hand. Then, with an initializednode you can add it in list with:
add_node (&mylist, nodebuf);After that your node is added in your list. The bufnode will
be set to null, so you can't touch list through it. The maximum number
of nodes is demilited by your avaible memory. The nodes are allocated
inside init_node function. If there is no memory avaible the programm
will exit with a failure status and an error message.
Since this you may want to free some space, to do this you will need
to delete some nodes. You can delete a node with del_node () function
but you need to know what to delete before to delete. The search_node ()
function is what you want.
struct search_result sr = search_node (&mylist, "keyname");search_result struct is declared as follow:
struct search_result {
node *n;
node *prior;
};
n points to node that you searched. It will be NULL if your node was not found.prior is an implementation detail. If the node was found and it's not the first
item in list, prior will point the prior node of n.
Now that you found (or not) your node, sr.n points to it. You can delete it
with the follow statement:
int rval = del_node (&mylist, sr.n, sr.prior);The integer rval will hold the return status of del_node () function.
Note that I don't check if my "keyname" was found. The del_node () function
will return BAD_CALL if you call it with 2nd and 3rd arguments as NULL
and will stat if you are trying to delete the first node. The sr.prior member
is used to linking stuff, but you don't need to botter with it, just recieve
from search_node () and pass as it is to del_node () everything is stated
by del_node ().
Here is the two files and an example!
/*
Copyright 2010 Daniel Hilst Selli
This file is part of gkos Linked List API.
gkos Linked List API is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
gkos Linked List API is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser Public License for more details.
You should have received a copy of the GNU Lesser Public License
along with gkos Linked List API. If not, see <http://www.gnu.org/licenses/>.
Daniel Hilst aka gkos <danielhilst@gmail.com>
*/
/******************
* llapi.h *
******************/
#ifndef LLAPI_H
#define LLAPI_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define KEY_SIZ 8
#define EMPTY 0
#define HAS_ONE 1
#define HAS_MORE_THAN_ONE 2
#define ERROR -1
#define BADCALL (ERROR -1)
#define KEY_FOUND_AT_FIRST (struct search_result) {l->first, NULL}
#define KEY_FOUND (struct search_result) {np, prior}
#define KEY_NOT_FOUND (struct search_result) {NULL, NULL}
/* data */
typedef struct node {
struct node *next;
char key[KEY_SIZ + 1]; /* +1 to the nil terminator char */
char *data[BUFSIZ];
} node;
typedef struct llist {
node *first; /* first item in list */
node *last; /* last item in list */
} llist;
struct search_result {
node *n;
node *prior;
};
/* prototypes */
void add_node (llist *, node *);
int del_node (llist *, node *, node *);
node *init_node (char *k, char *);
void init_llist (llist *);
struct search_result search_node (llist *, char *);
#endif // LLAPI_H
/*
Copyright 2010 Daniel Hilst Selli
This file is part of gkos Linked List API.
gkos Linked List API is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
gkos Linked List API is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser Public License for more details.
You should have received a copy of the GNU Lesser Public License
along with gkos Linked List API. If not, see <http://www.gnu.org/licenses/>.
Daniel Hilst aka gkos <danielhilst@gmail.com>
*/
/**********************
* libllapi.c *
**********************/
#include "llapi.h"
#define PRIVATE static
/* internal prototypes */
PRIVATE node *alloc_node (void);
PRIVATE int isempty (llist *);
/* interface */
void
add_node (llist *l, node *n)
{
int rval = isempty (l);
if (rval == EMPTY) {
l->first = l->last = n;
} else if (rval == HAS_ONE) {
l->first->next = n;
l->last = n;
} else if (rval == HAS_MORE_THAN_ONE) {
l->last->next = n;
l->last = n;
} else {
perror ("isempty");
exit (EXIT_FAILURE);
}
n = NULL; /* so peopple can't touch list directly */
}
int
del_node (llist *l, node *n, node *prior)
{
int rval = isempty (l);
if (rval == HAS_ONE) {
init_llist (l); /* set list as empty again */
free (n);
} else if (rval == HAS_MORE_THAN_ONE) {
if (n == l->first) {
l->first = l->first->next;
free (n); /* or free (l->first) */
} else if (n == l->last) {
l->last = prior;
l->last->next = NULL;
free (n); /* or free the ex last */
} else {
prior->next = prior->next->next; /* link over n */
free (n);
}
} else if (rval == EMPTY) { /* the list is empty */
return BADCALL;
} else {
return ERROR;
}
return 0;
}
void
init_llist (llist *l)
{
l->first = l->last = NULL;
}
node *
init_node (char *k, char *data)
{
/* alloc new node */
node *new = alloc_node ();
/* set next */
new->next = NULL;
/* set key */
strncpy (new->key, k, KEY_SIZ);
new->key[KEY_SIZ] = '\0';
/* set data */
memcpy (new->data, data, BUFSIZ);
/* return the new initalized node */
return new;
}
struct search_result
search_node (llist *l, char *k)
{
struct node *np, *prior;
if (strlen (k) > KEY_SIZ) {
k[KEY_SIZ] = '\0';
}
if (strcmp (l->first->key, k) == 0) {
return (struct search_result) KEY_FOUND_AT_FIRST; /* (struct search_result) {l->first, NULL} */
} else {
for (np = l->first->next, prior = l->first; np != NULL; np = np->next) {
if (strcmp (np->key, k) == 0) {
return KEY_FOUND; /* (struct search_result) {np, prior} */
}
prior = prior->next;
}
return KEY_NOT_FOUND; /* (struct search_result) {NULL, NULL} */
}
}
/* internals */
PRIVATE int
isempty (llist *l)
{
if (l->first == NULL && l->last == NULL)
return EMPTY;
else if (l->first == l->last)
return HAS_ONE;
else if (l->first->next != NULL)
return HAS_MORE_THAN_ONE;
else
return ERROR;
}
PRIVATE node *
alloc_node (void)
{
node *new = malloc (sizeof (node));
if (new == NULL) {
perror ("malloc");
exit (EXIT_FAILURE);
}
return new;
}
#include <stdio.h>
#include "llapi.h"
int
main (void)
{
int i;
llist mylist;
node *bufnode;
char databuffer[BUFSIZ];
memcpy (databuffer, "Daniel Hilst", strlen ("Daniel Hilst") + 1);
struct search_result sr;
init_llist (&mylist);
bufnode = init_node ("name", databuffer);
add_node (&mylist, bufnode);
bufnode = init_node ("myname", databuffer);
add_node (&mylist, bufnode);
bufnode = init_node ("thename", databuffer);
add_node (&mylist, bufnode);
bufnode = init_node ("onwname", databuffer);
add_node (&mylist, bufnode);
sr = search_node (&mylist, "thename");
printf ("%s => %s\n", sr.n->key, sr.n->data);
del_node (&mylist, sr.n, sr.prior);
sr = search_node (&mylist, "myname");
printf ("%s => %s\n", sr.n->key, sr.n->data);
del_node (&mylist, sr.n, sr.prior);
sr = search_node (&mylist, "onwname");
printf ("%s => %s\n", sr.n->key, sr.n->data);
del_node (&mylist, sr.n, sr.prior);
sr = search_node (&mylist, "name");
printf ("%s => %s\n", sr.n->key, sr.n->data);
del_node (&mylist, sr.n, sr.prior);
return 0;
}
This would print:
thename => Daniel Hilst
myname => Daniel Hilst
onwname => Daniel Hilst
name => Daniel Hilst
*edit
I create a git repository to this. It's easier to update stuff with git...
there you'll find an updated README.
http://github.com/gkos/gko-s-Linked-List
cheers! :-)