More efficient way to check range?

Question

Given a Config (0-3) and input index, I have to determine which Region index is in, so the output is 1,2,3, or 4.

Note: the range of values is determined by some formula, for example let's ignore Config 0 and look at Config 1-3, let's say range is defined as numbers 0-111 and it comes from a formula 2*7*{0-7}+{0-13}(the last two numbers are from additional parameters we can ignore for now), and for subsequent regions it is 2*7*8+range, 4*7*8+range, 6*7*8+range respectively, hence those values.

Right now, what I do is check the config, then I perform a range check where I check that the index is between the min and max of a specific region. So if given this table:

+--------------+---------+---------+---------+---------+
|Region\Config |    0    |    1    |    2    |    3    |
+--------------+---------+---------+---------+---------+
|     1st      |  0-56   |  0-111  |  0-111  |  0-111  |
+--------------+---------+---------+---------+---------+
|     2nd      |         |         | 112-223 | 112-223 |
+--------------+---------+---------+---------+---------+
|     3rd      |         |         |         | 224-335 |
+--------------+---------+---------+---------+---------+
|     4th      |         |         |         | 336-447 |
+--------------+---------+---------+---------+---------+

My logic is:

- If config 0, <if index is 0-56> return 1
- If config 1, <if index is 0-111> return 1
- If config 2, if index is between 0-111, return 1
                 else if between 112-223, return 2
- If config 3, if index is between 0-111, return 1
                 else if between 112-223, return 2 
                 else if between 224-335, return 3
                 else if between 336-447, return 4
- Bottom of function: return -1

Is there a better way of doing this code rather than just doing a bunch of if-elses? I feel like it's possible to make sure of the additional parameters in the formula, but I can't seem to see it.

Answer 1

I commented to selbie that it should be possible to use an initializer for the structure. The riposte was:

I tried. I keep getting a "too many initializers" error …

Here's the proof that it is possible, but it was more mind-blowing than I expected, requiring 5 (as in 'five'!) levels of braces in the initializers.

struct Table table =
{   // structure
    {   // array
        {   // structure
            {   // array
                { "1st",   0,  56 },
            },
        },
        {   {   { "1st",   0, 111 },   },   },
        …
    },
};

That was more complex than I expected. It makes laying out the data a pain. I'm not sure whether I've got a really good layout either above or below.

Here's the full code (mostly based on selbie's code), which checks that the data works by printing out the table to simulate the table in the question. The search function is made static inline so that the compiler (GCC 7.1.0) won't complain about it not being used.

#include <stdio.h>

#define MAX_REGIONS  4
#define MAX_CONFIGS  4

struct Region {
    char* name;
    int min;
    int max;
};

struct Config {
    struct Region regions[MAX_REGIONS];
};

struct Table {
    struct Config configs[MAX_CONFIGS];
};

static inline int searchTable(struct Table* table, int configIndex, int value) {
    if ((configIndex < 0) || (configIndex >= MAX_CONFIGS)) {
        return -1;  // out of range
    }

    struct Config* config = &table->configs[configIndex];
    for (int x = 0; x < MAX_REGIONS; x++) {
        struct Region* region = &config->regions[x];
        if ((value >= region->min) && (value <= region->max)) {
            return x;
        }
    }
    return -1;  // not found
}

static void print_line(int wid_1, int wid_2, int num_2)
{
    putchar('+');
    for (int i = 0; i < wid_1; i++)
        putchar('-');
    for (int k = 0; k < num_2; k++)
    {
        putchar('+');
        for (int i = 0; i < wid_2; i++)
            putchar('-');
    }
    putchar('+');
    putchar('\n');
}

int main(void)
{
    struct Table table =
    {
        {
            { { { "1st",   0,  56 }, }, },
            { { { "1st",   0, 111 }, }, },
            { { { "1st",   0, 111 },
                { "2nd", 112, 223 }, }, },
            { { { "1st",   0, 111 }, 
                { "2nd", 112, 223 }, 
                { "3rd", 224, 335 },
                { "4th", 336, 447 }, }, },
        },
    };

    print_line(15, 9, MAX_CONFIGS);
    printf("| %-13s ", "Region/Config");
    for (int i = 0; i < MAX_CONFIGS; i++)
        printf("|    %d    ", i);
    puts("|");
    print_line(15, 9, MAX_CONFIGS);
    for (int i = 0; i < MAX_REGIONS; i++)
    {
        printf("|      %s      ", table.configs[MAX_CONFIGS-1].regions[i].name);
        for (int j = 0; j < MAX_CONFIGS; j++)
        {
            if (table.configs[j].regions[i].name == NULL)
                printf("|         ");
            else
                printf("| %3d-%-3d ", table.configs[j].regions[i].min,
                                     table.configs[j].regions[i].max);
        }
        puts("|");
        print_line(15, 9, MAX_CONFIGS);
    }

    return 0;
}

The output:

+---------------+---------+---------+---------+---------+
| Region/Config |    0    |    1    |    2    |    3    |
+---------------+---------+---------+---------+---------+
|      1st      |   0-56  |   0-111 |   0-111 |   0-111 |
+---------------+---------+---------+---------+---------+
|      2nd      |         |         | 112-223 | 112-223 |
+---------------+---------+---------+---------+---------+
|      3rd      |         |         |         | 224-335 |
+---------------+---------+---------+---------+---------+
|      4th      |         |         |         | 336-447 |
+---------------+---------+---------+---------+---------+

Answer 2

Because the particular boundary values you present follow a consistent pattern, you can compute the region number by formula. You can in any case check whether the input is out of range by comparing against per-config limits tabulated in an array. For example,

int get_region(unsigned char config, unsigned int index) {
    static const unsigned int upper_bound[] = { 56, 111, 223, 447};
    static const size_t num_configs = sizeof(upper_bound) / sizeof(upper_bound[0]);

    if (config >= num_configs || index > upper_bound[config]) {
        // handle input error; maybe:
        return -1;
    } else {
        return (index / 112) + 1;
    }
}

Answer 3

You can do a 2d array, but I prefer the a set of nested structures representing each region, config, and the table as a whole.

#define MAX_REGIONS  4
#define MAX_CONFIGS  4

struct Region {
    char* name;
    int min;
    int max;
};

struct Config {
    struct Region regions[MAX_REGIONS];
};

struct Table {
    struct Config configs[MAX_CONFIGS];
};

Then to search the table to find the region for a given config and search index:

int searchTable(struct Table* table, int configIndex, int value) {
    if ((configIndex < 0) || (configIndex >= MAX_CONFIGS)) {
        return -1;  // out of range
    }

    struct Config* config = &table->configs[configIndex];
    for (int x = 0; x < MAX_REGIONS; x++) {
        struct Region* region = &config->regions[x];
        if ((value >= region->min) && (value <= region->max)) {
            return x;
        }
    }
    return -1;  // not found
}

Then to build the table initially, you would have code that looks like this:

int main()
{
    struct Table table;
    table.configs[0].regions[0].name = "1st";
    table.configs[0].regions[0].min = 0;
    table.configs[0].regions[0].max = 56;
    // ...
    table.configs[3].regions[3].name = "4th";
    table.configs[3].regions[3].max = 335;
    table.configs[3].regions[3].max = 447;

};