odb.h

Go to the documentation of this file.

#ifndef ODB_HASH_H
#define ODB_HASH_H

#include <stddef.h>
#include <stdint.h>

#include "op_list.h"

typedef uint64_t odb_key_t;
typedef unsigned int odb_value_t;
typedef unsigned int odb_index_t;
typedef odb_index_t odb_node_nr_t;
typedef odb_index_t odb_hash_mask_t;

/* there is (bucket factor * nr node) entry in hash table, this can seem
 * excessive but hash coding eip don't give a good distributions and our
 * goal is to get a O(1) amortized insert time. bucket factor must be a
 * power of two. FIXME: see big comment in odb_hash_add_node, you must
 * re-enable zeroing hash table if BUCKET_FACTOR > 2 (roughly exact, you
 * want to read the comment in odb_hash_add_node() if you tune this define)
 */
#define BUCKET_FACTOR 1

typedef struct {
    odb_key_t key;          
    odb_value_t value;      
    odb_index_t next;       
} odb_node_t;

typedef struct {
    odb_node_nr_t size;     
    odb_node_nr_t current_size; 
    int padding[6];         
} odb_descr_t;

typedef struct odb_data {
    odb_node_t * node_base;     
    odb_index_t * hash_base;    
    odb_descr_t * descr;        
    odb_hash_mask_t hash_mask;  
    unsigned int sizeof_header; 
    unsigned int offset_node;   
    void * base_memory;     
    int fd;             
    char * filename;                
    int ref_count;                  
    struct list_head list;          
} odb_data_t;

typedef struct {
    odb_data_t * data;
} odb_t;

#ifdef __cplusplus
extern "C" {
#endif

/* db_manage.c */

enum odb_rw {
    ODB_RDONLY = 0, 
    ODB_RDWR = 1    
};

void odb_init(odb_t * odb);

int odb_open(odb_t * odb, char const * filename,
             enum odb_rw rw, size_t sizeof_header);

void odb_close(odb_t * odb);

int odb_open_count(odb_t const * odb);

void * odb_get_data(odb_t * odb);

void odb_sync(odb_t const * odb);

int odb_grow_hashtable(odb_data_t * data);
static __inline void odb_commit_reservation(odb_data_t * data)
{
    ++data->descr->current_size;
}

#define ODB_NODE_NR_INVALID ((odb_node_nr_t)-1)

/* db_debug.c */
int odb_check_hash(odb_t const * odb);

/* db_stat.c */
typedef struct odb_hash_stat_t odb_hash_stat_t;
odb_hash_stat_t * odb_hash_stat(odb_t const * odb);
void odb_hash_display_stat(odb_hash_stat_t const * stats);
void odb_hash_free_stat(odb_hash_stat_t * stats);

/* db_insert.c */
int odb_update_node(odb_t * odb, odb_key_t key);

int odb_update_node_with_offset(odb_t * odb, 
                odb_key_t key, 
                unsigned long int offset);

int odb_add_node(odb_t * odb, odb_key_t key, odb_value_t value);

/* db_travel.c */
odb_node_t * odb_get_iterator(odb_t const * odb, odb_node_nr_t * nr);

static __inline unsigned int
odb_do_hash(odb_data_t const * data, odb_key_t value)
{
    /* FIXME: better hash for eip value, needs to instrument code
     * and do a lot of tests ... */
    /* trying to combine high order bits his a no-op: inside a binary image
     * high order bits don't vary a lot, hash table start with 7 bits mask
     * so this hash coding use bits 0-7, 8-15. Hash table is stored in
     * files avoiding to rebuilding them at profiling re-start so
     * on changing do_hash() change the file format!
     */
    uint32_t temp = (value >> 32) ^ value;
    return ((temp << 0) ^ (temp >> 8)) & data->hash_mask;
}

#ifdef __cplusplus
}
#endif

#endif /* !ODB_H */