fusenbd/src/hashtab.c

/*
 * hashtab.c
 *
 * Copyright (C) 2019 Alex A. <coderain@sdf.org>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "hashtab.h"

void *hash_table_search(hash_table_t *ht, void *entry, int auto_add)
{
    size_t bucket = ht->hash(entry);

    if (ht->lengths[bucket] > 0)
    {
        void **array = ht->buckets[bucket];
        int low = 0, high = ht->lengths[bucket] - 1;

        while (low <= high)
        {
            int mid = (low + high) / 2;
            int comp = ht->compare(array[mid], entry);

            if (comp < 0) low = mid + 1;
            else if (comp > 0) high = mid - 1;
            else return array[mid];
        }

        if (!auto_add || ht->lengths[bucket] == DUPLICATES) return NULL;

        if (low < ht->lengths[bucket])
        {
            /* Maintain the ascending order by moving all the bigger ones right */
            memmove(&array[low + 1], &array[low], (ht->lengths[bucket] - low) * sizeof(void*));
        }

        array[low] = entry;
        ht->lengths[bucket]++;
    }
    else
    {
        if (!auto_add) return NULL;
        ht->buckets[bucket][0] = entry;
        ht->lengths[bucket] = 1;
    }

    return entry;
}

void hash_table_delete(hash_table_t *ht, const void *entry)
{
    size_t bucket = ht->hash(entry);
    void **array = ht->buckets[bucket];
    if (!array) return;

    int low = 0;
    int high = ht->lengths[bucket] - 1;
    int mid;

    while (low <= high)
    {
        mid = (low + high) / 2;
        int comp = ht->compare(array[mid], entry);

        if (comp < 0) low = mid + 1;
        else if (comp > 0) high = mid - 1;
        else break;
    }

    if (low <= high) memmove(&array[mid], &array[mid + 1], (--ht->lengths[bucket] - mid) * sizeof(void*));
}

void **hash_table_enum(hash_table_t *ht, void **current)
{
    size_t bucket = current ? ht->hash(*current) : 0;

    if (current)
    {
        size_t index = current - ht->buckets[bucket] + 1;
        if (index < ht->lengths[bucket]) return &ht->buckets[bucket][index];
    }

    while (++bucket < BUCKETS) if (ht->lengths[bucket] > 0) return ht->buckets[bucket];
    return NULL;
}