gc/list.d

   1 /**
   2  * Singly linked list of Cells.
   3  *
   4  * This module implements a simple singly linked list of Cells to be used as
   5  * live/free list in the Naive Garbage Collector implementation.
   6  *
   7  * See_Also:  gc module
   8  * Copyright: Public Domain
   9  * License:   Public Domain
  10  * Authors:   Leandro Lucarella <llucax@gmail.com>
  11  */
  12
  13 module gc.list;
  14
  15 // Internal imports
  16 private import gc.cell: Cell;
  17
  18
  19 package:
  20
  21 /**
  22  * Singly linked list of Cells.
  23  *
  24  * This is used for live and free lists.
  25  */
  26 struct List
  27 {
  28
  29     /// First element in the list.
  30     Cell* first = null;
  31
  32     /**
  33      * Find the first cell for which predicate(cell) is true.
  34      *
  35      * Returns a pointer to the cell if found, null otherwise.
  36      */
  37     Cell* find(bool delegate(Cell*) predicate)
  38     {
  39         auto cell = this.first;
  40         while (cell) {
  41             if (predicate(cell))
  42                 return cell;
  43             cell = cell.next;
  44         }
  45         return null;
  46     }
  47
  48     /**
  49      * Find the cell that holds the object pointed by ptr.
  50      *
  51      * Returns a pointer to the cell if found, null otherwise.
  52      */
  53     Cell* find(void* ptr)
  54     {
  55         return this.find((Cell* cell) { return cell.ptr == ptr; });
  56     }
  57
  58     /**
  59      * Link a new cell into the list.
  60      */
  61     void link(Cell* cell)
  62     {
  63         cell.next = this.first;
  64         this.first = cell;
  65     }
  66
  67     /**
  68      * Find and remove the first cell for which predicate(cell) is true.
  69      *
  70      * If no cell is found, no cell is removed.
  71      *
  72      * Returns a pointer to the removed cell if found, null otherwise.
  73      */
  74     Cell* pop(bool delegate(Cell*) predicate)
  75     {
  76         Cell* prev = null;
  77         auto cell = this.first;
  78         while (cell) {
  79             if (predicate(cell)) {
  80                 if (prev)
  81                     prev.next = cell.next;
  82                 else
  83                     this.first = cell.next;
  84                 return cell;
  85             }
  86             prev = cell;
  87             cell = cell.next;
  88         }
  89         return null;
  90     }
  91
  92     /**
  93      * Find and remove the cell that holds the object pointed by ptr.
  94      *
  95      * If no cell is found, no cell is removed.
  96      *
  97      * Returns a pointer to the removed cell if found, null otherwise.
  98      */
  99     Cell* pop(void* ptr)
 100     {
 101         return this.pop((Cell* cell) { return cell.ptr == ptr; });
 102     }
 103
 104     /**
 105      * Find and remove the first cell with a capacity of at least min_size.
 106      *
 107      * If no cell is found, no cell is removed.
 108      *
 109      * Returns a pointer to the removed cell if found, null otherwise.
 110      */
 111     Cell* pop(size_t min_size)
 112     {
 113         return this.pop((Cell* cell) { return cell.capacity >= min_size; });
 114     }
 115
 116     /**
 117      * Remove a cell from the list.
 118      *
 119      * If the cell was not linked into the list, this method has no effect.
 120      */
 121     void unlink(Cell* cell)
 122     {
 123         this.pop((Cell* cell2) { return cell is cell2; });
 124     }
 125
 126     /**
 127      * Iterate over the cells in the list.
 128      *
 129      * unlink()ing cells from the list while iterating is supported, but
 130      * link()ing may not work.
 131      */
 132     int opApply(int delegate(ref Cell*) dg)
 133     {
 134         int result = 0;
 135         auto cell = this.first;
 136         while (cell) {
 137             // this is necessary to allow removing a node while iterating
 138             auto next = cell.next;
 139             result = dg(cell);
 140             if (result)
 141                 break;
 142             cell = next;
 143         }
 144         return result;
 145     }
 146
 147 }
 148
 149 debug (UnitTest)
 150 {
 151
 152 private:
 153
 154     import tango.stdc.stdlib: malloc;
 155
 156     unittest // List
 157     {
 158         List l;
 159         assert (l.first == null);
 160         assert (l.find(cast(void*) null) is null);
 161         assert (l.find(cast(void*) &l) is null);
 162         Cell[5] cells;
 163         foreach (ref c; cells)
 164             l.link(&c);
 165         size_t i = 5;
 166         foreach (c; l)
 167             assert (c is &cells[--i]);
 168     }
 169
 170 } // debug (UnitTest)
 171
 172 // vim: set et sw=4 sts=4 :