map.h

template <class T>
struct MapItem {
    char* key;
    T value;
};

// Hash map indexed by NULL-terminated strings
template <class T>
struct Map {
    uint64_t capacity;  // allocated capacity
    uint64_t count;     // number of items in the map
    MapItem<T>* items;  // array with length capacity

    void print(bool all, void (*value_print)(const T&)) const {
        printf("Map <%p>, count %" PRIu64 "/%" PRIu64 ", items <%p>\n", this, count, capacity,
               items);
        if (all) {
            MapItem<T>* item = items;
            if (value_print) {
                for (uint64_t i = 0; i < capacity; i++, item++) {
                    printf("Item %" PRIu64 " <%p>, key %p (%s): ", i, item, item->key,
                           item->key ? item->key : "");
                    value_print(item->value);
                }
            } else {
                for (uint64_t i = 0; i < capacity; i++, item++) {
                    printf("Item %" PRIu64 " <%p>, key %p (%s): value <%p>\n", i, item, item->key,
                           item->key ? item->key : "", item->value);
                }
            }
        }
    }

    // The instance should be zeroed before using copy_from
    void copy_from(const Map<T>& map) {
        count = 0;
        capacity = map.capacity;
        items = (MapItem<T>*)allocate_clear(capacity * sizeof(MapItem<T>));
        for (MapItem<T>* item = map.next(NULL); item; item = map.next(item)) {
            set(item->key, item->value);
        }
    }

    void resize(uint64_t new_capacity) {
        Map<T> new_map;
        new_map.count = 0;
        new_map.capacity = new_capacity;
        new_map.items = (MapItem<T>*)allocate_clear(new_capacity * sizeof(MapItem<T>));
        const MapItem<T>* limit = items + capacity;
        for (MapItem<T>* it = items; it != limit; it++) {
            if (it->key) new_map.set(it->key, it->value);
        }
        clear();
        capacity = new_map.capacity;
        count = new_map.count;
        items = new_map.items;
    }

    // Function to iterate over all values in the map:
    // for (MapItem<T>* item = map.next(NULL); item; item = map.next(item)) {…}
    MapItem<T>* next(const MapItem<T>* current) const {
        MapItem<T>* next_ = current ? (MapItem<T>*)(current + 1) : items;
        const MapItem<T>* limit = items + capacity;
        while (next_ < limit) {
            if (next_->key) return next_;
            next_++;
        }
        return NULL;
    }

    void to_array(Array<T>& result) const {
        result.ensure_slots(count);
        const MapItem<T>* limit = items + capacity;
        for (MapItem<T>* it = items; it != limit; it++) {
            if (it->key) result.append_unsafe(it->value);
        }
    }

    void clear() {
        if (items) {
            MapItem<T>* item = items;
            for (uint64_t i = 0; i < capacity; i++, item++) {
                if (item->key) {
                    free_allocation(item->key);
                    item->key = NULL;
                }
            }
            free_allocation(items);
            items = NULL;
        }
        capacity = 0;
        count = 0;
    }

    MapItem<T>* get_slot(const char* key) const {
        assert(capacity > 0);
        assert(count < capacity);
        uint64_t h = hash(key) % capacity;
        MapItem<T>* item = items + h;
        while (item->key != NULL && strcmp(item->key, key) != 0) {
            item++;
            if (item == items + capacity) item = items;
        }
        // DEBUG_PRINT("get_slot %s [%" PRIu64 "] -> [%" PRIu64 "]\n", key, h, item - items);
        return item;
    }

    // Key is internally allocated and copied; value is simply assigned
    void set(const char* key, T value) {
        // Equality is important for capacity == 0
        if (count * 10 >= capacity * GDSTK_MAP_CAPACITY_THRESHOLD)
            resize(capacity >= GDSTK_INITIAL_MAP_CAPACITY ? capacity * GDSTK_MAP_GROWTH_FACTOR
                                                          : GDSTK_INITIAL_MAP_CAPACITY);
        MapItem<T>* item = get_slot(key);
        if (item->key == NULL) {
            item->key = copy_string(key, NULL);
            count++;
        }
        item->value = value;
    }

    bool has_key(const char* key) const {
        if (count == 0) return false;
        const MapItem<T>* item = get_slot(key);
        return item->key != NULL;
    }

    // If the desired key is not found, returns T{}
    T get(const char* key) const {
        if (count == 0) return T{};
        const MapItem<T>* item = get_slot(key);
        return item->key == NULL ? T{} : item->value;
    }

    // Return true if the key existed, false otherwise
    bool del(const char* key) {
        if (count == 0) return false;
        MapItem<T>* item = get_slot(key);
        if (item->key == NULL) return false;

        // DEBUG_PRINT("DEL [%" PRIu64 "] %s\n", item - items, item->key);
        free_allocation(item->key);
        item->key = NULL;
        count--;

        // Re-insert this block to fill any undesired gaps
        while (true) {
            item++;
            if (item == items + capacity) item = items;
            if (item->key == NULL) return true;
            char* temp_key = item->key;
            item->key = NULL;
            MapItem<T>* new_item = get_slot(temp_key);
            new_item->key = temp_key;
            new_item->value = item->value;
            // if (new_item != item) {
            //     DEBUG_PRINT("MOVE %s [%" PRIu64 "] -> [%" PRIu64 "]\n", new_item->key,
            //                 item - items, new_item - items);
            // }
        }
        assert(false);
        return true;
    }
};