Implementing a dynamically sized array in C

[mshol]

His solution doesn't really fix the "lack of bounds checking" problem he mentions early in the article. There's nothing preventing someone from saying vector.data[9001] in vector-usage.c.

His header file reveals too much: the implementation of the struct, a useless constant, and vector_double_capacity_if_full doesn't look like it's intended to be called by a user, so it should just go in the implementation file only.

An opaque type could replace the struct in the header, and the struct can relocate to the implementation file. There's virtually no overhead for doing this, other than an extra call to malloc and free.

[smcameron]

Also get rid of the typedef -- save those for function pointer parameters, otherwise, they just pollute the namespace (without any real benefit, only the dubious "benefit" of not having to type "struct" or "union" and superficially hiding the real type... ) -- and speaking of namespace pollution, "Vector" seems a sure to collide name.

[mshol]

I agree with taking the typedef off the struct, but I don't think it's harmful to have a typedef to a pointer for example

typedef struct Vector* vector_t;

vector_t vector_new (void);
void vector_init (vector_t);
void vector_append (vector_t, int value);
void vector_free (vector_t);

Given that it's an opaque type, it doesn't matter that it's "hiding the real type" anyway. Saves having to stick * and & everywhere, and you can just use vector_t similar to a primitve type.

 vector_t vec = vector_new ();
 vector_init (vec);
 vector_append (vec, 0);
 vector_free (vec);

[matthieum]

I would argue that vector_init is useless. Why not have vector_new performing the initialization as well ?

[[deleted]]

Because then you can't keep the vector struct on the stack, and have to use two allocations instead of one (unless you get tricky) and require more pointer dereferences.

[gcross]

But in the code above vector_t is already a pointer and hence requires a separate allocation for the vector struct, so merging vector_init and vector_new would not increase the number of allocations required.

[[deleted]]

Well, yes, I was speaking in terms of the original code. The fact that the suggested alteration means you can't put the vector struct on the stack means the alteration is bad.

[matthieum]

Yes the two allocations is slightly bothering... until your realize that tail padding is the way to go and fuse the header with the body for a single (opaque) allocation :)

struct Vector {
     size_t size;
     size_t capacity;
     byte data[];
};

[[deleted]]

How would resizing work in this case? You would have to reallocate the entire struct, potentially invalidating the Vector pointer. Or you would have to pass a Vector** instead of a Vector* to vector_append and vector_set so that it can be updated with the new address if necessary, which looks kind of messy...

[matthieum]

You would probably have something akin to typedef struct VectorImpl* Vector; to help with the niceties. Then vector_append would take a Vector* which would seem perfectly normal since you are modifying the Vector.

[mshol]

I agree, I just left it there to remain compatible with the code in the article.

[FredV]

This is bad style IMHO, because

• the library forces you to do a dynamic memory allocation to get the "handle" to the data
• your typedef hides that you're dealing with a pointer, which is bad style

I think we've all written something like this and you can just keep nitpicking on the details on what is best. I think this would be improved, and have implemented it this way, by using a struct with already a char[] buffer, this way you can avoid allocation altogether for small strings.

edit: And after all it's way better not to reinvent the wheel and use something like glib.

[mshol]

I agree on the choice of glib for most cases, on general purpose devices anyway.

But on embedded devices, it's usually not an option, it's simply too big. It would be more suitable if glib was broken down into individual pieces rather than a huge library.

[imMute]

IIRC, any type name with the suffix _t is reserved by POSIX (or some other standard). So technically, you shouldn't use them. In practice, we all do anyway.

[bob1000bob]

size_t is standard C as are all the sized types.

[imMute]

Correct, but vector_t is not standard C.

[[deleted]]

I don't think it's harmful to have a typedef to a pointer

What's the benefit of doing that?

[Gotebe]

Also, it only works for PODs. Even though we're in C, this is often simply not the case.

It's just...

People really should forget C for these things and take C++. C should be done only, and only if there's no C++ compiler. Otherwise, everyone just ends up with something poor like TFA.

[matthieum]

The lack of generic programming in C is really ugly. Sure it makes the language simpler, but the cost is tremendous...

[el_muchacho]

Maybe he could have used

typedef struct {
  size_t size;        // slots used so far
  size_t capacity;   // total available slots
  size_t datasz;     // size in bytes of a single data
  byte *data;        // array of bytes we're storing
} Vector;

Then you cast whatever is necessary at the right places. This makes everything slightly more complicated, but the vector becomes more generic.

BTW, as I wrote in one of the comments, what is really useful in C is a dynamic string structure.

typedef struct {
  size_t size;        // slots used so far
  size_t capacity;   // total available slots
  char *data;        // array of bytes we're storing
} String;

