1ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** 2ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @file odb.h 3ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * This file contains various definitions and interface for management 4ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * of in-memory, through mmaped file, growable hash table, that stores 5ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * sample files. 6ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 7ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * @remark Copyright 2002 OProfile authors 8b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * @remark Read the file COPYING 9b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * 10b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * @author Philippe Elie 11b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov */ 12b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 13ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifndef ODB_HASH_H 14ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define ODB_HASH_H 15ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 16ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <stddef.h> 17ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include <stdint.h> 18ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 19ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#include "op_list.h" 20ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 21ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** the type of key. 64-bit because CG needs 32-bit pair {from,to} */ 22ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef uint64_t odb_key_t; 23ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** the type of an information in the database */ 24ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef unsigned int odb_value_t; 25ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** the type of index (node number), list are implemented through index */ 26ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef unsigned int odb_index_t; 27ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** the type store node number */ 28ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef odb_index_t odb_node_nr_t; 29ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** store the hash mask, hash table size are always power of two */ 30ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef odb_index_t odb_hash_mask_t; 31ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 32ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/* there is (bucket factor * nr node) entry in hash table, this can seem 33ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * excessive but hash coding eip don't give a good distributions and our 34ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * goal is to get a O(1) amortized insert time. bucket factor must be a 35ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * power of two. FIXME: see big comment in odb_hash_add_node, you must 36ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * re-enable zeroing hash table if BUCKET_FACTOR > 2 (roughly exact, you 37ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * want to read the comment in odb_hash_add_node() if you tune this define) 38ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 39ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#define BUCKET_FACTOR 1 40ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 41ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** a db hash node */ 42ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct { 43ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_key_t key; /**< eip */ 44ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_value_t value; /**< samples count */ 45ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_index_t next; /**< next entry for this bucket */ 46ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} odb_node_t; 47ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 48ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** the minimal information which must be stored in the file to reload 49ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * properly the data base, following this header is the node array then 50ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * the hash table (when growing we avoid to copy node array) 51ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 52ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct { 53ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_node_nr_t size; /**< in node nr (power of two) */ 54ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_node_nr_t current_size; /**< nr used node + 1, node 0 unused */ 55ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown int padding[6]; /**< for padding and future use */ 56ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} odb_descr_t; 57ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 58ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown/** a "database". this is an in memory only description. 59ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 60ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * We allow to manage a database inside a mapped file with an "header" of 61ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * unknown size so odb_open get a parameter to specify the size of this header. 62ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * A typical use is: 63ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 64ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * struct header { int etc; ... }; 65ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * odb_open(&hash, filename, ODB_RW, sizeof(header)); 66ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * so on this library have no dependency on the header type. 67ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * 68ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * the internal memory layout from base_memory is: 69ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * the unknown header (sizeof_header) 70ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * odb_descr_t 71ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * the node array: (descr->size * sizeof(odb_node_t) entries 72ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * the hash table: array of odb_index_t indexing the node array 73ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * (descr->size * BUCKET_FACTOR) entries 74ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 75ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Browntypedef struct odb_data { 76ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_node_t * node_base; /**< base memory area of the page */ 77ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_index_t * hash_base; /**< base memory of hash table */ 78ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_descr_t * descr; /**< the current state of database */ 79ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown odb_hash_mask_t hash_mask; /**< == descr->size - 1 */ 80ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned int sizeof_header; /**< from base_memory to odb header */ 81ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown unsigned int offset_node; /**< from base_memory to node array */ 82ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown void * base_memory; /**< base memory of the maped memory */ 83b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov int fd; /**< mmaped memory file descriptor */ 84b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov char * filename; /**< full path name of sample file */ 85b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov int ref_count; /**< reference count */ 86b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov struct list_head list; /**< hash bucket list */ 87b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} odb_data_t; 88b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 89b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovtypedef struct { 90b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov odb_data_t * data; 91b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov} odb_t; 92b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 93b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov#ifdef __cplusplus 94b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovextern "C" { 95b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov#endif 96b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 97b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/* db_manage.c */ 98b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 99436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** how to open the DB file */ 100436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovenum odb_rw { 101436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov ODB_RDONLY = 0, /**< open for read only */ 102436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov ODB_RDWR = 1 /**< open for read and/or write */ 103436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov}; 104436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 105436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** 106436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * odb_init - initialize a DB file 107436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param odb the DB file to init 108436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov */ 109436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid odb_init(odb_t * odb); 110436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 111436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** 112436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * odb_open - open a DB file 113436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param odb the data base object to setup 114436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param filename the filename where go the maped memory 115436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param rw \enum ODB_RW if opening for writing, else \enum ODB_RDONLY 116436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param sizeof_header size of the file header if any 117b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * 118b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * The sizeof_header parameter allows the data file to have a header 119b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * at the start of the file which is skipped. 120b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * odb_open() always preallocate a few number of pages. 121b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov * returns 0 on success, errno on failure 122b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov */ 123b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovint odb_open(odb_t * odb, char const * filename, 124b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov enum odb_rw rw, size_t sizeof_header); 125b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 126b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/** Close the given ODB file */ 127b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovvoid odb_close(odb_t * odb); 128b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov 129b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanov/** return the number of times this sample file is open */ 130b32f58018498ea2225959b0ba11c18f0c433deefEvgeniy Stepanovint odb_open_count(odb_t const * odb); 131663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 132436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** return the start of the mapped data */ 133436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid * odb_get_data(odb_t * odb); 134663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 135663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng/** issue a msync on the used size of the mmaped file */ 136436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid odb_sync(odb_t const * odb); 137663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 138663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng/** 139436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * grow the hashtable in such way current_size is the index of the first free 140436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * node. Take care all node pointer can be invalidated by this call. 141436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 142436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * Node allocation is done in a two step way 1st) ensure a free node exist 143436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * eventually, caller can setup it, 2nd) commit the node allocation with 144436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * odb_commit_reservation(). 145436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * This is done in this way to ensure node setup is visible from another 146436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * process like pp tools in an atomic way. 147436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 148436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * returns 0 on success, non zero on failure in this case this function do 149436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * nothing and errno is set by the first libc call failure allowing to retry 150663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng * after cleanup some program resource. 151436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov */ 152663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengint odb_grow_hashtable(odb_data_t * data); 153663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng/** 154436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * commit a previously successfull node reservation. This can't fail. 155663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng */ 156663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengstatic __inline void odb_commit_reservation(odb_data_t * data) 157663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng{ 158663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng ++data->descr->current_size; 159436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov} 160663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng 161663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng/** "immpossible" node number to indicate an error from odb_hash_add_node() */ 162436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov#define ODB_NODE_NR_INVALID ((odb_node_nr_t)-1) 163436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 164436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* db_debug.c */ 165436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** check that the hash is well built */ 166436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint odb_check_hash(odb_t const * odb); 167436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 168436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* db_stat.c */ 169663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengtypedef struct odb_hash_stat_t odb_hash_stat_t; 170663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengodb_hash_stat_t * odb_hash_stat(odb_t const * odb); 171436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid odb_hash_display_stat(odb_hash_stat_t const * stats); 172436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovvoid odb_hash_free_stat(odb_hash_stat_t * stats); 173436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 174436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* db_insert.c */ 175436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** update info at key by incrementing its associated value by one, 176436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * if the key does not exist a new node is created and the value associated 177436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * is set to one. 178436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 179436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * returns EXIT_SUCCESS on success, EXIT_FAILURE on failure 180436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov */ 181436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint odb_update_node(odb_t * odb, odb_key_t key); 182436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 183436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** 184436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * odb_update_node_with_offset 185436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param odb the data base object to setup 186436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param key the hash key 187436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * @param offset the offset to be added 188436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 189436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * update info at key by adding the specified offset to its associated value, 190436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * if the key does not exist a new node is created and the value associated 191436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * is set to offset. 192436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 193436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * returns EXIT_SUCCESS on success, EXIT_FAILURE on failure 194436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov */ 195436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint odb_update_node_with_offset(odb_t * odb, 196436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov odb_key_t key, 197436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov unsigned long int offset); 198436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 199436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** Add a new node w/o regarding if a node with the same key already exists 200436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 201436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * returns EXIT_SUCCESS on success, EXIT_FAILURE on failure 202436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov */ 203436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanovint odb_add_node(odb_t * odb, odb_key_t key, odb_value_t value); 204436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov 205436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/* db_travel.c */ 206436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov/** 207436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * return a base pointer to the node array and number of node in this array 208436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * caller then will iterate through: 209436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 210436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * odb_node_nr_t node_nr, pos; 211436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * odb_node_t * node = odb_get_iterator(odb, &node_nr); 212436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * for ( pos = 0 ; pos < node_nr ; ++pos) 213436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * // do something 214436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * 215436e89c602e787e7a27dd6624b09beed41a0da8aDmitriy Ivanov * note than caller does not need to filter nil key as it's a valid key, 216663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng * The returned range is all valid (i.e. should never contain zero value). 217663860b1408516d02ebfcb3a9999a134e6cfb223Ben Cheng */ 218663860b1408516d02ebfcb3a9999a134e6cfb223Ben Chengodb_node_t * odb_get_iterator(odb_t const * odb, odb_node_nr_t * nr); 219ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 220ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownstatic __inline unsigned int 221ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brownodb_do_hash(odb_data_t const * data, odb_key_t value) 222ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown{ 223ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* FIXME: better hash for eip value, needs to instrument code 224ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * and do a lot of tests ... */ 225ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown /* trying to combine high order bits his a no-op: inside a binary image 226ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * high order bits don't vary a lot, hash table start with 7 bits mask 227ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * so this hash coding use bits 0-7, 8-15. Hash table is stored in 228ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * files avoiding to rebuilding them at profiling re-start so 229ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown * on changing do_hash() change the file format! 230ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown */ 231ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown uint32_t temp = value & 0xffffffff; 232ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown return ((temp << 0) ^ (temp >> 8)) & data->hash_mask; 233ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 234ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 235ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#ifdef __cplusplus 236ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown} 237ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif 238ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown 239ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown#endif /* !ODB_H */ 240ed07e00d438c74b7a23c01bfffde77e3968305e4Jeff Brown