← Back to branch summary

~vadim-tk/percona-server/flushing-algo

« back to all changes in this revision

Viewing changes to storage/ndb/src/kernel/vm/LinearPool.hpp

  • Committer: root
  • Date: 2011-10-29 01:34:40 UTC
  • Revision ID: root@hppro1.office.percona.com-20111029013440-qhnf4jk8kdjcf4e0
Initial import

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/ndb/src/kernel/vm/LinearPool.hpp
 
1
/* Copyright (C) 2003 MySQL AB
 
2
 
 
3
   This program is free software; you can redistribute it and/or modify
 
4
   it under the terms of the GNU General Public License as published by
 
5
   the Free Software Foundation; version 2 of the License.
 
6
 
 
7
   This program is distributed in the hope that it will be useful,
 
8
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
9
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
10
   GNU General Public License for more details.
 
11
 
 
12
   You should have received a copy of the GNU General Public License
 
13
   along with this program; if not, write to the Free Software
 
14
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
15
 
 
16
#ifndef LINEAR_POOL_HPP
 
17
#define LINEAR_POOL_HPP
 
18
 
 
19
#include <Bitmask.hpp>
 
20
#include "SuperPool.hpp"
 
21
 
 
22
/*
 
23
 * LinearPool - indexed record pool
 
24
 *
 
25
 * LinearPool implements a pool where each record has a 0-based index.
 
26
 * Any index value (up to 2^32-1) is allowed.  Normal efficient usage is
 
27
 * to assign index values in sequence and to re-use any values which
 
28
 * have become free.  This is default seize/release behaviour.
 
29
 *
 
30
 * LinearPool has 2 internal RecordPool instances:
 
31
 *
 
32
 * (a) record pool of T (the template argument class)
 
33
 * (b) record pool of "maps" (array of Uint32)
 
34
 *
 
35
 * The maps translate an index into an i-value in (a).  Each map has
 
36
 * a level.  Level 0 maps point to i-values.  Level N+1 maps point to
 
37
 * level N maps.  There is a unique "root map" at top.
 
38
 *
 
39
 * This works exactly like numbers in a given base.  Each map has base
 
40
 * size entries.  For implementation convenience the base must be power
 
41
 * of 2 between 2^1 and 2^15.  It is given by its log2 value (1-15).
 
42
 *
 
43
 * A position in a map is also called a "digit".
 
44
 *
 
45
 * There is a doubly linked list of available maps (some free entries)
 
46
 * on each level.  There is a doubly linked freelist within each map.
 
47
 * There is also a bitmask of used entries in each map.
 
48
 *
 
49
 * Level 0 free entry has space for one record.  Level N free entry
 
50
 * implies space for base^N records.  The implied levels are created and
 
51
 * removed on demand.  Empty maps are usually removed.
 
52
 *
 
53
 * Default base is 256 (log2 = 8) which requires maximum 4 levels or
 
54
 * digits (similar to ip address).
 
55
 *
 
56
 * TODO
 
57
 *
 
58
 * - move most of the inline code to LinearPool.cpp
 
59
 * - optimize for common case
 
60
 * - add optimized 2-level implementation (?)
 
61
 */
 
62
 
 
63
#include "SuperPool.hpp"
 
64
 
 
65
template <class T, Uint32 LogBase = 8>
 
