Simple vector-implementation in C

.gitignore

.svn/
test_vector
vector.o
git.staged.diff
git.unstaged.diff
svn.diff
tags

README_git

http://help.github.com/fork-a-repo/

These instructions don't work exactly when the forked repo is a "gist". Here's my history of commands:
  604  git clone git@gist.github.com:1453219.git vector
  605  cd vector/
  611  git remote add upstream git://gist.github.com/1453219.git
  612  git fetch upstream
  613  git branch
  ... edit files
  620  git add kp_macros.h 
  621  git add test_vector.c 
  622  git add vector.c 
  623  git add vector.h 
  625  git commit -m "Initial commit: revised vector interface, reimplemented delete function, added test file."
  626  git push origin master

Makefile

INCL = -I./

CC 	= gcc
CFLAGS 	= $(INCL) -g -Wall -Wunused

default: test_vector test_vector64
ALL = test_vector test_vector64
all: $(ALL)

######################################################
vector.o: vector.c vector.h vector_macros.h
	$(CC) -c -o $@ $< $(CFLAGS)

VEC_OBJ		= vector.o

test_vector: test_vector.c $(VEC_OBJ)
	$(CC) -o $@ $^ $(CFLAGS) $(LIBS)

######################################################
vector64.o: vector64.c vector64.h vector_macros.h
	$(CC) -c -o $@ $< $(CFLAGS)

VEC_OBJ		= vector64.o

test_vector64: test_vector64.c $(VEC_OBJ)
	$(CC) -o $@ $^ $(CFLAGS) $(LIBS)

######################################################
clean:
	rm -f *.o $(ALL)

test_vector.c

/* Peter Hornyack and Katelin Bailey
 * 12/8/11
 * University of Washington
 */

#include <stdlib.h>
#include <time.h>
#include "vector.h"
#include "vector_macros.h"

#define ELT_SIZE_MIN 2     //at least 2!!
#define ELT_SIZE_MAX 256
#define ELT_SIZE_DIFF 8
#define APPENDS_MIN 2
#define APPENDS_MAX 8
#define DELETES_MIN 4
#define DELETES_MAX 6
#define LOOPS 1000

void stress_test()
{
	int i, j, ret;
	unsigned long long idx, count;
	unsigned long tid;
	vector *v;
	void *e;
	long int rand_int;
	ssize_t size;
	char *final;

	if (APPENDS_MAX <= APPENDS_MIN) {
		v_die("invalid APPENDS_MAX %u and APPENDS_MIN %u\n", APPENDS_MAX,
				APPENDS_MIN);
	}
	if (DELETES_MAX <= DELETES_MIN) {
		v_die("invalid DELETES_MAX %u and DELETES_MIN %u\n", DELETES_MAX,
				DELETES_MIN);
	}

	srandom((unsigned int)time(NULL));
	tid = pthread_self();
	size = ELT_SIZE_MIN;
	ret = vector_alloc(&v);

	for (i = 0; i < LOOPS; i++) {
		/* First, do some appends: */
		rand_int = random();
		rand_int = (rand_int % (APPENDS_MAX - APPENDS_MIN)) + APPENDS_MIN;
		v_debug("appending %ld elements of size %u to vector:\n",
				rand_int, size);
		for (j = rand_int; j > 0; j--) {
			e = malloc(size);
			((char *)e)[0] = 'A' + ((i+rand_int-j)%26);
			((char *)e)[1] = '\0';
			ret = vector_append(v, e);
		}
		v_debug("appended %ld elements, now count=%llu\n", rand_int, vector_count(v));

		/* Then, do some deletes: */
		rand_int = random();
		rand_int = (rand_int % (DELETES_MAX - DELETES_MIN)) + DELETES_MIN;
		v_debug("deleting up to %ld values from vector\n", rand_int);
		for (j = rand_int; j > 0; j--) {
			count = vector_count(v);
			if (count == 0) {
				break;
			}
			idx = (i + j) % count;
			ret = vector_delete(v, idx, &e);
			v_debug("deleted element %s at idx=%llu, now freeing element\n",
					(char *)e, idx);
			free(e);
		}
		v_debug("deleted %ld elements, now count=%llu\n", rand_int - j,
				vector_count(v));

		/* Loop again: */
		size = size + ELT_SIZE_DIFF;
		if (size > ELT_SIZE_MAX) {
			size = ELT_SIZE_MIN;
		}
	}

	/* Print final contents of vector: */
	count = vector_count(v);
	v_debug("final vector count=%llu\n", count);
	final = malloc(count + 1);
	for (i = 0; i < count; i++) {
		ret = vector_get(v, i, &e);
		final[i] = ((char *)e)[0];
	}
	final[count] = '\0';
	v_debug("final contents of vector: %s\n", final);
	free(final);

	/* Free vector: */
	vector_free_contents(v);
	vector_free(v);
}