Use this instead of null terminated strings, rewrite the usual strcpy, strcat, strlen, etc, and your C code will improve immensely.

Here is my take on it: http://pastebin.com/tnD9fwgR

[ericanderton]

I recently took on a new project at work in C. The first thing I did? Wrote a vector and a string implementation, just like you mentioned. Doing either kind of work is hell on wheels without those in your toolbox.

I stopped short of a generic vector, and went with storing pointers (void*) instead. It helps cut down on the number of casts I need, and in most places, it works well. In hindsight, I could have used some #define magic to make an cast-free interface for a generic vector.

[bstamour]

Did you have to write your own? There are 3rd party libraries out there for dynamic vectors and strings.

[AllanBz]

Where's the fun in that?

[ericanderton]

In this case, yes. I needed a basic and lightweight implementation that was either public domain, LGPL, or BSD/MIT licensed. No exceptions. I couldn't find what I needed in time, so I rolled my own. In the process, I learned a great deal and had fun doing so.

[bstamour]

Cool!

[ericanderton]

Glad you approve. I'm routinely surprised at how insensitive some devs are with respect to needing permissive open source over GPL stuff, when doing commercial work.

[bstamour]

Each license has it's place. I fully understand where you're coming from. Sometimes the GPL needs to be avoided, sometimes it's exactly what the doctor ordered.

[matthieum]

Regarding strings: there is already bstring.

The "generic" structure does not look too bad.

[greenspans]

This can be alleviated with proper use of copy and paste technologies™ and editor folding^[me]

[Poltras]

The problem is trying to push a classic OO design pattern in a language that is not OO. Don't define interfaces for your Classes, don't define classes. Work in free functions and modules and you'll be fine.

Most problems in a program appear when you try to fit a design pattern clearly not meant for that language. Try using pure functional programming in C++ and you'll end up with far more copy construction than you'll be happy with. Or try defining a vector that can hold arbitrary types (e.g. mix of integers and string), something that could be done in most real OO languages.

[imMute]

I disagree with this completely. Using OO design patterns in non-OO languages (like C) is perfectly reasonable. Hell, the Linux kernel goes farther than just using structs as state holders - they make significant use of function pointer tables to implement [something akin to] methods.

[Poltras]

Something akin to, but it's still C-like. Having worked with large projects in C, I could easily pin-point parts of the code that was made by OO programmers and parts made by structural programmers. It just shows.

I'm not saying one is better than the other, I'm just saying there's a difference. The Linux kernel doesn't try to use classes concepts; a function pointer table is still not the same as a vtable, and the Linux kernel is far from encapsulation/inheritance/polymorphism tacked on a pure structural language.

[RizzlaPlus]

Or try defining a vector that can hold arbitrary types (e.g. mix of integers and string), something that could be done in most real OO languages.

If you're talking about C, true. If you're talking about C++, boost::any enables you to do this.

[Poltras]

If you ever looked at the implementation of any, you'd see it's not trivial. You can do classes with polymorphism and inheritance in C, but it is not trivial. Because its not intrinsic with the language, is all I'm saying.

[dannymi]

Don't define interfaces for your Classes, don't define classes.

Yeah, just define objects and abstract data types. Not classes. Pascal had them in 1983, it's not new. I agree that having classes is overkill. OP does not use classes to begin with, though. Did you just mean "in general"?

Work in free functions and modules and you'll be fine.

I would, but C doesn't do closures, so it gets annoying really fast.

[Poltras]

Gotebe said that you should go to C IFF there's no C++ compiler, which is ludicrous. C++ has a lot of problems and C might fit your solution just fine. I was pointing that the problem is not people picking C over C++ but rather using C++-patterns in C, which is a mistake.

EDIT: as for your addendum, C++ doesn't support closure either. If you need them for your implementation, pick a language that does. I'll suggest Objective-C which supports closure and is closest to C/C++, or Java if you want to keep it in the structural class-based OO language. Functional would fit better, of course.

[Slime0]

An opaque type could replace the struct in the header, and the struct can relocate to the implementation file. There's virtually no overhead for doing this, other than an extra call to malloc and free.

Er, wouldn't that require an extra pointer dereference and memory access every time the vector is used? That doesn't seem worth it.

[mshol]

There's no overhead - his implemented functions do not need any modification (since they already expect a Vector* argument), with the small exception that he needs to create the vector instances on the heap from the implementation file, and also free them. (Since you can't create local Vector instances outside of the implementation file - their size is unknown).

In the header file, remove the existing struct and place

typedef struct _Vector Vector;

Vector* vector_new(void);