66
class LinearPool {
 
67
  typedef SuperPool::PtrI PtrI;
 
68
 
 
69
  // Base.
 
70
  STATIC_CONST( Base = 1 << LogBase );
 
71
 
 
72
  // Digit mask.
 
73
  STATIC_CONST( DigitMask = Base - 1 );
 
74
 
 
75
  // Max possible levels (0 to max root level).
 
76
  STATIC_CONST( MaxLevels = (32 + LogBase - 1) / LogBase );
 
77
 
 
78
  // Number of words in map used bit mask.
 
79
  STATIC_CONST( BitmaskSize = (Base + 31) / 32 );
 
80
 
 
81
  // Map.
 
82
  struct Map {
 
83
    Uint32 m_level;
 
84
    Uint32 m_occup;     // number of used entries
 
85
    Uint32 m_firstfree; // position of first free entry
 
86
    PtrI m_parent;      // parent map
 
87
    Uint32 m_index;     // from root to here
 
88
    PtrI m_nextavail;
 
89
    PtrI m_prevavail;
 
90
    Uint32 m_bitmask[BitmaskSize];
 
91
    PtrI m_entry[Base];
 
92
  };
 
93
 
 
94
public:
 
95
 
 
96
  // Constructor.
 
97
  LinearPool(GroupPool& gp);
 
98
 
 
99
  // Destructor.
 
100
  ~LinearPool();
 
101
 
 
102
  // Update pointer ptr.p according to index value ptr.i.
 
103
  void getPtr(Ptr<T>& ptr);
 
104
 
 
105
  // Allocate record from the pool.  Reuses free index if possible.
 
106
  bool seize(Ptr<T>& ptr);
 
107
 
 
108
  // Allocate given index.  Like seize but returns -1 if in use.
 
109
  int seize_index(Ptr<T>& ptr, Uint32 index);
 
110
 
 
111
  // Return record to the pool.
 
112
  void release(Ptr<T>& ptr);
 
113
 
 
114
  // Return number of used records (may require 1 page scan).
 
115
  Uint32 count();
 
116
 
 
117
  // Verify (debugging).
 
118
  void verify();
 
119
 
 
120
private:
 
121
 
 
122
  // Given index find the bottom map.
 
123
  void get_map(Ptr<Map>& map_ptr, Uint32 index);
 
124
 
 
125
  // Add new root map and increase level
 
126
  bool add_root();
 
127
 
 
128
  // Add new non-root map.
 
129
  bool add_map(Ptr<Map>& map_ptr, Ptr<Map> parent_ptr, Uint32 digit);
 
130
 
 
131
  // Subroutine to initialize map free lists.
 
132
  void init_free(Ptr<Map> map_ptr);
 
133
 
 
134
  // Add entry at given free position.
 
135
  void add_entry(Ptr<Map> map_ptr, Uint32 digit, PtrI ptr_i);
 
136
 
 
137
  // Remove entry and map if it becomes empty.
 
138
  void remove_entry(Ptr<Map> map_ptr, Uint32 digit);
 
139
 
 
140
  // Remove map and all parents which become empty.
 
141
  void remove_map(Ptr<Map> map_ptr);
 
142
 
 
143
  // Add map to available list.
 
144
  void add_avail(Ptr<Map> map_ptr);
 
145
 
 
146
  // Remove map from available list.
 
147
  void remove_avail(Ptr<Map> map_ptr);
 
148
 
 
149
  // Verify available lists
 
150
  void verify_avail();
 
151
 
 
152
  // Verify map (recursive).
 
153
  void verify_map(Ptr<Map> map_ptr, Uint32 level, Uint32* count);
 
154
 
 
155
  RecordPool<T> m_records;
 
156
  RecordPool<Map> m_maps;
 
157
  Uint32 m_levels;              // 0 means empty pool
 
158
  PtrI m_root;
 
159
  PtrI m_avail[MaxLevels];
 
160
};
 
161
 
 
162
template <class T, Uint32 LogBase>
 
163
inline
 
164
LinearPool<T, LogBase>::LinearPool(GroupPool& gp) :
 
165
  m_records(gp),
 
166
  m_maps(gp),
 
167
  m_levels(0),
 
168
  m_root(RNIL)
 
169
{
 
170
  Uint32 n;
 
171
  for (n = 0; n < MaxLevels; n++)
 
172
    m_avail[n] = RNIL;
 
173
}
 
174
 
 
175
template <class T, Uint32 LogBase>
 
176
inline
 
177
LinearPool<T, LogBase>::~LinearPool()
 
178
{
 
179
}
 
180
 
 
181
template <class T, Uint32 LogBase>
 
182
inline void
 
183
LinearPool<T, LogBase>::getPtr(Ptr<T>& ptr)
 
184
{
 
185
  Uint32 index = ptr.i;
 
186
  // get level 0 map
 
187
  Ptr<Map> map_ptr;
 
188
  get_map(map_ptr, index);
 
189
  // get record
 
190
  Ptr<T> rec_ptr;
 
191
  Uint32 digit = index & DigitMask;
 
192
  assert(BitmaskImpl::get(BitmaskSize, map_ptr.p->m_bitmask, digit));
 
193
  rec_ptr.i = map_ptr.p->m_entry[digit];
 
194
  m_records.getPtr(rec_ptr);
 
195
  ptr.p = rec_ptr.p;
 
196
}
 
