xapian-core/backends/glass/glass_freelist.h

   1 /** @file glass_freelist.h
   2  * @brief Glass freelist
   3  */
   4 /* Copyright 2014 Olly Betts
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2 of the
   9  * License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
  19  * USA
  20  */
  21
  22 #ifndef XAPIAN_INCLUDED_GLASS_FREELIST_H
  23 #define XAPIAN_INCLUDED_GLASS_FREELIST_H
  24
  25 #include "glass_defs.h"
  26 #include "pack.h"
  27
  28 class GlassTable;
  29
  30 class GlassFLCursor {
  31   public:
  32     /// Block number of current freelist chunk.
  33     uint4 n;
  34
  35     /// Current offset in block.
  36     unsigned c;
  37
  38     GlassFLCursor() : n(0), c(0) { }
  39
  40     bool operator==(const GlassFLCursor & o) const {
  41         return n == o.n && c == o.c;
  42     }
  43
  44     bool operator!=(const GlassFLCursor & o) const {
  45         return !(*this == o);
  46     }
  47
  48     void swap(GlassFLCursor &o) {
  49         std::swap(n, o.n);
  50         std::swap(c, o.c);
  51     }
  52
  53     void pack(std::string & buf) {
  54         pack_uint(buf, n);
  55         pack_uint(buf, c / 4);
  56     }
  57
  58     bool unpack(const char ** p, const char * end) {
  59         bool r = unpack_uint(p, end, &n) && unpack_uint(p, end, &c);
  60         if (usual(r))
  61             c *= 4;
  62         return r;
  63     }
  64 };
  65
  66 class GlassFreeList {
  67     GlassFreeList(const GlassFreeList &);
  68
  69     void operator=(const GlassFreeList &);
  70
  71     void read_block(const GlassTable * B, uint4 n, byte * p);
  72
  73     void write_block(const GlassTable * B, uint4 n, byte * p, uint4 rev);
  74
  75   protected:
  76     uint4 revision;
  77
  78     uint4 first_unused_block;
  79
  80     GlassFLCursor fl, fl_end, flw;
  81
  82     bool flw_appending;
  83
  84   private:
  85     /// Current freelist block.
  86     byte * p;
  87
  88     /// Current freelist block we're writing.
  89     byte * pw;
  90
  91   public:
  92     GlassFreeList() {
  93         revision = 0;
  94         first_unused_block = 0;
  95         flw_appending = false;
  96         p = pw = NULL;
  97     }
  98
  99     void reset() {
 100         revision = 0;
 101         first_unused_block = 0;
 102         flw_appending = false;
 103     }
 104
 105     ~GlassFreeList() { delete [] p; delete [] pw; }
 106
 107     bool empty() const { return fl == fl_end; }
 108
 109     uint4 get_block(const GlassTable * B, uint4 block_size,
 110                     uint4 * blk_to_free = NULL);
 111
 112     uint4 walk(const GlassTable *B, uint4 block_size, bool inclusive);
 113
 114     void mark_block_unused(const GlassTable * B, uint4 block_size, uint4 n);
 115
 116     uint4 get_revision() const { return revision; }
 117     void set_revision(uint4 revision_) { revision = revision_; }
 118
 119     uint4 get_first_unused_block() const { return first_unused_block; }
 120
 121     // Used when compacting to a single file.
 122     void set_first_unused_block(uint4 base) { first_unused_block = base; }
 123
 124     void commit(const GlassTable * B, uint4 block_size);
 125
 126     void pack(std::string & buf) {
 127         pack_uint(buf, revision);
 128         pack_uint(buf, first_unused_block);
 129         fl.pack(buf);
 130         flw.pack(buf);
 131     }
 132
 133     bool unpack(const char ** pstart, const char * end) {
 134         bool r = unpack_uint(pstart, end, &revision) &&
 135                  unpack_uint(pstart, end, &first_unused_block) &&
 136                  fl.unpack(pstart, end) &&
 137                  flw.unpack(pstart, end);
 138         if (r) {
 139             fl_end = flw;
 140             flw_appending = false;
 141         }
 142         return r;
 143     }
 144
 145     bool unpack(const std::string & s) {
 146         const char * ptr = s.data();
 147         const char * end = ptr + s.size();
 148         return unpack(&ptr, end) && ptr == end;
 149     }
 150 };
 151
 152 class GlassFreeListChecker {
 153     // FIXME: uint_fast32_t is probably a good choice.
 154     typedef unsigned long elt_type;
 155
 156     uint4 bitmap_size;
 157
 158     elt_type * bitmap;
 159
 160     // Prevent copying
 161     GlassFreeListChecker(const GlassFreeListChecker&);
 162     GlassFreeListChecker& operator=(const GlassFreeListChecker&);
 163
 164   public:
 165     explicit GlassFreeListChecker(const GlassFreeList & fl);
 166
 167     ~GlassFreeListChecker() {
 168         delete [] bitmap;
 169     }
 170
 171     bool mark_used(uint4 n) {
 172         const unsigned BITS_PER_ELT = sizeof(elt_type) * 8;
 173         elt_type mask = static_cast<elt_type>(1) << (n & (BITS_PER_ELT - 1));
 174         n /= BITS_PER_ELT;
 175         if (rare(n >= bitmap_size)) return false;
 176         if ((bitmap[n] & mask) == 0) return false;
 177         bitmap[n] &= ~mask;
 178         return true;
 179     }
 180
 181     /// Count how many bits are still set.
 182     uint4 count_set_bits(uint4 * p_first_bad_blk) const;
 183 };
 184
 185 #endif // XAPIAN_INCLUDED_GLASS_FREELIST_H