← Back to branch summary

~ubuntu-branches/ubuntu/precise/mysql-5.1/precise

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Norbert Tretkowski
  • Date: 2010-03-17 14:56:02 UTC
  • Revision ID: james.westby@ubuntu.com-20100317145602-x7e30l1b2sb5s6w6
Tags: upstream-5.1.45
Import upstream version 5.1.45

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/ndb/src/kernel/vm/DLFifoList.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 DLFIFOLIST_HPP
 
17
#define DLFIFOLIST_HPP
 
18
 
 
19
#include <ndb_global.h>
 
20
#include <kernel_types.h>
 
21
#include "Pool.hpp"
 
22
 
 
23
/**
 
24
 * Template class used for implementing an
 
25
 *   list of object retreived from a pool
 
26
 */
 
27
template <typename P, typename T, typename U = T>
 
28
class DLFifoListImpl 
 
29
{
 
30
public:
 
31
  /**
 
32
   * List head
 
33
   */
 
34
  struct Head 
 
35
  {
 
36
    Head();
 
37
    Uint32 firstItem;
 
38
    Uint32 lastItem;
 
39
 
 
40
#ifdef VM_TRACE
 
41
    bool in_use;
 
42
#endif
 
43
 
 
44
    inline bool isEmpty() const { return firstItem == RNIL;}
 
45
  };
 
46
  
 
47
  DLFifoListImpl(P & thePool);
 
48
  
 
49
  bool seizeFirst(Ptr<T> &);
 
50
  bool seizeLast(Ptr<T> &);
 
51
  bool seize(Ptr<T> & ptr) { return seizeLast(ptr);}
 
52
  
 
53
  void release(Ptr<T> &);
 
54
  void release(); // release all
 
55
  
 
56
  void addFirst(Ptr<T> &);
 
57
  void addLast(Ptr<T> &);
 
58
  void add(Ptr<T> & ptr) { addLast(ptr);}
 
59
 
 
60
  /**
 
61
   * Insert object <em>ptr</ptr> _before_ <em>loc</em>
 
62
   */
 
63
  void insert(Ptr<T> & ptr, Ptr<T>& loc);
 
64
  
 
65
  void remove();
 
66
  void remove(Ptr<T> &);
 
67
  void remove(T*);
 
68
  /**
 
69
   *  Update i & p value according to <b>i</b>
 
70
   */
 
71
  void getPtr(Ptr<T> &, Uint32 i) const;
 
72
  
 
73
  /**
 
74
   * Update p value for ptr according to i value 
 
75
   */
 
76
  void getPtr(Ptr<T> &) const ;
 
77
  
 
78
  /**
 
79
   * Get pointer for i value
 
80
   */
 
81
  T * getPtr(Uint32 i) const ;
 
82
 
 
83
  /**
 
84
   * Update ptr to first element in list
 
85
   *
 
86
   * Return i
 
87
   */
 
88
  bool first(Ptr<T> &) const ;
 
89
 
 
90
  /**
 
91
   * Update ptr to first element in list
 
92
   *
 
93
   * Return i
 
94
   */
 
95
  bool last(Ptr<T> &) const ;
 
96
 
 
97
  /**
 
98
   * Get next element
 
99
   *
 
100
   * NOTE ptr must be both p & i
 
101
   */
 
102
  bool next(Ptr<T> &) const ;
 
103
  
 
104
  /**
 
105
   * Get next element
 
106
   *
 
107
   * NOTE ptr must be both p & i
 
108
   */
 
109
  bool prev(Ptr<T> &) const ;
 
110
  
 
111
  /**
 
112
   * Check if next exists i.e. this is not last
 
113
   *
 
114
   * NOTE ptr must be both p & i
 
115
   */
 
116
  bool hasNext(const Ptr<T> &) const;
 
117
 
 
118
  /**
 
119
   * Check if next exists i.e. this is not last
 
120
   *
 
121
   * NOTE ptr must be both p & i
 
122
   */
 
123
  bool hasPrev(const Ptr<T> &) const;
 
124
  
 
125
  inline bool isEmpty() const { return head.firstItem == RNIL;}
 
126
 
 
127
  /**
 
128
   * Copy list (head)
 
129
   *   Will construct to identical lists
 
130
   */
 
131
  DLFifoListImpl<P,T,U>& operator=(const DLFifoListImpl<P,T,U>& src){
 
132
    assert(&thePool == &src.thePool);
 
133
    this->head = src.head;
 
134
    return * this;
 
135
  }
 
136
  
 
137
protected:
 
138
  Head head;
 
139
  P & thePool;
 
140
};
 
