Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Untitled

By: a guest on Dec 26th, 2011  |  syntax: D  |  size: 5.83 KB  |  views: 145  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #!/usr/bin/env rdmd -unittest
  2.  
  3. import std.stdio, std.typecons;
  4.  
  5. version = DebugRefCounted;
  6.  
  7. /**
  8.  
  9. Offers reference counting on top of any type. Currently not
  10. implemented for classes.
  11.  
  12.  */
  13. struct RefCounted(T, bool cow = false) {
  14.     // We allocate payload and counter together.
  15.     private struct DataBlock
  16.     {
  17.         uint refs;
  18.         T payload;
  19.         this(uint _refs, T _payload)
  20.         {
  21.             refs = _refs;
  22.             payload = _payload;
  23.         }
  24.     }
  25.  
  26.     // This is the entire state
  27.     private DataBlock * data;
  28.  
  29.     // "empty" object intended for static and immutable methods when
  30.     // the data pointer is null. It won't be modified. We assume the
  31.     // empty object is equivalent to a null stored pointer.
  32.     private static immutable T _empty;
  33.  
  34.     private ref immutable(T) asImmutable() immutable
  35.     {
  36.         return data ? data.payload : _empty;
  37.     }
  38.  
  39.     private ref const(T) asConst() const
  40.     {
  41.         return data ? data.payload : _empty;
  42.     }
  43.  
  44.     // Makes sure that the payload exists. If cow, also make sure it is not shared.
  45.     void ensureUnique()
  46.     {
  47.         if (!data)
  48.         {
  49.             data = new DataBlock(1, T.init);
  50.         }
  51.         else static if (cow)
  52.         {
  53.             if (data.refs > 1)
  54.             {
  55.                 data = new DataBlock(1, data.payload.dup);
  56.             }
  57.         }
  58.     }
  59.  
  60.     // Copying adds to the reference count
  61.     this(this)
  62.     {
  63.         if (!data) return;
  64.         ++data.refs;
  65.         version(DebugRefCounted) writeln("Increasing refcount to ", data.refs);
  66.     }
  67.  
  68.     void opAssign(ref RefCounted rhs)
  69.     {
  70.         if (data is rhs.data) return;
  71.         version(DebugRefCounted) writeln("Assigning to ", data ? "existing object." : "empty object.");
  72.         this.__dtor();
  73.         data = rhs.data;
  74.         if (data) ++data.refs;
  75.     }
  76.  
  77.     // Destruction deletes the target if no more references
  78.     ~this()
  79.     {
  80.         if (!data || --data.refs) return;
  81.         version(DebugRefCounted) writeln("Gone with the wind.");
  82.         data.payload.dispose();
  83.     }
  84.  
  85.     // Const methods against the data
  86.     auto ref opDispatch(string fun, A...)(auto ref A args) const
  87.     {
  88.         version(DebugRefCounted) writeln("Calling ", fun, "(", args, ") const.");
  89.         return mixin("asConst()." ~ fun ~ "(args)");
  90.     }
  91.  
  92.     // Immutable methods against the data
  93.     auto ref opDispatch(string fun, A...)(auto ref A args) immutable
  94.     {
  95.         version(DebugRefCounted) writeln("Calling ", fun, "(", args, ") immutable.");
  96.         return mixin("asImmutable()." ~ fun ~ "(args)");
  97.     }
  98.  
  99.     // Non-const methods always ensure that the payload is unique
  100.     // prior to the call.
  101.     auto ref opDispatch(string fun, A...)(auto ref A args)
  102.     {
  103.         alias typeof(mixin("data.payload." ~ fun ~ "(args)")) Result;
  104.         static if (is(typeof(mixin("asConst()." ~ fun ~ "(args)")) ConstResult))
  105.         {
  106.             // Invoking the method as const would work! Let's see
  107.             // whether the programmer intended it to work the same as
  108.             // for non-const objects.
  109.             static if (is(Result == ConstResult))
  110.             {
  111.                 // Same thing, let's save some sweat and call the const method
  112.                 version(DebugRefCounted) writeln("Calling ", T.stringof, ".", fun, "(", args, ") const.");
  113.                 return mixin("asConst()." ~ fun ~ "(args)");
  114.             }
  115.             else
  116.             {
  117.                 // Ehm, must call the non-const version
  118.                 ensureUnique();
  119.                 assert(data);
  120.                 version(DebugRefCounted) writeln("Calling ", T.stringof, ".", fun, "(", args, ").");
  121.                 return mixin("data.payload." ~ fun ~ "(args)");
  122.             }
  123.         }
  124.         else
  125.         {
  126.             // Only mutable version is callable.
  127.             version(DebugRefCounted) writeln("Calling ", T.stringof, ".", fun, "(", args, ").");
  128.             ensureUnique();
  129.             assert(data);
  130.             return mixin("data.payload." ~ fun ~ "(args)");
  131.         }
  132.     }
  133. }
  134.  
  135. /**
  136.  
  137. Doubly-linked list prototype.
  138.  
  139.  */
  140. struct DListImpl(T)
  141. {
  142.     struct Node
  143.     {
  144.         Node * prev, next;
  145.         T payload;
  146.         this(T payload)
  147.         {
  148.             this.payload = payload;
  149.         }
  150.     }
  151.     Node * root;
  152.  
  153.     static void connect(Node* first, Node* second)
  154.     {
  155.         assert(first && second);
  156.         first.next = second;
  157.         second.prev = first;
  158.     }
  159.  
  160.     void insertFront(T value)
  161.     {
  162.         auto n = new Node(value);
  163.         if (root)
  164.         {
  165.             connect(n, root);
  166.         }
  167.         root = n;
  168.     }
  169.  
  170.     @property ref T front()
  171.     {
  172.         assert(root);
  173.         return root.payload;
  174.     }
  175.  
  176.     @property bool empty() const
  177.     {
  178.         return !root;
  179.     }
  180.  
  181.     void dispose()
  182.     {
  183.         for (auto n = root; n; )
  184.         {
  185.             auto goner = n;
  186.             n = n.next;
  187.             delete goner;
  188.         }
  189.         root = null;
  190.     }
  191.  
  192.     DListImpl dup()
  193.     {
  194.         DListImpl result;
  195.         if (!root) return result;
  196.         result.root = new Node(root.payload);
  197.         auto target = root;
  198.         for (auto n = root.next; n; n = n.next)
  199.         {
  200.             auto dupe = new Node(n.payload);
  201.             connect(target, dupe);
  202.             target = dupe;
  203.         }
  204.         return result;
  205.     }
  206. }
  207.  
  208. template DList(T, bool cow = false)
  209. {
  210.     alias RefCounted!(DListImpl!T, cow) DList;
  211. }
  212.  
  213. unittest
  214. {
  215.     DList!(int, true) lst;
  216.     assert(lst.empty);
  217.     lst.insertFront(42);
  218.     assert(lst.front == 42);
  219.     auto p = &lst.front;
  220.     assert(*p == 42);
  221.  
  222.     // Assignment
  223.     lst = lst;
  224.     DList!(int, true) lst2;
  225.     lst2 = lst;
  226.     lst2.insertFront(43);
  227.     assert(lst.front == 42);
  228.     assert(lst2.front == 43);
  229.     lst = lst2;
  230. }
  231.  
  232. void main(){}