197
 
 
198
template <class T, Uint32 LogBase>
 
199
inline bool
 
200
LinearPool<T, LogBase>::seize(Ptr<T>& ptr)
 
201
{
 
202
  // look for free list on some level
 
203
  Ptr<Map> map_ptr;
 
204
  map_ptr.i = RNIL;
 
205
  Uint32 n = 0;
 
206
  while (n < m_levels) {
 
207
    if ((map_ptr.i = m_avail[n]) != RNIL)
 
208
      break;
 
209
    n++;
 
210
  }
 
211
  if (map_ptr.i == RNIL) {
 
212
    // add new level with available maps
 
213
    if (! add_root())
 
214
      return false;
 
215
    assert(n < m_levels);
 
216
    map_ptr.i = m_avail[n];
 
217
  }
 
218
  m_maps.getPtr(map_ptr);
 
219
  // walk down creating missing levels and using an entry on each
 
220
  Uint32 digit;
 
221
  Ptr<Map> new_ptr;
 
222
  new_ptr.i = RNIL;
 
223
  while (true) {
 
224
    digit = map_ptr.p->m_firstfree;
 
225
    if (n == 0)
 
226
      break;
 
227
    Ptr<Map> child_ptr;
 
228
    if (! add_map(child_ptr, map_ptr, digit)) {
 
229
      if (new_ptr.i != RNIL)
 
230
        remove_map(new_ptr);
 
231
      return false;
 
232
    }
 
233
    new_ptr = child_ptr;
 
234
    map_ptr = child_ptr;
 
235
    n--;
 
236
  }
 
237
  // now on level 0
 
238
  assert(map_ptr.p->m_level == 0);
 
239
  Ptr<T> rec_ptr;
 
240
  if (! m_records.seize(rec_ptr)) {
 
241
    if (new_ptr.i != RNIL)
 
242
      remove_map(new_ptr);
 
243
    return false;
 
244
  }
 
245
  add_entry(map_ptr, digit, rec_ptr.i);
 
246
  ptr.i = digit + (map_ptr.p->m_index << LogBase);
 
247
  ptr.p = rec_ptr.p;
 
248
  return true;
 
249
}
 
250
 
 
251
template <class T, Uint32 LogBase>
 
252
inline int
 
253
LinearPool<T, LogBase>::seize_index(Ptr<T>& ptr, Uint32 index)
 
254
{
 
255
  // extract all digits at least up to current root level
 
256
  Uint32 digits[MaxLevels];
 
257
  Uint32 n = 0;
 
258
  Uint32 tmp = index;
 
259
  do {
 
260
    digits[n] = tmp & DigitMask;
 
261
    tmp >>= LogBase;
 
262
  } while (++n < m_levels || tmp != 0);
 
263
  // add any new root levels
 
264
  while (n > m_levels) {
 
265
    if (! add_root())
 
266
      return false;
 
267
  }
 
268
  // start from root
 
269
  Ptr<Map> map_ptr;
 
270
  map_ptr.i = m_root;
 
271
  m_maps.getPtr(map_ptr);
 
272
  // walk down creating or re-using existing levels
 
273
  Uint32 digit;
 
274
  bool used;
 
275
  Ptr<Map> new_ptr;
 
276
  new_ptr.i = RNIL;
 
277
  while (true) {
 
278
    digit = digits[--n];
 
279
    used = BitmaskImpl::get(BitmaskSize, map_ptr.p->m_bitmask, digit);
 
280
    if (n == 0)
 
281
      break;
 
282
    if (used) {
 
283
      map_ptr.i = map_ptr.p->m_entry[digit];
 
284
      m_maps.getPtr(map_ptr);
 
285
    } else {
 
286
      Ptr<Map> child_ptr;
 
287
      if (! add_map(child_ptr, map_ptr, digit)) {
 
288
        if (new_ptr.i != RNIL)
 
289
          remove_map(new_ptr);
 
290
      }
 
291
      new_ptr = child_ptr;
 
292
      map_ptr = child_ptr;
 
293
    }
 
294
  }
 
295
  // now at level 0
 
296
  assert(map_ptr.p->m_level == 0);
 
297
  Ptr<T> rec_ptr;
 
298
  if (used || ! m_records.seize(rec_ptr)) {
 
299
    if (new_ptr.i != RNIL)
 
300
      remove_map(new_ptr);
 
301
    return used ? -1 : false;
 
302
  }
 
303
  add_entry(map_ptr, digit, rec_ptr.i);
 
304
  assert(index == digit + (map_ptr.p->m_index << LogBase));
 
305
  ptr.i = index;
 
306
  ptr.p = rec_ptr.p;
 
307
  return true;
 
308
}
 
