list.d

   1 /**
   2  * This module contains a minimal garbage collector implementation according to
   3  * Tango requirements.  This library is mostly intended to serve as an example,
   4  * but it is usable in applications which do not rely on a garbage collector
   5  * to clean up memory (ie. when dynamic array resizing is not used, and all
   6  * memory allocated with 'new' is freed deterministically with 'delete').
   7  *
   8  * Please note that block attribute data must be tracked, or at a minimum, the
   9  * FINALIZE bit must be tracked for any allocated memory block because calling
  10  * rt_finalize on a non-object block can result in an access violation.  In the
  11  * allocator below, this tracking is done via a leading uint bitmask.  A real
  12  * allocator may do better to store this data separately, similar to the basic
  13  * GC normally used by Tango.
  14  *
  15  * Copyright: Public Domain
  16  * License:   BOLA
  17  * Authors:   Leandro Lucarella
  18  */
  19
  20 module list;
  21
  22 private import cell: Cell;
  23 private import alloc: mem_free;
  24
  25 struct List
  26 {
  27
  28     Cell* first;
  29
  30     Cell* find(bool delegate(Cell*) predicate)
  31     {
  32         auto cell = this.first;
  33         while (cell) {
  34             if (predicate(cell))
  35                 return cell;
  36             cell = cell.next;
  37         }
  38         return null;
  39     }
  40
  41     Cell* find(void* ptr)
  42     {
  43         return this.find((Cell* cell) { return cell.ptr == ptr; });
  44     }
  45
  46     void link(Cell* cell)
  47     {
  48         cell.next = this.first;
  49         this.first = cell;
  50     }
  51
  52     Cell* pop(bool delegate(Cell*) predicate)
  53     {
  54         Cell* prev = null;
  55         auto cell = this.first;
  56         while (cell) {
  57             if (predicate(cell)) {
  58                 if (prev)
  59                     prev.next = cell.next;
  60                 else
  61                     this.first = cell.next;
  62                 return cell;
  63             }
  64             prev = cell;
  65             cell = cell.next;
  66         }
  67         return null;
  68     }
  69
  70     Cell* pop(void* ptr)
  71     {
  72         return this.pop((Cell* cell) { return cell.ptr == ptr; });
  73     }
  74
  75     Cell* pop(size_t min_size)
  76     {
  77         return this.pop((Cell* cell) { return cell.capacity >= min_size; });
  78     }
  79
  80     void unlink(Cell* cell)
  81     {
  82         this.pop((Cell* cell2) { return cell is cell2; });
  83     }
  84
  85     void swap(Cell* old_cell, Cell* new_cell)
  86     {
  87         Cell* prev = null;
  88         auto cell = this.first;
  89         while (cell) {
  90             if (cell is old_cell) {
  91                 new_cell.next = cell.next;
  92                 if (prev)
  93                     prev.next = new_cell;
  94                 else
  95                     this.first = new_cell;
  96                 return;
  97             }
  98             prev = cell;
  99             cell = cell.next;
 100         }
 101     }
 102
 103     int opApply(int delegate(ref Cell*) dg)
 104     {
 105         int result = 0;
 106         auto cell = this.first;
 107         while (cell) {
 108             // this is necessary to allow removing node while iterating
 109             auto next = cell.next;
 110             result = dg(cell);
 111             if (result)
 112                 break;
 113             cell = next;
 114         }
 115         return result;
 116     }
 117
 118 }
 119
 120 // vim: set et sw=4 sts=4 :