Array indices for guard in loop? What is it actually checking for?

Question

These are sections of C code used to implement a hashmap using open-addressing. I don't understand what the while loop in the insert function is checking and the if statement in the twoSum Function is checking for.

Does the while loop condition check if the value is in the array or if the value isn't null. Does the if statement check if the value is not 0? I don't understand.

I always thought something like this would work like a while(1) loop that needs to manually break.

I want to know what the conditions of the loops guard statement are I understand the body.

void insert(int *keys, int *values, int key, int value) {
    int index = hash(key);
    while (values[index]) { // What does this check for?
        index = (index + 1) % SIZE;
    }
    keys[index] = key;
    values[index] = value;
}

int* twoSum(int* nums, int numsSize, int target) {
    int keys[SIZE];
    int values[SIZE] = {0};
    for (int i = 0; i < numsSize; i++) {
        int complements = target - nums[i];
        int value = search(keys, values, complements);
        if (value) { // What does this line check for?
            int *indices = (int *) malloc(sizeof(int) * 2);
            indices[0] = value - 1;
            indices[1] = i;
            return indices;
        }
        insert(keys, values, nums[i], i + 1);
    }
    return NULL;
}

More specifically, the first one is checking if a position is occupied. If there is “something” (a non-zero value) in it, the code proceeds to the next position. When it finds an “empty” (zero value) position, it fills it in with the data to be inserted. (This is not a good design—when the array is full, the code will loop infinitely. And it inserts elements in unpredictable locations, causing any lookup code to be inefficient.) — Eric Postpischil, Jul 02 '19 at 09:59
Yeah I agree with you there I appreciate the detailed insight on this, I didn't even notice that fault in the design. I was confused as to why there was no break point, but blamed it on my lack of knowledge. Very good explanation. — Kerelos Tawfik, Jul 02 '19 at 11:24
@EricPostpischil We do have an answer section if you want to do that. — Lightness Races in Orbit, Jul 02 '19 at 11:35
A question being closed doesn't mean you should answer it in the comments section. It means it's closed. Though this particular closure seems a little heavy-handed. — Lightness Races in Orbit, Jul 02 '19 at 13:24

score 0 · Answer 1 · answered Jul 02 '19 at 09:44

0

We can only guess.

It looks like insert expects pointers to arrays that always have a final element of value zero, that the designer of the function has chosen that convention to signify "end of the array".

And it looks like search returns zero when the search failed.

However, either could instead be a bug (I'm suspicious because this design prohibits zero ever being treated as a "real"/valid value), and both are arguably bad design — in the former case, why not pass the array size as an argument instead? In the latter case, why not return bool and give the result (if successful) as an "out argument", like other C APIs?

Ultimately, we cannot magically know the preconditions of a function, so you will have to ask the person who wrote it.

This is why code should have explanatory comments.

answered Jul 02 '19 at 09:44

Lightness Races in Orbit

378,754
76
643
1,055

It drives me _crazy_ how much undocumented code exists. It's really not hard to briefly annotate your functions. – Lightness Races in Orbit Jul 02 '19 at 09:46
I'm trying to ask more about the actual guard of the loop rather than the body. – Kerelos Tawfik Jul 02 '19 at 09:47
@KerelosTawfik Yes, I answered your question. If `values[index]` is the value `0`, then the loop ends, no? Because it's `while(0)`? – Lightness Races in Orbit Jul 02 '19 at 11:34
Yeah thanks for the help, knowing this I've realised it's terribly designed code. It's one of the commented C solutions for LeetCode Problem 1 (Two Sum). – Kerelos Tawfik Jul 02 '19 at 13:50

Array indices for guard in loop? What is it actually checking for?

1 Answers1