141
 
 
142
template <typename P, typename T, typename U = T>
 
143
class LocalDLFifoListImpl : public DLFifoListImpl<P,T,U> 
 
144
{
 
145
public:
 
146
  LocalDLFifoListImpl(P & thePool, typename DLFifoListImpl<P,T,U>::Head &_src)
 
147
    : DLFifoListImpl<P,T,U>(thePool), src(_src)
 
148
  {
 
149
    this->head = src;
 
150
#ifdef VM_TRACE
 
151
    assert(src.in_use == false);
 
152
    src.in_use = true;
 
153
#endif
 
154
  }
 
155
  
 
156
  ~LocalDLFifoListImpl(){
 
157
#ifdef VM_TRACE
 
158
    assert(src.in_use == true);
 
159
#endif
 
160
    src = this->head;
 
161
  }
 
162
private:
 
163
  typename DLFifoListImpl<P,T,U>::Head & src;
 
164
};
 
165
 
 
166
template <typename P, typename T, typename U>
 
167
inline
 
168
DLFifoListImpl<P,T,U>::DLFifoListImpl(P & _pool):
 
169
  thePool(_pool)
 
170
{
 
171
}
 
172
 
 
173
template <typename P, typename T, typename U>
 
174
inline
 
175
DLFifoListImpl<P,T,U>::Head::Head()
 
176
{
 
177
  firstItem = RNIL;
 
178
  lastItem = RNIL;
 
179
#ifdef VM_TRACE
 
180
  in_use = false;
 
181
#endif
 
182
}
 
183
 
 
184
template <typename P, typename T, typename U>
 
185
inline
 
186
bool
 
187
DLFifoListImpl<P,T,U>::seizeFirst(Ptr<T> & p)
 
188
{
 
189
  if (likely(thePool.seize(p)))
 
190
  {
 
191
    addFirst(p);
 
192
    return true;
 
193
  }
 
194
  p.p = NULL;
 
195
  return false;
 
196
}
 
197
 
 
198
template <typename P, typename T, typename U>
 
199
inline
 
200
bool
 
201
DLFifoListImpl<P,T,U>::seizeLast(Ptr<T> & p)
 
202
{
 
203
  if (likely(thePool.seize(p)))
 
204
  {
 
205
    addLast(p);
 
206
    return true;
 
207
  }
 
208
  p.p = NULL;
 
209
  return false;
 
210
}
 
211
 
 
212
template <typename P, typename T, typename U>
 
213
inline
 
214
void
 
215
DLFifoListImpl<P,T,U>::addFirst(Ptr<T> & p)
 
216
{
 
217
  Uint32 ff = head.firstItem;
 
218
  
 
219
  p.p->U::prevList = RNIL;
 
220
  p.p->U::nextList = ff;
 
221
  head.firstItem = p.i;
 
222
  if (ff == RNIL)
 
223
  {
 
224
    head.lastItem = p.i;
 
225
  }
 
226
  else
 
227
  {
 
228
    T * t2 = thePool.getPtr(ff);
 
229
    t2->U::prevList = p.i;
 
230
  }
 
231
}
 
232
 
 
233
template <typename P, typename T, typename U>
 
234
inline
 
235
void
 
236
DLFifoListImpl<P,T,U>::addLast(Ptr<T> & p)
 