int main(int argc, char *argv[])
{
	int i, ret;
	unsigned long long count;
	unsigned long tid;
	vector *v;
	void *e;

	stress_test();
	v_print("stress test complete\n");

	tid = pthread_self();
	v_print("sizeof(void *)=%u, sizeof(unsigned int)=%u, "
			"sizeof(unsigned long int)=%u, sizeof(unsigned long)=%u, "
			"sizeof(unsigned long long)=%u\n",
			sizeof(void *), sizeof(unsigned int), sizeof(unsigned long int),
			sizeof(unsigned long), sizeof(unsigned long long));
	v_print("value of null-zero = %p\n", (void *)'\0');

	ret = vector_alloc(&v);
	v_testcase_int(tid, "vector_alloc", 0, ret);

	/* TODO: how/where are these strings allocated? Only have local scope
	 * (this main() function), right?
	 */
	ret = vector_append(v, "emil");
	v_testcase_int(tid, "vector_append", 0, ret);
	ret = vector_append(v, "hannes");
	v_testcase_int(tid, "vector_append", 0, ret);
	ret = vector_append(v, "lydia");
	v_testcase_int(tid, "vector_append", 0, ret);
	ret = vector_append(v, "olle");
	v_testcase_int(tid, "vector_append", 0, ret);
	ret = vector_append(v, "erik");
	v_testcase_int(tid, "vector_append", 0, ret);

	v_test("first round:\n");
	count = vector_count(v);
	for (i = 0; i < count; i++) {
		ret = vector_get(v, i, &e);
		v_testcase_int(tid, "vector_get", 0, ret);
		v_test("got element: %s\n", (char *)e);
	}

	ret = vector_delete(v, 1, &e);  //don't free e, statically allocated
	v_testcase_int(tid, "vector_delete", 0, ret);
	v_testcase_string(tid, "vector_delete", "hannes", (char *)e);
	ret = vector_delete(v, 3, &e);  //don't free e, statically allocated
	v_testcase_int(tid, "vector_delete", 0, ret);
	v_testcase_string(tid, "vector_delete", "erik", (char *)e);

	v_test("second round:\n");
	count = vector_count(v);
	for (i = 0; i < count; i++) {
		ret = vector_get(v, i, &e);
		v_testcase_int(tid, "vector_get", 0, ret);
		v_test("got element: %s\n", (char *)e);
	}

	ret = vector_delete(v, 3, &e);
	v_testcase_int(tid, "vector_delete", -1, ret);
	ret = vector_delete(v, 2, &e);  //don't free e, statically allocated
	v_testcase_int(tid, "vector_delete", 0, ret);
	v_testcase_string(tid, "vector_delete", "olle", (char *)e);
	ret = vector_delete(v, 0, &e);  //don't free e, statically allocated
	v_testcase_int(tid, "vector_delete", 0, ret);
	v_testcase_string(tid, "vector_delete", "emil", (char *)e);
	ret = vector_delete(v, 0, &e);  //don't free e, statically allocated
	v_testcase_int(tid, "vector_delete", 0, ret);
	v_testcase_string(tid, "vector_delete", "lydia", (char *)e);

	vector_free(v);

	return 0;
}

test_vector64.c

/* Peter Hornyack and Katelin Bailey
 * 12/8/11
 * University of Washington
 */

#include <stdlib.h>
#include <time.h>
#include "vector64.h"
#include "vector_macros.h"

#define APPENDS_MIN 2
#define APPENDS_MAX 8
#define DELETES_MIN 4
#define DELETES_MAX 5
#define ELT_MIN 0
#define ELT_MAX 1000000
#define LOOPS 1000

void stress_test64()
{
	int ret;
	uint64_t i, j;
	uint64_t idx, count;
	unsigned long tid;
	vector64 *v;
	uint64_t e;
	long int rand_int;

	if (APPENDS_MAX <= APPENDS_MIN) {
		v_die("invalid APPENDS_MAX %u and APPENDS_MIN %u\n", APPENDS_MAX,
				APPENDS_MIN);
	}
	if (DELETES_MAX <= DELETES_MIN) {
		v_die("invalid DELETES_MAX %u and DELETES_MIN %u\n", DELETES_MAX,
				DELETES_MIN);
	}
	if (ELT_MAX <= ELT_MIN) {
		v_die("invalid ELT_MAX %u and ELT_MIN %u\n", ELT_MAX, ELT_MIN);
	}

	srandom((unsigned int)time(NULL));
	tid = pthread_self();
	ret = vector64_alloc(&v);
	v_testcase_int(tid, "vector64_alloc", 0, ret);

	for (i = 0; i < LOOPS; i++) {
		/* First, do some appends: */
		rand_int = random();
		rand_int = (rand_int % (APPENDS_MAX - APPENDS_MIN)) + APPENDS_MIN;
		v_debug("appending %ld elements to vector64:\n", rand_int);
		for (j = rand_int; j > 0; j--) {
			e = (uint64_t)random();
			e = (e % (ELT_MAX - ELT_MIN)) + ELT_MIN;
			ret = vector64_append(v, e);
			//v_testcase_int(tid, "vector64_append", 0, ret);
		}
		v_debug("appended %ld elements, now count=%llu\n", rand_int,
				vector64_count(v));

		/* Then, do some deletes: */
		rand_int = random();
		rand_int = (rand_int % (DELETES_MAX - DELETES_MIN)) + DELETES_MIN;
		v_debug("deleting up to %ld values from vector64\n", rand_int);
		for (j = rand_int; j > 0; j--) {
			count = vector64_count(v);
			if (count == 0) {
				break;
			}
			idx = (uint64_t)random() % count;
			e = vector64_delete(v, idx);
			v_debug("deleted element %llu at idx=%llu\n", e, idx);
		}
		v_debug("deleted %llu elements, now count=%llu\n", rand_int - j,
				vector64_count(v));
	}

	/* Print final contents of vector64: */
	count = vector64_count(v);
	v_print("final vector64 count=%llu\n", count);
	v_print("final vector64 contents: ");
	for (i = 0; i < count; i++) {
		e = vector64_get(v, i);
		printf("%llu ", e);
	}
	printf("\n");

	/* Free vector64: */
	vector64_free(v);
}

