Skip to content

Instantly share code, notes, and snippets.

@cutthroat

cutthroat/pickle_list.c

Created December 21, 2010 00:40
Show Gist options
  • Save cutthroat/749302 to your computer and use it in GitHub Desktop.
Save cutthroat/749302 to your computer and use it in GitHub Desktop.
Download ZIP
basic linked list serialization
Raw
pickle_list.c
#include <stdlib.h>
#include <stdio.h>
/* list in core */
/* node in our linked list */
struct node {
struct node *link;
long data;
};
/* list structure (keeping pointer to the first node in a linked list of nodes)
an array of nodes is preallocated for further use. when a new element to
the list is added its node is taken from this array.
the unused nodes from the preallocated array are kept in another list, the
free list. when a new node is needed it is popped from the free list. when a
node is not needed anymore, it is pushed onto the free list for further use.
the whole list cannot be larger than the initially preallocated number of
nodes.
a little trick allows us to treat the space after the structure as an array
of nodes. this is the field `data' with zero elements. the number of nodes
in this array (the space after the structure) is kept in the field `size'.
allocating nodes from the elements of array allows us to use their index as
an unique identifier when stored in file. this is done because pointers
stored in a file are useless. */
struct list {
int size;
struct node *free, *head;
struct node data[0];
};
void push_node(struct node *n, struct node **hp)
{
n->link = *hp;
*hp = n;
}
struct node *pop_node(struct node **hp)
{
struct node *n = *hp;
if (n)
*hp = n->link;
return n;
}
/* allocating node is just popping from the free list */
struct node *alloc_node(struct list *l)
{
return pop_node(&l->free);
}
/* marking node free is just pushing onto the free list */
void free_node(struct node *n, struct list *l)
{
push_node(n, &l->free);
}
/* push_data may fail if there are not enough free nodes in the node array */
int push_data(long d, struct list *l)
{
struct node *n = alloc_node(l);
if (n == NULL)
return -1;
n->data = d;
push_node(n, &l->head);
return 0;
}
/* pop_data may fail if the list is empty */
int pop_data(struct list *l, long *dp)
{
struct node *n = pop_node(&l->head);
if (n == NULL)
return -1;
*dp = n->data;
free_node(n, l);
return 0;
}
/* marks all preallocated nodes as free */
void purge_list(struct list *l)
{
int i;
l->head = l->free = NULL;
for (i = 0; i < l->size; ++i)
free_node(l->data + i, l);
}
/* calculate the size of the structure plus the array of nodes at the back */
size_t sizeof_list(size_t max_size)
{
return sizeof(struct list) + sizeof(struct node) * max_size;
}
/* create a list with given number of preallocated nodes */
struct list *make_list(size_t max_size)
{
struct list *l = malloc(sizeof_list(max_size));
if (l == NULL)
return NULL;
l->size = max_size;
purge_list(l);
return l;
}
/* list on file */
/* node_on_file represents list node stored in file
because we cannot use a pointer to the next node, we use the index in the
preallocated array of nodes. */
struct node_on_file {
long link, data;
};
/* list_on_file keeps the needed information for the whole list
- the number of preallocated nodes
- the index of the first node in the free list
- the first node of the list itself.
in the file it is stored before the array of nodes. */
struct list_on_file {
long size, free, head;
struct node_on_file data[0]; /* we actually never use this field */
};
/* node pointer to index
returns the index of the node in the array of preallocated nodes
NULL pointers are represented as -1 which is invalid index in the nodes
array. */
long ptr2l(struct node *n, struct list *l)
{
if (n == NULL)
return -1;
return n - l->data;
}
/* node index to pointer */
struct node *l2ptr(long k, struct list *l)
{
if (k == -1)
return NULL;
return l->data + k;
}
/* saving list to a file in binary format
the list_on_file structure is written first, followed by the array of
nodes.
a temporary buffer of nodes_on_file is used to allow more efficient i/o,
instead of writing nodes one by one. */
int dump_list(struct list *l, FILE *f)
{
struct list_on_file xl; struct node_on_file xn[512];
struct node *n;
int nodes_left, nodes_to_write, nodes_written, i;
xl.size = l->size;
xl.free = ptr2l(l->free, l);
xl.head = ptr2l(l->head, l);
if (fwrite(&xl, sizeof xl, 1, f) != 1)
return -1;
nodes_left = l->size;
n = l->data;
while (nodes_left > 0) {
nodes_to_write = nodes_left < 512 ? nodes_left : 512;
for (i = 0; i < nodes_to_write; ++i, ++n) {
xn[i].link = ptr2l(n->link, l);
xn[i].data = n->data;
}
nodes_written = fwrite(xn, sizeof xn[0], nodes_to_write, f);
nodes_left -= nodes_written;
if (nodes_written != nodes_to_write)
break;
}
if ((n - l->data) != l->size)
return -1;
return 0;
}
/* loading list from file into the memory */
struct list *load_list(FILE *f)
{
struct list_on_file xl; struct node_on_file xn[512];
struct list *l; struct node *n;
int nodes_left, nodes_read, i;
if (fread(&xl, sizeof xl, 1, f) != 1)
return NULL;
l = malloc(sizeof_list(xl.size));
if (l == NULL)
return NULL;
l->size = xl.size;
l->free = l2ptr(xl.free, l);
l->head = l2ptr(xl.head, l);
nodes_left = xl.size;
n = l->data;
while (nodes_left > 0) {
nodes_read = fread(xn, sizeof xn[0], nodes_left < 512 ? nodes_left : 512, f);
if (nodes_read == 0)
break;
for (i = 0; i < nodes_read; ++i, ++n) {
n->link = l2ptr(xn[i].link, l);
n->data = xn[i].data;
}
nodes_left -= nodes_read;
}
if ((n - l->data) != l->size) {
free(l);
return NULL;
}
return l;
}
/* demo */
void test_dump_load()
{
int i;
long d;
struct list *l;
FILE *f;
/* initialize the list */
l = make_list(8);
if (l == NULL)
exit(-1);
for (i = 0; i < 8; ++i)
push_data(i, l);
/* dump the list */
f = fopen("test.bin", "wb");
if (f == NULL)
exit(-1);
if (dump_list(l, f))
exit(-1);
if (fclose(f))
exit(-1);
free(l);
/* load the list */
f = fopen("test.bin", "rb");
if (f == NULL)
exit(-1);
l = load_list(f);
if (l == NULL)
exit(-1);
while (pop_data(l, &d) == 0)
printf("%ld\n", d);
if (fclose(f))
exit(-1);
}
int main()
{
test_dump_load();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment