Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A good C equivalent of STL vector?

Tags:

c

c89

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?

like image 495
Christoffer Avatar asked Aug 11 '10 08:08

Christoffer


2 Answers

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.

like image 59
lunaryorn Avatar answered Oct 06 '22 18:10

lunaryorn


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;
}
like image 27
user411313 Avatar answered Oct 06 '22 17:10

user411313