root/software/fss-parallel-tools/inodemap.c @ 96e4083c
| 7e8045d8 | David Sorber | /**
|
|
* 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++;
|
|||
}
|