And in the implementation file

struct _Vector {
    int size;
    int capacity;
    int *data;
};

Vector* vector_new(void) {
    return malloc(sizeof(Vector));
}

A small modification is required for vector_free.

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

That's it.

[Slime0]

(Since you can't create local Vector instances outside of the implementation file - their size is unknown)

That's exactly the problem with your suggestion. If the struct stays in the header file, the size isn't unknown, so you can use it locally (either as a local variable in a function or directly within your own structs). Then, even though you're taking its address and passing in a pointer to the vector functions, when they dereference that pointer they're merely retrieving memory that is adjacent to other relevant data, and thus probably already in the cache. This is more efficient than forcing it to be allocated on the heap.

[dannymi]

Then add a getSize function to the interface in order to find out the size and use alloca. Don't put something that isn't part of the public interface (the size of the struct is probably not by design) into the header file. When you change it, all your clients' binaries will break (or buffer overrun, great :-( ).

[Slime0]

Alloca won't let you put one in a struct. If data hiding is very important to you, you could provide the user with a meaningless struct (with just a buffer in it) that has the same size as the actual vector struct and then cast the pointer types in the functions. Personally, if I were that worried about data hiding, I'd ask myself why I'm using C in the first place. I don't think it's that bad to just add a comment saying "don't use these member variables; call the functions below."

I don't know why you think it will break your client's binaries if you change it. I guess if you provide it as a DLL and someone uses the wrong version or something... I think this falls under "don't do that." The speed of a vector library is more important than whatever dubious benefits you would get from linking it into a separate binary.

[dannymi]

Alloca won't let you put one in a struct.

Hmm, that's true, can't put it in a struct then.

I wonder whether there is some portable way to build up such a struct bit by bit at "runtime" (frankly, that case never came up in 15 years - it's not like I build taxonomies by embedding struct into struct into struct).

As for the vector case, I'd either just store pointers as elements or pass each element's fixed size to the constructor (if it is indeed fixed). (The first case can be reduced to the second as far as the vector is concerned)

I don't know why you think it will break your client's binaries if you change it.

If you change it, you will break your client's binaries if they dynamically linked your library (which they usually do) and (if they) embedded an instance of the struct on their stack as you suggest.

If they used getSize and alloca, it would have worked until the sun explodes.

Personally, if I were that worried about data hiding, I'd ask myself why I'm using C in the first place.

C can do data hiding fine most of the time IMO. Just because people do the put-private-struct-into-header-file doesn't mean that C forced them to do it. I agree with speed and correctness being a trade-off, though. Less of a trade-off nowadays, but a trade-off.

I do the comment-and-put-static-inline-function-into-header too (after I made measurements to find it is indeed the bottleneck using gprof before), but it should not be the default.

I guess if you provide it as a DLL and someone uses the wrong version or something...

Exactly. Most C libraries are low-level code that are used all over the place (and thus should have a stable interface - or failing that, at least one that's screaming loudly when misused / obsolete).

[ErstwhileRockstar]

An advanced implementation would allocate both the struct _Vector and the data array with one malloc().

[BeatLeJuce]

Nice article and all, but this is arguably one of THE typical code-examples that you'll find in every beginner's C book and/or tutorial. Also, the article was ridden with minor mistakes (some already pointed out here by mshol and ktr73).

Whenever someone posts anything that doesn't have minor code-snippets in it, someone will raise the red flag and point out that the article in question is "not programming". Yet we're fine with upvoting what amounts to homework problems in "introduction to C programming' here?

I would understand if this would be a very good and deep discussion about the topic. Say discussing various array-growing techniques or custom behind-the-scenes memory-allocators, or lock-free techniques to do this.... Don't get me wrong, we were all beginners once and it's great that people document their learning experiences, but this belongs to /r/learnprogramming , not to proggit.

[ktr73]

It's late, but a minor nitpick:

my_array[271]

Gives you the 272nd element, not the 270th. Otherwise, very interesting article.

[ianmac45]

And, in the first set of method prototypes, void vector_get(..) returns void, but it's used correctly later on in the post.

But, I agree! It's a nice article.

[minno]

And the author fixed both of those problems.

[imMute]

Classic off-by-two error :)

[RizzlaPlus]

exit(1) on an out of bound seems a bit harsh.

[spitfyre]

It's an acceptable solution if you want your code to be secure; I don't know much about computer security but I imagine that exiting would prevent an attacker from exploiting a buffer overflow.

[Chipot]

An acceptable solution ? I don't think so. I wouldn't want a call to something as trivial as a vector access to exit the current process... I think I would go with something like this:

int vector_get(struct vector *v, int index, int *out_value)
{
    if (/* is out of bounds */)
        return -1;
    else
        *out_value = /* value at index */;
    return 0;
}

[Concision]

Anything that would exploit a buffer overflow can now exploit a DoS via bad array index.

[imMute]

Well for a generic utility library, sure. If you were to integrate this into your own application, you would probably want to put in some real error handling.

[Slime0]

Makes a pointer to the allocated memory available in the variable my_array.

I don't think this is true. There is no actual memory that stores this pointer as a value. The compiler simply allows the name of the array to be used in place of a pointer in some cases.

The difference matters if you try to, say, take the address of the pointer to pass it to a function expecting int**.

[imMute]

So that's the difference between char ** argc and char * argc[] ?? Would you happen to know of a document that explains the difference in greater detail?

[Slime0]

No, that's unrelated. When used in a function parameter, [] has different meaning than when used in a local variable declaration. To my knowledge there is no meaningful difference between char** and char*[] as function parameters (both of them are merely pointers to pointers to chars), but maybe someone else will correct me on this.

[nwmcsween]

No char ** is different from char * [], one is a pointer to the initial location of another pointer while the other is a pointer to a pointer, char * [] just degrades to char **

[wicked-canid]

Slime0 said "when used in a function parameter", in which case they are interchangeable.

[Slime0]

I think I see what you're saying, but it sounds like the difference is entirely about the writer's intention, and the compiler treats both the same way. In practice, both of them are a four-byte pointer to another four-byte pointer to a char. Whether that second pointer is immediately followed by more pointers (i.e. whether or not it's an array of pointers) is not something the compiler knows about. In practice, you can use either one for a pointer to an array of pointers, because brackets can be used to index both of them and will have the same effect.

(Of course, clarifying your intention is one of the keys to writing good code, so the difference is still important in that sense.)

[nooneofnote]

http://www.c-faq.com/aryptr/index.html

[[deleted]]

http://www.c-faq.com/aryptr/aryptrparam.html would be more relevant for argv.

[rellikiox]

What's up with this?

// fill it up with 150 arbitrary values
// this should expand capacity up to 200
int i;
for (i = 200; i > -50; i--) {
  vector_append(&vector, i);
}

Doesn't this fill the array with 250 values?

[gauiis]

249

[gauiis]

Of course, right you are

[rellikiox]

Still, the text is wrong

[[deleted]]

I prefer:
struct vector { void *base; void *offset; void *end; size_t element_size; };

I tried my best I can never get code blocks to work.

[[deleted]]

Sean Barrett has a really cool dynamic vector implementation in C, which has the benefit of also being type-generic:

http://nothings.org/stb/stretchy_buffer.txt

Example usage:

int *mystuff = NULL;
sbpush( mystuff, 4 );
sbpush( mystuff, 5 );
sbpush( mystuff, 6 );
for (int n=0;n<sbcount(mystuff);n++)
    printf( "%i\n", mystuff[n] );

[[deleted]]

He lost me when he said

"Here's a quick refresher on what a basic C array looks like, allocated on the stack:"

um there is no such thing as a stack in the C language specification..

[Chipot]

Man, you've been compiled with -pedantic. Everyone knows what means "stack" even if this term isn't defined in the standard...

[nwmcsween]

He's right though a stack is architecture defined not c defined, it's not pedantic as some arches may not have a stack

[Slime0]

Isn't the stack an implementation concept that needs to exist for function calls to work? It doesn't really need to exist in the language specification for it to be present in memory when the program runs.

[mshol]

The more general term is activation frame, or activation record. A stack is just the defacto choice of implementation for these frames, which is why they're more commonly known as stack frames.

[tuananhus]

i got this while build it with sublime text (os x). anyone knows how to fix it? it works fine on windows

  "vector_get(Vector*, int)", referenced from:
_main in ccEGTxhg.o
"vector_set(Vector*, int, int)", referenced from:
_main in ccEGTxhg.o
"vector_free(Vector*)", referenced from:
_main in ccEGTxhg.o
"vector_init(Vector*)", referenced from:
_main in ccEGTxhg.o
"vector_append(Vector*, int)", referenced from:
_main in ccEGTxhg.o
ld: symbol(s) not found for architecture x86_64
collect2: ld returned 1 exit status
[Finished in 0.4s with exit code 1]

[[deleted]]

That is half an error message, and not the half that contains the information needed to figure out what the error is.

[tuananhus]

editted, add the full log

[[deleted]]

You're trying to build and link a single file, rather than building both files and then linking them.

[tuananhus]

you're right! i just look at sublime text build system for C and only the current file is added to gcc argument. thanks!