iframe-proxy | Sunbelt Computer Software

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

#ifndef ROW_CACHE_H

#define ROW_CACHE_H

#include <vector>

#include <numeric>

#include <algorithm>

#include <stdexcept>

/**

cache structure adapted to the existing access patterns in

SqliteTableModel. handles many large segments with gaps in between

well.

logical structure resembling a std::vector<std::optional<T>>, but

implementation avoids actually allocating space for the non-empty

optionals, and supports (hopefully) more efficient insertion /

deletion.

actually, this is not even a "cache" - once set, elements are never

thrown away to make space for new elements.

TODO introduce maximum segment size?

**/

template <typename T>

class RowCache

{

public:

using value_type = T;

/// constructs an empty cache

explicit RowCache ();

/// \returns number of cached rows

size_t numSet () const;

/// \returns number of segments

size_t numSegments () const;

/// \returns 1 if specified row is loaded, 0 otherwise

size_t count (size_t pos) const;

/// \returns specified row. \throws if not available

const T & at (size_t pos) const;

T & at (size_t pos);

/// assigns value to specified row; may increase numSet() by one

void set (size_t pos, T && value);

/// insert new element; increases numSet() by one

void insert (size_t pos, T && value);

/// delete element; decreases numSet() by one

void erase (size_t pos);

/// reset to state after construction

void clear ();

/// given a range of rows (end is exclusive), narrow it in order

/// to remove already-loaded rows from both ends.

void smallestNonAvailableRange (size_t & row_begin, size_t & row_end) const;

private:

/// a single segment containing contiguous entries

struct Segment

{

size_t pos_begin;

std::vector<T> entries;

/// returns past-the-end position of this segment

size_t pos_end () const { return pos_begin + entries.size(); }

};

/// collection of non-overlapping segments, in order of increasing

/// position

using Segments = std::vector<Segment>;

Segments segments;

// ------------------------------------------------------------------------------

/// \returns first segment that definitely cannot contain 'pos',

/// because it starts at some later position.

typename Segments::const_iterator getSegmentBeyond (size_t pos) const {

// first segment whose pos_begin > pos (so can't contain pos itself):

return std::upper_bound(segments.begin(), segments.end(), pos, pred);

}

typename Segments::iterator getSegmentBeyond (size_t pos) {

return std::upper_bound(segments.begin(), segments.end(), pos, pred);

}

static bool pred (size_t pos, const Segment & s) { return pos < s.pos_begin; }

// ------------------------------------------------------------------------------

/// \returns segment containing 'pos'

typename Segments::const_iterator getSegmentContaining (size_t pos) const

{

auto it = getSegmentBeyond(pos);

if(it != segments.begin()) {

auto prev_it = it - 1;

if(pos < prev_it->pos_end())

return prev_it;

}

return segments.end();

}

};

template <typename T>

RowCache<T>::RowCache ()

{

}

template <typename T>

size_t RowCache<T>::numSet () const

{

return std::accumulate(segments.begin(), segments.end(), size_t(0),

[](size_t r, const Segment & s) { return r + s.entries.size(); });

}

template <typename T>

size_t RowCache<T>::numSegments () const

{

return segments.size();

}

template <typename T>

size_t RowCache<T>::count (size_t pos) const

{

return getSegmentContaining(pos) != segments.end();

}

template <typename T>

const T & RowCache<T>::at (size_t pos) const

{

auto it = getSegmentContaining(pos);

if(it != segments.end())

return it->entries[pos - it->pos_begin];

throw std::out_of_range("no matching segment found");

}

template <typename T>

T & RowCache<T>::at (size_t pos)

{

return const_cast<T&>(static_cast<const RowCache &>(*this).at(pos));

}

template <typename T>

void RowCache<T>::set (size_t pos, T && value)

{

auto it = getSegmentBeyond(pos);

if(it != segments.begin())

{

auto prev_it = it - 1;

auto d = pos - prev_it->pos_begin; // distance from segment start (>=0)

if(d < prev_it->entries.size())

{

// replace value

prev_it->entries[d] = std::move(value);

return;

}

if(d == prev_it->entries.size())

{

// extend existing segment

prev_it->entries.insert(prev_it->entries.end(), std::move(value));

return;

}

// make new segment

segments.insert(it, { pos, { std::move(value) } });

}

template <typename T>

void RowCache<T>::insert (size_t pos, T && value)

{

auto it = getSegmentBeyond(pos);

if(it != segments.begin())

{

auto prev_it = it - 1;

auto d = pos - prev_it->pos_begin; // distance from segment start (>=0)

if(d <= prev_it->entries.size())

{

// can extend existing segment

prev_it->entries.insert(prev_it->entries.begin() + d, std::move(value));

goto push;

}

// make new segment

it = segments.insert(it, { pos, { std::move(value) } }) + 1;

push:

// push back all later segments

std::for_each(it, segments.end(), [](Segment &s){ s.pos_begin++; });

}

template <typename T>

void RowCache<T>::erase (size_t pos)

{

auto it = getSegmentBeyond(pos);

// if previous segment actually contains pos, shorten it

if(it != segments.begin())

{

auto prev_it = it - 1;

auto d = pos - prev_it->pos_begin; // distance from segment start (>=0)

if(d < prev_it->entries.size())

{

prev_it->entries.erase(prev_it->entries.begin() + d);

if(prev_it->entries.empty())

{

it = segments.erase(prev_it);

}

// pull forward all later segments

std::for_each(it, segments.end(), [](Segment &s){ s.pos_begin--; });

}

template <typename T>

void RowCache<T>::clear ()

{

segments.clear();

}

template <typename T>

void RowCache<T>::smallestNonAvailableRange (size_t & row_begin, size_t & row_end) const

{

if(row_end < row_begin)

throw std::invalid_argument("end must be >= begin");

while(row_begin < row_end) {

auto it = getSegmentContaining(row_begin);

if(it == segments.end())

break;

row_begin = it->pos_end();

}

while(row_end > row_begin) {

auto it = getSegmentContaining(row_end - 1);

if(it == segments.end())

break;

row_end = it->pos_begin;

}

if(row_end < row_begin)

row_end = row_begin;

}

#endif // SEGMENTING_CACHE_H

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Repository navigation

RowCache.h

RowCache.h

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

RowCache.h

Latest commit

History

RowCache.h

File metadata and controls