cvector.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cvector.h"

/* CVECTOR SPECIFIC */

/* allocates an empty & zeroed vector with room for capacity number of
   elements that uses element_size bytes of RAM each, the iterators array
   of iterator pointers will use sizeof(void*) * elements number of bytes,
   the rest of the structure is either 12 or 6 bytes depending on compile-time
   #define's =)

   if pvector equals 0 the function will allocate a new vector dynamically
   instead of using a static OR already existing but free()'d vector pointed
   to by pvector */
struct t_cvector* cvector_alloc(struct t_cvector *pvector,
                                CVECTOR_UINT element_size, CVECTOR_UINT capacity) {
 struct t_cvector *v = 0;
 CVECTOR_UINT i;

 if(element_size == 0)
  return 0;

 if(pvector == 0) {
  v = (struct t_cvector*)malloc(sizeof(struct t_cvector));

  if(v == 0)
   return 0;

  // this cvector was dynamically allocated
  v->conf_bits = CVECTOR_DYN_ALLOC;

 } else {
  v = pvector;

  // and this was not!
  v->conf_bits = 0;
 }

 v->element_size = element_size;
 v->capacity = 0;
 v->elements = 0;
 v->data = 0;
 v->iterators = 0;

 /* reserve RAM for capacity number of elements */
 if(capacity < 1)
  capacity = 2;

 // error-check when reserving memory
 if(cvector_reserve(v, capacity) == 0) {
  if(pvector == 0)
   free(v);

  return 0;
 }

 return v;
}

/* free allocated capacity for vector, rendering all data and iterators
   'lost', thus all pointers to specific elements WILL cause a CRASH (sooner or later) */
void cvector_free(struct t_cvector *v) {
 if(v->capacity > 0) {
  free(v->data);
  free(v->iterators);

  v->element_size = 0;
  v->capacity = 0;
  v->elements = 0;
  v->data = 0;
  v->iterators = 0;

  if(v->conf_bits & CVECTOR_DYN_ALLOC)
   free(v);
 }
}

/* ITERATORS */

/* returns an iteratable pointer array that points to the crude data,
   from the beginning of the vector */
CVECTOR_VOID* cvector_begin(struct t_cvector *v) {
 return (CVECTOR_VOID*)(v->iterators[0]);
}

/* returns an iteratable pointer array that points to the crude data,
   from the end of the vector */
CVECTOR_VOID* cvector_end(struct t_cvector *v) {
 return (CVECTOR_VOID*)(v->iterators[v->elements - 1]);
}

/* CAPACITY */

/* ***hidden from public access - function prototype commented in header file***

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure

   this fuction will test if there is any need to grow capacity if n elements
   were going to be added to the vector, if needed a reallocation and rise of
   vector capacity will happen automatically */
CVECTOR_UINT cvector_grow_capacity(struct t_cvector *v, CVECTOR_UINT n) {
 CVECTOR_UINT reserve;

 /* grow capacity with "guesses", that is: if the vector grows bigger than
    the capacity we need exactly as much space we need, but as we do not really
    know how much more RAW we will need in this vector we can quite safely assume
    that if the vector reaches capacity it needs at least capacity+(capacity/2)
 */

 while((v->elements + n) > v->capacity) {
  reserve = v->capacity + (v->capacity / 2);

  if(!cvector_reserve(v, reserve))
   return 0;
 }

 return 1;
}

/* returns the number of elements stored in the vector */
CVECTOR_UINT cvector_size(struct t_cvector *v) {
 return v->elements;
}

/* returns the (currently allocated) capacity of elements
   to be stored in the vector */
CVECTOR_UINT cvector_capacity(struct t_cvector *v) {
 return v->capacity;
}

/* returns 1 if vector is empty, otherwise 0 */
CVECTOR_UINT cvector_empty(struct t_cvector *v) {
 return (v->elements == 0 ? 1 : 0);
}

/* resize number of elements in vector to n

   if n is greater than current number of elements the newly added elements will
   get their contents copied from *data

   if n is greater than vector capacity (currently allocated storage) a
   reallocation is required to happen - meaning all old pointers and iterators
   will be invalid

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure  */
CVECTOR_UINT cvector_resize(struct t_cvector *v, CVECTOR_UINT n, CVECTOR_VOID *data) {
 CVECTOR_UINT i;

 if(n < v->elements) {
  for(i=n;i<v->elements;i++) {
   cvector_pop_back(v);
  }

  return 1;
 }

 /* if n is greater than the capacity (currently allocated storage)
    a reallocation is needed */
 if(!cvector_reserve(v, n))
  return 0;

 /* if n is greater than current number of elements the newly added elements will
    get their contents copied from *data */
 if(n > v->elements) {
  for(i=v->elements;i<n;i++) {
   if(data)
    memmove(v->iterators[i], data, v->element_size);
  }
 }

 v->elements = n;

 return 1;
}

