find elements of an array in another array, why do I have this error?

Question

I was trying to visualize the algorithm of this exercise, but I'm having a lot of problems.

the exercise asks to implement this function:

extern const void *memmem(const void *haystack, size_t hsize, const void *needle, size_t nsize); 

• haystack and needle are two pointers to two different areas of memory. haystack points to a memory of size hsize, and needle points to a memory of size nsize.
• find *needle elements in *haystack, and if *needle elements are in *haystack too, return a pointer to the new allocated memory (containing *needle elements) and this pointer has to point to the 0-th element of the new memory.

I hope I've explained it better than the original exercise (it's not clear, so I had a hard time trying to understand it).

---

I've tried to sketch the algorithm this way:

algorithm accepts two pointers and their sizes. (loop) increment *needle by one at each step in order to find a common element (comparing that element with the current element of haystack), and if that condition is true, increment a counter by one. Doing this way I've obtained the length of the final array. Then, I allocate enough memory, and do another loop to copy each element in the final vector. last but not least, return this pointer.

this is how is it suppose to look like in code (I know it's not complete, but I'm currently building it step by step, it's not easy at all):

#include <stdlib.h>
const void* memmem(const void* haystack, size_t hsize, const void* needle, size_t nsize) {
    if ((hsize == 0) || (nsize = 0)) {
        return NULL; // here, I should've done a NULL pointer exception check too, because haystack and needle may be null pointer too. for now, ignore that. 
    }
    for (size_t i = 0; i < nsize; i++) {
        if (needle[i] == haystack[i])
    } 

}


int main(void) {

    int haystack[] = {-1, 0, 1, 2, 3, 4};
    size_t hsize = 6; 
    int needle[] = {-1, 8, 4, 2};
    size_t nsize = 4; 

    int* ptr = memmem(haystack, hsize, needle, nsize); 


    return 0; 
}

the crucial part is here:

for (size_t i = 0; i < nsize; i++) {
            if (needle[i] == haystack[i])
        } 

because I have this error: expression must be a pointer to a complete object type. What does it mean? I've never heard of this error message before. arrays are complete, I've defined them correctly, therefore I don't know why I have that.

Answer 1

The type void is incomplete type. Its size is unknown. The compiler has no possibility to determine the size of objects of that type (though for backward compatibility some compilers have their own extensions that determine sizeof( void ) equal to 1. But this does not satisfy the C Standard).

From the C Standard (6.2.5 Types)

19 The void type comprises an empty set of values; it is an incomplete object type that cannot be completed.

So you may not dereference a pointer of the type cv void *. You need to cast the pointer to a pointer to a complete object type to access a pointed object.

In any case this for loop

for (size_t i = 0; i < nsize; i++) {
    if (needle[i] == haystack[i])
} 

even if the pointers were casted is incorrect because nsize and hsize can be unequal.

I think you need two nested for loops.

Also at least the qualifier const in the return type of the function

extern const void *memmem(const void *haystack, size_t hsize, const void *needle, size_t nsize); 

does not make a great sense. It should be removed.