309
 
 
310
template <class T, Uint32 LogBase>
 
311
inline void
 
312
LinearPool<T, LogBase>::release(Ptr<T>& ptr)
 
313
{
 
314
  Uint32 index = ptr.i;
 
315
  // get level 0 map
 
316
  Ptr<Map> map_ptr;
 
317
  get_map(map_ptr, index);
 
318
  // release record
 
319
  Ptr<T> rec_ptr;
 
320
  Uint32 digit = index & DigitMask;
 
321
  rec_ptr.i = map_ptr.p->m_entry[digit];
 
322
  m_records.release(rec_ptr);
 
323
  // remove entry
 
324
  remove_entry(map_ptr, digit);
 
325
  // null pointer
 
326
  ptr.i = RNIL;
 
327
  ptr.p = 0;
 
328
}
 
329
 
 
330
template <class T, Uint32 LogBase>
 
331
inline Uint32
 
332
LinearPool<T, LogBase>::count()
 
333
{
 
334
  SuperPool& sp = m_records.m_superPool;
 
335
  Uint32 count1 = sp.getRecUseCount(m_records.m_recInfo);
 
336
  return count1;
 
337
}
 
338
 
 
339
template <class T, Uint32 LogBase>
 
340
inline void
 
341
LinearPool<T, LogBase>::verify()
 
342
{
 
343
  verify_avail();
 
344
  if (m_root == RNIL) {
 
345
    assert(m_levels == 0);
 
346
    return;
 
347
  }
 
348
  assert(m_levels != 0);
 
349
  Ptr<Map> map_ptr;
 
350
  map_ptr.i = m_root;
 
351
  m_maps.getPtr(map_ptr);
 
352
  Uint32 count1 = count();
 
353
  Uint32 count2 = 0;
 
354
  verify_map(map_ptr, m_levels - 1, &count2);
 
355
  assert(count1 == count2);
 
356
}
 
357
 
 
358
// private methods
 
359
 
 
360
template <class T, Uint32 LogBase>
 
361
inline void
 
362
LinearPool<T, LogBase>::get_map(Ptr<Map>& map_ptr, Uint32 index)
 
363
{
 
364
  // root map must exist
 
365
  Ptr<Map> tmp_ptr;
 
366
  tmp_ptr.i = m_root;
 
367
  m_maps.getPtr(tmp_ptr);
 
368
  assert(tmp_ptr.p->m_level + 1 == m_levels);
 
369
  // extract index digits up to current root level
 
370
  Uint32 digits[MaxLevels];
 
371
  Uint32 n = 0;
 
372
  do {
 
373
    digits[n] = index & DigitMask;
 
374
    index >>= LogBase;
 
375
  } while (++n < m_levels);
 
376
  assert(index == 0);
 
377
  // walk down indirect levels
 
378
  while (--n > 0) {
 
379
    tmp_ptr.i = tmp_ptr.p->m_entry[digits[n]];
 
380
    m_maps.getPtr(tmp_ptr);
 
381
  }
 
382
  // level 0 map
 
383
  assert(tmp_ptr.p->m_level == 0);
 
384
  map_ptr = tmp_ptr;
 
385
}
 
386
 
 
387
template <class T, Uint32 LogBase>
 
388
inline bool
 
389
LinearPool<T, LogBase>::add_root()
 
