Ex37: DArray_pop unintended selection?

During review of code in ex37 of Hashmap_delete() my attention was drawn to a condition that might be unintended (my suspicion). Only Zed can confirm whether it is. The condition is part of the code for DArray_pop:

void *DArray_pop(DArray *array)
{
    check(array->end - 1 >= 0, "Attempt to pop from empty array.");

    void *el = DArray_remove(array, array->end - 1);
    array->end--;

    if (DArray_end(array) > (int) array->expand_rate
            && DArray_end(array) % array->expand_rate)  <----------
    {
        DArray_contract(array);
    }

    return el;
error:
    return NULL;
}

My suspicion is that the indicated condition (arrow) is meant to be as follows:

if (DArray_end(array) > (int) array->expand_rate
    && DArray_end(array) % array->expand_rate == 0)

That would make more sense, because contraction takes place when the array is a multiple of the expand rate. In the current condition, contraction only takes place when the array size is not a multiple of the expand rate. This probably is for every pop.

Is this reasoning correct?

Kind regards, Guus.

Uhhhhhhhhhhhhh, yes I believe you are right. I’d say, can you write a test that checks this expansion is happening correctly and then fix it according to what you found? If that works then let me know what you come up with.

EDIT: The exercise originating this code is not Ex37, but Ex34. I discovered it while doing review in Ex37, hence the title.

The test code is:

char *test_contract_after_pop()
{
    int element_size = sizeof(int);
    int initial_max = 100;
    int item[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 29, 20};
    array2 = DArray_create(element_size, initial_max);
    mu_assert(array2 != NULL, "Failed to create array2.");

    // Filling the stack with the figures from the item array.
    size_t size_item_array = sizeof(item)/sizeof(int);
    for(size_t i=0; i<size_item_array; i++)
    {
        int rc = DArray_push(array2, &item[i]);
        mu_assert(rc == 0, "Failed to set item %lu.", i);
    }

    array2->expand_rate = 10;

    // We pop the last element and the size should change: it is a multiple of the expand rate.
    int *popped = DArray_pop(array2);
    mu_assert(popped != NULL, "Failed to pop item.");
    mu_assert(array2->end == item[size_item_array - 1], "End set improperly after pop: %d", array2->end);
    mu_assert(array2->max == 21, "Failed to contract array to 20 elements, maxsize = %d.", array2->max);

    popped = DArray_pop(array2);
    mu_assert(popped != NULL, "Failed to pop item.");
    mu_assert(array2->max == 21, "Failed to pop without contracting, size = %d.", array2->max);

    DArray_destroy(array2);

    return NULL;
}

The test contains 2 testcases:

  1. It should contract when the number of items is an exact mutiple of the expand_rate.
  2. It should not contract when the number of items is not an exact multiple of the expand_rate.

I changed the default expand_rate from 300 to 10, to simplify testing. Also, I added VA_ARGS to the macro mu_assert, in order to add variables to the display:

#define mu_assert(test, message, ...) if (!(test)) {\
    log_err(message, ##__VA_ARGS__); return message; }

The original code does not pass as it calls contract on every pop except for an exact multiple of expand_rate. The altered code in darray_c is:

@@ -125,9 +130,10 @@ void *DArray_pop(DArray *array)
     array->end--;

     if (DArray_end(array) > (int) array->expand_rate
-            && DArray_end(array) % array->expand_rate)
+            && DArray_end(array) % array->expand_rate == 0)
     {
-        DArray_contract(array);
+        int rc = DArray_contract(array);
+        check(rc == 0, "Failed to contract array.");
     }

     return el;

I also added a check to the call to DArray_contract to be sure it did not error out.

Kind regards, Guus.