seahag/linkmap.c

/*                 _,.---._    .-._        .--.-. ,--.--------.
 *   _,..---._   ,-.' , -  `. /==/ \  .-._/==/  //==/,  -   , -\
 * /==/,   -  \ /==/_,  ,  - \|==|, \/ /, |==\ -\\==\.-.  - ,-./
 * |==|   _   _\==|   .=.     |==|-  \|  | \==\- \`--`\==\- \
 * |==|  .=.   |==|_ : ;=:  - |==| ,  | -|  `--`-'     \==\_ \
 * |==|,|   | -|==| , '='     |==| -   _ |             |==|- |
 * |==|  '='   /\==\ -    ,_ /|==|  /\ , |             |==|, |
 * |==|-,   _`/  '.='. -   .' /==/, | |- |             /==/ -/
 * `-.`.____.'     `--`--''   `--`./  `--`             `--`--`
 *                    _ __    ,---.      .-._         .=-.-.  _,.----.
 *                 .-`.' ,`..--.'  \    /==/ \  .-._ /==/_ /.' .' -   \
 *                /==/, -   \==\-/\ \   |==|, \/ /, /==|, |/==/  ,  ,-'
 *               |==| _ .=. /==/-|_\ |  |==|-  \|  ||==|  ||==|-   |  .
 *               |==| , '=',\==\,   - \ |==| ,  | -||==|- ||==|_   `-' \
 *               |==|-  '..'/==/ -   ,| |==| -   _ ||==| ,||==|   _  , |
 *               |==|,  |  /==/-  /\ - \|==|  /\ , ||==|- |\==\.       /
 *               /==/ - |  \==\ _.\=\.-'/==/, | |- |/==/. / `-.`.___.-'
 *               `--`---'   `--`        `--`./  `--``--`-`
 *
 *	@(#)Copyright (c) 2023, Nathan D. Fisher.
 *
 *      This is free software.  It comes with NO WARRANTY.
 *      Permission to use, modify and distribute this source code
 *      is granted subject to the following conditions.
 *      1/ that the above copyright notice and this notice
 *      are preserved in all copies and that due credit be given
 *      to the author.
 *      2/ that any changes to this code are clearly commented
 *      as such so that the author does not get blamed for bugs
 *      other than his own.
 */

#include "haggis.h"
#include "haggis_private.h"

#include <limits.h>        // PATH_MAX
#include <stdio.h>
#include <stdlib.h>        // calloc, free
#include <string.h>        // strndup

#define FNV64_OFFSET_BASIS 14695981039346656037u
#define FNV64_PRIME        1099511628211u

uint64_t hash_fnv1a_64(uint8_t *key, size_t len) {
    int i;
    uint64_t hash = FNV64_OFFSET_BASIS;

    for (i = 0; i < len; i++) {
        hash = hash ^ *key;
        hash = hash * FNV64_PRIME;
        key++;
    }
    return hash;
}

uint64_t hash_str_fnv1a_64(char * s) {
    uint64_t hash = FNV64_OFFSET_BASIS;

    while (*s != '\0') {
        hash = hash ^ *s;
        hash = hash * FNV64_PRIME;
        s++;
    }
    return hash;
}

haggis_linkmap* haggis_linkmap_init() {
    haggis_linkmap *map;

    map = calloc(1, sizeof(haggis_linkmap));
    if (map == NULL)
        return NULL;
    map->buckets = calloc(HAGGIS_BUCKETS_BASE, sizeof(haggis_bucket));
    if (map->buckets == NULL) {
        free(map);
        return NULL;
    }
    map->capacity = HAGGIS_BUCKETS_BASE;
    return map;
}

void haggis_linkmap_deinit(haggis_linkmap *self) {
    free(self->buckets);
    free(self);
}

int haggis_linkmap_expand(haggis_linkmap *self) {
    haggis_bucket *buckets_new;
    haggis_bucket *buckets_old;
    size_t         i, idx;

    buckets_new = calloc(self->capacity + HAGGIS_BUCKETS_BASE, sizeof(haggis_bucket));
    if (buckets_new == NULL)
        return 2;
    for (i = 0; i < self->capacity + HAGGIS_BUCKETS_BASE; i++) {
        self->buckets[i].path = NULL;
    }
    for (i = 0; i < self->capacity; i++) {
        if (self->buckets[i].key != 0) {
            self ->capacity += HAGGIS_BUCKETS_BASE;
            idx = self->capacity % self->buckets[i].hash;
            buckets_new[idx] = self->buckets[i];
        }
    }
    buckets_old = self->buckets;
    self->buckets = buckets_new;
    free(buckets_old);
    self->capacity += HAGGIS_BUCKETS_BASE;
    return 0;
}

char* haggis_linkmap_get_or_add(haggis_linkmap *self, ino_t inode, char *path) {
    union {
        ino_t val;
        u8 bytes[sizeof(ino_t)];
    } key;
    char * target = NULL;
    size_t idx, hash, i;
    haggis_bucket *bucket;

    pthread_mutex_lock(&self->mutex);
    if (self->len >= self->capacity)
        haggis_linkmap_expand(self);
    key.val = inode;
    hash = hash_fnv1a_64(key.bytes, sizeof(ino_t));
    idx = hash % self->capacity;
    for (i = 0; i < self->capacity; i++) {
        bucket = &self->buckets[idx];
        if (bucket->key == inode) {
            target = strndup(bucket->path, PATH_MAX - 1);
            break;
        } else if (bucket->key == 0) {
            bucket->path = path;
            bucket->key = inode;
            bucket->hash = hash;
            self->len++;
            break;
        } else {
            idx++;
            if (idx == self->capacity)
                idx = 0;
        }
    }
    pthread_mutex_unlock(&self->mutex);
    return target;
}