390
{
 
391
  // new root
 
392
  Ptr<Map> map_ptr;
 
393
  if (! m_maps.seize(map_ptr))
 
394
    return false;
 
395
  Uint32 n = m_levels++;
 
396
  assert(n < MaxLevels);
 
397
  // set up
 
398
  map_ptr.p->m_level = n;
 
399
  map_ptr.p->m_parent = RNIL;
 
400
  map_ptr.p->m_index = 0;
 
401
  init_free(map_ptr);
 
402
  // on level > 0 digit 0 points to old root
 
403
  if (n > 0) {
 
404
    Ptr<Map> old_ptr;
 
405
    old_ptr.i = m_root;
 
406
    m_maps.getPtr(old_ptr);
 
407
    assert(old_ptr.p->m_parent == RNIL);
 
408
    old_ptr.p->m_parent = map_ptr.i;
 
409
    add_entry(map_ptr, 0, old_ptr.i);
 
410
  }
 
411
  // set new root
 
412
  m_root = map_ptr.i;
 
413
  return true;
 
414
}
 
415
 
 
416
template <class T, Uint32 LogBase>
 
417
inline bool
 
418
LinearPool<T, LogBase>::add_map(Ptr<Map>& map_ptr, Ptr<Map> parent_ptr, Uint32 digit)
 
419
{
 
420
  if (! m_maps.seize(map_ptr))
 
421
    return false;
 
422
  assert(parent_ptr.p->m_level != 0);
 
423
  // set up
 
424
  map_ptr.p->m_level = parent_ptr.p->m_level - 1;
 
425
  map_ptr.p->m_parent = parent_ptr.i;
 
426
  map_ptr.p->m_index = digit + (parent_ptr.p->m_index << LogBase);
 
427
  init_free(map_ptr);
 
428
  add_entry(parent_ptr, digit, map_ptr.i);
 
429
  return true;
 
430
}
 
431
 
 
432
template <class T, Uint32 LogBase>
 
433
inline void
 
434
LinearPool<T, LogBase>::init_free(Ptr<Map> map_ptr)
 
435
{
 
436
  map_ptr.p->m_occup = 0;
 
437
  map_ptr.p->m_firstfree = 0;
 
438
  // freelist
 
439
  Uint32 j;
 
440
  Uint16 back = ZNIL;
 
441
  for (j = 0; j < Base - 1; j++) {
 
442
    map_ptr.p->m_entry[j] = back | ((j + 1) << 16);
 
443
    back = j;
 
444
  }
 
445
  map_ptr.p->m_entry[j] = back | (ZNIL << 16);
 
446
  // bitmask
 
447
  BitmaskImpl::clear(BitmaskSize, map_ptr.p->m_bitmask);
 
448
  // add to available
 
449
  add_avail(map_ptr);
 
450
}
 
451
 
 
452
template <class T, Uint32 LogBase>
 
453
inline void
 
454
LinearPool<T, LogBase>::add_entry(Ptr<Map> map_ptr, Uint32 digit, PtrI ptr_i)
 
455
{
 
456
  assert(map_ptr.p->m_occup < Base && digit < Base);
 
457
  assert(! BitmaskImpl::get(BitmaskSize, map_ptr.p->m_bitmask, digit));
 
458
  // unlink from freelist
 
459
  Uint32 val = map_ptr.p->m_entry[digit];
 
460
  Uint16 back = val & ZNIL;
 
461
  Uint16 forw = val >> 16;
 
462
  if (back != ZNIL) {
 
463
    assert(back < Base);
 
464
    map_ptr.p->m_entry[back] &= ZNIL;
 
465
    map_ptr.p->m_entry[back] |= (forw << 16);
 
466
  }
 
467
  if (forw != ZNIL) {
 
468
    assert(forw < Base);
 
469
    map_ptr.p->m_entry[forw] &= (ZNIL << 16);
 
470
    map_ptr.p->m_entry[forw] |= back;
 
471
  }
 
472
  if (back == ZNIL) {
 
473
    map_ptr.p->m_firstfree = forw;
 
474
  }
 
475
  // set new value
 
476
  map_ptr.p->m_entry[digit] = ptr_i;
 
477
  map_ptr.p->m_occup++;
 
478
  BitmaskImpl::set(BitmaskSize, map_ptr.p->m_bitmask, digit);
 
479
  if (map_ptr.p->m_occup == Base)
 
480
    remove_avail(map_ptr);
 
481
}
 
