Code:
#ifndef VECTOR_H_INCLUDED
#define VECTOR_H_INCLUDED
#ifdef _cplusplus
extern "C"{
#endif
struct sll_t{
int elem;
int size;
struct data_node *data;
};
const struct sll_t *sll_init(int size); /* Initializes a sll_t to hold the specified size */
const void *sll_read_data(const struct sll_t *ll, int index); /* Returns a pointer to the data stored at "index" offset in sll_t "ll" */
const void *sll_write_data(const struct sll_t *ll, int index, void *data); /* Stores a pointer to dynamically allocated copy of "data" at "index" offset in sll_t "ll" */
const void *sll_insert_node(struct sll_t *ll, int index, void *data); /* Inserts a pointer to dynamically allocated copy of "data" at "index" offset in sll_t "ll" */
const void *sll_append_node(struct sll_t *ll, void *data); /* Wrapper for insert_data with "index" always 0 */
const void *sll_prepend_node(struct sll_t *ll, void *data); /* Wrapper for insert_data with "index" always the index after last */
int sll_free(struct sll_t *ll); /* Frees a whole sll_t, "ll" */
int sll_free_range(struct sll_t *ll, int index, int len); /* Frees a range from "index" to "index + len" */
int sll_free_node(struct sll_t *ll, int index); /* Frees a single node identified with a unique index */
int sll_trim_start(struct sll_t *ll, int len); /* Wrapper for "free_range" with "index" always 0 */
int sll_trim_end(struct sll_t *ll, int len); /* Wrapper for "free_range" that frees nodes from the end of the sll_t */
const struct sll_t *sll_copy(const struct sll_t *ll);
const struct sll_t *sll_merge(struct sll_t *ll, struct sll_t *mergee);
#ifdef _cplusplus
}
#endif
#endif /* VECTOR_H_INCLUDED */
vector.c
Code:
#include <stdlib.h>
#include <string.h>
#include "error.h"
#include "vector.h"
struct data_node{
void* data;
struct data_node *next;
};
struct data_node *get_node_extend(struct sll_t *ll, int index); /* These don't need specific typeing because they're not made public */
struct data_node *get_node_no_extend(struct sll_t *ll, int index);
struct data_node *get_node_extend(struct sll_t *ll, int index)
{
struct data_node *cur_node;
cur_node = ll->data; /* Set the current node to the root node */
if(index >= 0)
{
if(ll->elem > index) /* Check to see if the index is within the bounds of the sll_t, if it is, do this the easy way */
{
cur_node = ll->data;
for(;index > 0;index--)
cur_node = cur_node->next;
}
else /* If it's not, do it the hard way */
{
int c;
if(ll->elem == 0) /* Check to see the root node exists */
{
if((ll->data = cur_node = (struct data_node*)calloc(1, sizeof(struct data_node))) == NULL) /* Allocate memory for it */
setlasterr(0, "Couldn't allocate memory.", "get_data_extend");
cur_node->data = calloc(1, ll->size); /* Allocate memory for it's data */
setlasterr(0, "Couldn't allocate memory.", "get_data_extend");
}
for(c = 0;c < index;c++) /* Skip to index */
{
if((c + 1) >= ll->elem && (c + 1) <= index) /* Does the next node exist, if not... */
{
if((cur_node->next = (struct data_node*)calloc(1, sizeof(struct data_node))) == NULL) /* Allocate memory for it */
setlasterr(0, "Couldn't allocate memory.", "get_data_extend");
if((cur_node->next->data = calloc(1, ll->size)) == NULL) /* Allocate memory for it's data */
setlasterr(0, "Couldn't allocate memory.", "get_data_extend");
}
cur_node = cur_node->next;
}
if(index >= ll->elem)
ll->elem = index + 1;
}
}
else
cur_node = get_node_no_extend(ll, index); /* get_data_no_extend has built-in handler for negative indexes */
return cur_node;
}
struct data_node *get_node_no_extend(struct sll_t *ll, int index)
{
struct data_node *cur_node;
cur_node = ll->data; /* Set the current node to the root node */
if(index >= 0)
{
if(ll->elem > index) /* Sanity check */
{
for(;index;index--) /* Skip to node requested */
cur_node = cur_node->next;
}
else /* Caller tried to access outside bounds, only valid on write */
{
setlasterr(0, "Referenced non-existant sll_t index", "get_data_no_extend");
return NULL;
}
}
else /* Negative indexes start at -1 and increase in distance from the end */
if(ll->elem + index >= 0)
cur_node = get_node_no_extend(ll, ll->elem + index);
else
setlasterr(0, "Referenced non-existant sll_t index", "get_data_no_extend");
return cur_node;
}
const struct sll_t *sll_init(int size)
{
struct sll_t *ll;
if((ll = (struct sll_t*)calloc(1, sizeof(struct sll_t))) == NULL) /* Allocate memory for the sll_t structure and check for null pointer*/
{
setlasterr(0, "Couldn't allocate memory.", "init_vector");
return NULL;
}
if((ll->data = (struct data_node*)calloc(1, sizeof(struct data_node))) == NULL) /* Allocate memory for the root of the linked list of data and check for null pointer*/
{
setlasterr(0, "Couldn't allocate memory.", "init_vector");
return NULL;
}
ll->elem = 0; /* No elements yet */
ll->size = size; /* Size of an element */
return ll;
}
const void *sll_read_data(const struct sll_t *ll, int index)
{
struct data_node *cur_node;
if((cur_node = get_node_no_extend(ll, index)) != NULL)
return cur_node->data;
else
{
setlasterr(0, "Referenced non-existant sll_t index", "read_data");
return NULL;
}
}
const void *sll_write_data(const struct sll_t *ll, int index, void *data)
{
return memcpy(get_node_extend(ll, index)->data, data, ll->size);
}
const void *sll_insert_node(struct sll_t *ll, int index, void *data)
{
struct data_node *cur_node, *next_node;
cur_node = get_node_extend(ll, index);
ll->elem++;
if((next_node = (struct data_node*)calloc(1, sizeof(struct data_node))) == NULL)
setlasterr(0, "Couldn't allocate memory.", "insert_data");
next_node->data = cur_node->data;
next_node->next = cur_node->next;
cur_node->data = memcpy(calloc(1, ll->size), data, ll->size);
cur_node->next = next_node;
return cur_node->data;
}
const void *sll_append_node(struct sll_t *ll, void *data)
{
return sll_insert_node(ll, ll->elem, data);
}
const void *sll_prepend_node(struct sll_t *ll, void *data)
{
return sll_insert_node(ll, 0, data);
}
int sll_free(struct sll_t *ll)
{
struct data_node *cur_node, *next_node;
cur_node = ll->data; /* Set the current node pointer to the root node */
for(;ll->elem;ll->elem--)
{
next_node = cur_node->next; /* Temporarily store the next node in next node while the current node is being freed */
free(cur_node); /* Free the current node */
cur_node = next_node; /* Set the current node to the next node */
}
free(ll); /* Free the sll_t structure */
return 1;
}
int sll_free_range(struct sll_t *ll, int index, int len)
{
struct data_node *cur_node, *next_node, *from;
if(((cur_node = get_node_no_extend(ll, index)) != NULL) && index + len <= ll->elem)
{
int c;
from = cur_node;
cur_node = cur_node->next;
for(c = 1;c < len;c++)
{
next_node = cur_node->next;
free(cur_node);
cur_node = next_node;
}
if((from->next = cur_node) == 0)
free(from);
else
{
from->data = cur_node->data;
from->next = cur_node->next;
}
ll->elem -= len;
return 1;
}
else
{
setlasterr(0, "Attempted to free non-existand sll_t index range.", "free_range");
return NULL;
}
}
int sll_free_node(struct sll_t *ll, int index)
{
struct data_node *cur_node;
if(index > 0)
{
if((cur_node = get_node_no_extend(ll, index - 1)) != NULL)
{
void* t;
t = cur_node->next;
cur_node->next = cur_node->next->next;
free(t);
}
else
{
setlasterr(0, "Attempted to free non-existand sll_t index.", "free_data");
return NULL;
}
}
else
if(ll->elem > 0)
ll->data = ll->data->next;
else
{
setlasterr(0, "Attempted to free non-existand sll_t index.", "free_data");
return NULL;
}
ll->elem--;
return 1;
}
int sll_trim_start(struct sll_t *ll, int len)
{
return sll_free_range(ll, 0, len);
}
int sll_trim_end(struct sll_t *ll, int len)
{
return sll_free_range(ll, ll->elem - len, len);
}
const struct sll_t *sll_copy(const struct sll_t *ll)
{
struct data_node *copy_node, *orig_node;
struct sll_t *copy = sll_init(ll->size); /* Initialize the sll_t to copy into */
if((copy_node = copy->data = calloc(1, sizeof(struct data_node))) == NULL) /* Allocate memory for the root node */
{
setlasterr(0, "Couldn't allocate memory.", "copy_vector");
return NULL;
}
orig_node = ll->data;
for(copy->elem = 0;copy->elem < ll->elem;copy->elem++)
{
if((copy_node->data = malloc(copy->size)) == NULL) /* Allocate memory for to data is this node */
{
setlasterr(0, "Couldn't allocate memory.", "copy_vector");
return NULL;
}
memcpy(copy_node->data, orig_node->data, ll->size); /* Copy data from original */
if((copy_node->next = calloc(1, sizeof(struct data_node))) == NULL) /* Allocate next data node */
{
setlasterr(0, "Couldn't allocate memory.", "copy_vector");
return NULL;
}
copy_node = copy_node->next; /* Advance the node pointers */
orig_node = orig_node->next;
}
return copy;
}
Would it be worth the time to add an "insert_vector()" or a "trim_vector()" function?