int main(int argc, char *argv[])
{
	int ret;
	uint64_t i, count, ret64;
	unsigned long tid;
	vector64 *v;

	stress_test64();
	v_print("stress test complete\n");

	tid = pthread_self();
	v_print("sizeof(void *)=%u, sizeof(unsigned int)=%u, sizeof(uint64_t)=%u\n",
			sizeof(void *), sizeof(unsigned int), sizeof(uint64_t));

	ret = vector64_alloc(&v);
	v_testcase_int(tid, "vector64_alloc", 0, ret);

	ret64 = vector64_get(v, 0);  //error case
	v_testcase_uint64(tid, "vector64_get empty", UINT64_MAX, ret64);

	ret = vector64_append(v, 0);
	v_testcase_int(tid, "vector64_append", 0, ret);
	ret = vector64_append(v, 12);
	v_testcase_int(tid, "vector64_append", 0, ret);
	ret = vector64_append(v, 345);
	v_testcase_int(tid, "vector64_append", 0, ret);
	ret = vector64_append(v, 678);
	v_testcase_int(tid, "vector64_append", 0, ret);
	ret = vector64_append(v, 9012);
	v_testcase_int(tid, "vector64_append", 0, ret);
	
	ret = vector64_search_linear(v, 0, &ret64);
	v_testcase_int(tid, "vector64_search_linear 0", 0, ret);
	v_testcase_uint64(tid, "vector64_search_linear 0", (uint64_t)0, ret64);
	ret = vector64_search_linear(v, 1, &ret64);
	v_testcase_int(tid, "vector64_search_linear 1", 1, ret);
	ret = vector64_search_linear(v, 9012, &ret64);
	v_testcase_int(tid, "vector64_search_linear 9012", 0, ret);
	v_testcase_uint64(tid, "vector64_search_linear 9012", (uint64_t)4, ret64);
	ret = vector64_search_linear(v, 345, &ret64);
	v_testcase_int(tid, "vector64_search_linear 345", 0, ret);
	v_testcase_uint64(tid, "vector64_search_linear 345", (uint64_t)2, ret64);

	v_test("first round:\n");
	count = vector64_count(v);
	for (i = 0; i < count; i++) {
		ret64 = vector64_get(v, i);
		v_testcase_uint64_not(tid, "vector64_get", UINT64_MAX, ret64);
		v_test("got element %llu from idx %llu\n", ret64, i);
	}
	ret64 = vector64_get(v, 10);  //error case
	v_testcase_uint64(tid, "vector64_get out-of-bounds", UINT64_MAX, ret64);

	ret64 = vector64_delete(v, 1);
	v_testcase_uint64(tid, "vector64_delete", (uint64_t)12, ret64);
	ret64 = vector64_delete(v, 3);
	v_testcase_uint64(tid, "vector64_delete", (uint64_t)9012, ret64);

	v_test("second round:\n");
	count = vector64_count(v);
	for (i = 0; i < count; i++) {
		ret64 = vector64_get(v, i);
		v_testcase_uint64_not(tid, "vector64_get", UINT64_MAX, ret64);
		v_test("got element %llu from idx %llu\n", ret64, i);
	}

	ret = vector64_search_linear(v, 0, &ret64);
	v_testcase_int(tid, "vector64_search_linear 0", 0, ret);
	v_testcase_uint64(tid, "vector64_search_linear 0", (uint64_t)0, ret64);
	ret = vector64_search_linear(v, 9012, &ret64);
	v_testcase_int(tid, "vector64_search_linear 9012", 1, ret);
	ret = vector64_search_linear(v, 345, &ret64);
	v_testcase_int(tid, "vector64_search_linear 345", 0, ret);
	v_testcase_uint64(tid, "vector64_search_linear 345", (uint64_t)1, ret64);

	ret64 = vector64_delete(v, 3);  //error case
	v_testcase_uint64(tid, "vector64_delete out-of-bounds", UINT64_MAX, ret64);
	ret64 = vector64_delete(v, 2);
	v_testcase_uint64(tid, "vector64_delete", (uint64_t)678, ret64);
	ret64 = vector64_delete(v, 0);
	v_testcase_uint64(tid, "vector64_delete", (uint64_t)0, ret64);
	ret64 = vector64_delete(v, 0);
	v_testcase_uint64(tid, "vector64_delete", (uint64_t)345, ret64);
	ret64 = vector64_delete(v, 0);  //error case
	v_testcase_uint64(tid, "vector64_delete empty", UINT64_MAX, ret64);

	ret = vector64_search_linear(v, 345, &ret64);
	v_testcase_int(tid, "vector64_search_linear 345", 1, ret);

	vector64_free(v);

	return 0;
}

vector.c

/* c-basic-offset: 2; tab-width: 2; indent-tabs-mode: t
 * vi: set noexpandtab:
 * :noTabs=false:
 *
 * Forked from: https://gist.github.com/953968
 */

#include <stdlib.h>
#include "vector.h"
#include "vector_macros.h"

#define VECTOR_INIT_SIZE 2
#define VECTOR_RESIZE_FACTOR 2

