SHARE
TWEET

cvector.c

a guest Oct 31st, 2019 108 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "cvector.h"
  5.  
  6. /* CVECTOR SPECIFIC */
  7.  
  8. /* allocates an empty & zeroed vector with room for capacity number of
  9.    elements that uses element_size bytes of RAM each, the iterators array
  10.    of iterator pointers will use sizeof(void*) * elements number of bytes,
  11.    the rest of the structure is either 12 or 6 bytes depending on compile-time
  12.    #define's =)
  13.    
  14.    if pvector equals 0 the function will allocate a new vector dynamically
  15.    instead of using a static OR already existing but free()'d vector pointed
  16.    to by pvector */
  17. struct t_cvector* cvector_alloc(struct t_cvector *pvector,
  18.                                 CVECTOR_UINT element_size, CVECTOR_UINT capacity) {
  19.  struct t_cvector *v = 0;
  20.  CVECTOR_UINT i;
  21.  
  22.  if(element_size == 0)
  23.   return 0;
  24.  
  25.  if(pvector == 0) {
  26.   v = (struct t_cvector*)malloc(sizeof(struct t_cvector));
  27.  
  28.   if(v == 0)
  29.    return 0;
  30.  
  31.   // this cvector was dynamically allocated
  32.   v->conf_bits = CVECTOR_DYN_ALLOC;
  33.  
  34.  } else {
  35.   v = pvector;
  36.  
  37.   // and this was not!
  38.   v->conf_bits = 0;
  39.  }
  40.  
  41.  v->element_size = element_size;
  42.  v->capacity = 0;
  43.  v->elements = 0;
  44.  v->data = 0;
  45.  v->iterators = 0;
  46.  
  47.  /* reserve RAM for capacity number of elements */
  48.  if(capacity < 1)
  49.   capacity = 2;
  50.  
  51.  // error-check when reserving memory
  52.  if(cvector_reserve(v, capacity) == 0) {
  53.   if(pvector == 0)
  54.    free(v);
  55.  
  56.   return 0;
  57.  }
  58.  
  59.  return v;
  60. }
  61.  
  62. /* free allocated capacity for vector, rendering all data and iterators
  63.    'lost', thus all pointers to specific elements WILL cause a CRASH (sooner or later) */
  64. void cvector_free(struct t_cvector *v) {
  65.  if(v->capacity > 0) {
  66.   free(v->data);
  67.   free(v->iterators);
  68.  
  69.   v->element_size = 0;
  70.   v->capacity = 0;
  71.   v->elements = 0;
  72.   v->data = 0;
  73.   v->iterators = 0;
  74.  
  75.   if(v->conf_bits & CVECTOR_DYN_ALLOC)
  76.    free(v);
  77.  }
  78. }
  79.  
  80. /* ITERATORS */
  81.  
  82. /* returns an iteratable pointer array that points to the crude data,
  83.    from the beginning of the vector */
  84. CVECTOR_VOID* cvector_begin(struct t_cvector *v) {
  85.  return (CVECTOR_VOID*)(v->iterators[0]);
  86. }
  87.  
  88. /* returns an iteratable pointer array that points to the crude data,
  89.    from the end of the vector */
  90. CVECTOR_VOID* cvector_end(struct t_cvector *v) {
  91.  return (CVECTOR_VOID*)(v->iterators[v->elements - 1]);
  92. }
  93.  
  94. /* CAPACITY */
  95.  
  96. /* ***hidden from public access - function prototype commented in header file***
  97.    
  98.    returns 1 if there is no error and everything went successfull,
  99.    in all other cases it will return 0 as an indication of failure
  100.    
  101.    this fuction will test if there is any need to grow capacity if n elements
  102.    were going to be added to the vector, if needed a reallocation and rise of
  103.    vector capacity will happen automatically */
  104. CVECTOR_UINT cvector_grow_capacity(struct t_cvector *v, CVECTOR_UINT n) {
  105.  CVECTOR_UINT reserve;
  106.  
  107.  /* grow capacity with "guesses", that is: if the vector grows bigger than
  108.     the capacity we need exactly as much space we need, but as we do not really
  109.     know how much more RAW we will need in this vector we can quite safely assume
  110.     that if the vector reaches capacity it needs at least capacity+(capacity/2)
  111.  */
  112.  
  113.  while((v->elements + n) > v->capacity) {
  114.   reserve = v->capacity + (v->capacity / 2);
  115.  
  116.   if(!cvector_reserve(v, reserve))
  117.    return 0;
  118.  }
  119.  
  120.  return 1;
  121. }
  122.  
  123. /* returns the number of elements stored in the vector */
  124. CVECTOR_UINT cvector_size(struct t_cvector *v) {
  125.  return v->elements;
  126. }
  127.  
  128. /* returns the (currently allocated) capacity of elements
  129.    to be stored in the vector */
  130. CVECTOR_UINT cvector_capacity(struct t_cvector *v) {
  131.  return v->capacity;
  132. }
  133.  
  134. /* returns 1 if vector is empty, otherwise 0 */
  135. CVECTOR_UINT cvector_empty(struct t_cvector *v) {
  136.  return (v->elements == 0 ? 1 : 0);
  137. }
  138.  
  139. /* resize number of elements in vector to n
  140.  
  141.    if n is greater than current number of elements the newly added elements will
  142.    get their contents copied from *data
  143.    
  144.    if n is greater than vector capacity (currently allocated storage) a
  145.    reallocation is required to happen - meaning all old pointers and iterators
  146.    will be invalid
  147.    
  148.    returns 1 if there is no error and everything went successfull,
  149.    in all other cases it will return 0 as an indication of failure  */
  150. CVECTOR_UINT cvector_resize(struct t_cvector *v, CVECTOR_UINT n, CVECTOR_VOID *data) {
  151.  CVECTOR_UINT i;
  152.  
  153.  if(n < v->elements) {
  154.   for(i=n;i<v->elements;i++) {
  155.    cvector_pop_back(v);
  156.   }
  157.  
  158.   return 1;
  159.  }
  160.  
  161.  /* if n is greater than the capacity (currently allocated storage)
  162.     a reallocation is needed */
  163.  if(!cvector_reserve(v, n))
  164.   return 0;
  165.  
  166.  /* if n is greater than current number of elements the newly added elements will
  167.     get their contents copied from *data */
  168.  if(n > v->elements) {
  169.   for(i=v->elements;i<n;i++) {
  170.    if(data)
  171.     memmove(v->iterators[i], data, v->element_size);
  172.   }
  173.  }
  174.  
  175.  v->elements = n;
  176.  
  177.  return 1;
  178. }
  179.  
  180. /* request that n number of elements should fit in the vector,
  181.    if n is greater than the current capacity a reallocation is assured
  182.    and therefore all old pointers to individual elements in vector v
  183.    are rendered completely useless
  184.    
  185.    returns 1 if there is no error and everything went successfull,
  186.    in all other cases it will return 0 as an indication of failure */
  187. CVECTOR_UINT cvector_reserve(struct t_cvector *v, CVECTOR_UINT n) {
  188.  if(n > v->capacity) {
  189.   CVECTOR_UINT i;
  190.   CVECTOR_VOID *data;
  191.   CVECTOR_VOID **iterators;
  192.  
  193.   data = (CVECTOR_VOID*)realloc(v->data, n * v->element_size);
  194.  
  195.   if(data == 0) {
  196.    return 0;
  197.   }
  198.  
  199.   iterators = (CVECTOR_VOID**)realloc(v->iterators, n * sizeof(CVECTOR_VOID*));
  200.  
  201.   if(iterators == 0) {
  202.    free(data);
  203.    return 0;
  204.   }
  205.  
  206.   // calculate delta between old and new address of data locations for iterator
  207.   // fixing after two lines of code after this quick calculation
  208.   unsigned long data_delta;
  209.  
  210.   if(v->data > data)
  211.    data_delta = (unsigned long)v->data - (unsigned long)data;
  212.   else
  213.    data_delta = (unsigned long)data - (unsigned long)v->data;
  214.  
  215.   // now continue with the two last lines handling the reallocation
  216.   // TODO: lookup behaviour on realloc, do we need to free the old data space??
  217.   /*free(v->data);
  218.   free(v->iterators);*/
  219.   v->data = data;
  220.   v->iterators = iterators;
  221.  
  222.   /* setup NEW iterator pointers */
  223.   for(i=v->capacity;i<n;i++) {
  224.    
  225.    /* (char*) is there because arithmetic cannot be used on void* pointers
  226.       without warning, simply because the size of incerement/decrement
  227.       ain't known to the compiler - however the char is according to the
  228.       ANSI C standard ALWAYS exactly 1 byte */
  229.    v->iterators[i] = (char*)v->data + (v->element_size * i);
  230.   }
  231.  
  232.   /* then finally fix the OLD iterator pointers in such a way that the iterators
  233.      are still intact and usable even if the iterators have been swap'd before */
  234.   for(i=0;i<v->capacity;i++) {
  235.    v->iterators[i] = (char*)v->iterators[i] + data_delta;
  236.   }
  237.  
  238.   v->capacity = n;
  239.  
  240.   return 1;
  241.  }
  242.  
  243.  return 1;
  244. }
  245.  
  246. /* ELEMENT ACCESS */
  247.  
  248. /* return pointer to data at element index i */
  249. CVECTOR_VOID* cvector_at(struct t_cvector *v, CVECTOR_UINT i) {
  250.  return v->iterators[i];
  251. }
  252.  
  253. /* return pointer to data at the FIRST element in vector */
  254. CVECTOR_VOID* cvector_front(struct t_cvector *v) {
  255.  return v->iterators[0];
  256. }
  257.  
  258. /* return pointer to data at the LAST element in vector */
  259. CVECTOR_VOID* cvector_back(struct t_cvector *v) {
  260.  return v->iterators[v->elements - 1];
  261. }
  262.  
  263. /* MODIFIERS */
  264.  
  265. /* allocate vector t of size s, then assign d the same content as s
  266.    
  267.    if an error would occur when a vector of the same size as s is
  268.    allocated the data of d will remain and the function will return 0
  269.    
  270.    returns 1 if there is no error and everything went successfull,
  271.    in all other cases it will return 0 as an indication of failure */
  272. CVECTOR_UINT cvector_assign(struct t_cvector *d, struct t_cvector *s) {
  273.  
  274.  
  275.  return 1;
  276. }
  277.  
  278. // TODO: fill, copy, range
  279.  
  280.  
  281. /* push element to the end of the vector
  282.    
  283.    returns 1 if there is no error and everything went successfull,
  284.    in all other cases it will return 0 as an indication of failure */
  285. CVECTOR_UINT cvector_push_back(struct t_cvector *v, CVECTOR_VOID *data) {
  286.  if(!cvector_grow_capacity(v, 1))
  287.   return 0;
  288.  
  289.  memcpy(v->iterators[v->elements], data, v->element_size);
  290.  //memmove(v->iterators[v->elements], data, v->element_size);
  291.  v->elements++;
  292.  
  293.  return 1;
  294. }
  295.  
  296. /* pop element from the end of the vector
  297.  
  298.    returns 1 until there is no elements left to pop and thus returns 0 */
  299. CVECTOR_UINT cvector_pop_back(struct t_cvector *v) {
  300.  if(v->elements > 0) {
  301.   v->elements--;
  302.  
  303.   return 1;
  304.  }
  305.  
  306.  return 0;
  307. }
  308.  
  309. /* insert data at index i in vector v, moving the element at index
  310.    i to i+1 and so on for the rest of the vector
  311.    
  312.    (alternative route: redirect iterators using cvector_swap(...) instead of
  313.                        really heavy memory moving)
  314.    
  315.    returns 1 if there is no error and everything went successfull,
  316.    in all other cases it will return 0 as an indication of failure */
  317. CVECTOR_UINT cvector_insert(struct t_cvector *v, CVECTOR_UINT i, CVECTOR_VOID *data) {
  318.  CVECTOR_UINT n;
  319.  
  320.  /* first add new data element to the vector by doing a cvector_push_back() */
  321.  if(!cvector_push_back(v, data))
  322.   return 0;
  323.  
  324.  /* simply scroll the iterators "to the right", making room for the newly added
  325.     element at position i - where the newly added data element auto-magically
  326.     will be placed =D */
  327.  for(n=(v->elements-1);n>i;n--)
  328.   cvector_swap(v, n, n-1);
  329.  
  330.  return 1;
  331. }
  332.  
  333. /* erase element at index i in vector v
  334.    
  335.    returns 1 if there is no error and everything went successfull,
  336.    in all other cases it will return 0 as an indication of failure */
  337. CVECTOR_UINT cvector_erase(struct t_cvector *v, CVECTOR_UINT i) {
  338.  CVECTOR_UINT n;
  339.  
  340.  /* simply scroll the iterators to the left, which ultimately will place
  341.     the to-be-erased element in the last element, which is then ignored by
  342.     decrementing v->elements with a cvector_pop_back() */
  343.  for(n=(i+1);n<v->elements;n++)
  344.   cvector_swap(v, n, n-1);
  345.  
  346.  /* now make the number of elements -1 as we just erased an element */
  347.  cvector_pop_back(v);
  348.  
  349.  return 1;
  350. }
  351.  
  352. /* swap element iterators of index a and b in vector v
  353.    
  354.    returns 1 if there is no error and everything went successfull,
  355.    in all other cases it will return 0 as an indication of failure */
  356. CVECTOR_UINT cvector_swap(struct t_cvector *v, CVECTOR_UINT a, CVECTOR_UINT b) {
  357.  CVECTOR_VOID *ptmp;
  358.  
  359.  if(a >= v->capacity || b >= v->capacity)
  360.   return 0;
  361.  
  362.  ptmp = v->iterators[a];
  363.  v->iterators[a] = v->iterators[b];
  364.  v->iterators[b] = ptmp;
  365.  
  366.  return 1;
  367. }
  368.  
  369. /* clear "contents" (ie. reset number of elements) of vector v, also resets all
  370.    iterators but does NOT free any allocated data at all, leaving that for
  371.    cvector_free(...) */
  372. void cvector_clear(struct t_cvector *v) {
  373.  CVECTOR_UINT i;
  374.  
  375.  v->elements = 0;
  376.  
  377.  for(i=0;i<v->capacity;i++)
  378.   v->iterators[i] = (char*)v->data + (v->element_size * i);
  379. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top