list-c

Simple library to create and maintain lists in C
Log | Files | Refs

list.c (4206B)

      1 #include "list.h"
      2 
      3 #include <dirent.h>
      4 #include <errno.h>
      5 #include <stdio.h>
      6 #include <stdlib.h>
      7 #include <string.h>
      8 #include <sys/types.h>
      9 
     10 #define DIE_RETURN(err) \
     11 	{                   \
     12 		errno = (err);  \
     13 		return -1;      \
     14 	}
     15 
     16 #define DIE_RETURN_NULL(err) \
     17 	{                        \
     18 		errno = (err);       \
     19 		return NULL;         \
     20 	}
     21 
     22 
     23 struct list {
     24 	size_t length;
     25 	size_t capacity;
     26 	size_t element_size;
     27 	char*  array;
     28 
     29 	list_malloc_t  malloc;
     30 	list_realloc_t realloc;
     31 	list_free_t    free;
     32 };
     33 
     34 struct list_iter {
     35 	list_t* list;
     36 	size_t  current;
     37 };
     38 
     39 static size_t translate_index(list_t* this, ssize_t index) {
     40 	if (index >= 0)
     41 		return index;
     42 
     43 	return this->length + index;
     44 }
     45 
     46 list_t* list(size_t element_size, list_malloc_t list_malloc, list_realloc_t list_realloc, list_free_t list_free) {
     47 	list_t* this;
     48 
     49 	if ((this = list_malloc(sizeof(list_t))) == NULL)
     50 		return NULL;
     51 
     52 	this->length       = 0;
     53 	this->capacity     = LIST_DEFAULT_CAPACITY;
     54 	this->element_size = element_size;
     55 
     56 	this->malloc  = list_malloc;
     57 	this->realloc = list_realloc;
     58 	this->free    = list_free;
     59 
     60 	if ((this->array = this->malloc(this->capacity)) == NULL)
     61 		DIE_RETURN_NULL(ENOMEM);
     62 
     63 	return this;
     64 }
     65 
     66 list_t* list_default_alloc(size_t element_size) {
     67 	list_t* this;
     68 
     69 	if ((this = malloc(sizeof(list_t))) == NULL)
     70 		return NULL;
     71 
     72 	this->length       = 0;
     73 	this->capacity     = LIST_DEFAULT_CAPACITY;
     74 	this->element_size = element_size;
     75 
     76 	this->malloc  = malloc;
     77 	this->realloc = realloc;
     78 	this->free    = free;
     79 
     80 	if ((this->array = this->malloc(this->capacity)) == NULL)
     81 		DIE_RETURN_NULL(ENOMEM);
     82 
     83 	return this;
     84 }
     85 
     86 void list_free(list_t* this) {
     87 	list_free_t list_free = this->free;
     88 
     89 	list_free(this->array);
     90 	list_free(this);
     91 }
     92 
     93 int list_grow(list_t* this, size_t new_length) {
     94 	if (new_length <= this->capacity)
     95 		return 0;
     96 
     97 	void* new_array;
     98 
     99 	if ((new_array = realloc(this->array, this->capacity * LIST_GROW)) == NULL)
    100 		DIE_RETURN(ENOMEM);
    101 
    102 	this->capacity *= LIST_GROW;
    103 	this->array = new_array;
    104 
    105 	return 0;
    106 }
    107 
    108 int list_add(list_t* this, void* element) {
    109 	if (list_grow(this, this->length + 1) == -1)
    110 		return -1;
    111 
    112 	memcpy(&this->array[this->length++ * this->element_size], element, this->element_size);
    113 
    114 	return 0;
    115 }
    116 
    117 
    118 void* list_get(list_t* this, ssize_t index) {
    119 	index = translate_index(this, index);
    120 
    121 	return &this->array[index * this->element_size];
    122 }
    123 
    124 void* list_get_copy(list_t* this, ssize_t index) {
    125 	void* element;
    126 
    127 	index = translate_index(this, index);
    128 
    129 	if ((element = this->malloc(this->element_size)) == NULL)
    130 		DIE_RETURN_NULL(ENOMEM);
    131 
    132 	memcpy(element, list_get(this, index), this->element_size);
    133 
    134 	return element;
    135 }
    136 
    137 int list_shrink(list_t* this, size_t new_length) {
    138 	if (new_length >= this->capacity / LIST_GROW)
    139 		return 0;
    140 
    141 	void* new_array;
    142 
    143 	if ((new_array = realloc(this->array, this->capacity / LIST_GROW)) == NULL)
    144 		DIE_RETURN(ENOMEM);
    145 
    146 	this->capacity /= LIST_GROW;
    147 	this->array = new_array;
    148 
    149 	return 0;
    150 }
    151 
    152 int list_remove(list_t* this, ssize_t index) {
    153 	index = translate_index(this, index);
    154 
    155 	memmove(list_get(this, index + 1), list_get(this, index + 1), --this->length - index);
    156 
    157 	return list_shrink(this, this->length);
    158 }
    159 
    160 void* list_remove_copy(list_t* this, ssize_t index) {
    161 	void* element;
    162 
    163 	index = translate_index(this, index);
    164 
    165 	if ((element = list_get_copy(this, index)) == NULL)
    166 		return NULL;
    167 
    168 	memmove(list_get(this, index + 1), list_get(this, index + 1), --this->length - index);
    169 
    170 	if (list_shrink(this, this->length) == -1)
    171 		return NULL;
    172 
    173 	return element;
    174 }
    175 
    176 
    177 size_t list_length(list_t* this) {
    178 	return this->length;
    179 }
    180 
    181 size_t list_capacity(list_t* this) {
    182 	return this->capacity;
    183 }
    184 
    185 list_iter_t* list_iter(list_t* this) {
    186 	list_iter_t* iter;
    187 
    188 	if ((iter = malloc(sizeof(list_iter_t))) == NULL)
    189 		return NULL;
    190 
    191 	iter->list    = this;
    192 	iter->current = 0;
    193 
    194 	return iter;
    195 }
    196 
    197 int list_iter_has_next(list_iter_t* iter) {
    198 	return iter->current < iter->list->length;
    199 }
    200 
    201 void* list_iter_next(list_iter_t* iter) {
    202 	return list_get(iter->list, iter->current++);
    203 }
    204 
    205 void* list_iter_next_copy(list_iter_t* iter) {
    206 	return list_get_copy(iter->list, iter->current++);
    207 }
    208 
    209 void list_iter_free(list_iter_t* iter) {
    210 	list_free_t list_free = iter->list->free;
    211 
    212 	list_free(iter);
    213 }