Writing a generic function to detect if an array of pointers contains NULL

Question

I would like to write a generic function to detect if an array of pointers to some arbitrary type contains a NULL. My initial attempt was something along these lines:

bool find_null (void *ptrs, size_t num_ptrs) {
    void **array = ptrs;
    size_t i;
    for (i = 0; i < num_ptrs; ++i) {
        if (array[i] == NULL) return true;
    }
    return false;
}

It was pointed out that this could cause a strict aliasing violation, since the array of pointers to Foo would be accessed as array of pointers to void, which is not listed as one of the allowed ways an object is allowed to be accessed in C.2011 §6.5¶7.

I could rewrite the function to access the array of pointers as unsigned char * instead, but I am not sure how to perform the NULL check without breaking strict aliasing. Can someone provide a valid technique?

bool find_null (void *ptrs, size_t num_ptrs) {
    unsigned char *array = ptrs;
    void *p;
    size_t i;
    for (i = 0; i < num_ptrs; ++i) {
        memcpy(&p, array + i * sizeof(p), sizeof(p));
        if (p == NULL) return true;
        /*
         * Above seems to still break strict aliasing.
         * What should be done instead?
         */
    }
    return false;
}

---

The goal is to write a generic function that would work the same as a type specific function. In other words, a generic version of the function below:

bool find_null_Foo (Foo *array[], size_t num_ptrs) {
    size_t i;
    for (i = 0; i < num_ptrs; ++i) {
        if (array[i] == NULL) return true;
    }
    return false;
}

Demagoguery

This is not possible in general. There is no requirement that sizeof(void*) is equal to sizeof(Foo*). They can be unequal on non-byte-addressable machines, where sizeof(void*) is a little bit bigger than sizeof(Foo*) due to the need to record the byte within the word that the pointer is referencing. – Lacto

Do you want code to only consider a null pointer with the value of (void*)NULL or want to handle the possibility that the platform has various null pointers values? (Of course all null pointers equate to each other - though they may have different encodings.) – Farmland

@RaymondChen: Thanks for bringing that up, it is a valid point. I posted an answer which should account for that. However, for such a machine, I would probably end up designing it to be 30 bit addressable (for 4 byte words) or 61 bit addressable (for 8 byte words) instead of trying to deal with pointers of different sizes. – Demagoguery

@Demagoguery good luck with the PDP-10. 36-bit word-addressible address space and 36-bit registers. – Lacto

@RaymondChen: 34-bit addressable in that case. – Demagoguery

@Demagoguery I suspect your compiler won't be very popular. Pointer dereferencing becomes much more expensive (several instructions instead of just one), and throwing out the top two bits of the address means that one of the base registers becomes useless. But hey, let the market decide. – Lacto

Answer 1

You cannot do it with the specific interface you present, but you may be able to do it in this somewhat clunky way:

bool find_null (const void *array, size_t num_ptrs, size_t ptr_size,
        const void *null) {
    const char (*ptr_array)[ptr_size] = array;
    size_t i;
    for (i = 0; i < num_ptrs; ++i) {
        if (!memcmp(array[i], null, ptr_size)) return true;
    }
    return false;
}

You would call that like so:

struct Foo;

#define ARRAY_SIZE 53
int main(void) {
    struct Foo *my_array[ARRAY_SIZE] = { ... };
    struct Foo * const foo_null = (struct Foo *) 0;
    if (find_null(my_array, ARRAY_SIZE, sizeof(*my_array), &foo_null)) {
        puts("It contains NULL");
    } else {
        puts("It does not contain NULL");
    }
}

Do note that that assumes that there is only one representation for null pointers of the type in question, which is true in many implementations, but is not required by the language.

Note also that that isn't actually specific to looking for null pointers, so in fact you can use it to search your pointer array for any pointer value. In fact, it isn't even specific to arrays of pointers -- you can use it to search any array for any value, as long as byte-for-byte equality is a suitable matching criterion (which it isn't for structs or unions, and might not be for some other types).

Additionally, if that suits you then you could probably devise a wrapper macro that makes it a bit easier to use for some of your more common scenarios.

Sake

There is no guarantee you can compare null pointers of different sizes will memcmp,. In fact there is no guarantee that sizeof(void*) >= size of(int*) – Elide

@Elide that is correct. That is why the function I presented accepts a pointer to the null pointer value to compare with the array elements, and uses memcmp() to perform the comparisons. I am comparing pointers of the same type. – Sake

Oops, you do indeed, but as you mention, there seems to be no guarantee that there be a unique representation of null pointers for any given type. – Elide

Answer 2

The generic function is not guaranteed to work as expected on systems where pointers to different types may have different representations and/or sizes. Thankfully such architectures are quite rare nowadays. Posix compliant systems for example are guaranteed to use the same representation and size for all pointer types.

Elide

Unfortunately, violating strict aliasing can still lead the compiler to generate unexpected optimization results even on systems where the pointer sizes are the same. – Demagoguery

@jxh: this kind of behavior is so counterintuitive it should be considered a bug. I wonder how the strict aliasing could be formulated so as to prevent such far reaching consequences. – Elide

@chqrlie: The simplest formulation would be to specify that casting a pointer from type T* to U* will grant license to use that target or pointers derived from it as a U* until the next time the object is accessed via any pointer not derived from the result of the aforementioned cast. That would not preclude many useful optimizations, but would probably avoid the need to use -fno-strict-aliasing with 90% of programs that presently require it. – Underbrush

Answer 3

Based on Raymond's comment, it seems a generic function would require additional arguments. Since there is no way to convert the unsigned char representation of the pointers into a void *, this has to be done via a callback.

bool find_null_generic (const void *ptrs, size_t ptr_sz, size_t num_ptrs,
                        const void *(*convert)(const void *)) {
    const unsigned char *array = ptrs;
    size_t i;
    for (i = 0; i < num_ptrs; ++i) {
        if (convert(array + i * ptr_sz) == NULL) return true;
    }
    return false;
}

For the hypothetical array of pointer to Foo:

const void *convert_Foo (const void *data) {
    const Foo *foo;
    memcpy(&foo, data, sizeof(foo));
    return foo;
}

Foo *foo_array[N] = {...};
bool result = find_null_generic(foo_array, sizeof(Foo *), N, convert_Foo);

Demagoguery