I have this struct (with details omitted ... for brevity):

struct Deb {
    string name;
    ...
    RedBlackTree!string tags;

    void clear() { name = ""; ...; tags.clear; }

    bool valid() { return !(name.empty || description.empty); }
}

I plan to store >65K of these (with potential for growth to >250K) in an AA:

Deb[string] debForName;

I plan to populate debForName by reading data files (actually Debian Packages files) like this:

Deb deb;
auto file = File(filename):
foreach(line; file.byLine) {
    if (line.empty) {
        if (deb.valid) // end of package
            debForName[deb.name] = deb; // XXX
        // else report incomplete package
        deb.clear;
        continue;
    }
    ... // populate the deb
}
if (deb.valid)
    debForName[deb.name] = deb;

I'm assuming that line XXX will copy the Deb including the tree (which as usual I'm using as a set -- I really miss a set class in D!). Will this work (I'll find out myself next week when I get further, but D experts can likely tell from the above).

Should Deb be a class rather than a struct?

07.03.2020 13:20, mark пишет:
> I have this struct (with details omitted
> [ snip ]
> Should Deb be a class rather than a struct?

Do you consider using pointers in AA:
```
Deb*[string] debForName;
```

On Saturday, 7 March 2020 at 10:30:06 UTC, drug wrote:
> 07.03.2020 13:20, mark пишет:
>> I have this struct (with details omitted
>> [ snip ]
>> Should Deb be a class rather than a struct?
>
> Do you consider using pointers in AA:
> ```
> Deb*[string] debForName;
> ```

I've done some changes including using Deb* as you suggested:

struct Deb {
    string name;
    ...
    RedBlackTree!string tags;

    bool valid() { return !(name.empty || description.empty); }

    size_t toHash() const @safe nothrow {
        return typeid(name).getHash(&name); // names are unique
    }

    bool opEquals(const Deb other) const @safe pure nothrow {
        return name == other.name; // names are unique
    }

    int opCmp(ref const Deb other) const {
        return cmp(name, other.name); // names are unique
    }
}

Which I now want to store in:

RedBlackTree!Deb* debs; // name-ordered list of deb packages

And now I'm populating like this:

Deb* deb;
auto file = File(filename);
foreach(line; file.byLine) {
    line = strip(line);
    if (line.empty) {
        if (deb != null && deb.valid) {
            debs.insert(deb);
            deb.clear;
        }
        // else report incomplete package
        continue;
    }
    if (deb == null)
        deb = new Deb;
    ...
}
if (deb != null && deb.valid)
    debs.insert(deb);

But it crashes with:

Performing "debug" build using /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 for x86_64.
gtk-d:gtkd 3.9.0: target for configuration "library" is up to date.
debfind ~master: building configuration "application"...
src/model.d(96,36): Error: template std.container.rbtree.RedBlackTree!(Deb, "a < b", false).RedBlackTree.stableInsert cannot deduce function from argument types !()(Deb*), candidates are:
/home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/../import/std/container/rbtree.d(1256,12):        stableInsert(Stuff)(Stuff stuff)
  with Stuff = Deb*
  must satisfy the following constraint:
       isImplicitlyConvertible!(Stuff, Elem)
...

Instead of deb.clear I'm now doing deb = null;

change #1:

                if (line.empty) {
                    if (deb != null && deb.valid)
                        debs.insert(deb);
                    else // report incomplete
                    deb = null;
                    continue;
                }
                if (deb == null)
                    deb = new Deb;

change #2: gets rid of most errors:

    bool opEquals(const Deb* other) const @safe pure nothrow {

    int opCmp(ref const Deb* other) const {

Just changed to pointers & moved to a separate file.

So now I just have one error in line 12 of model.d:

RedBlackTree!Deb* debs; // name-ordered list of deb packages LINE 12


Performing "debug" build using /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 for x86_64.
gtk-d:gtkd 3.9.0: target for configuration "library" is up to date.
debfind ~master: building configuration "application"...
src/model.d(12,9): Error: template instance std.container.rbtree.RedBlackTree!(Deb) does not match template declaration RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
  with T = Deb
  must satisfy the following constraint:
       is(typeof(binaryFun!less(T.init, T.init)))
/home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 failed with exit code 1.

07.03.2020 13:58, mark пишет:
> change #1:
> 
>                  if (line.empty) {
>                      if (deb != null && deb.valid)
>                          debs.insert(deb);
>                      else // report incomplete
>                      deb = null;
>                      continue;
>                  }
>                  if (deb == null)
>                      deb = new Deb;
> 
> change #2: gets rid of most errors:
> 
>      bool opEquals(const Deb* other) const @safe pure nothrow {
> 
>      int opCmp(ref const Deb* other) const {
> 
> Just changed to pointers & moved to a separate file.
> 
> So now I just have one error in line 12 of model.d:
> 
> RedBlackTree!Deb* debs; // name-ordered list of deb packages LINE 12
> 
> 
> Performing "debug" build using /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 for x86_64.
> gtk-d:gtkd 3.9.0: target for configuration "library" is up to date.
> debfind ~master: building configuration "application"...
> src/model.d(12,9): Error: template instance std.container.rbtree.RedBlackTree!(Deb) does not match template declaration RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
>    with T = Deb
>    must satisfy the following constraint:
>         is(typeof(binaryFun!less(T.init, T.init)))
> /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 failed with exit code 1.
> 

try
```
RedBlackTree!(Deb*) debs;
```

On 3/7/20 5:58 AM, mark wrote:
> change #1:
> 
>                  if (line.empty) {
>                      if (deb != null && deb.valid)
>                          debs.insert(deb);
>                      else // report incomplete
>                      deb = null;
>                      continue;
>                  }
>                  if (deb == null)
>                      deb = new Deb;
> 
> change #2: gets rid of most errors:
> 
>      bool opEquals(const Deb* other) const @safe pure nothrow {
> 
>      int opCmp(ref const Deb* other) const {
> 
> Just changed to pointers & moved to a separate file.
> 
> So now I just have one error in line 12 of model.d:
> 
> RedBlackTree!Deb* debs; // name-ordered list of deb packages LINE 12
> 
> 
> Performing "debug" build using /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 for x86_64.
> gtk-d:gtkd 3.9.0: target for configuration "library" is up to date.
> debfind ~master: building configuration "application"...
> src/model.d(12,9): Error: template instance std.container.rbtree.RedBlackTree!(Deb) does not match template declaration RedBlackTree(T, alias less = "a < b", bool allowDuplicates = false)
>    with T = Deb
>    must satisfy the following constraint:
>         is(typeof(binaryFun!less(T.init, T.init)))
> /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/ldc2 failed with exit code 1.
> 

Hm... I'd say:

1. Don't use a pointer for the element. Just use the struct directly. Using a pointer is bad because it's now going to compare pointers, and not the element data. Not only that, but RBNodes are stored as heap-allocated structs, so you are wasting a lot of memory by allocating another heap allocated thing to get stored inside there.

2. RedBlackTree allows you to identify the relationship that you consider unique by providing a "less" function. Instead of instrumenting your Deb type, which might affect other usages, just do:

RedBlackTree!(Deb, (a, b) => a.name < b.name)

No need to add opCmp and opEquals (if that doesn't make sense in other contexts).

-Steve

I've now gone back to using structs direct without pointers but I'm still doing something wrong.

struct Deb {
    string name;
    ...
    RedBlackTree!string tags;

    bool valid() { return !(name.empty || description.empty); }

    void clear() { name = ""; ...; tags.clear; }
}

RedBlackTree!(Deb, (a, b) => a.name < b.name) debs;

Deb deb;
auto file = File(filename);
foreach(line; file.byLine) {
    line = strip(line);
    if (line.empty) {
        if (deb.valid)
            debs.insert(deb); // XXX
        else // report incomplete
        deb.clear;
        continue;
    }
    ...
}
if (deb.valid)
    debs.insert(deb);

This compiles & crashes with "Program exited with code -11".

What I'm trying to do but clearly don't understand is this:

1. create a struct
repeat:
 2.1. populate the struct
 2.2. copy the struct into an rbtree // XXX
 2.3. clear the original struct
 2.4. loop

At XXX does a copy take place? I thought it did with structs?

Anyway, here's the backtrace:

$ gdb DebFind
GNU gdb (Ubuntu 8.1-0ubuntu3.2) 8.1.0.20180409-git
...
Reading symbols from DebFind...done.
(gdb) run
Starting program: /home/mark/app/d/debfind/DebFind
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
[New Thread 0x7ffff6e02700 (LWP 2366)]
...

Thread 1 "DebFind" received signal SIGSEGV, Segmentation fault.
0x0000555555701ef0 in _D3std9container6rbtree__T12RedBlackTreeTAyaVQea5_61203c2062Vbi0ZQBn5emptyMFNaNbNdNiNfZb (this=0x0)
    at /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/../import/std/container/rbtree.d:967
967	        return _end.left is null;
(gdb) bt
#0  0x0000555555701ef0 in _D3std9container6rbtree__T12RedBlackTreeTAyaVQea5_61203c2062Vbi0ZQBn5emptyMFNaNbNdNiNfZb (this=0x0)
    at /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/../import/std/container/rbtree.d:967
#1  0x0000555555701a11 in qtrac.debfind.model.Model.readPackageFile(immutable(char)[]) (this=0x0, filename=...) at model.d:66
warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

warning: (Internal error: pc 0x55555591b820 in read in psymtab, but not in symtab.)

warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

#2  0x0000555555701671 in qtrac.debfind.model.Model.initialize(int) (this=0x0, maxDebNamesForWord=100) at model.d:31
warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

#3  0x00005555557045b0 in _D5qtrac7debfind9appwindow9AppWindow6__ctorMFC3gtk11ApplicationQnZCQCnQCkQCfQBy (this=0x7ffff7ece630, application=0x7ffff7ed1360) at appwindow.d:31
#4  0x0000555555722819 in _D5qtrac7debfind3app4mainFAAyaZ__T12__dgliteral2TC3gio11ApplicationQnZQBkMFQBaZv (GioApplication=0x7ffff7ed1360) at app.d:16
#5  0x000055555575be54 in _D7gobject8DClosureQj__T17d_closure_marshalTDFC3gio11ApplicationQnZvZQBtUPSQCv1c5types8GClosurePSQDrQwQw6GValuekQrPvQcZv (closure=0x555555c37690, return_value=0x0, n_param_values=1, param_values=0x7ffff7ef46e0, invocation_hint=0x7fffffffd710 "\b", marshal_data=0x0) at DClosure.d:122
#6  0x00007ffff419410d in g_closure_invoke () at /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#7  0x00007ffff41a705e in  () at /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#8  0x00007ffff41af715 in g_signal_emit_valist () at /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
#9  0x00007ffff41b012f in g_signal_emit () at /usr/lib/x86_64-linux-gnu/libgobject-2.0.so.0
warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

#10 0x00007fffee148b95 in  () at /usr/lib/x86_64-linux-gnu/libgio-2.0.so.0
warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

#11 0x00007fffee148da6 in g_application_run () at /usr/lib/x86_64-linux-gnu/libgio-2.0.so.0
warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

#12 0x000055555591b875 in warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

_D3gio11ApplicationQn3runMFAAyaZiwarning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

 (warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

this=0x7ffff7ed1360, warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

argv=...)warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

 at Application.dwarning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

warning: (Internal error: pc 0x55555591b874 in read in psymtab, but not in symtab.)

:931
#13 0x0000555555722760 in D main (args=...) at app.d:18


And thanks for helping!

07.03.2020 15:58, Steven Schveighoffer пишет:
> 
> Hm... I'd say:
> 
> 1. Don't use a pointer for the element. Just use the struct directly. Using a pointer is bad because it's now going to compare pointers, and not the element data. Not only that, but RBNodes are stored as heap-allocated structs, so you are wasting a lot of memory by allocating another heap allocated thing to get stored inside there.
> 
You can use predicate to solve the issue like you suggest below. But I'm totally missed that RBNodes are heap-allocated, thanks!

> 2. RedBlackTree allows you to identify the relationship that you consider unique by providing a "less" function. Instead of instrumenting your Deb type, which might affect other usages, just do:
> 
> RedBlackTree!(Deb, (a, b) => a.name < b.name)
>  > No need to add opCmp and opEquals (if that doesn't make sense in other
> contexts).
> 
> -Steve

On 3/7/20 8:22 AM, mark wrote:
> 0x0000555555701ef0 in _D3std9container6rbtree__T12RedBlackTreeTAyaVQea5_61203c2062Vbi0ZQBn5emptyMFNaNbNdNiNfZb (this=0x0)
>      at /home/mark/opt/ldc2-1.20.0-linux-x86_64/bin/../import/std/container/rbtree.d:967 
> 
> 967            return _end.left is null;
> (gdb) bt
> #0  0x0000555555701ef0 in _D3std9container6rbtree__T12RedBlackTreeTAyaVQea5_61203c2062Vbi0ZQBn5emptyMFNaNbNdNiNfZb (this=0x0)

RedBlackTree is a class. Make sure you allocate it. The above shows "this = 0x0".

I saw a few other "this = 0x0" items, but perhaps that's OK for your code, I don't know what those types are.

-Steve