"default value" of allocated struct pointer in C

Question

I am storing the input data which includes the specific order, so I choose to use array to sort them:

struct Node** array = (struct Node**)malloc(sizeof(Node**) * DEFAULT_SIZE);

int i;
int size = DEFAULT_SIZE;
while(/* reading input */) {
    // do something
    int index = token;    // token is part of an input line, which specifies the order
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    *node = (struct Node){value, index};
    // do something

    if (index >= size) {
        array = realloc(array, index + 1);
        size = index + 1;
    }

    array[index] = node;
}

I am trying to loop through the array and do something when the node exists at the index

int i;
for (i = 0; i < size; i++) {
    if (/* node at array[i] exists */) {
        // do something
    }
}

How can I check if node exists at the specific index of the array? (Or what is the "default value" of the struct node after I allocated its memory?) I only know it is not NULL...

Should I use calloc and try if ((int)array[index] != 0)? Or there is a better data structure I am able to use?

Answer 1

When you realloc (or malloc) your list of pointers, the system resizes/moves the array, copying your data if needed, and reserving more space ahead without changing the data, so you get what was there before. You cannot rely on the values.

Only calloc does a zero init, but you cannot calloc when you realloc.

For starters you should probably use calloc:

struct Node** array = calloc(DEFAULT_SIZE,sizeof(*array));

In your loop, just use realloc and set the new memory to NULL so you can test for null pointers

Note that your realloc size is incorrect, you have to multiply by the size of the element. Also update the size after reallocation or that won't work more than once.

Note the tricky memset which zeroes only the unallocated data without changing the valid pointer data. array+size computes the proper address size due to pointer arithmetic, but the size parameter is in bytes, so you have to multiply by sizeof(*array) (the size of the element)

if (index >= size)
   {
      array = realloc(array, (index + 1)*sizeof(*array));  // fixed size
      memset(array+size,0,(index+1-size) * sizeof(*array));  // zero the rest of elements
      size = index+1;  // update size
   }

aside:

• realloc for each element is inefficient, you should realloc by chunks to avoid too many system calls/copies
• I have simplified the malloc calls, no need to cast the return value of malloc, and also better to pass sizeof(*array) instead of sizeof(Node **). In case the type of array changes you're covered (also protects you from one-off errors with starred types)

Answer 2

The newly-allocated memory contains garbage and reading a pointer from uninitialized memory is a bug.

If you allocated using calloc( DEFAULT_SIZE, sizeof(Node*) ) instead, the contents of the array would be defined: all bits would be set to zero. On many implementations, this is a NULL pointer, although the standard does not guarantee it. Technically, there could be a standard-conforming compiler that makes the program crash if you attempt to read a pointer with all bits set to zero.

(Only language lawyers need to worry about that, though. In practice, even the fifty-year-old mainframes people bring up as the example of a machine where NULL was not binary 0 updated its C compiler to recognize 0 as a NULL pointer, because that broke too much code.)

The safe, portable way to do what you want is to initialize every pointer in the array to NULL:

struct Node** const array = malloc(sizeof(Node**) * DEFAULT_SIZE);
// Check for out-of-memory error if you really want to.
for ( ptrdiff_t i = 0; i < DEFAULT_SIZE; ++i )
  array[i] = NULL;

After the loop executes, every pointer in the array is equal to NULL, and the ! operator returns 1 for it, until it is set to something else.

The realloc() call is erroneous. If you do want to do it that way, the size argument should be the new number of elements times the element size. That code will happily make it a quarter or an eighth the desired size. Even without that memory-corruption bug, you’ll find yourself doing reallocations far too often, which might require copying the entire array to a new location in memory.

The classic solution to that is to create a linked list of array pages, but if you’re going to realloc(), it would be better to multiply the array size by a constant each time.

Similarly, when you create each Node, you’d want to initialize its pointer fields, if you care about portability. No compiler this century will generate less-efficient code if you do.

If you only allocate nodes in sequential order, an alternative is to create an array of Node rather than Node*, and maintain a counter of how many nodes are in use. A modern desktop OS will only map in as many pages of physical memory for the array as your process writes to, so simply allocating and not initializing a large dynamic array does not waste real resources in most environments.

One other mistake that’s probably benign: the elements of your array have type struct Node*, but you allocate sizeof(Node**) rather than sizeof(Node*) bytes for each. However, the compiler does not type-check this, and I am unaware of any compiler where the sizes of these two kinds of object pointer could be different.

Answer 3

You might need something like this

unsigned long i;
for (i = 0; i < size; i++) {
    if (array[i]->someValidationMember==yourIntValue) {
        // do something
    }
}

Edit. The memory to be allocated must be blank. Or if an item is deleted just simply change the Node member to zero or any of your choice.