C-Struct is "losing" its values?

Question

I built a simple Map/Dictionary in C. But as the title suggests, it does not work as expected. My struct seems to lose given values and I have absolutely no idea why.

Here is the code:

#include <stdio.h>
#include <stdbool.h>

typedef struct {
    unsigned char key;
    unsigned char value;
} KeyValuePair;

typedef struct {
    KeyValuePair *pairs;
    unsigned char max_size;
    unsigned char size;
    bool not_found;
} SimpleMap;

/**
 * Initializes a given "SimpleMap" struct with given size
 * 
 * @param map Pointer to simple map struct
 * @param size Your desired size if this simple map
 */
void simple_map_init(SimpleMap* map, const unsigned char size) {
    KeyValuePair empty_pairs[size];
    map->pairs = empty_pairs;
    map->max_size = size;
    map->size = 0;
    map->not_found = false;
}

/**
 * Searches through the map array, for a given key. If key is found, the corresponding value will be returned.
 * If key is NOT found, zero will be returned return.
 * 
 * NOTE: Since zero is an absolutely valid value within a map, you may look up the "not_found" attribute
 *       of your map, to distinguish between a zero as value or a "NOT FOUND" zero!
 * 
 * @param map Pointer to simple map struct
 * @param key Specific key you are looking for
 * @return Value if key was found, 0 otherwise
 */
const unsigned char simple_map_get(SimpleMap* map, const unsigned char key) {
    for(unsigned short i = 0; i < map->size; i++) {
        if(map->pairs[i].key == key) {
            map->not_found = false;
            return map->pairs[i].value;
        }
    }
    map->not_found = true;
    return 0;
}

/**
 * Adds/Overwrites given key with given value
 * 
 * @param map Pointer to simple map struct
 * @param key Key
 * @param value Value
 * @return TRUE if given key/value pair was added successfully, FALSE otherwise 
 */
bool simple_map_put(SimpleMap* map, const unsigned char key, const unsigned char value) {
    for(unsigned short i = 0; i < map->size; i++) {
        if(map->pairs[i].key == key) {
            map->pairs[i].value = value;
            return true;
        }
    }

    if (map->size < map->max_size) {
        KeyValuePair pair = {key, value};
        map->pairs[map->size++] = pair;
        return true;
    } else {
        printf("Map is full!\n");
        return false;
    }
}

/**
 * Removes a key/value pair with given key, by removing the target key pair & shifting
 * remaining elements of the array to "position - 1", and reducing the size by 1.
 * 
 * @param map Pointer to simple map struct
 * @param key Key to remove
 * @return TRUE if key was found and removed, FALSE otherwise
 */
bool simple_map_remove(SimpleMap* map, const unsigned short key) {
    bool found_key = false;
    unsigned short i;
    for(i = 0; i < map->size; i++) {
        KeyValuePair current_pair = map->pairs[i];
        // printf("%d == %d\n", current_pair.key, key);
        if (current_pair.key == key) {
            found_key = true;
            break;
        }
    }
    if(found_key) {
        i++;
        for(; i < map->size; i++) {
            map->pairs[i-1] = map->pairs[i];
            printf("Overwrite index from %d with index %d\n", i-1, i);
        }
        map->--size;
        return true;
    } else {
        return false;
    }
}

void test_simple_map() {
    SimpleMap map;
    simple_map_init(&map, 8);

    unsigned char key_apple = 0x00;
    unsigned char key_banana = 0x01;
    unsigned char key_orange = 0x02;
    unsigned char key_grape = 0x03;

    simple_map_put(&map, key_apple, 5);
    simple_map_put(&map, key_banana, 7);
    simple_map_put(&map, key_orange, 3);

    for(short i=0; i < map.size; i++) {
        printf("%d -> %d\n", map.pairs[i].key, map.pairs[i].value);
    }

    printf("\n--------------------------------------\n\n");

    for(short i=0; i < map.size; i++) {
        printf("%d -> %d\n", map.pairs[i].key, map.pairs[i].value);
    }

    printf("\n--------------------------------------\n\n");

    printf("Value for key 'apple': %d\n", simple_map_get(&map, key_apple));
    printf("Is a not found zero: %s\n", map.not_found ? "TRUE" : "FALSE");
    printf("Value for key 'banana': %d\n", simple_map_get(&map, key_banana));
    printf("Is a not found zero: %s\n", map.not_found ? "TRUE" : "FALSE");
    printf("Value for key 'orange': %d\n", simple_map_get(&map, key_orange));
    printf("Is a not found zero: %s\n", map.not_found ? "TRUE" : "FALSE");
    printf("Value for key 'grape': %d\n", simple_map_get(&map, key_grape));
    printf("Is a not found zero: %s\n", map.not_found ? "TRUE" : "FALSE");
}

The result of the test_simple_map is following

0 -> 5
1 -> 7
2 -> 3

--------------------------------------

40 -> 0
0 -> 0
0 -> 0

--------------------------------------

Value for key 'apple': 0
Is a not found zero: FALSE
Value for key 'banana': 0
Is a not found zero: TRUE
Value for key 'orange': 0
Is a not found zero: TRUE
Value for key 'grape': 0
Is a not found zero: TRUE

As you can see, the first loop does work. The values are returned, but after that everything seems to be lost?!?

So the question is very simple: How may I keep my values?

---

UPDATE

As suggested by Some programmer dude:

You need to use dynamic allocation (i.e. malloc) to allocate memory that lasts for the life-time of the map object.

So the simple_map_init should change to:

void simple_map_init(SimpleMap* map, const unsigned char size) {
    map->pairs = malloc(size*sizeof(KeyValuePair));
    map->max_size = size;
    map->size = 0;
    map->not_found = false;
}

Additionally make a delete function:

void simple_map_del(SimpleMap* map) {
    free(map->pairs);
}