2
\$\begingroup\$

I tried to make a generic, header-only vector thingy I can use in other projects in the future. I omitted documentation comments because it's already quite long.

#ifndef __VECTOR__
#define __VECTOR__

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

static int VECTOR_DEFAULT_SIZE = 1;

typedef struct vector {
  void** data;
  int max;
  int size;
} vector;

static int vector_size(vector* v) {
  return v->size;
}

static int vector_capacity(vector* v) {
  return v->max;
}

static void* vector_get(vector* v, int i) {
  if (i < 0 || i >= vector_capacity(v))
    return NULL;
  return v->data[i];
}

static void vector_set(vector* v, int i, void* e) {
  if (i < 0 || i >= vector_capacity(v))
    return;

  v->data[i] = e;
}

static vector* vector_create_sized(int size) {
  vector* v = malloc(sizeof(vector));
  v->data = malloc(sizeof(void*) * size);
  v->max = size;
  v->size = 0;

  return v;
};

static vector* vector_create() {
  return vector_create_sized(VECTOR_DEFAULT_SIZE);
};

static void vector_clear(vector* v) {
  for(int i = 0; i < v->max; i++) {
    vector_set(v, i, NULL);
  }
  v->size = 0;
}

static bool vector_is_empty(vector* v) {
  return vector_size(v) == 0;
}

static void vector_resize(vector* v, int size) {
  if (size > vector_capacity(v)) {
    void** new = malloc(sizeof(void*) * size);

    for(int i = 0; i < vector_capacity(v); i++) {
      new[i] = vector_get(v, i);
    }

    free(v->data);
    v->data = new;
    v->max = size;
  }
}

static void vector_insert(vector* v, int i, void* e) {
  if (i < 0 || i >= vector_capacity(v))
    return;

  for(int j = vector_capacity(v) - 2; j >= i; j--) {
    vector_set(v, j + 1, vector_get(v, j));
  }

  vector_set(v, i, e);

  v->size++;

  if (vector_size(v) == vector_capacity(v))
    vector_resize(v, vector_capacity(v) * 2);
}

static void vector_unshift(vector* v, void* e) {
  vector_insert(v, 0, e);
}

static void vector_push(vector* v, void* e) {
  vector_insert(v, vector_size(v), e);
}

static void vector_foreach(vector* v, void (*func)(int, const void*)) {
  if (vector_is_empty(v))
    return;

  for(int i = 0; i < vector_size(v); i++) {
    func(i, v->data[i]);
  }
}

static vector* vector_map(vector* v, void* (*func)(int, const void*)) {
  vector* w = vector_create_sized(vector_capacity(v));

  for(int i = 0; i < vector_size(v); i++) {
    void* e = vector_get(v, i);
    vector_push(w, func(i, e));
  }

  return w;
}

static vector* vector_filter(vector* v, bool (*func)(int, const void*)) {
  vector* w = vector_create_sized(VECTOR_DEFAULT_SIZE);

  for(int i = 0; i < vector_size(v); i++) {
    void* e = vector_get(v, i);
    if (func(i, e))
      vector_push(w, e);
  }

  return w;
}

static bool vector_any(vector* v, bool (*func)(int, const void*)) {
  for(int i = 0; i < vector_size(v); i++) {
    void* e = vector_get(v, i);
    if (func(i, e))
      return true;
  }

  return false;
}

static bool vector_all(vector* v, bool (*func)(int, const void*)) {
  for(int i = 0; i < vector_size(v); i++) {
    void* e = vector_get(v, i);
    if (!func(i, e))
      return false;
  }

  return true;
}

static vector* vector_copy(vector* v) {
  vector* w = vector_create_sized(vector_capacity(v));

  for(int i = 0; i < vector_size(v); i++) {
    void* e = vector_get(v, i);
    vector_push(w, e);
  }

  return w;
}

static void* vector_remove(vector* v, int i) {
  if (i < 0 || i >= vector_capacity(v) || vector_is_empty(v))
    return NULL;

  void* tmp = vector_get(v, i);

  for(int j = i; j < vector_size(v); j++) {
    vector_set(v, j, vector_get(v, j + 1));
  }

  v->size--;

  return tmp;
}

static void vector_erase(vector* v, bool (*func)(int, const void*)) {
  for(int i = vector_size(v) - 1; i >= 0; i--) {
    void* e = vector_get(v, i);
    if (func(i, e))
      vector_remove(v, i);
  }
}

static void* vector_pop(vector* v) {
  return vector_remove(v, vector_size(v) - 1);
}

static void* vector_shift(vector* v) {
  return vector_remove(v, 0);
}

static void vector_swap(vector* v, int i, int j) {
  if (i < 0 || i >= vector_size(v) || j < 0 || j >= vector_size(v))
    return;

  void* tmp = vector_get(v, i);
  vector_set(v, i, vector_get(v, j));
  vector_set(v, j, tmp);
}

