1 /** @file 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 GlassFLCursor()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 swap(GlassFLCursor & o)48 void swap(GlassFLCursor &o) { 49 std::swap(n, o.n); 50 std::swap(c, o.c); 51 } 52 pack(std::string & buf)53 void pack(std::string & buf) { 54 pack_uint(buf, n); 55 pack_uint(buf, c / 4); 56 } 57 unpack(const char ** p,const char * end)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, uint8_t * p); 72 73 void write_block(const GlassTable * B, uint4 n, uint8_t * 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 uint8_t * p; 87 88 /// Current freelist block we're writing. 89 uint8_t * pw; 90 91 public: GlassFreeList()92 GlassFreeList() { 93 revision = 0; 94 first_unused_block = 0; 95 flw_appending = false; 96 p = pw = NULL; 97 } 98 reset()99 void reset() { 100 revision = 0; 101 first_unused_block = 0; 102 flw_appending = false; 103 } 104 ~GlassFreeList()105 ~GlassFreeList() { delete [] p; delete [] pw; } 106 empty()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 get_revision()116 uint4 get_revision() const { return revision; } set_revision(uint4 revision_)117 void set_revision(uint4 revision_) { revision = revision_; } 118 get_first_unused_block()119 uint4 get_first_unused_block() const { return first_unused_block; } 120 121 // Used when compacting to a single file. set_first_unused_block(uint4 base)122 void set_first_unused_block(uint4 base) { first_unused_block = base; } 123 124 void commit(const GlassTable * B, uint4 block_size); 125 pack(std::string & buf)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 unpack(const char ** pstart,const char * end)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 unpack(const std::string & s)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 ~GlassFreeListChecker()167 ~GlassFreeListChecker() { 168 delete [] bitmap; 169 } 170 mark_used(uint4 n)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 186