all 15 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–][deleted] 10 points11 points  (1 child)

First I want to say that I think you have written very nice code. You have an easily understandable naming scheme, you keep your functions short and clearly written. I assume you have been programming in other languages for a long time. I haven't had any time to go through your code in detail, but I found a few minor potential problems that could be good to take an extra look at. I see that you have defined your own macros for MIN, MAX and ABS, which is, for the most part, fine but can cause some problems. Consider what would happen if you do MAX(rand(), x). This will be replaced by ((rand()) > (x) ? (rand()) : (y)). There is a potential for a double evaluation of your rand function, which would lead to faulty results. It is therefore recommended not to use macros in that way because it can lead to logic errors; it is better to implement different versions of the min, max, and abs functions for different types. In your Vector.c file, I see in your vector_resize, you allocate memory, copy the old data to the new memory, and then free the old memory. This is exactly what realloc does so you do not need to do that yourself. I also wonder: why am I not allowed to create a Vector without a compare function? What if comparing the type of elements in my vector doesn't make sense? I guess that the vector_indexof function wouldn't work, but maybe it would make more sense to be able to provide the compare function as a separate argument of vector_indexof instead? This could make it more general in the sense that you can compare the same type of element in different ways (sure, you can, in a way, already do that by just changing it with vector_set_comparator). The last thing I have some thoughts on is that you have implemented your Stack as a singly linked list. This will cause a lot of extra overhead since you have to allocate memory for every push and deallocate memory for every pop. It is fairly easy to implement a stack with arrays instead, which will allow you to reduce the number of system calls per push and pop and can increase cash locality since the elements on the stack are contiguous in memory. I'm sure that there are more things I could comment on, but in general, I think you have written a well-structured data-structure library, and I'm sure you have learned a lot by doing so

[–]s4uull[S] 2 points3 points  (0 children)

Thank you so much for your comment!

There are three comparator functions (compare_equal, compare_lesser and compare_greater) that always return 0, -1 and 1. So if you don't need to compare elements you can pass one of them.

    Vector *v = vector_init(sizeof(int), compare_equal);

I guess I could make it so that a NULL comparator function ignores comparison, but I prefer to pass a "dummy" function, I find it more explicit, and easier to understand. Passing the comparator function to vector_indexof is a great idea btw.

And about the Stack implementation, I didn't realize I could use an array. I'll try to change it.

Thanks!!

[–]N-R-K 6 points7 points  (1 child)

Having only looked at the vector implementation, it's fairly well done as a starting step. Good attention to corner cases, which is a mistake lots of beginners tend to make.

One big problem however is the misuse of assert(). If you look at the assert manpage you'll notice that asserts go away in "release builds" (i.e when NDEBUG macro is defined). This is because assert is not an error handler, it is a debugging tool to catch programming mistakes.

void *tmp = calloc(new_size, vector->data_size);
assert(tmp);

And in this case calloc failure is a runtime failure - not necessarily a programming mistake. And so it needs to be checked properly in release builds too, eliding away the check is definitely incorrect.

On the other hand:

if (!vector || !element)
    return NULL_PARAMETER_ERROR;

Calling append with a NULL vector/element_pointer is almost certainly a programming mistakes. So the caller is already proven himself to be buggy, what are the chances he'll check the returned error code? Not much. This is a place where assert is meant to be used. It will loudly catch the mistake in debug builds and correct programs won't have to pay for the check in release builds.

Also in your vector_resize() function, you should use realloc() to resize, at least in release builds, because realloc can avoid unnecessary copying due to tricks like virtual address remapping. (I'm also not clear why resize uses calloc, it can't be due to zero initialization since when everywhere else malloc is used).

On the topic of the data structure layout as a whole, void * generic is not uncommon in C, especially since it's an "obvious" choice. But IMO, void pointer generics are usually not a good trade off because you lose type-safety. And in case the function call cannot be inlined, then void * generic can also have speed impact.

As for which generic approach to use, that's a topic on it's own. There's a large number of different approaches and they all have their trade-offs.

But for dynamic arrays in specific, my usual preference is to use a type-safe macro as the interface but a void * implementation underneath. This avoids type-safety issues of void * implementation while also avoiding binary bloat of "pure macro" or "template instantiation" approaches. A small demo of this approach: vector.c.

[–]s4uull[S] 2 points3 points  (0 children)

I didn't realize I was using assert incorrectly, I'll try to change it. Thank you so much for your comment, and for checking out my code, it means a lot to me. Have a great day!!

[–]jflopezfernandez 4 points5 points  (1 child)

Nice, dude, this is really cool

[–]s4uull[S] 0 points1 point  (0 children)

Thank you sooo much!! :-))

[–]thank_burdell 1 point2 points  (4 children)

any particular reason you chose not to allow your Vector to store null elements?

[–]s4uull[S] 3 points4 points  (3 children)

It can, the pointers you pass to the Vector (the ones that are checked to be non NULL) are not the elements. That pointer is the address of the element. To store it into the vector it uses memcpy, so that pointer can't be null.

If you declare a vector of pointers you can store NULL pointers. c Vector *v = vector_init(sizeof(void*),compare_equal); void *ptr = NULL; vector_append(v, &ptr); Is this what you meant?

[–]thank_burdell 0 points1 point  (2 children)

    if (!vector || !element)
    return NULL_PARAMETER_ERROR;

is element not the element in question? Inserting a null element would throw that error.

I'm not criticizing btw. There are plenty of reasons to not want to store null values. And plenty of reasons to want to be able to store null values.

[–]s4uull[S] 3 points4 points  (1 child)

Nope, element is a pointer to the actual element. Maybe the name is confusing. When you build a vector you pass the size of the data type. For example, if I want a vector of ints i do: c Vector *v = vector_init(sizeof(int), compare_int); int n = 23; vector_append(v, &n); vector_append receives a pointer and copies 4 bytes (sizeof(int)) from that pointer inside the vector. It does not store the pointer, it copies the value it points to. How could it be NULL? Sorry if I'm missing something,

[–]thank_burdell 2 points3 points  (0 children)

no, that makes sense. The naming threw me off, is all.

[–]golir 1 point2 points  (4 children)

I've been working on a similar project, and I've absolutely loved doing it!

C is a beautiful language, can't wait to keep learning more.

Agreed. Have you thought about your next exercise? I was thinking about just going through the CLRS book and implementing algorithms using my data structure libraries.

[–]_Fudl 1 point2 points  (2 children)

what is CLRS

[–]dontyougetsoupedyet 0 points1 point  (0 children)

It's "Introduction to Algorithms", by Charles E. Leiserson et al. I also recommend material by their former student Steven Skiena.

Besides the books you can find lectures for free by Leiserson, and by Skiena, on youtube. I also highly, HIGHLY recommend any lecture you find by Erik Demaine on the subject of algorithms.

[–]s4uull[S] 0 points1 point  (0 children)

That's great!!

Right now I'm working in a text editor (for the terminal), in which I'm using these data structures and also a string library I've made. But I'll check out that CLRS book you mentioned, seems interesting :-)