Hi,

I would have thought that RefCounted!(T, RefCountedAutoInitialize.no) is to be used in place T* when I want reference counting instead of the usual garbage collection (or manual allocation). Perhaps this is wrong?

If I am correct what am I doing wrong here?

(Sorry for two space squashed style).

import std.stdio;
import std.typecons;

struct Node(T) {
  RefCounted!(Node!T, RefCountedAutoInitialize.no) next;
  T val;
}

struct List(T) {
  RefCounted!(Node!T, RefCountedAutoInitialize.no) head;
  bool empty() { return head.refCountedStore.isInitialized; }
  T front() { return head.val; }
  void popFront() { head = head.next; }
  typeof(this) save() { return typeof(this)(head); }
}

void main() {
  List!long l;
}

I also tried my own implementation but that is not working (since not everything is being freed) and probably
relies on undefined behavior with my casting away inout, which I did because
otherwise the compiler kept giving me errors about not being able to generate a copy constructor for List.

import std.stdio;
import core.stdc.stdlib;


private struct RefCountedPointer(T) {
  static struct Payload(T) {
    long cnt=1;
    T val;
  }
  Payload!T* ptr;
  this(T x) {
    ptr = cast(Payload!T*) calloc(0,Payload!T.sizeof);
    *ptr = Payload!T(1,x);
  }
  ~this() {
    if(ptr==null) { return; }
    (*ptr).cnt--;
    if((*ptr).cnt == 0) {
      ptr.val.destroy();
      free(ptr);
    }
  }
  @disable this(ref return scope immutable(typeof(this)) rhs);
  this(ref return scope inout(typeof(this)) rhs) {
    ptr = cast(Payload!T*) rhs.ptr;
    if(ptr==null) { return; }
    ptr.cnt++;
  }
  void opAssign(typeof(this) rhs) {
    if(this.ptr!=null) { (*this.ptr).cnt--; }
    this.ptr = rhs.ptr;
    if(this.ptr!=null) { (*this.ptr).cnt++; }
  }
  bool isNull() { return ptr==null; }
  ref auto dref() { assert(!isNull); return (*ptr).val; }
}

private struct Node(T) {
  RefCountedPointer!(Node!T) next;
  T val;
}


struct List(T) {
  private RefCountedPointer!(Node!T) head;
  bool empty() { return head.isNull; }
  T front() { return head.dref.val; }
  void popFront()  { head = head.dref.next;  }
  auto save() { return typeof(this)(head); }
  auto insert(T x) {
    head = RefCountedPointer!(Node!T)(Node!T(head,x));
  }
}

void main() {
  List!long list;
  list.insert(8);
import std.stdio;
import core.stdc.stdlib;


private struct RefCountedPointer(T) {
  static struct Payload(T) {
    long cnt=1;
    T val;
  }
  Payload!T* ptr;
  this(T x) {
    ptr = cast(Payload!T*) calloc(0,Payload!T.sizeof);
    *ptr = Payload!T(1,x);
  }
  ~this() {
    if(ptr==null) { return; }
    (*ptr).cnt--;
    if((*ptr).cnt == 0) {
      writeln("free");
      ptr.val.destroy();
      free(ptr);
    }
  }
  @disable this(ref return scope immutable(typeof(this)) rhs);
  this(ref return scope inout(typeof(this)) rhs) {
    ptr = cast(Payload!T*) rhs.ptr;
    if(ptr==null) { return; }
    ptr.cnt++;
  }
  void opAssign(typeof(this) rhs) {
    "here".writeln;
    if(this.ptr!=null) { (*this.ptr).cnt--; }
    this.ptr = rhs.ptr;
    if(this.ptr!=null) { (*this.ptr).cnt++; }
  }
  bool isNull() { return ptr==null; }
  ref auto dref() { assert(!isNull); return (*ptr).val; }
}

private struct Node(T) {
  RefCountedPointer!(Node!T) next;
  T val;
}


struct List(T) {
  private RefCountedPointer!(Node!T) head;
  bool empty() { return head.isNull; }
  T front() { return head.dref.val; }
  void popFront()  { head = head.dref.next;  }
  auto save() { return typeof(this)(head); }
  auto insert(T x) {
    head = RefCountedPointer!(Node!T)(Node!T(head,x));
  }
}

void main() {
  List!long list;
  list.insert(8);
import std.stdio;
import core.stdc.stdlib;


private struct RefCountedPointer(T) {
  static struct Payload(T) {
    long cnt=1;
    T val;
  }
  Payload!T* ptr;
  this(T x) {
    ptr = cast(Payload!T*) calloc(0,Payload!T.sizeof);
    *ptr = Payload!T(1,x);
  }
  ~this() {
    if(ptr==null) { return; }
    (*ptr).cnt--;
    if((*ptr).cnt == 0) {
      writeln("free");
      ptr.val.destroy();
      free(ptr);
    }
  }
  @disable this(ref return scope immutable(typeof(this)) rhs);
  this(ref return scope inout(typeof(this)) rhs) {
    ptr = cast(Payload!T*) rhs.ptr;
    if(ptr==null) { return; }
    ptr.cnt++;
  }
  void opAssign(typeof(this) rhs) {
    "here".writeln;
    if(this.ptr!=null) { (*this.ptr).cnt--; }
    this.ptr = rhs.ptr;
    if(this.ptr!=null) { (*this.ptr).cnt++; }
  }
  bool isNull() { return ptr==null; }
  ref auto dref() { assert(!isNull); return (*ptr).val; }
}

private struct Node(T) {
  RefCountedPointer!(Node!T) next;
  T val;
}


struct List(T) {
  private RefCountedPointer!(Node!T) head;
  bool empty() { return head.isNull; }
  T front() { return head.dref.val; }
  void popFront()  { head = head.dref.next;  }
  auto save() { return typeof(this)(head); }
  auto insert(T x) {
    head = RefCountedPointer!(Node!T)(Node!T(head,x));
  }
}

void main() {
  List!long list;
  list.insert(8);
  list.insert(7);
  list.insert(6);
  list.insert(5);
  list.insert(4);
  list.popFront;
  list.writeln;
  list.insert(4);
  list.insert(3);
  list.insert(2);
  list.insert(1);
  list.writeln;
}

On Wednesday, 13 April 2022 at 20:47:33 UTC, JG wrote:

Perhaps I should have added in case it is relevant, I am not actually interested in building lists. I eventually want to use this in a "persistent" version of a red black tree (where if r is such a tree and we set r1=r.insert(x) then r is unaffected and r1 has the new element inserted - but they share most nodes). This data structure is to be used in a multithreaded application searching for a solution to some problem. The current version has bad performance seemingly due to gc stopping all threads while freeing unused nodes.

On Wednesday, 13 April 2022 at 21:15:13 UTC, JG wrote:

I don't know what RefCount is for but I fixed your codes that mixed up:

import std.stdio;
import core.stdc.stdlib;

 private struct RefCountedPointer(T) {
   static struct Payload(T) {
     int cnt = 1;
     T val;
   }

   Payload!T* ptr;

   this(T x) {
     ptr = cast(Payload!T*) calloc(0, Payload!T.sizeof);
     *ptr = Payload!T(1, x);
   }

   ~this() {
     if(ptr == null) {
       return;
     }
     (*ptr).cnt--;

     if((*ptr).cnt == 0) {
       writeln("free");
       ptr.val.destroy();
       free(ptr);
     }
   }

   @disable
   this(ref return scope immutable(typeof(this)) rhs);

   this(ref return scope inout(typeof(this)) rhs) {
     ptr = cast(Payload!T*) rhs.ptr;
     if(ptr == null) {
       return;
     }
     ptr.cnt++;
   }

   void opAssign(typeof(this) rhs) {
     "here".writeln;
     if(this.ptr != null) {
       (*this.ptr).cnt--;
     }

     this.ptr = rhs.ptr;

     if(this.ptr != null) {
       (*this.ptr).cnt++;
     }
   }

   bool isNull() {
     return ptr == null;
   }

   ref auto dref() {
     assert(!isNull);
     return (*ptr).val;
   }
 }

 struct List(T) {
   private RefCountedPointer!(Node!T) head;
   bool empty() { return head.isNull; }
   T front() { return head.dref.val; }
   void popFront()  { head = head.dref.next;  }
   auto save() { return typeof(this)(head); }
   auto insert(T x) { head = RefCountedPointer!(Node!T)(Node!T(head,x)); }
 }

 private struct Node(T) {
   RefCountedPointer!(Node!T) next;
   T val;
 }

void main()
{
   List!long list;
   list.insert(8);
   list.insert(7);
   list.insert(6);
   list.insert(5);
   list.insert(4);
   list.popFront;
   list.writeln;
   list.insert(4);
   list.insert(3);
   list.insert(2);
   list.insert(1);
   list.writeln;
}

On Wednesday, 13 April 2022 at 20:47:33 UTC, JG wrote:

In case some one has a similar problem, try: https://code.dlang.org/packages/automem

import std.stdio;
import std.experimental.allocator.mallocator;
import std.experimental.allocator;
import automem;

    struct Node(T) {
      RefCounted!(Node!T) next;
      T val;
    }

    struct List(T) {
      RefCounted!(Node!T) head;
      bool empty() { return head == null; }
      T front() { return head.val; }
      void popFront() { head = head.next; }
      typeof(this) save() { return typeof(this)(head); }
      void insert(T x) {
        head = RefCounted!(Node!T)(head,x);
      }
    }

    void main() {
      theAllocator = allocatorObject(Mallocator.instance);
      List!long l;
      l.insert(5);
      l.insert(4);
      l.insert(3);
      l.insert(2);
      l.insert(1);
      writeln(l);
    }
    ```