237
{
 
238
  T * t = p.p;
 
239
  Uint32 last = head.lastItem;
 
240
  head.lastItem = p.i;    
 
241
  
 
242
  t->U::nextList = RNIL;
 
243
  t->U::prevList = last;
 
244
  
 
245
  if(last != RNIL)
 
246
  {
 
247
    T * t2 = thePool.getPtr(last);
 
248
    t2->U::nextList = p.i;
 
249
  }
 
250
  else
 
251
  {
 
252
    head.firstItem = p.i;
 
253
  }
 
254
}
 
255
 
 
256
template <typename P, typename T, typename U>
 
257
inline
 
258
void
 
259
DLFifoListImpl<P,T,U>::insert(Ptr<T> & ptr, Ptr<T> & loc)
 
260
{
 
261
  Uint32 prev= loc.p->U::prevList;
 
262
  if(loc.i == head.firstItem)
 
263
  {
 
264
    head.firstItem = ptr.i;
 
265
    assert(prev == RNIL);
 
266
  }
 
267
  else
 
268
  {
 
269
    T* t2 = thePool.getPtr(prev);
 
270
    t2->U::nextList = ptr.i;
 
271
  }
 
272
  
 
273
  loc.p->U::prevList = ptr.i;
 
274
  ptr.p->U::prevList = prev;
 
275
  ptr.p->U::nextList = loc.i;
 
276
}
 
277
 
 
278
template <typename P, typename T, typename U>
 
279
inline
 
280
void
 
281
DLFifoListImpl<P,T,U>::remove()
 
282
{
 
283
  head.firstItem = RNIL;
 
284
  head.lastItem = RNIL;
 
285
}
 
286
 
 
287
template <typename P, typename T, typename U>
 
288
inline
 
289
void
 
290
DLFifoListImpl<P,T,U>::remove(Ptr<T> & p)
 
291
{
 
292
  remove(p.p);
 
293
}
 
294
 
 
295
template <typename P, typename T, typename U>
 
296
inline
 
297
void
 
298
DLFifoListImpl<P,T,U>::remove(T * t)
 
299
{
 
300
  Uint32 ni = t->U::nextList;
 
301
  Uint32 pi = t->U::prevList;
 
302
 
 
303
  if(ni != RNIL)
 
304
  {
 
305
    T * t = thePool.getPtr(ni);
 
306
    t->U::prevList = pi;
 
307
  } 
 
308
  else 
 
309
  {
 
310
    // We are releasing last
 
311
    head.lastItem = pi;
 
312
  }
 
313
  
 
314
  if(pi != RNIL)
 
315
  {
 
316
    T * t = thePool.getPtr(pi);
 
317
    t->U::nextList = ni;
 
318
  } 
 
319
  else 
 
320
  {
 
321
    // We are releasing first
 
322
    head.firstItem = ni;
 
323
  }
 
324
}
 
325
 
 
326
template <typename P, typename T, typename U>
 
327
inline
 
328
void 
 
329
DLFifoListImpl<P,T,U>::release()
 
330
{
 
331
  Ptr<T> ptr;
 
332
  Uint32 curr = head.firstItem;
 
333
  while(curr != RNIL)
 
334
  {
 
335
    thePool.getPtr(ptr, curr);
 
336
    curr = ptr.p->U::nextList;
 
337
    thePool.release(ptr);
 
338
  }
 
339
  head.firstItem = RNIL;
 
340
  head.lastItem = RNIL;
 
341
}
 
342
 
 
343
template <typename P, typename T, typename U>
 
344
inline
 
345
void 
 
346
DLFifoListImpl<P,T,U>::release(Ptr<T> & p)
 
347
{
 
348
  remove(p.p);
 
349
  thePool.release(p);
 
350
}
 
351
 
 
352
template <typename P, typename T, typename U>
 
353
inline
 
354
void 
 
355
DLFifoListImpl<P,T,U>::getPtr(Ptr<T> & p, Uint32 i) const 
 
356
{
 
357
  p.i = i;
 
358
  p.p = thePool.getPtr(i);
 
359
}
 