struct vector_ {
	void** data;         //array of void pointers
	unsigned long long size;   //number of array elements allocated
	unsigned long long count;  //number of elements in use
};

int vector_alloc(vector **v)
{
	*v = malloc(sizeof(vector));
	if (*v == NULL) {
		v_error("malloc(vector) failed\n");
		return -1;
	}

	(*v)->data = NULL;
	(*v)->size = 0;
	(*v)->count = 0;

	v_debug("successfully allocated new vector\n");
	return 0;
}

unsigned long long vector_count(vector *v)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;  //vector_count isn't supposed to return an error, oh well
	}
	v_debug("returning count=%llu (size=%llu)\n", v->count, v->size);
	return v->count;
}

int vector_append(vector *v, void *e)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;
	}
	//TODO: should check if vector has hit max size here!

	if (v->size == 0) {
		v->size = VECTOR_INIT_SIZE;
		v->data = malloc(sizeof(void*) * v->size);
		if (v->data == NULL) {
			v_error("malloc(array) failed\n");
			return -1;
		}
		v_debug("allocated new array of size %llu (%llu slots)\n",
				sizeof(void*) * v->size, v->size);
	}

	/* When the last array slot is exhausted, increase the size of the
	 * array by multiplying it by the resize factor.
	 * Realloc leaves the contents at the beginning of the array unchanged;
	 * the newly-allocated memory will be uninitialized.
	 */
	if (v->size == v->count) {
		v->size *= VECTOR_RESIZE_FACTOR;
		v->data = realloc(v->data, sizeof(void*) * v->size);
		if (v->data == NULL) {
			v_error("realloc(array) failed\n");
			return -1;
		}
		v_debug("re-allocated array, now has size %llu (%llu slots)\n",
				sizeof(void*) * v->size, v->size);
	}

	v->data[v->count] = e;
	v->count++;
	v_debug("stored new element %s in slot %llu (now count=%llu, size=%llu)\n",
			(char *)(v->data[(v->count)-1]), v->count-1, v->count, v->size);

	return 0;
}

