CODEWITHSUNDEEP
calgorithmrandom
Naeem Khan
Naeem Khan

Reputation: 960

C trying to fix infinite loop

I have a function that gets an index value, puts it in an array. Then generates a new new random index using rand + srand(key). And it checks if the newly generated index is in array already, it will will keep on generating new index and checking until a unique value is generated.

The problem is that it works fine for small keys, but at longer keys it gets stuck in an infinite loop and can never find a unique value. Here's my code:

int getNewIndex(PPM *im, int index, int *visitedPixels, int *visitedPixelsIndex) {

    int i = 0;
    if(*visitedPixelsIndex == im->height) {
        perror("Cannot encode anymore: pixels limit reached");
        exit(1);
    }

    visitedPixels[*visitedPixelsIndex] = index;
    (*visitedPixelsIndex)++;
    // If index is already in the list, generate a new number and check again.
    while (i < *visitedPixelsIndex) {
        if(index == visitedPixels[i]) {
            index = rand() % im->height;
            i = 0;
        } else {
            i++;
        }
    }

    return index;
}

EDIT: im->height which is the image height is about 400-600 in average.

Upvotes: 0

Views: 104

Answers (1)

4386427
4386427

Reputation: 44274

As far as I can see the code will generate an infinite loop when you insert the last free index into the array.

Assume that:

1) im->height is 500 so that valid index is in the range [0 .. 499]

2) You have already inserted 499 values, i.e. *visitedPixelsIndex is 499

So when the function is called this condition *visitedPixelsIndex == im->height will be false so you don't exit but continue on and you insert value number 500 in the array.

Then you do (*visitedPixelsIndex)++; so that *visitedPixelsIndex becomes 500.

After that you enter the while loop trying to find a new unused index. However - since you have already used all 500 valid index values, you'll never find an unused index.

In other words - an infinite loop

Maybe you should do:

(*visitedPixelsIndex)++;
if(*visitedPixelsIndex == im->height) {
    perror("Cannot encode anymore: pixels limit reached");
    exit(1);
}

I also think you should generate a new index before the while loop.

However, in general I think your code would be more clear if you split the current function into two functions. Like

int isPresent(int index, int *visitedPixels, int N) 
{
    for(int i = 0; i<N; ++i)
    {
        if (index == visitedPixels[i]) return 1;
    }
    return 0;
}

int getNewIndex(PPM *im, int index, int *visitedPixels, int *visitedPixelsIndex) 
{
    visitedPixels[*visitedPixelsIndex] = index;

    (*visitedPixelsIndex)++;

    if (*visitedPixelsIndex == im->height) {
        perror("Cannot encode anymore: pixels limit reached");
        exit(1);
    }

    do
    {
        index = rand() % im->height;
    } while(isPresent(index, visitedPixels, *visitedPixelsIndex));

    return index;
}

Upvotes: 1

Related Questions