Here's some code I've been using lately for variable sized arrays.
Uncommented, but it should be easy to follow. The idea is to use it
to stuff things in and have random access to any of the data without
having to deal with a linked list. It grows automatically if it needs
to. v_push and v_set are the main ways to set entries. Right now it
used a typedef for Vdata to a void *, but you could change it to about
anything. Note the growth patterns use a Fibbonaci sequence. Why?
It seems to work, is sub-exponential, yet grows quickly. Computation
of the next size is a snap, but at the price of an integer. (The
Fibbonaci sequence proceeds like 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
etc, with a given term being the sum of the two prior terms). I'll
post a few more posts, one of which demonstrates this piece of code.
--cut here--
typedef void * Vdata;
struct varray_t {
int prev_size;
int size;
int len;
Vdata *data;
};
typedef struct varray_t Varray;
Varray *
v_create(int size)
{
Varray *v;
assert(size > 0);
v = malloc(sizeof(*v));
v->size = v->prev_size = size;
v->len = 0;
v->data = malloc(sizeof(Vdata) * size);
return v;
}
void
v_free(Varray *v)
{
free(v->data);
free(v);
}
void
v_resize(Varray *v, int size)
{
Vdata *tp;
int temp;
assert(size > 0);
while(v->size <= (size + 1)) {
temp = v->size;
v->size = v->size + v->prev_size;
v->prev_size = temp;
}
tp = malloc(sizeof(Vdata) * v->size);
if (v->len > 0)
memcpy(tp, v->data, sizeof(Vdata) * (v->len));
free(v->data);
v->data = tp;
}
void
v_set(Varray *v, int n, Vdata val)
{
assert(n >= 0);
if (v->size < (n + 1))
v_resize(v, n + 1);
if (v->len < (n + 1))
v->len = n + 1;
v->data[n] = val;
}
int
v_len(Varray *v)
{
return v->len;
}
void
v_shrink(Varray *v)
{
Vdata *nv;
nv = malloc(sizeof(Vdata) * (v->len));
memcpy(nv, v->data, sizeof(Vdata) * v->len);
free(v->data);
v->data = nv;
v->size = v->len;
v->prev_size = v->len;
}
void
v_push(Varray *v, Vdata val)
{
v_set(v, v->len, val);
}
Vdata
v_pop(Varray *v)
{
assert(v->len > 0);
v->len--;
return v->data[v->len];
}
void
v_trunc(Varray *v, int t)
{
assert(t >= 0);
v->len = t;
}
Vdata
v_qoq(Varray *v)
{
Vdata val;
val = v->data[0];
memmove(v->data, v->data + 1, (v->len - 1) * sizeof(Vdata));
v->len--;
return val;
}
--cut here--
--
James Turner turnerjh@pattern.net UIN: 1102038
http://www.vuse.vanderbilt.edu/~turnerjh/
+------------------------------------------------------------+
| Ensure that you have read the CircleMUD Mailing List FAQ: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/15/00 PST