int vector_set(vector *v, unsigned long long idx, void *e, void **old_e)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;
	}
	if (idx >= v->count) {
		if (VECTOR_DIE_ON_OOB) {
			v_die("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		}
		v_error("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		return -1;
	}

	*old_e = v->data[idx];
	v->data[idx] = e;
	v_debug("stored element %s in slot %llu (count=%llu, size=%llu)\n",
			(char *)(v->data[idx]), idx, v->count, v->size);

	return 0;
}

int vector_get(vector *v, unsigned long long idx, void **e)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;
	}
	if (idx >= v->count) {
		if (VECTOR_DIE_ON_OOB) {
			v_die("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		}
		v_error("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		return -1;
	}

	*e = v->data[idx];
	v_debug("got element %s from slot %llu (count=%llu, size=%llu)\n",
			(char *)(*e), idx, v->count, v->size);

	return 0;
}

int vector_delete(vector *v, unsigned long long idx, void **e)
{
	unsigned long long i;

	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;
	}
	if (idx >= v->count) {
		if (VECTOR_DIE_ON_OOB) {
			v_die("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		}
		v_error("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		return -1;
	}

	/* Don't free the element to be deleted, but set *e to point to it
	 * so that the caller can free it. Then, shift all of the other
	 * elements in the array down one slot:
	 */
	v_debug("deleting element %s from slot %llu\n", (char *)v->data[idx], idx);
	if (e) {
		*e = v->data[idx];
	}
	for (i = idx; i < v->count - 1; i++) {
		v->data[i] = v->data[i+1];
		v_debug("shifted element %s from slot %llu down to slot %llu\n",
				(char *)(v->data[i]), i+1, i);
	}
	v->count--;
	v_debug("now count=%llu, size=%llu (resize factor=%u)\n", v->count, v->size,
			VECTOR_RESIZE_FACTOR);

	/* Shrink the array if the number of used slots falls below the number
	 * of allocated slots divided by the resize factor times 2. We double
	 * the resize factor when checking this condition, but only shrink the
	 * array by a single resize factor, to avoid "pathological" behavior
	 * where the vector reaches some size and then the client repeatedly
	 * adds one element and deletes one element, causing a resize on every
	 * operation (note: this analysis is not scientific nor empirical).
	 *
	 * In the condition below, <= causes resizing to happen a bit earlier
	 * and seems better than just <. With VECTOR_RESIZE_FACTOR = 2, this
	 * logic causes the array to be cut in half when the number of elements
	 * is decreased to 1/4 of the number of allocated slots.
	 */
	if ((v->size > VECTOR_INIT_SIZE) &&
	    (v->count <= v->size / (VECTOR_RESIZE_FACTOR * 2))) {
		v_debug("count %llu is <= %llu, shrinking array\n", v->count,
				v->size / (VECTOR_RESIZE_FACTOR * 2));
		v->size /= VECTOR_RESIZE_FACTOR;  //inverse of vector_append()
		v->data = realloc(v->data, sizeof(void*) * v->size);
		if (v->data == NULL) {
			v_die("realloc(array) failed\n");
		}
		v_debug("shrunk array, now has size %llu (%llu slots)\n",
				sizeof(void*) * v->size, v->size);
	}

	return 0;
}

void vector_free_contents(vector *v)
{
	unsigned long long i, count;

	if (v == NULL) {
		v_error("v is NULL\n");
		return;
	}

	count = v->count;
	for (i = 0; i < count; i++) {
		if (v->data[i]) {
			v_debug("freeing element %s from slot %llu\n",
					(char *)(v->data[i]), i);
			free(v->data[i]);
		} else {
			v_debug("NULL pointer in array, not freeing it\n");
		}
	}
	v_debug("successfully freed %llu elements from vector\n", count);
}

void vector_free(vector *v)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return;
	}

	free(v->data);
	free(v);
	v_debug("freed vector's array and vector struct itself\n");
}

unsigned int vector_struct_size()
{
	return sizeof(vector);
}

/*
 * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 *
 * Local variables:
 * c-basic-offset: 2
 * tab-width: 2
 * indent-tabs-mode: t
 * End:
 *
 * vi: set noexpandtab:
 * :noTabs=false:
 */

vector.h

/* c-basic-offset: 2; tab-width: 2; indent-tabs-mode: t
 * vi: set noexpandtab:
 * :noTabs=false:
 *
 * Forked from: https://gist.github.com/953968
 *
 * This implementation is "thread-safe," meaning that multiple clients
 * can create and use vectors that are completely independent of each
 * other; the memory-management functions (malloc, realloc, free) that
 * are used internally are thread-safe. However, this DOES NOT mean
 * that multiple readers/writers to the SAME vector will not step on each
 * other; the client must perform its own synchronization for the vector.
 *
 * This vector stores generic void* as its elements, and can store up to
 * 2^n - 1 of them, where n is the number of bits in an unsigned long long.
 */

#ifndef VECTOR_H__
#define VECTOR_H__

/* Set to 1 if we should die on index out-of-bounds errors, or 0 if we
 * should just return an error.
 */
#define VECTOR_DIE_ON_OOB 1

/* Opaque handle: */
struct vector_;
typedef struct vector_ vector;

/* Allocates and initializes a vector. The vector should later be freed
 * by passing it to vector_free().
 * Returns: 0 on success, -1 on error. On success, *v will be set to point
 * to the newly-allocated vector.
 */
int vector_alloc(vector **v);

/* Returns: the number of elements in the vector.
 * Important: be careful about calling vector_count() directly in the
 * loop-condition of a for/while loop: it will be re-called on every loop!
 */
unsigned long long vector_count(vector *v);

/* Appends an element to the vector.
 * Note that currently, if the number of appended elements goes over the
 * maximum (2^n - 1, where n is the number of bits in an unsigned long long),
 * then undefined behavior will result (this error case is not checked
 * for).
 * Returns: 0 on success, -1 on error.
 */
int vector_append(vector *v, void *e);

/* Replaces the element at the specified index.
 * Returns: 0 on success, -1 on error. On success, *old_e is set to point
 * to the element that was previously stored in the slot.
 */
int vector_set(vector *v, unsigned long long idx, void *e, void **old_e);

/* Gets the element at the specified index. If VECTOR64_DIE_ON_OOB is set
 * to true, then the only other error case for this function is if the pointer
 * that is passed to it is NULL, so if you're lazy, then you can skip
 * error-checking this function's return value.
 * Returns: 0 on success, -1 on error. On success, *e is set to point to
 * the gotten element.
 */
int vector_get(vector *v, unsigned long long idx, void **e);

/* Removes the element at the specified index, and shifts all of the
 * remaining elements down in the vector. Importantly, the element
 * itself is NOT freed; if e is non-NULL, then *e is set to point to
 * the element, so that the caller can free it.
 * Returns: 0 on success, -1 on error.
 */
int vector_delete(vector *v, unsigned long long idx, void **e);

/* Calls free() on all non-null pointers that are stored in the vector.
 * It does not remove these pointers from the vector however, so the
 * vector's element count will be unchanged.
 * USE THIS FUNCTION WITH CAUTION: it should probably only be called
 * just before calling vector_free(v).
 */
void vector_free_contents(vector *v);

/* Frees the vector's array and the vector struct itself. NOTE: if the
 * array contains pointers to other data, the data that is pointed to
 * is NOT freed!
 */
void vector_free(vector *v);

/* Returns: the size of the vector struct */
unsigned int vector_struct_size();

#endif  //VECTOR_H

/*
 * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 *
 * Local variables:
 * c-basic-offset: 2
 * tab-width: 2
 * indent-tabs-mode: t
 * End:
 *
 * vi: set noexpandtab:
 * :noTabs=false:
 */

vector64.c

/* c-basic-offset: 2; tab-width: 2; indent-tabs-mode: t
 * vi: set noexpandtab:
 * :noTabs=false:
 *
 * Forked from: https://gist.github.com/953968
 */

#include <stdlib.h>
#include "vector64.h"
#include "vector_macros.h"

/* Factors that define when and how the vector is resized. The initial
 * size must be an integer, but the resize factor may be non-integral
 * (although I've only tested integer factors, namely 2.0).
 */
#define VECTOR64_INIT_SIZE 4
#define VECTOR64_RESIZE_FACTOR 2.0

struct vector64_ {
	/* Tip: use "%llu" in printf strings to print uint64_t types. */
	uint64_t *array; //array of unsigned 64-bit integers
	uint64_t size;   //number of array elements allocated
	uint64_t count;  //number of elements in use
};

int vector64_alloc(vector64 **v)
{
	*v = malloc(sizeof(vector64));
	if (*v == NULL) {
		v_error("malloc(vector64) failed\n");
		return -1;
	}

	/* NOTE: we don't pre-allocate the array here, so there will be some
	 * overhead on the first put. For evaluation purposes, that could
	 * disrupt the measurement of the cost of an alloc versus a put/append,
	 * but then again other puts/appends may require re-allocation of the
	 * array anyway, so this is probably no big deal.
	 */
	(*v)->array = NULL;
	(*v)->size = 0;
	(*v)->count = 0;

	v_debug("successfully allocated new vector64\n");
	return 0;
}

uint64_t vector64_count(vector64 *v)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return UINT64_MAX;
	}
	v_debug("returning count=%llu (size=%llu)\n", v->count, v->size);
	return v->count;
}

int vector64_append(vector64 *v, uint64_t e)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;
	}
	if (v->count == UINT64_MAX-1) {
		v_error("v has hit max size (%llu)\n", UINT64_MAX-1);
		return -1;
	}

	if (v->size == 0) {
		v->size = VECTOR64_INIT_SIZE;
		v->array = malloc(sizeof(uint64_t) * v->size);
		if (v->array == NULL) {
			v_error("malloc(array) failed\n");
			return -1;
		}
		v_debug("allocated new array of size %llu (%llu slots)\n",
				sizeof(uint64_t) * v->size, v->size);
	}

	/* When the last array slot is exhausted, increase the size of the
	 * array by multiplying it by the resize factor.
	 * Realloc leaves the contents at the beginning of the array unchanged;
	 * the newly-allocated memory will be uninitialized.
	 */
	if (v->size == v->count) {
		v->size = (uint64_t)(v->size * VECTOR64_RESIZE_FACTOR);
		v->array = realloc(v->array, sizeof(uint64_t) * v->size);
		if (v->array == NULL) {
			v_error("realloc(array) failed\n");
			return -1;
		}
		v_debug("re-allocated array, now has size %llu (%llu slots)\n",
				sizeof(uint64_t) * v->size, v->size);
	}

	v->array[v->count] = e;
	v->count++;
	v_debug("stored new element %llu in slot %llu (now count=%llu, "
			"size=%llu)\n", v->array[(v->count)-1], v->count-1, v->count,
			v->size);

	return 0;
}

