/**
 * Copyright © 2019, Oracle and/or its affiliates. All rights reserved.
 *
 * Licensed under the Universal Permissive License v 1.0 as shown at
 * http://oss.oracle.com/licenses/upl
 *
 */
/* Maintain a set of inodes */
#include "inodemap.h"
#include "malloc.h"
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>

struct entry {
    bool  valid;
    dev_t dev;
    ino_t inode;
    void *value;
};

struct inodemap {
    size_t n_entries;
    size_t hash_size;
    struct entry *entries;
};

struct inodemap *mk_inodemap(void) {
    size_t initial_hash_size = 2;
    struct inodemap *MALLOC(result);
    struct entry *MALLOC_N(entries, initial_hash_size);
    *result = (struct inodemap){.n_entries = 0,
                                .hash_size = initial_hash_size,
                                .entries   = entries};
    for (size_t i = 0; i < initial_hash_size; i++) {
        entries[i].valid = false;
    }
    return result;
}

struct inodemap *inodemap_destroy(struct inodemap *is,
                                  void (*destroy_value_fun)(void*)) {
    assert(is);
    for (size_t i = 0; i < is->hash_size; i++) {
        if (is->entries[i].valid) {
            destroy_value_fun(is->entries[i].value);
        }
    }
    free(is->entries);
    free(is);
    return NULL;
}

static const uint64_t FNV_OFFSET = 14695981039346656037ull;
static const uint64_t FNV_PRIME  = 1099511628211ull;

static uint64_t hash128(uint64_t a, uint64_t b) {
    uint64_t hash = FNV_OFFSET;
    for (size_t i = 0; i < 8; i++) {
        hash ^= (a>>(i*8))&0xFFul;
        hash *= FNV_PRIME;
        hash ^= (b>>(i*8))&0xFFul;
        hash *= FNV_PRIME;
    }
    return hash;
}

uint64_t inodemap_hash(dev_t dev, ino_t inode) {
    return hash128(dev, inode);
}

static struct entry *
find_entry(struct entry *entries, size_t hash_size, dev_t dev, ino_t ino) {
    // hash_size must be a power of two
    assert(0 == (hash_size & (hash_size - 1)));
    uint64_t h = inodemap_hash(dev, ino);
    for (size_t i = 0; i < hash_size; i++) {
        size_t idx = ((size_t)h + i) & (hash_size-1);
        if (!entries[idx].valid
            || (entries[idx].dev == dev && entries[idx].inode == ino)) {
            return entries+idx;
        }
    }
    assert(0);
}

bool
inodemap_lookup(struct inodemap *im,
                dev_t dev,
                ino_t inode,
                void const **value) {
    struct entry *e = find_entry(im->entries, im->hash_size, dev, inode);
    if (e->valid) {
        *value = e->value;
    }
    return e->valid;

}

static void
maybe_grow_table(struct inodemap *im) {
    if (im->n_entries * 2 < im->hash_size) {
        return;
    }
    size_t new_size = 2*im->hash_size;
    struct entry *MALLOC_N(new_entries, new_size);
    for (size_t i = 0; i < new_size; i++) {
        new_entries[i].valid = false;
    }
    for (size_t i = 0; i < im->hash_size; i++) {
        if (im->entries[i].valid) {
            struct entry *e = find_entry(new_entries, new_size,
                                         im->entries[i].dev,
                                         im->entries[i].inode);
            assert(!e->valid);
            *e = im->entries[i];
        }
    }
    free(im->entries);
    im->entries = new_entries;
    im->hash_size = new_size;
}

static void
inodemap_print(struct inodemap *im, FILE *f)
    __attribute__((unused));
static void
inodemap_print(struct inodemap *im, FILE *f) {
    fprintf(f, "Inode map %p.  n_entries=%zd hash_size=%zd\n",
            im, im->n_entries, im->hash_size);
    for (size_t i = 0 ; i < im->hash_size; i++) {
        if (im->entries[i].valid) {
            fprintf(f, "%zd: %lu,%lu -> %p\n", i,
                    im->entries[i].dev, im->entries[i].inode,
                    im->entries[i].value);
        } else {
            fprintf(f, "%zd: empty\n", i);
        }
    }
}

void
inodemap_insert(struct inodemap *im, dev_t dev, ino_t inode, void *value) {
    maybe_grow_table(im);
    // Now we know we have space.
    struct entry *e = find_entry(im->entries, im->hash_size, dev, inode);
    assert(!e->valid);
    *e = (struct entry){.valid = true,
                        .dev   = dev,
                        .inode = inode,
                        .value = value};
    im->n_entries++;
}