/*
* sbit.cpp
- * serp++
+ * binmap, a hybrid of bitmap and binary tree
*
* Created by Victor Grishchenko on 3/28/09.
* Copyright 2009 Delft University of Technology. All rights reserved.
#define BINS_H
#include "bin64.h"
-/** A binmap covering 2^64 range. Complexity limit: 100+200LoC */
-class bins {
+class iterator; // FIXME shame
+
+/** A binmap covering 2^64 range. Binmap is a hybrid of a bitmap (aka
+ bit vector) and a binary tree. The key ability of a binmap is
+ the aggregation of solid (all-0 or all-1) ranges. */
+class binmap_t {
public:
- typedef enum { FILLED=0xffff, EMPTY=0x0000 } fill_t;
+ /** Need a 3-valued logic as a range might be either all-0 or all-1
+ or some mix. In fact, any value different from 0x0 or 0xffff
+ must be interpreted as MIXED.
+ All read/write operations on a binmap are made in terms of
+ aligned binary intervals (bins).
+ */
+ typedef enum { FILLED=0xffff, EMPTY=0x0000, MIXED=0x5555 } fill_t;
static const int NOJOIN;
- bins();
+ binmap_t();
- bins(const bins& b);
+ /** Copying constructor. */
+ binmap_t(const binmap_t& b);
+ /** Destructor. */
+ ~binmap_t();
+
+ /** Get value for the bin. */
uint16_t get (bin64_t bin);
+ /** Set value for the bin. */
void set (bin64_t bin, fill_t val=FILLED);
- void copy_range (bins& origin, bin64_t range);
-
+ typedef enum {
+ OR_OP,
+ AND_OP,
+ REMOVE_OP,
+ COPY_OP
+ } bin_op_t;
+
+ /** Copy a range from another binmap. */
+ void range_op (binmap_t& mask, bin64_t range, bin_op_t op);
+ void range_copy (binmap_t& mask, bin64_t range)
+ { range_op(mask, range, COPY_OP); }
+ void range_remove (binmap_t& mask, bin64_t range)
+ { range_op(mask, range, REMOVE_OP); }
+ void range_or (binmap_t& mask, bin64_t range)
+ { range_op(mask, range, OR_OP); }
+ void range_and (binmap_t& mask, bin64_t range)
+ { range_op(mask, range, AND_OP); }
+
+ /** Find the leftmost bin within the specified range which is
+ either filled or empty. */
bin64_t find (const bin64_t range, fill_t seek=EMPTY) ;
+ /** Find the leftmost bin within the specified range which is
+ either filled or empty. Bins set to 1 in the filter binmap cannot
+ be returned. In fact, this is an incremental bitwise op. */
bin64_t find_filtered
- (bins& filter, bin64_t range, fill_t seek=EMPTY) ;
+ (binmap_t& filter, bin64_t range, fill_t seek=EMPTY) ;
- void remove (bins& b);
+ /** Bitwise SUB; any bins set to one in the filter binmap should
+ be set to 0 in this binmap. */
+ void remove (binmap_t& filter);
void dump(const char* note);
+ /** Represent the binmap as a sequence of 0 and 1 stripes; for each
+ new stripe only the starting offset is given. The first stripe
+ is supposed to be empty (if the (0,0) bin is actually filled,
+ the next stripe will also start at 0). */
uint64_t* get_stripes (int& count);
+ /** Return the number of cells allocated in the binmap. */
uint32_t size() { return cells_allocated; }
uint64_t seq_length ();
+ /** Return the topmost solid bin which covers the specified bin. */
bin64_t cover(bin64_t val);
uint64_t mass ();
- bool is_empty () const { return !deep(0) && !halves[0]; }
+ /** Return true if the range is solid (either all-0 or 1). If val is
+ specified, the interval must be both solid and filled/empty,
+ depending on the value. */
+ bool is_solid (bin64_t range=bin64_t::ALL, fill_t val=MIXED) ;
+ /** Whether range/bin is empty. */
+ bool is_empty (bin64_t range=bin64_t::ALL) { return is_solid(range,EMPTY); }
+ /** Whether range/bin is filled. */
+ bool is_filled (bin64_t range=bin64_t::ALL) { return is_solid(range,FILLED); }
+ /** Clear everything, empty all bins. */
void clear ();
+ /** Returns whether the int is mixed (not all-1 or all-0). */
static bool is_mixed (uint16_t val) { return val!=EMPTY && val!=FILLED; }
+ /** Returns whether the int is solid (0x0 or 0xffff). */
+ static bool is_solid (uint16_t val) { return val==EMPTY || val==FILLED; }
+ /** Twisting is some generalization of XOR. For every 1-bit in the mask,
+ the respective layer of the binary tree is flipped, i.e. left and
+ right change places. Twisting is mostly needed for randomization. */
void twist (uint64_t mask);
+ /** Convert binmap to a conventional flat bitmap; only bits corresponding
+ to solid filled bins are set to 1.
+ @param range the bin (the range) to cover
+ @param height aggregation level; use 2**height bins (2**height base
+ layer bits per one bitmap bit).
+ @param bits uint16_t array to put bitmap into; must have enough
+ of space, i.e. 2**(range.layer()-height-4) cells. */
+ void to_coarse_bitmap (uint16_t* bits, bin64_t range, uint8_t height);
+
private:
/** Every 16th uint32 is a flag field denoting whether
uint32_t blocks_allocated;
uint32_t cells_allocated;
int height;
- uint32_t ap;
uint64_t twist_mask;
+ uint16_t free_top;
void extend();
static uint32_t split16to32(uint16_t half);
static int join32to16(uint32_t cell);
+
+ void map16 (uint16_t* target, bin64_t range);
friend class iterator;
#ifdef FRIEND_TEST
or FILLED/EMPTY. */
class iterator {
public: // rm this
- bins *host;
+ binmap_t *host;
uint32_t history[64];
uint32_t half;
uint8_t layer_;
bin64_t pos; // TODO: half[] layer bin
public:
- iterator(bins* host, bin64_t start=bin64_t(0,0), bool split=false);
+ iterator(binmap_t* host, bin64_t start=bin64_t(0,0), bool split=false);
~iterator();
bool deep () { return host->deep(half); }
bool solid () {
- return !deep() && (host->halves[half]==bins::FILLED ||
- host->halves[half]==bins::EMPTY);
+ return !deep() && binmap_t::is_solid(host->halves[half]);
}
void sibling () { half^=1; pos=pos.sibling(); }
bool end () { return half==1; }
void right() {to(1);}
/** Move to the next defined (non-deep, flat) cell.
If solid==true, move to a solid (0xffff/0x0) cell. */
- bin64_t next (bool solid=false);
+ bin64_t next (bool stop_undeep=true, bool stop_solid=false, uint8_t stop_layer=0);
+ bin64_t next_solid () { return next(false, true,0); }
bin64_t bin() { return pos; }
void towards(bin64_t bin) {
bin64_t next = pos.towards(bin);
projects / swift-upb.git / blobdiff