Skip to content

Instantly share code, notes, and snippets.

@pjh

pjh/.gitignore

Created December 9, 2011 20:43
Show Gist options
  • Save pjh/1453219 to your computer and use it in GitHub Desktop.
Save pjh/1453219 to your computer and use it in GitHub Desktop.
Download ZIP
Simple vector-implementation in C
Raw
.gitignore
.svn/
test_vector
vector.o
git.staged.diff
git.unstaged.diff
svn.diff
tags
Raw
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 [email protected]: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
Raw
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)
Raw
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;
}
Raw
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;
}
Raw
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:
*/
Raw
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:
*/
Raw
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:
*/
Raw
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:
*/
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment