Pastebin is 300% more awesome when you are logged in. Sign Up, it's FREE!
Guest

Refcounted containers prototype

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