/* This file is part of Jellyfish. Jellyfish is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. Jellyfish is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Jellyfish. If not, see . */ #ifndef __JELLYFISH_OFFSETS_KEY_VALUE_HPP__ #define __JELLYFISH_OFFSETS_KEY_VALUE_HPP__ #include #include #include namespace jellyfish { /* A word is whatever aligned type used for atomic operations * (CAS). Typically, a uint64_t. We store pairs of (key, value), in a * bit packed fashion. The key and value can have abritrary size as * long as they each fit in one word. A block is the largest number of * (key, value) pair such that the first key, and only the first, * starts at an aligned word. * * The key 0x0 is not valid. A key which fits completely within one * word is not protected by a "set" bit. A key which straddle the * boundary between two aligned words has a set bit in each parts. * * A value field can have any value and is initialized to 0x0. It has * no "set" bit ever. * * A key is prefixed with a "large" bit. If this bit is 0, the key * field is length key_len (not counting the possible set bits) and * the value field has length val_len. If the large bit has value 1, * the key field is just long enough to encode the number of * reprobing hops to go backward to find the actual key. The * remainder bits is used for the value field. In this scheme, we * assume the length needed to encode the number of reprobes is much * less than the length needed to encode the key. */ /* Offsets holds all the possible offset for a given combination of * key length, value length and reprobe limit. */ template class Offsets { public: // woff: offset in words from beginning of block // boff: offset in bits within that word. Past large bit. // shift: shift in second word, if any // mask1: includes the large bit and the set bit if any. // mask2: mask in second word. Idem as mask1. 0 if fits in one word. // sb_mask[12]: mask for set bit in word 1 and 2, if any. set bit is the // last usable bit of the field. // lb_mask: mask for the large bit. It is the first bit of the key field. typedef struct { struct { uint_t woff, boff, shift, cshift; word mask1, mask2, sb_mask1, sb_mask2, lb_mask; } key; struct { uint_t woff, boff, shift, cshift; word mask1, mask2; } val; } offset_t; typedef struct { offset_t normal; offset_t large; } offset_pair_t; struct block_info { uint_t len; uint_t word_len; }; // Offsets() {} Offsets(uint_t _key_len, uint_t _val_len, uint_t _reprobe_limit) : key_len(_key_len), val_len(_val_len), reprobe_limit(_reprobe_limit), reprobe_len(bitsize(reprobe_limit)), lval_len(key_len + val_len - reprobe_len), block(compute_offsets()), bld(block.len) { } ~Offsets() {} uint_t get_block_len() const { return block.len; } uint_t get_block_word_len() const { return block.word_len; } uint_t get_reprobe_len() const { return reprobe_len; } uint_t get_key_len() const { return key_len; } uint_t get_val_len() const { return val_len; } uint_t get_lval_len() const { return lval_len; } word get_max_val(bool large) const { return (((uint64_t)1) << (large ? lval_len : val_len)) - 1; } // Discretize and round down number of entries according to length // of a block. Return in blocks the number of blocks. size_t floor_block(size_t entries, size_t &blocks) const { blocks = entries / bld; return block.len * blocks; } word *get_word_offset(size_t id, const offset_t **o, const offset_t **lo, word * const base) const { uint64_t q, r; bld.division(id, q, r); word *w = base + (block.word_len * q); *o = &offsets[r].normal; *lo = &offsets[r].large; return w; } private: const uint_t key_len, val_len; const uint_t reprobe_limit, reprobe_len, lval_len; const block_info block; const divisor64 bld; // Fast divisor by block.len offset_pair_t offsets[bsizeof(word)]; block_info compute_offsets(); bool update_current_offsets(uint_t &cword, uint_t &cboff, uint_t add); word mask(uint_t length, uint_t shift); }; template bool Offsets::update_current_offsets(uint_t &cword, uint_t &cboff, uint_t add) { cboff += add; if(cboff >= bsizeof(word)) { cword++; cboff %= bsizeof(word); return cboff > 0; } return false; } template word Offsets::mask(uint_t length, uint_t shift) { return (((word)1u << length) - 1) << shift; } template typename Offsets::block_info Offsets::compute_offsets() { offset_pair_t *offset = offsets; uint_t cword = 0; // current word in block uint_t cboff = 0; // current offset in word uint_t lcword; // idem for large fields uint_t lcboff; uint_t ocboff; memset(offsets, '\0', sizeof(offsets)); do { offset->normal.key.woff = offset->large.key.woff = lcword = cword; ocboff = lcboff = cboff; offset->normal.key.boff = cboff + 1; offset->normal.key.lb_mask = mask(1, cboff); if(update_current_offsets(cword, cboff, key_len + 1)) { // key extends over two words -> add extra set bits update_current_offsets(cword, cboff, 2); offset->normal.key.mask1 = mask(bsizeof(word) - ocboff, ocboff); offset->normal.key.mask2 = mask(cboff, 0); offset->normal.key.shift = key_len + 1 - cboff; offset->normal.key.cshift = cboff - 1; offset->normal.key.sb_mask1 = mask(1, bsizeof(word) - 1); offset->normal.key.sb_mask2 = mask(1, cboff - 1); } else { offset->normal.key.mask1 = mask(key_len + 1, ocboff); offset->normal.key.mask2 = 0; offset->normal.key.shift = 0; offset->normal.key.cshift = 0; offset->normal.key.sb_mask1 = 0; offset->normal.key.sb_mask2 = 0; } offset->normal.val.woff = cword; offset->normal.val.boff = cboff; offset->normal.val.mask1 = mask(val_len, cboff); if(update_current_offsets(cword, cboff, val_len)) { offset->normal.val.mask2 = mask(cboff, 0); offset->normal.val.shift = val_len - cboff; offset->normal.val.cshift = cboff; } else { offset->normal.val.mask2 = 0; offset->normal.val.shift = val_len; offset->normal.val.cshift = 0; } ocboff = lcboff; offset->large.key.boff = lcboff + 1; offset->large.key.lb_mask = mask(1, lcboff); if(update_current_offsets(lcword, lcboff, reprobe_len + 1)) { update_current_offsets(lcword, lcboff, 2); offset->large.key.mask1 = mask(bsizeof(word) - ocboff, ocboff); offset->large.key.mask2 = mask(lcboff, 0); offset->large.key.shift = reprobe_len + 1 - lcboff; offset->large.key.cshift = lcboff - 1; offset->large.key.sb_mask1 = mask(1, bsizeof(word) - 1); offset->large.key.sb_mask2 = mask(1, lcboff - 1); } else { offset->large.key.mask1 = mask(reprobe_len + 1, ocboff); offset->large.key.mask2 = 0; offset->large.key.boff = ocboff + 1; offset->large.key.shift = 0; offset->large.key.cshift = 0; offset->large.key.sb_mask1 = 0; offset->large.key.sb_mask2 = 0; } offset->large.val.woff = lcword; offset->large.val.boff = lcboff; offset->large.val.mask1 = mask(lval_len, lcboff); if(update_current_offsets(lcword, lcboff, lval_len)) { offset->large.val.mask2 = mask(lcboff, 0); offset->large.val.shift = lval_len - lcboff; offset->large.val.cshift = lcboff; } else { offset->large.val.mask2 = 0; offset->large.val.shift = lval_len; offset->large.val.cshift = 0; } offset++; } while(cboff != 0 && cboff < bsizeof(word) - 2); block_info res = { static_cast(offset - offsets), cword + (cboff == 0 ? 0 : 1) }; return res; } } #endif // __OFFSETS_KEY_VALUE_HPP__