hash.h

Go to the documentation of this file.

#pragma once
 
 
#include <stddef.h>
#include <inttypes.h>
#include <stdbool.h>
 
#include <crater/container.h>
 
typedef struct{
    void *table_a;
    void *table_b;
    uint64_t *flags_a;
    uint64_t *flags_b;
    uint64_t cap;
    uint64_t len_a;
    uint64_t len_b;
    uint64_t i;
    uint64_t r;
    uint64_t full;
} cr8r_hashtbl_t;
 
typedef struct{
    cr8r_base_ft base;
    uint64_t (*hash)(const cr8r_base_ft*, const void*);
    int (*cmp)(const cr8r_base_ft*, const void*, const void*);
    int (*add)(cr8r_base_ft*, void*, void*);
    void (*del)(cr8r_base_ft*, void*);
    double load_factor;
} cr8r_hashtbl_ft;
 
 
bool cr8r_hash_ft_init(cr8r_hashtbl_ft*,
    void *data, uint64_t size,
    uint64_t (*hash)(const cr8r_base_ft*, const void*),
    int (*cmp)(const cr8r_base_ft*, const void*, const void*),
    int (*add)(cr8r_base_ft*, void*, void*),
    void (*del)(cr8r_base_ft*, void*)
);
 
 
int cr8r_hash_init(cr8r_hashtbl_t*, const cr8r_hashtbl_ft*, uint64_t reserve);
 
void *cr8r_hash_get(cr8r_hashtbl_t*, const cr8r_hashtbl_ft*, const void *key);
 
void *cr8r_hash_insert(cr8r_hashtbl_t*, const cr8r_hashtbl_ft*, const void *key, int *status);
 
void *cr8r_hash_append(cr8r_hashtbl_t*, cr8r_hashtbl_ft*, void *key, int *status);
 
int cr8r_hash_remove(cr8r_hashtbl_t*, cr8r_hashtbl_ft*, const void *key);
 
void cr8r_hash_delete(cr8r_hashtbl_t*, cr8r_hashtbl_ft*, void *ent);
 
void cr8r_hash_clear(cr8r_hashtbl_t*, cr8r_hashtbl_ft*);
 
void cr8r_hash_destroy(cr8r_hashtbl_t*, cr8r_hashtbl_ft*);
 
inline static void *cr8r_hash_next(cr8r_hashtbl_t *self, const cr8r_hashtbl_ft *ft, void *cur){
    uint64_t a = 0, b = 0;
    if(self->table_b){
        if(cur){
            b = (cur - self->table_b)/ft->base.size;
            if(b++ >= self->len_b){// also goes to SEARCH_A if "b < 0" due to unsigned overflow wrapping
                goto SEARCH_A;
            }
        }
        for(; b < self->len_b; ++b){
            if((self->flags_b[b >> 5] >> (b&0x1F))&0x100000000ULL){
                return self->table_b + b*ft->base.size;
            }
        }
    }else{
        SEARCH_A:
        if(cur){
            a = (cur - self->table_a)/ft->base.size;
            if(a++ >= self->len_a){
                return NULL;
            }
        }
    }
    for(; a < self->len_a; ++a){
        if((self->flags_a[a >> 5] >> (a&0x1F))&0x100000000ULL){
            return self->table_a + a*ft->base.size;
        }
    }
    return NULL;
}
 
extern const uint64_t cr8r_hash_u64_prime;
 
extern cr8r_hashtbl_ft cr8r_htft_u64_void;
 
extern cr8r_hashtbl_ft cr8r_htft_u64_u64;
 
typedef struct{
    const char* str;
    uint64_t n;
} cr8r_htent_cstr_u64;
 
extern cr8r_hashtbl_ft cr8r_htft_cstr_u64;