360
 
 
361
template <typename P, typename T, typename U>
 
362
inline
 
363
void 
 
364
DLFifoListImpl<P,T,U>::getPtr(Ptr<T> & p) const 
 
365
{
 
366
  thePool.getPtr(p);
 
367
}
 
368
  
 
369
template <typename P, typename T, typename U>
 
370
inline
 
371
T * 
 
372
DLFifoListImpl<P,T,U>::getPtr(Uint32 i) const 
 
373
{
 
374
  return thePool.getPtr(i);
 
375
}
 
376
 
 
377
/**
 
378
 * Update ptr to first element in list
 
379
 *
 
380
 * Return i
 
381
 */
 
382
template <typename P, typename T, typename U>
 
383
inline
 
384
bool
 
385
DLFifoListImpl<P,T,U>::first(Ptr<T> & p) const 
 
386
{
 
387
  p.i = head.firstItem;
 
388
  if(p.i != RNIL)
 
389
  {
 
390
    p.p = thePool.getPtr(p.i);
 
391
    return true;
 
392
  }
 
393
  p.p = NULL;
 
394
  return false;
 
395
}
 
396
 
 
397
template <typename P, typename T, typename U>
 
398
inline
 
399
bool
 
400
DLFifoListImpl<P,T,U>::last(Ptr<T> & p) const 
 
401
{
 
402
  p.i = head.lastItem;
 
403
  if(p.i != RNIL)
 
404
  {
 
405
    p.p = thePool.getPtr(p.i);
 
406
    return true;
 
407
  }
 
408
  p.p = NULL;
 
409
  return false;
 
410
}
 
411
 
 
412
template <typename P, typename T, typename U>
 
413
inline
 
414
bool
 
415
DLFifoListImpl<P,T,U>::next(Ptr<T> & p) const 
 
416
{
 
417
  p.i = p.p->U::nextList;
 
418
  if(p.i != RNIL)
 
419
  {
 
420
    p.p = thePool.getPtr(p.i);
 
421
    return true;
 
422
  }
 
423
  p.p = NULL;
 
424
  return false;
 
425
}
 
426
 
 
427
template <typename P, typename T, typename U>
 
428
inline
 
429
bool
 
430
DLFifoListImpl<P,T,U>::prev(Ptr<T> & p) const 
 
431
{
 
432
  p.i = p.p->U::prevList;
 
433
  if(p.i != RNIL)
 
434
  {
 
435
    p.p = thePool.getPtr(p.i);
 
436
    return true;
 
437
  }
 
438
  p.p = NULL;
 
439
  return false;
 
440
}
 
441
 
 
442
template <typename P, typename T, typename U>
 
443
inline
 
444
bool
 
445
DLFifoListImpl<P,T,U>::hasNext(const Ptr<T> & p) const 
 
446
{
 
447
  return p.p->U::nextList != RNIL;
 
448
}
 
449
 
 
450
template <typename P, typename T, typename U>
 
451
inline
 
452
bool
 
453
DLFifoListImpl<P,T,U>::hasPrev(const Ptr<T> & p) const 
 
454
{
 
455
  return p.p->U::prevList != RNIL;
 
456
}
 
457
 
 
458
// Specializations
 
459
 
 
460
template <typename T, typename U = T>
 
461
class DLFifoList : public DLFifoListImpl<ArrayPool<T>, T, U>
 
462
{
 
463
public:
 
464
  DLFifoList(ArrayPool<T> & p) : DLFifoListImpl<ArrayPool<T>, T, U>(p) {}
 
465
};
 
466
 
 
467
template <typename T, typename U = T>
 
468
class LocalDLFifoList : public LocalDLFifoListImpl<ArrayPool<T>,T,U> {
 
469
public:
 
470
  LocalDLFifoList(ArrayPool<T> & p, typename DLFifoList<T,U>::Head & _src)
 
471
    : LocalDLFifoListImpl<ArrayPool<T>,T,U>(p, _src) {}
 
472
};
 
473
 
 
474
#endif