482
 
 
483
template <class T, Uint32 LogBase>
 
484
inline void
 
485
LinearPool<T, LogBase>::remove_entry(Ptr<Map> map_ptr, Uint32 digit)
 
486
{
 
487
  assert(map_ptr.p->m_occup != 0 && digit < Base);
 
488
  assert(BitmaskImpl::get(BitmaskSize, map_ptr.p->m_bitmask, digit));
 
489
  // add to freelist
 
490
  Uint32 firstfree = map_ptr.p->m_firstfree;
 
491
  map_ptr.p->m_entry[digit] = ZNIL | (firstfree << 16);
 
492
  if (firstfree != ZNIL) {
 
493
    assert(firstfree < Base);
 
494
    map_ptr.p->m_entry[firstfree] &= (ZNIL << 16);
 
495
    map_ptr.p->m_entry[firstfree] |= digit;
 
496
  }
 
497
  map_ptr.p->m_firstfree = digit;
 
498
  map_ptr.p->m_occup--;
 
499
  BitmaskImpl::clear(BitmaskSize, map_ptr.p->m_bitmask, digit);
 
500
  if (map_ptr.p->m_occup + 1 == Base)
 
501
    add_avail(map_ptr);
 
502
  else if (map_ptr.p->m_occup == 0)
 
503
    remove_map(map_ptr);
 
504
}
 
505
 
 
506
template <class T, Uint32 LogBase>
 
507
inline void
 
508
LinearPool<T, LogBase>::remove_map(Ptr<Map> map_ptr)
 
509
{
 
510
  assert(map_ptr.p->m_occup == 0);
 
511
  remove_avail(map_ptr);
 
512
  Ptr<Map> parent_ptr;
 
513
  parent_ptr.i = map_ptr.p->m_parent;
 
514
  Uint32 digit = map_ptr.p->m_index & DigitMask;
 
515
  PtrI map_ptr_i = map_ptr.i;
 
516
  m_maps.release(map_ptr);
 
517
  if (m_root == map_ptr_i) {
 
518
    assert(parent_ptr.i == RNIL);
 
519
    Uint32 used = count();
 
520
    assert(used == 0);
 
521
    m_root = RNIL;
 
522
    m_levels = 0;
 
523
  }
 
524
  if (parent_ptr.i != RNIL) {
 
525
    m_maps.getPtr(parent_ptr);
 
526
    // remove child entry (recursive)
 
527
    remove_entry(parent_ptr, digit);
 
528
  }
 
529
}
 
530
 
 
531
template <class T, Uint32 LogBase>
 
532
inline void
 
533
LinearPool<T, LogBase>::add_avail(Ptr<Map> map_ptr)
 
534
{
 
535
  Uint32 n = map_ptr.p->m_level;
 
536
  assert(n < m_levels);
 
537
  map_ptr.p->m_nextavail = m_avail[n];
 
538
  if (map_ptr.p->m_nextavail != RNIL) {
 
539
    Ptr<Map> next_ptr;
 
540
    next_ptr.i = map_ptr.p->m_nextavail;
 
541
    m_maps.getPtr(next_ptr);
 
542
    next_ptr.p->m_prevavail = map_ptr.i;
 
543
  }
 
544
  map_ptr.p->m_prevavail = RNIL;
 
545
  m_avail[n] = map_ptr.i;
 
546
}
 
547
 
 
548
template <class T, Uint32 LogBase>
 
549
inline void
 
550
LinearPool<T, LogBase>::remove_avail(Ptr<Map> map_ptr)
 
551
{
 
552
  Uint32 n = map_ptr.p->m_level;
 
553
  assert(n < m_levels);
 
554
  if (map_ptr.p->m_nextavail != RNIL) {
 
555
    Ptr<Map> next_ptr;
 
556
    next_ptr.i = map_ptr.p->m_nextavail;
 
557
    m_maps.getPtr(next_ptr);
 
558
    next_ptr.p->m_prevavail = map_ptr.p->m_prevavail;
 
559
  }
 
560
  if (map_ptr.p->m_prevavail != RNIL) {
 
561
    Ptr<Map> prev_ptr;
 
562
    prev_ptr.i = map_ptr.p->m_prevavail;
 
563
    m_maps.getPtr(prev_ptr);
 
564
    prev_ptr.p->m_nextavail = map_ptr.p->m_nextavail;
 
565
  }
 
566
  if (map_ptr.p->m_prevavail == RNIL) {
 
567
    m_avail[n] = map_ptr.p->m_nextavail;
 
568
  }
 
569
  map_ptr.p->m_nextavail = RNIL;
 
570
  map_ptr.p->m_prevavail = RNIL;
 
571
}
 