uint64_t vector64_set(vector64 *v, uint64_t idx, uint64_t e)
{
	uint64_t old_e;

	if (v == NULL) {
		v_error("v is NULL\n");
		return UINT64_MAX;
	}
	if (idx >= v->count) {
		if (VECTOR64_DIE_ON_OOB) {
			v_die("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		}
		v_error("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		return UINT64_MAX;
	}

	old_e = v->array[idx];
	v->array[idx] = e;
	v_debug("stored element %llu in slot %llu (count=%llu, size=%llu)\n",
			v->array[idx], idx, v->count, v->size);

	return old_e;
}

uint64_t vector64_get(vector64 *v, uint64_t idx)
{
	uint64_t e;

	if (v == NULL) {
		v_error("v is NULL\n");
		return UINT64_MAX;
	}
	if (idx >= v->count) {
		if (VECTOR64_DIE_ON_OOB) {
			v_die("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		}
		v_error("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		return UINT64_MAX;
	}

	e = v->array[idx];
	//v_debug("got element %llu from slot %llu (count=%llu, size=%llu)\n",
	//		e, idx, v->count, v->size);

	return e;
}

uint64_t vector64_delete(vector64 *v, uint64_t idx)
{
	uint64_t old_e;
	uint64_t i;

	if (v == NULL) {
		v_error("v is NULL\n");
		return UINT64_MAX;
	}
	if (idx >= v->count) {
		if (VECTOR64_DIE_ON_OOB) {
			v_die("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		}
		v_error("index %llu out-of-bounds, v->count=%llu\n", idx, v->count);
		return UINT64_MAX;
	}

	/* Remember the deleted element, then shift all of the other elements
	 * in the array down one slot:
	 */
	old_e = v->array[idx];
	v_debug("deleting element %llu from slot %llu\n", old_e, idx);
	for (i = idx; i < v->count - 1; i++) {
		v->array[i] = v->array[i+1];
		v_debug("shifted element %llu from slot %llu down to slot %llu\n",
				v->array[i], i+1, i);
	}
	v->count--;
	v_debug("now count=%llu, size=%llu (resize factor=%f)\n", v->count,
			v->size, VECTOR64_RESIZE_FACTOR);

	/* Shrink the array if the number of used slots falls below the number
	 * of allocated slots divided by the resize factor times 2. We double
	 * the resize factor when checking this condition, but only shrink the
	 * array by a single resize factor, to avoid "pathological" behavior
	 * where the vector reaches some size and then the client repeatedly
	 * adds one element and deletes one element, causing a resize on every
	 * operation (note: this analysis is not scientific nor empirical).
	 *
	 * In the condition below, <= causes resizing to happen a bit earlier
	 * and seems better than just <. With VECTOR64_RESIZE_FACTOR = 2, this
	 * logic causes the array to be cut in half when the number of elements
	 * is decreased to 1/4 of the number of allocated slots (so the array
	 * will be half-filled after it is shrunk). Also, we allow
	 * the resize factor to be non-integral, so we cast the computation
	 * results back to uint64_t; there could presumably be rounding errors
	 * here, but during debugging such errors did not occur, and even if
	 * they do, it shouldn't be a big deal.
	 */
	if ((v->size > VECTOR64_INIT_SIZE) &&
	    (v->count <= (uint64_t)(v->size / (VECTOR64_RESIZE_FACTOR * 2)))) {
		v_debug("count %llu is <= %llu, shrinking array\n", v->count,
				(uint64_t)(v->size / (VECTOR64_RESIZE_FACTOR * 2)));
		v->size = (uint64_t)(v->size / VECTOR64_RESIZE_FACTOR);  //inverse of vector64_append()
		v->array = realloc(v->array, sizeof(uint64_t) * v->size);
		if (v->array == NULL) {
			v_die("realloc(array) failed\n");
		}
		v_debug("shrunk array, now has size %llu (%llu slots)\n",
				sizeof(uint64_t) * v->size, v->size);
	}

	return old_e;
}

int vector64_search_linear(vector64 *v, uint64_t key, uint64_t *idx)
{
	uint64_t i;

	if (v == NULL) {
		v_error("v is NULL\n");
		return -1;
	}

	for (i = 0; i < v->count; i++) {
		if (v->array[i] == key) {
			*idx = i;
			v_debug("found search key %llu at idx=%llu\n", key, *idx);
			return 0;
		}
	}

	v_debug("searched through all %llu elements, did not find search key "
			"%llu\n", v->count, key);
	return 1;
}

void vector64_free(vector64 *v)
{
	if (v == NULL) {
		v_error("v is NULL\n");
		return;
	}

	free(v->array);
	free(v);
	v_debug("freed vector64's array and vector64 struct itself\n");
}

unsigned int vector64_struct_size()
{
	return sizeof(vector64);
}

#define VECTOR64_MAX_STRLEN 2048
char *vector64_to_string(vector64 *v)
{
	int len;
	uint64_t i;
	char *bigstring, *littlestring;
	
	bigstring = malloc(VECTOR64_MAX_STRLEN);
	if (bigstring == NULL) {
		return NULL;
	}
	littlestring = malloc(VECTOR64_MAX_STRLEN);
	if (littlestring == NULL) {
		return NULL;
	}

	bigstring[0]='\0';
	len = 0;
	for (i = 0; i < v->count && len < VECTOR64_MAX_STRLEN-1; i++) {
		/* hopefully vector doesn't change during loop... */
		snprintf(littlestring, VECTOR64_MAX_STRLEN, "[%llu:%llu]", i,
				v->array[i]);
		strncat(bigstring, littlestring, VECTOR64_MAX_STRLEN - len - 1);
		len = strlen(bigstring);
	}
	
	free(littlestring);
	return bigstring;
}

/*
 * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 *
 * Local variables:
 * c-basic-offset: 2
 * tab-width: 2
 * indent-tabs-mode: t
 * End:
 *
 * vi: set noexpandtab:
 * :noTabs=false:
 */

vector64.h

/* c-basic-offset: 2; tab-width: 2; indent-tabs-mode: t
 * vi: set noexpandtab:
 * :noTabs=false:
 *
 * Forked from: https://gist.github.com/953968
 *
 * This implementation is "thread-safe," meaning that multiple clients
 * can create and use vectors that are completely independent of each
 * other; the memory-management functions (malloc, realloc, free) that
 * are used internally are thread-safe. However, this DOES NOT mean
 * that multiple readers/writers to the SAME vector will not step on each
 * other; the client must perform its own synchronization for the vector.
 *
 * This vector stores unsigned 64-bit integers (uint64_t) as its elements,
 * and can store up to 2^64 - 2 (UINT64_MAX - 1) of them.
 */

#ifndef VECTOR64_H__
#define VECTOR64_H__

#include <stdint.h>

/* Set to 1 if we should die on index out-of-bounds errors, or 0 if we
 * should just return an error.
 */
#define VECTOR64_DIE_ON_OOB 1

/* Opaque handle: */
struct vector64_;
typedef struct vector64_ vector64;

/* Allocates and initializes a vector. The vector should later be freed
 * by passing it to vector_free().
 * Returns: 0 on success, -1 on error. On success, *v will be set to point
 * to the newly-allocated vector.
 */
int vector64_alloc(vector64 **v);

/* Returns: the number of elements in the vector, or UINT64_MAX on error.
 * (The only error case for this function is if the pointer that is passed
 * to it is NULL, so if you're lazy, then you can skip error-checking this
 * function's return value.)
 * Important: be careful about calling vector64_count() directly in the
 * loop-condition of a for/while loop: it will be re-called on every loop!
 */
uint64_t vector64_count(vector64 *v);

/* Appends an element to the vector. Valid element values range from 0 to
 * UINT64_MAX-1.
 * Returns: 0 on success, -1 on error.
 */
int vector64_append(vector64 *v, uint64_t e);

/* Replaces the element at the specified index. Valid element values range
 * from 0 to UINT64_MAX-1.
 * Returns: the element that was previously stored in the slot on success,
 * or UINT64_MAX on error.
 */
uint64_t vector64_set(vector64 *v, uint64_t idx, uint64_t e);

/* Gets the element at the specified index. If VECTOR64_DIE_ON_OOB is set
 * to true, then the only other error case for this function is if the pointer
 * that is passed to it is NULL, so if you're lazy, then you can skip
 * error-checking this function's return value.
 * Returns: the specified element, or UINT64_MAX on error.
 */
uint64_t vector64_get(vector64 *v, uint64_t idx);

/* Removes the element at the specified index, and shifts all of the
 * remaining elements down in the vector.
 * Returns: the element that was stored at the specified index, or
 * UINT64_MAX on error.
 */
uint64_t vector64_delete(vector64 *v, uint64_t idx);

/* Performs a linear search through the vector for the key, suitable for
 * an unsorted vector.
 * Returns: on success, 0 is returned and *idx is set to the index where
 * the key was found. 1 is returned if the key was not found. -1 is
 * returned on error.
 */
int vector64_search_linear(vector64 *v, uint64_t key, uint64_t *idx);

/* Frees the vector.
 */
void vector64_free(vector64 *v);

/* Returns: the size of the vector struct */
unsigned int vector64_struct_size();

/* Creates a string with the contents of the vector, which must be 
 * freed by the caller (if it is non-null)!
 * Returns: pointer to the string, or NULL on error.
 */
char *vector64_to_string(vector64 *v);


#endif  //VECTOR64_H

/*
 * Editor modelines  -  http://www.wireshark.org/tools/modelines.html
 *
 * Local variables:
 * c-basic-offset: 2
 * tab-width: 2
 * indent-tabs-mode: t
 * End:
 *
 * vi: set noexpandtab:
 * :noTabs=false:
 */

vector_macros.h

/*
 * Peter Hornyack
 * Created: 8/28/2011
 * University of Washington
 */

#ifndef VECTOR_MACROS_H
#define VECTOR_MACROS_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

/* VECTOR_ASSERT should always be defined for sanity-checking purposes,
 * and only un-defined when we want to disable sanity-checking code to
 * get maximum performance (it will probably make very little difference
 * though).
 * VECTOR_DEBUG enables verbose debug messages.
 * VECTOR_DEBUG_LOCK enables verbose messages for mutex and rwlock lock/unlock.
 */
//#define VECTOR_ASSERT
//#define VECTOR_DEBUG
//#define VECTOR_DEBUG_LOCK

/* Note that printing the result of pthread_self() in this way is not
 * portable. On systems lab machines, /usr/include/bits/pthreadtypes.h
 * contains: "typedef unsigned long int pthread_t;".
 */

/* Print normal and debug output to stdout, warning and error output to
 * stderr. Always flush after printing; this makes debugging etc. easier,
 * but possibly causes slowdown.
 */
#define v_print(f, a...)  do { \
	fprintf(stdout, "VECTOR: %lu: " f, pthread_self(), ##a); \
	fflush(stdout); \
	} while(0)
#define v_warn(f, a...)  do { \
	fprintf(stderr, "**WARNING**: %lu: %s: " f, pthread_self(), __func__, ##a); \
	fflush(stderr); \
	} while(0)
#define v_error(f, a...)  do { \
	fprintf(stderr, "ERROR: %lu: %s: " f, pthread_self(), __func__, ##a); \
	fflush(stderr); \
	} while(0)
#define v_test(f, a...) fprintf(stdout, "TEST: %lu: " f, pthread_self(), ##a)

#ifdef v_DEBUG
#define v_debug(f, a...)  do { \
	fprintf(stdout, "DEBUG: %lu: %s: " f, pthread_self(), __func__, ##a); \
	fflush(stdout); \
	} while(0)
#else
#define v_debug(f, a...)  do { ; } while(0)
#endif
#define v_debug2(f, a...)  do { \
	fprintf(stdout, "DEBUG: %lu: %s: " f, pthread_self(), __func__, ##a); \
	fflush(stdout); \
	} while(0)

/* die by abort()ing; is exit(-1) better? */
#define v_die(f, a...)  do { \
	fprintf(stderr, "VECTOR: Fatal error (%lu: %s): " f, pthread_self(), __func__, ##a); \
	fflush(stderr); \
	abort(); \
	} while(0)

#ifdef VECTOR_DEBUG_LOCK
#define v_debug_lock(f, a...)  do { \
	fprintf(stdout, "DEBUG: %lu: %s: " f, pthread_self(), __func__, ##a); \
	fflush(stderr); \
	} while(0)
#else
#define v_debug_lock(f, a...)  do { ; } while(0)
#endif

#define v_testcase_int(tid, description, expected, actual) do { \
	fprintf(stdout, "TEST %s: %lu: %s: expected=%d, actual=%d\n", \
			(expected == actual) ? "PASS" : "FAIL", \
			tid, description, expected, actual); \
} while(0)

#define v_testcase_uint64(tid, description, expected, actual) do { \
	fprintf(stdout, "TEST %s: %lu: %s: expected=%llu, actual=%llu\n", \
			(expected == actual) ? "PASS" : "FAIL", \
			tid, description, expected, actual); \
} while(0)

#define v_testcase_uint64_not(tid, description, expected, actual) do { \
	fprintf(stdout, "TEST %s: %lu: %s: expected != %llu, actual=%llu\n", \
			(expected != actual) ? "PASS" : "FAIL", \
			tid, description, expected, actual); \
} while(0)

#define v_testcase_string(tid, description, expected, actual) do { \
	fprintf(stdout, "TEST %s: %lu: %s: expected=%s, actual=%s\n", \
			(expected == NULL) ? "FAIL" : \
			(actual == NULL) ? "FAIL" : \
			(strcmp(expected, actual) == 0) ? "PASS" : "FAIL", \
			tid, description, expected, actual); \
} while(0)

#endif  //VECTOR_MACROS_H