static void vector_sort(vector* v, int (*cmp)(const void*, const void*)) {
  for (int i = 0; i < vector_size(v); i++) {
    int j = i;
    while (j > 0 && cmp(vector_get(v, j - 1), vector_get(v, j)) > 0) {
      vector_swap(v, j, j - 1);
      j--;
    }
  }
}

static void vector_reverse(vector* v) {
  int i = vector_size(v) - 1;
  int j = 0;

  while(i > j) {
    vector_swap(v, i, j);
    i--;
    j++;
  }
}

static vector* vector_concat(vector* a, vector* b) {
  vector* c = vector_create_sized(vector_size(a) + vector_size(b));

  for(int i = 0; i < vector_size(a); i++) {
    vector_push(c, vector_get(a, i));
  }
  for(int i = 0; i < vector_size(b); i++) {
    vector_push(c, vector_get(b, i));
  }

  return c;
}

static void vector_debug(vector* v) {
  printf("\n----------\nVector %i/%i\n", vector_size(v), vector_capacity(v));
  for(int i = 0; i < vector_size(v); i++) {
    printf("%i %p\n", i, vector_get(v, i));
  }

  for(int i = vector_size(v); i < vector_capacity(v); i++) {
    printf("%i NULL\n", i);
  }
  printf("----------\n");
}

static void vector_free(vector* v) {
  free(v->data);
  free(v);
};

#endif

Also here's a short example of usage, generating 2 vectors of random ints, concatenating, sorting and then reversing them in a third list:

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

void free_int(int x, const void* p) {
  int* i = (int*)p;
  free(i);
}

void print_int(int x, const void* p) {
  int* i = (int*)p;
  int j = *i;
  printf("%i ", j);
}

int sort(const void* a, const void* b) {
  return *((int*)a) - *((int*)b);
}

int main(void) {
  srand(time(NULL));

  vector* a = vector_create();
  vector* b = vector_create();

  for(int i = 0; i < 10; i++) {
    int* n = malloc(sizeof(int));
    *n = rand() % 50;
    vector_push(a, n);
  }

  for(int i = 0; i < 10; i++) {
    int* n = malloc(sizeof(int));
    *n = rand() % 50;
    vector_push(b, n);
  }

  printf("A: ");
  vector_foreach(a, print_int);
  printf("\nB: ");
  vector_foreach(b, print_int);

  vector* c = vector_concat(a, b);
  vector_sort(c, sort);
  vector_reverse(c);

  printf("\n\nA concat B sorted descending:\n");
  vector_foreach(c, print_int);

  vector_foreach(c, free_int);
  vector_free(a);
  vector_free(b);
  vector_free(c);

  return 0;
};
\$\endgroup\$
1
  • \$\begingroup\$ Comment on vector_resize: it's probably easier and faster to use realloc. \$\endgroup\$ Commented Jan 11, 2019 at 1:33

1 Answer 1

Reset to default
3
\$\begingroup\$

Why one way re-sizing?

vector_resize() only allows the vector to grow.

vector_insert() growth oddity

Code can grow the vector size indefinitely if done by inserting at the end, yet quietly fails if the insert is far beyond the end.

I'd expect the function to not grow at all or allow an insertion anywhere.

Sort can overflow

In sort(), rather than return a - b (with its UB overflow), use the idiomatic, not overflow possible: return (a > b) - (a < b).

Avoid C++ keywords

For potential portability as well as clarity, avoid new as an object in C code.

Code looks wrong.

void** new = malloc(sizeof(void*) * size);

Allocate to the size of the de-referenced object

Avoid size errors. Do not allocate to the size of the type. The below is easier to code right, review and maintain.

// void** new = malloc(sizeof(void*) * size);
void** nu = malloc(sizeof *nu * size);

Allow state

With vector_any() pass in a state argument and return int for additional flexibility.

static int vector_any_alt(vector* v, void *state, int (*func)(state, int, const void*))  {
  for(int i = 0; i < vector_size(v); i++) {
    int retval = func(state, i, v->data[i]);
    if (retval) {
      return retval;
    }
  }
  return 0;
}

Minor: int indexing vs. size_t

I would have used size_t indexing rather than int, yet I suspect OP's desires int.

Naming

Why call use .max instead of .capacity? or
Why call use vector_capacity() instead of vector_max().

Use const

Various functions like vector_is_empty(vector* v) convey meaning better, allow for expanded use and sometime optimize better with const.

// vector_is_empty(vector* v)
vector_is_empty(const vector* v)

Use (void)

With (), no parameters checking occurs allowing vector_create(1,2,3) to not generate an error.

// static vector* vector_create()
static vector* vector_create(void)

Why clear to capacity?

vector_clear() clears all v->max rather than v>size.

Why upper case object name?

static int VECTOR_DEFAULT_SIZE = 1; will certainly throw off users. Consider static int vector_default_size = 1;

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.