/* request that n number of elements should fit in the vector,
   if n is greater than the current capacity a reallocation is assured
   and therefore all old pointers to individual elements in vector v
   are rendered completely useless

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure */
CVECTOR_UINT cvector_reserve(struct t_cvector *v, CVECTOR_UINT n) {
 if(n > v->capacity) {
  CVECTOR_UINT i;
  CVECTOR_VOID *data;
  CVECTOR_VOID **iterators;

  data = (CVECTOR_VOID*)realloc(v->data, n * v->element_size);

  if(data == 0) {
   return 0;
  }

  iterators = (CVECTOR_VOID**)realloc(v->iterators, n * sizeof(CVECTOR_VOID*));

  if(iterators == 0) {
   free(data);
   return 0;
  }

  // calculate delta between old and new address of data locations for iterator
  // fixing after two lines of code after this quick calculation
  unsigned long data_delta;

  if(v->data > data)
   data_delta = (unsigned long)v->data - (unsigned long)data;
  else
   data_delta = (unsigned long)data - (unsigned long)v->data;

  // now continue with the two last lines handling the reallocation
  // TODO: lookup behaviour on realloc, do we need to free the old data space??
  /*free(v->data);
  free(v->iterators);*/
  v->data = data;
  v->iterators = iterators;

  /* setup NEW iterator pointers */
  for(i=v->capacity;i<n;i++) {

   /* (char*) is there because arithmetic cannot be used on void* pointers
      without warning, simply because the size of incerement/decrement
      ain't known to the compiler - however the char is according to the
      ANSI C standard ALWAYS exactly 1 byte */
   v->iterators[i] = (char*)v->data + (v->element_size * i);
  }

  /* then finally fix the OLD iterator pointers in such a way that the iterators
     are still intact and usable even if the iterators have been swap'd before */
  for(i=0;i<v->capacity;i++) {
   v->iterators[i] = (char*)v->iterators[i] + data_delta;
  }

  v->capacity = n;

  return 1;
 }

 return 1;
}

/* ELEMENT ACCESS */

/* return pointer to data at element index i */
CVECTOR_VOID* cvector_at(struct t_cvector *v, CVECTOR_UINT i) {
 return v->iterators[i];
}

/* return pointer to data at the FIRST element in vector */
CVECTOR_VOID* cvector_front(struct t_cvector *v) {
 return v->iterators[0];
}

/* return pointer to data at the LAST element in vector */
CVECTOR_VOID* cvector_back(struct t_cvector *v) {
 return v->iterators[v->elements - 1];
}

/* MODIFIERS */

/* allocate vector t of size s, then assign d the same content as s

   if an error would occur when a vector of the same size as s is
   allocated the data of d will remain and the function will return 0

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure */
CVECTOR_UINT cvector_assign(struct t_cvector *d, struct t_cvector *s) {


 return 1;
}

// TODO: fill, copy, range


/* push element to the end of the vector

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure */
CVECTOR_UINT cvector_push_back(struct t_cvector *v, CVECTOR_VOID *data) {
 if(!cvector_grow_capacity(v, 1))
  return 0;

 memcpy(v->iterators[v->elements], data, v->element_size);
 //memmove(v->iterators[v->elements], data, v->element_size);
 v->elements++;

 return 1;
}

/* pop element from the end of the vector

   returns 1 until there is no elements left to pop and thus returns 0 */
CVECTOR_UINT cvector_pop_back(struct t_cvector *v) {
 if(v->elements > 0) {
  v->elements--;

  return 1;
 }

 return 0;
}

/* insert data at index i in vector v, moving the element at index
   i to i+1 and so on for the rest of the vector

   (alternative route: redirect iterators using cvector_swap(...) instead of
                       really heavy memory moving)

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure */
CVECTOR_UINT cvector_insert(struct t_cvector *v, CVECTOR_UINT i, CVECTOR_VOID *data) {
 CVECTOR_UINT n;

 /* first add new data element to the vector by doing a cvector_push_back() */
 if(!cvector_push_back(v, data))
  return 0;

 /* simply scroll the iterators "to the right", making room for the newly added
    element at position i - where the newly added data element auto-magically
    will be placed =D */
 for(n=(v->elements-1);n>i;n--)
  cvector_swap(v, n, n-1);

 return 1;
}

/* erase element at index i in vector v

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure */
CVECTOR_UINT cvector_erase(struct t_cvector *v, CVECTOR_UINT i) {
 CVECTOR_UINT n;

 /* simply scroll the iterators to the left, which ultimately will place
    the to-be-erased element in the last element, which is then ignored by
    decrementing v->elements with a cvector_pop_back() */
 for(n=(i+1);n<v->elements;n++)
  cvector_swap(v, n, n-1);

 /* now make the number of elements -1 as we just erased an element */
 cvector_pop_back(v);

 return 1;
}

/* swap element iterators of index a and b in vector v

   returns 1 if there is no error and everything went successfull,
   in all other cases it will return 0 as an indication of failure */
CVECTOR_UINT cvector_swap(struct t_cvector *v, CVECTOR_UINT a, CVECTOR_UINT b) {
 CVECTOR_VOID *ptmp;

 if(a >= v->capacity || b >= v->capacity)
  return 0;

 ptmp = v->iterators[a];
 v->iterators[a] = v->iterators[b];
 v->iterators[b] = ptmp;

 return 1;
}

/* clear "contents" (ie. reset number of elements) of vector v, also resets all
   iterators but does NOT free any allocated data at all, leaving that for
   cvector_free(...) */
void cvector_clear(struct t_cvector *v) {
 CVECTOR_UINT i;

 v->elements = 0;

 for(i=0;i<v->capacity;i++)
  v->iterators[i] = (char*)v->data + (v->element_size * i);
}