MySQL 5.6.14 Source Code Document
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DLFifoList.hpp
1 /*
2  Copyright (C) 2003-2007 MySQL AB, 2008, 2009 Sun Microsystems, Inc.
3  All rights reserved. Use is subject to license terms.
4 
5  This program is free software; you can redistribute it and/or modify
6  it under the terms of the GNU General Public License as published by
7  the Free Software Foundation; version 2 of the License.
8 
9  This program is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with this program; if not, write to the Free Software
16  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
17 */
18 
19 #ifndef DLFIFOLIST_HPP
20 #define DLFIFOLIST_HPP
21 
22 #include <ndb_global.h>
23 #include <kernel_types.h>
24 #include "Pool.hpp"
25 
30 template <typename P, typename T, typename U = T>
31 class DLFifoListImpl
32 {
33 public:
37  struct Head
38  {
39  Head();
40  Uint32 firstItem;
41  Uint32 lastItem;
42 
43 #ifdef VM_TRACE
44  bool in_use;
45 #endif
46 
47  inline bool isEmpty() const { return firstItem == RNIL;}
48  };
49 
50  DLFifoListImpl(P & thePool);
51 
52  bool seizeFirst(Ptr<T> &);
53  bool seizeLast(Ptr<T> &);
54  bool seize(Ptr<T> & ptr) { return seizeLast(ptr);}
55 
56  void release(Ptr<T> &);
57  void release(); // release all
58 
59  void addFirst(Ptr<T> &);
60  void addLast(Ptr<T> &);
61  void add(Ptr<T> & ptr) { addLast(ptr);}
62 
66  void insert(Ptr<T> & ptr, Ptr<T>& loc);
67 
68  void remove();
69  void remove(Ptr<T> &);
70  void remove(T*);
74  void getPtr(Ptr<T> &, Uint32 i) const;
75 
79  void getPtr(Ptr<T> &) const ;
80 
84  T * getPtr(Uint32 i) const ;
85 
91  bool first(Ptr<T> &) const ;
92 
98  bool last(Ptr<T> &) const ;
99 
105  bool next(Ptr<T> &) const ;
106 
112  bool prev(Ptr<T> &) const ;
113 
119  bool hasNext(const Ptr<T> &) const;
120 
126  bool hasPrev(const Ptr<T> &) const;
127 
128  inline bool isEmpty() const { return head.firstItem == RNIL;}
129 
134  DLFifoListImpl<P,T,U>& operator=(const DLFifoListImpl<P,T,U>& src){
135  assert(&thePool == &src.thePool);
136  this->head = src.head;
137  return * this;
138  }
139 
140 protected:
141  Head head;
142  P & thePool;
143 };
144 
145 template <typename P, typename T, typename U = T>
146 class LocalDLFifoListImpl : public DLFifoListImpl<P,T,U>
147 {
148 public:
149  LocalDLFifoListImpl(P & thePool, typename DLFifoListImpl<P,T,U>::Head &_src)
150  : DLFifoListImpl<P,T,U>(thePool), src(_src)
151  {
152  this->head = src;
153 #ifdef VM_TRACE
154  assert(src.in_use == false);
155  src.in_use = true;
156 #endif
157  }
158 
159  ~LocalDLFifoListImpl(){
160 #ifdef VM_TRACE
161  assert(src.in_use == true);
162 #endif
163  src = this->head;
164  }
165 private:
166  typename DLFifoListImpl<P,T,U>::Head & src;
167 };
168 
169 template <typename P, typename T, typename U>
170 inline
171 DLFifoListImpl<P,T,U>::DLFifoListImpl(P & _pool):
172  thePool(_pool)
173 {
174 }
175 
176 template <typename P, typename T, typename U>
177 inline
178 DLFifoListImpl<P,T,U>::Head::Head()
179 {
180  // Require user defined constructor on T since we fiddle
181  // with T's members
182  ASSERT_TYPE_HAS_CONSTRUCTOR(T);
183 
184  firstItem = RNIL;
185  lastItem = RNIL;
186 #ifdef VM_TRACE
187  in_use = false;
188 #endif
189 
190 }
191 
192 template <typename P, typename T, typename U>
193 inline
194 bool
195 DLFifoListImpl<P,T,U>::seizeFirst(Ptr<T> & p)
196 {
197  if (likely(thePool.seize(p)))
198  {
199  addFirst(p);
200  return true;
201  }
202  p.p = NULL;
203  return false;
204 }
205 
206 template <typename P, typename T, typename U>
207 inline
208 bool
209 DLFifoListImpl<P,T,U>::seizeLast(Ptr<T> & p)
210 {
211  if (likely(thePool.seize(p)))
212  {
213  addLast(p);
214  return true;
215  }
216  p.p = NULL;
217  return false;
218 }
219 
220 template <typename P, typename T, typename U>
221 inline
222 void
223 DLFifoListImpl<P,T,U>::addFirst(Ptr<T> & p)
224 {
225  Uint32 ff = head.firstItem;
226 
227  p.p->U::prevList = RNIL;
228  p.p->U::nextList = ff;
229  head.firstItem = p.i;
230  if (ff == RNIL)
231  {
232  head.lastItem = p.i;
233  }
234  else
235  {
236  T * t2 = thePool.getPtr(ff);
237  t2->U::prevList = p.i;
238  }
239 }
240 
241 template <typename P, typename T, typename U>
242 inline
243 void
244 DLFifoListImpl<P,T,U>::addLast(Ptr<T> & p)
245 {
246  T * t = p.p;
247  Uint32 last = head.lastItem;
248  head.lastItem = p.i;
249 
250  t->U::nextList = RNIL;
251  t->U::prevList = last;
252 
253  if(last != RNIL)
254  {
255  T * t2 = thePool.getPtr(last);
256  t2->U::nextList = p.i;
257  }
258  else
259  {
260  head.firstItem = p.i;
261  }
262 }
263 
264 template <typename P, typename T, typename U>
265 inline
266 void
267 DLFifoListImpl<P,T,U>::insert(Ptr<T> & ptr, Ptr<T> & loc)
268 {
269  Uint32 prev= loc.p->U::prevList;
270  if(loc.i == head.firstItem)
271  {
272  head.firstItem = ptr.i;
273  assert(prev == RNIL);
274  }
275  else
276  {
277  T* t2 = thePool.getPtr(prev);
278  t2->U::nextList = ptr.i;
279  }
280 
281  loc.p->U::prevList = ptr.i;
282  ptr.p->U::prevList = prev;
283  ptr.p->U::nextList = loc.i;
284 }
285 
286 template <typename P, typename T, typename U>
287 inline
288 void
289 DLFifoListImpl<P,T,U>::remove()
290 {
291  head.firstItem = RNIL;
292  head.lastItem = RNIL;
293 }
294 
295 template <typename P, typename T, typename U>
296 inline
297 void
298 DLFifoListImpl<P,T,U>::remove(Ptr<T> & p)
299 {
300  remove(p.p);
301 }
302 
303 template <typename P, typename T, typename U>
304 inline
305 void
306 DLFifoListImpl<P,T,U>::remove(T * t)
307 {
308  Uint32 ni = t->U::nextList;
309  Uint32 pi = t->U::prevList;
310 
311  if(ni != RNIL)
312  {
313  T * t = thePool.getPtr(ni);
314  t->U::prevList = pi;
315  }
316  else
317  {
318  // We are releasing last
319  head.lastItem = pi;
320  }
321 
322  if(pi != RNIL)
323  {
324  T * t = thePool.getPtr(pi);
325  t->U::nextList = ni;
326  }
327  else
328  {
329  // We are releasing first
330  head.firstItem = ni;
331  }
332 }
333 
334 template <typename P, typename T, typename U>
335 inline
336 void
337 DLFifoListImpl<P,T,U>::release()
338 {
339  Ptr<T> ptr;
340  Uint32 curr = head.firstItem;
341  while(curr != RNIL)
342  {
343  thePool.getPtr(ptr, curr);
344  curr = ptr.p->U::nextList;
345  thePool.release(ptr);
346  }
347  head.firstItem = RNIL;
348  head.lastItem = RNIL;
349 }
350 
351 template <typename P, typename T, typename U>
352 inline
353 void
354 DLFifoListImpl<P,T,U>::release(Ptr<T> & p)
355 {
356  remove(p.p);
357  thePool.release(p);
358 }
359 
360 template <typename P, typename T, typename U>
361 inline
362 void
363 DLFifoListImpl<P,T,U>::getPtr(Ptr<T> & p, Uint32 i) const
364 {
365  p.i = i;
366  p.p = thePool.getPtr(i);
367 }
368 
369 template <typename P, typename T, typename U>
370 inline
371 void
372 DLFifoListImpl<P,T,U>::getPtr(Ptr<T> & p) const
373 {
374  thePool.getPtr(p);
375 }
376 
377 template <typename P, typename T, typename U>
378 inline
379 T *
380 DLFifoListImpl<P,T,U>::getPtr(Uint32 i) const
381 {
382  return thePool.getPtr(i);
383 }
384 
390 template <typename P, typename T, typename U>
391 inline
392 bool
393 DLFifoListImpl<P,T,U>::first(Ptr<T> & p) const
394 {
395  p.i = head.firstItem;
396  if(p.i != RNIL)
397  {
398  p.p = thePool.getPtr(p.i);
399  return true;
400  }
401  p.p = NULL;
402  return false;
403 }
404 
405 template <typename P, typename T, typename U>
406 inline
407 bool
408 DLFifoListImpl<P,T,U>::last(Ptr<T> & p) const
409 {
410  p.i = head.lastItem;
411  if(p.i != RNIL)
412  {
413  p.p = thePool.getPtr(p.i);
414  return true;
415  }
416  p.p = NULL;
417  return false;
418 }
419 
420 template <typename P, typename T, typename U>
421 inline
422 bool
423 DLFifoListImpl<P,T,U>::next(Ptr<T> & p) const
424 {
425  p.i = p.p->U::nextList;
426  if(p.i != RNIL)
427  {
428  p.p = thePool.getPtr(p.i);
429  return true;
430  }
431  p.p = NULL;
432  return false;
433 }
434 
435 template <typename P, typename T, typename U>
436 inline
437 bool
438 DLFifoListImpl<P,T,U>::prev(Ptr<T> & p) const
439 {
440  p.i = p.p->U::prevList;
441  if(p.i != RNIL)
442  {
443  p.p = thePool.getPtr(p.i);
444  return true;
445  }
446  p.p = NULL;
447  return false;
448 }
449 
450 template <typename P, typename T, typename U>
451 inline
452 bool
453 DLFifoListImpl<P,T,U>::hasNext(const Ptr<T> & p) const
454 {
455  return p.p->U::nextList != RNIL;
456 }
457 
458 template <typename P, typename T, typename U>
459 inline
460 bool
461 DLFifoListImpl<P,T,U>::hasPrev(const Ptr<T> & p) const
462 {
463  return p.p->U::prevList != RNIL;
464 }
465 
466 // Specializations
467 
468 template <typename T, typename U = T>
469 class DLFifoList : public DLFifoListImpl<ArrayPool<T>, T, U>
470 {
471 public:
472  DLFifoList(ArrayPool<T> & p) : DLFifoListImpl<ArrayPool<T>, T, U>(p) {}
473 };
474 
475 template <typename T, typename U = T>
476 class LocalDLFifoList : public LocalDLFifoListImpl<ArrayPool<T>,T,U> {
477 public:
478  LocalDLFifoList(ArrayPool<T> & p, typename DLFifoList<T,U>::Head & _src)
479  : LocalDLFifoListImpl<ArrayPool<T>,T,U>(p, _src) {}
480 };
481 
482 #endif