Provided below is a bare bones dynamic array library. The game is to extend this library with new primitives and features that interest you, that you've needed in the past, or that you feel may be useful. The intention of this game is to give some of the newer folks a chance to get some design experience, but it's by no means limited to beginners; anyone can join in. And if we end up with a handy library as a result, all the better. :)
The starting library is very basic. It offers only construction/destruction, resize, and get/set. Suggested improvements might be insertion, removal, sorting, and searching. The sky is the limit! See what you can come up with, and post it for everyone to see (though sharing what you've done isn't necessary since this is for your own personal growth).
But first, an example using the base library:
#include <stdio.h>
#include "darray.h"
int main(void)
{
darray a = {sizeof(int)};
size_t i;
int x;
/* Populate the array from user input */
printf("Enter a list of integers: ");
fflush(stdout);
while (scanf("%d", &x) == 1) {
darray_resize(&a, a.capacity + 1);
darray_set(&a, a.capacity - 1, &x);
}
/* Use the array */
for (i = 0; i < a.capacity; ++i)
printf("%4d", darray_getval(&a, i, int));
putchar('\n');
/* Clean up the array */
darray_reset(&a);
return 0;
}
It can define a multidimensional array too, but it's somewhat awkward (hint for extending the library):
#include <stdio.h>
#include "darray.h"
#define N 3
int main(void)
{
darray a, temp;
size_t i, j;
int k = 1;
/* Create an NxN square matrix using darray */
darray_init(&a, sizeof(darray), N);
for (i = 0; i < N; ++i) {
darray_init(&temp, sizeof(darray), N);
for (j = 0; j < N; ++j, ++k)
darray_set(&temp, j, &k);
darray_set(&a, i, &temp);
}
/* Use the matrix */
for (i = 0; i < a.capacity; ++i) {
darray *p = darray_get(&a, i);
for (j = 0; j < p->capacity; ++j)
printf("%4d", darray_getval(p, j, int));
putchar('\n');
}
/* Clean up the matrix */
for (size_t i = 0; i < a.capacity; ++i)
darray_reset(darray_get(&a, i));
darray_reset(&a);
return 0;
}
Now the library itself. Here is the header:
#ifndef DARRAY_H
#define DARRAY_H
#include <stddef.h>
#if __STDC_VERSION__ >= 199901L
#include <stdbool.h>
#elif !defined(DARRAY_DISABLE_BOOL)
/*
If another library defines a boolean type then DARRAY_DISABLE_BOOL
can be defined to disable this library's definition.
*/
#define true 1
#define false 0
typedef int bool;
#endif
/*
@description:
Defines a type-dependent wrapper around darray_get
to avoid ugly casting and dereferencing when a
stored value is needed.
*/
#define darray_getval(p,pos,type) (*(type*)darray_get(p, pos))
/*
@description:
Defines a type-independent wrapper around darray_set
to correspond with darray_getval.
Note: This macro isn't 100% comparable to darray_set.
1) darray_setval cannot be used in an expression.
2) darray_setval will not return a value like darray_set.
*/
#define darray_setval(p,pos,item,type) \
do { \
type dummy = item; \
darray_set(p, pos, &dummy); \
} while(false)
typedef struct darray darray;
struct darray {
size_t item_size; /* Size in bytes of each item (homogeneous) */
size_t capacity; /* Number of valid items possible without a resize */
unsigned char *data; /* Storage for array items */
};
extern void darray_init(darray *p, size_t item_size, size_t capacity);
extern void darray_free(darray *p);
extern bool darray_resize(darray *p, size_t new_size);
extern void *darray_get(const darray *p, size_t pos);
extern bool darray_set(darray *p, size_t pos, void *item);
#endif /* DARRAY_H */
And here is the implementation:
#include "darray.h"
/*
@description:
Initializes the darray pointed to by p to the requested capacity.
*/
extern void darray_init(darray *p, size_t item_size, size_t capacity)
{
p->item_size = item_size;
p->capacity = 0;
p->data = NULL;
if (capacity > 0)
darray_resize(p, capacity);
}
/*
@description:
Releases memory from a previously initialized darray
pointed to by p, and resets to empty status. The item_size
value of the darray is preserved.
*/
extern void darray_reset(darray *p)
{
free(p->data);
darray_init(p, p->item_size, 0);
}
/*
@description:
Resizes the darray pointed to by p to a new capacity.
If the new capacity and current capacity are equal, nothing
is done. If the new capacity is smaller than the current
size, the array is truncated to fit the new capacity.
*/
extern bool darray_resize(darray *p, size_t new_capacity)
{
unsigned char *new_data;
size_t nitems;
if (new_capacity == p->capacity)
return true; /* Don't resize to the same capacity (wasted effort) */
else {
new_data = calloc(new_capacity, p->item_size);
if (!new_data)
return false; /* Memory allocation failed */
nitems = p->capacity;
if (nitems > new_capacity)
nitems = new_capacity; /* Truncate to a smaller capacity */
/* Populate the new data array and release the old one */
memcpy(new_data, p->data, nitems * p->item_size);
free(p->data);
/* Apply the changes to the darray */
p->capacity = new_capacity;
p->data = new_data;
return true;
}
}
/*
@description:
Retrieves the item stored at position pos within the
darray and returns a pointer to it.
*/
extern void *darray_get(const darray *p, size_t pos)
{
return &p->data[pos * p->item_size];
}
/*
@description:
Sets the item stored at position pos within the darray
and returns true, or returns false if the position
is out of range.
*/
extern bool darray_set(darray *p, size_t pos, void *item)
{
if (pos >= p->capacity)
return false;
memcpy(&p->data[pos * p->item_size], item, p->item_size);
return true;
}
Have fun! :)
