A good C equivalent of STL vector?

Question

I've noticed that at several places in our code base we use dynamically expanding arrays, i.e. a base array coupled with an element counter and a "max elements" value.

What I want to do is replace these with a common data structure and utility functions, for the usual object-oriented reasons. The array elements can be either basic data types or structs, I need fast random access to the elements, and preferably a type-safe implementation.

So, basically, what I would like to use is an STL vector, but the code base is restricted to C89 so I have to come up with something else :-)

I gave it some thought and whipped up this initial draft, just to show what I'm aiming at:

/* Type-safe dynamic list in C89 */

#define list_declare(type) typedef struct _##type##_list_t { type * base_array; size_t elements; size_t max_size; } type##_list_t
#define list(type) type##_list_t
#define list_new(type, initial_size) { calloc(initial_size, sizeof(type)), 0, initial_size }
#define list_free(list) free(list.base_array)
#define list_set(list, place, element) if ( list.elements < list.max_size ) { list.base_array[place] = element; } else { /* Array index out of bounds */ }
#define list_add(list, element) if ( list.elements < list.max_size ) { list.base_array[list.elements++] = element; } else { /* Expand array then add */ }
#define list_get(list, n) list.base_array[n]

/* Sample usage: */

list_declare(int);

int main(void)
{
    list(int) integers = list_new(int, 10);
    printf("list[0] = %d\n", list_get(integers, 0));
    list_add(integers, 4);
    printf("list[0] = %d\n", list_get(integers, 0));
    list_set(integers, 0, 3);
    printf("list[0] = %d\n", list_get(integers, 0));
    list_free(integers);

    return EXIT_SUCCESS;
}

...however, there must be someone else who has done this before. I'm aware of the FreeBSD sys/queue.h implementation of a similar concept for some different queues, but I can't find anything like that for arrays.

Is anyone here any wiser?

Answer 1

glib provides an GArray type, which implements a dynamically growing array. If you can use external 3rd party libraries, glib is almost always a good choice as "standard" library for C. It provides types for all basic data structures, for unicode strings, for date and time values, and so on.

Answer 2

There is sglib, which implements various lists,hashmaps and rbtrees in a generic fashion (i.e. by specializing over a type). There is also a fast sorting function for arrays:

• http://sglib.sourceforge.net/

Answer 3

here a simple vector-replacement, its ONE function for all, its strictly C89 and threadsafe; libs are too difficult for me, i use my own; no performance, but easy to use

/* owner-structs too */
typedef struct {
  char name[20],city[20];
  int salary;
} My,*Myp;

typedef char Str80[80];

/* add here your type with its size */
typedef enum {SPTR,INT=sizeof(int),DOUBLE=sizeof(double),S80=sizeof(Str80),MY=sizeof(My)} TSizes;

typedef enum {ADD,LOOP,COUNT,FREE,GETAT,GET,REMOVEAT,REMOVE} Ops;

void *dynarray(char ***root,TSizes ts,Ops op,void *in,void *out)
{
  size_t d=0,s=in?ts?ts:strlen((char*)in)+1:0;
  char **r=*root;
  while( r && *r++ ) ++d;
  switch(op) {
  case ADD:   if( !*root ) *root=calloc(1,sizeof r);
              *root=realloc(*root,(d+2)*sizeof r);
              memmove((*root)+1,*root,(d+1)*sizeof r);
              memcpy(**root=malloc(s),in,s);
              break;
  case LOOP:  while( d-- ) ((void (*)(char*))in)((*root)[d]); break;
  case COUNT: return *(int*)out=d,out;
  case FREE:  if(r) {
                ++d; while( d-- ) realloc((*root)[d],0);
                free(*root);*root=0;
              } break;
  case GETAT: { size_t i=*(size_t*)in;
                if(r && i<=--d)
                  return (*root)[d-i];
              } break;
  case GET:   { int i=-1;
                while( ++i,d-- )
                if( !(ts?memcmp:strncmp)(in,(*root)[d],s) )
                  return *(int*)out=i,out;
                return *(int*)out=-1,out;
              }
  case REMOVEAT: { size_t i=*(size_t*)in;
                   if(r && i<=--d) {
                     free((*root)[d-i]);
                     memmove(&(*root)[d-i],&(*root)[d-i+1],(d-i+1)*sizeof r);
                     return in;
                   }
                 } break;
  case REMOVE: while( *(int*)dynarray(root,ts,GET,in,&d)>=0 )
                 dynarray(root,ts,REMOVEAT,&d,0);
  }
  return 0;
}

void outmy(Myp s)
{
  printf("\n%s,%s,%d",s->name,s->city,s->salary);
}

main()
{
  My    z[]={{"Buffet","Omaha",INT_MAX},{"Jobs","Palo Alto",1},{"Madoff","NYC",INT_MIN}};
  Str80 y[]={ "123","456","7890" };
  char **ptr=0;
  int x=1;

  /* precondition for first use: ptr==NULL */
  dynarray(&ptr,SPTR,ADD,"test1.txt",0);
  dynarray(&ptr,SPTR,ADD,"test2.txt",0);
  dynarray(&ptr,SPTR,ADD,"t3.txt",0);

  dynarray(&ptr,SPTR,REMOVEAT,&x,0); /* remove at index/key ==1 */
  dynarray(&ptr,SPTR,REMOVE,"test1.txt",0);

  dynarray(&ptr,SPTR,GET,"t3.txt",&x);
  dynarray(&ptr,SPTR,LOOP,puts,0);

  /* another option for enumerating */
  dynarray(&ptr,SPTR,COUNT,0,&x);
    while( x-- )
      puts(ptr[x]);
  dynarray(&ptr,SPTR,FREE,0,0); /* frees all mallocs and set ptr to NULL */

  /* start for another (user)type */
  dynarray(&ptr,S80,ADD,y[0],0);
  dynarray(&ptr,S80,ADD,y[1],0);
  dynarray(&ptr,S80,ADD,y[2],0);
  dynarray(&ptr,S80,ADD,y[0],0);
  dynarray(&ptr,S80,LOOP,puts,0);
  dynarray(&ptr,S80,FREE,0,0); /* frees all mallocs and set ptr to NULL */

  /* start for another (user)struct-type */
  dynarray(&ptr,MY,ADD,&z[0],0);
  dynarray(&ptr,MY,ADD,&z[1],0);
  dynarray(&ptr,MY,ADD,&z[2],0);
  dynarray(&ptr,MY,ADD,&z[0],0);
  dynarray(&ptr,MY,LOOP,outmy,0);
  dynarray(&ptr,MY,FREE,0,0);

  return 0;
}