572
 
 
573
template <class T, Uint32 LogBase>
 
574
inline void
 
575
LinearPool<T, LogBase>::verify_avail()
 
576
{
 
577
  // check available lists
 
578
  for (Uint32 n = 0; n < MaxLevels; n++) {
 
579
    Ptr<Map> map_ptr;
 
580
    map_ptr.i = m_avail[n];
 
581
    Uint32 back = RNIL;
 
582
    while (map_ptr.i != RNIL) {
 
583
      m_maps.getPtr(map_ptr);
 
584
      assert(map_ptr.p->m_occup < Base);
 
585
      assert(back == map_ptr.p->m_prevavail);
 
586
      back = map_ptr.i;
 
587
      map_ptr.i = map_ptr.p->m_nextavail;
 
588
    }
 
589
  }
 
590
}
 
591
 
 
592
template <class T, Uint32 LogBase>
 
593
inline void
 
594
LinearPool<T, LogBase>::verify_map(Ptr<Map> map_ptr, Uint32 level, Uint32* count)
 
595
{
 
596
  assert(level < MaxLevels);
 
597
  assert(map_ptr.p->m_level == level);
 
598
  // check freelist
 
599
  {
 
600
    Uint32 nused = BitmaskImpl::count(BitmaskSize, map_ptr.p->m_bitmask);
 
601
    assert(nused <= Base);
 
602
    assert(map_ptr.p->m_occup == nused);
 
603
    Uint32 nfree = 0;
 
604
    Uint32 j = map_ptr.p->m_firstfree;
 
605
    Uint16 back = ZNIL;
 
606
    while (j != ZNIL) {
 
607
      assert(j < Base);
 
608
      assert(! BitmaskImpl::get(BitmaskSize, map_ptr.p->m_bitmask, j));
 
609
      Uint32 val = map_ptr.p->m_entry[j];
 
610
      assert(back == (val & ZNIL));
 
611
      back = j;
 
612
      j = (val >> 16);
 
613
      nfree++;
 
614
    }
 
615
    assert(nused + nfree == Base);
 
616
  }
 
617
  // check entries
 
618
  {
 
619
    for (Uint32 j = 0; j < Base; j++) {
 
620
      bool free = ! BitmaskImpl::get(BitmaskSize, map_ptr.p->m_bitmask, j);
 
621
      if (free)
 
622
        continue;
 
623
      if (level != 0) {
 
624
        Ptr<Map> child_ptr;
 
625
        child_ptr.i = map_ptr.p->m_entry[j];
 
626
        m_maps.getPtr(child_ptr);
 
627
        assert(child_ptr.p->m_parent == map_ptr.i);
 
628
        assert(child_ptr.p->m_index == j + (map_ptr.p->m_index << LogBase));
 
629
        verify_map(child_ptr, level - 1, count);
 
630
      } else {
 
631
        Ptr<T> rec_ptr;
 
632
        rec_ptr.i = map_ptr.p->m_entry[j];
 
633
        m_records.getPtr(rec_ptr);
 
634
        (*count)++;
 
635
      }
 
636
    }
 
637
  }
 
638
  // check membership on available list
 
639
  {
 
640
    Ptr<Map> avail_ptr;
 
641
    avail_ptr.i = m_avail[map_ptr.p->m_level];
 
642
    bool found = false;
 
643
    while (avail_ptr.i != RNIL) {
 
644
      if (avail_ptr.i == map_ptr.i) {
 
645
        found = true;
 
646
        break;
 
647
      }
 
648
      m_maps.getPtr(avail_ptr);
 
649
      avail_ptr.i = avail_ptr.p->m_nextavail;
 
650
    }
 
651
    assert(found == (map_ptr.p->m_occup < Base));
 
652
  }
 
653
}
 
654
 
 
655
#endif