www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Are one or more standard data structure libraries available? Efficient? Reliable?

reply "Lynn Allan" <l_d_allan adelphia.net> writes:
Sorry if this has been asked previously.

My impression is that several proposed libraries are being developed
that are intended to (eventually?) provide data structures (ares,
diemos, dtl). Also, it seems that one or more of the emerging gui
libraries have their own data structures (DFL has ObjectCollection for
ListBox, TreeNodeCollection for TreeView, etc.).

I'd appreciate getting the status of data structure library
availability. Has a standard emerged? Or is one of the 'candidates'
anticipated to be accepted as a standard?

The ones I've looked at seem more or less stuck at versions less than
0.5. Some (most?) seem prone to "breaking" when a new release of DMD
arrives. It seems unfortunate / flawed if there will be a variety of
"wheel reinventions". Sigh.

On a related note, I wanted to check if significant performance
penalties accompany the following documented way of handling dynamic
arrays:

http://www.digitalmars.com/d/ctod.html#arraycreate
Creating an array of variable size
The C Way
<snip>

The D Way
D supports dynamic arrays, which can be easily resized. D supports all
the requisite memory management.




To this newbie, this seems "expensive", but perhaps there are
optimizations going on "behind the scenes". I want to do searching
thru a number of documents, and return an arbitrarily sized array of
"SearchHits". I didn't find standard data structures in phobos (list,
queue, tree, etc), but I note that Associative Arrays are part of the
language (very cool :-). I'd rather not do my own memory management.
Dec 24 2004
parent reply Ben Hinkle <Ben_member pathlink.com> writes:
You don't mention MinTL so in case you aren't aware of it:
http://home.comcast.net/~benhinkle/mintl/
I'm the author of that library so any comments would be welcome. It has been
stable for many months and I only recently updated some code in response to
compiler changes.

Another option is DTL:
http://www.synsoft.org/d/code/dtl_0_2_1.zip

See the newsgroup digitalmars.d.dtl for more info.

-Ben
Dec 24 2004
next sibling parent reply =?ISO-8859-1?Q?Anders_F_Bj=F6rklund?= <afb algonet.se> writes:
Ben Hinkle wrote:


 You don't mention MinTL so in case you aren't aware of it:
 http://home.comcast.net/~benhinkle/mintl/
 I'm the author of that library so any comments would be welcome. It has been
 stable for many months and I only recently updated some code in response to
 compiler changes.


One problem with MinTL is that the "Locks" sublibrary
uses X86-specific assembly - without using version(X86)
This means I would need to port that to PowerPC first...

The other problem is that the D code itself crashes (?)
the current version of GDC compiler it seems (GDC 0.9)
At least when compiling the library in unittest mode:


 concurrent/dualstack.d: In member function `addTail':
 concurrent/dualstack.d:93: internal compiler error: in smallest_mode_for_size,
at stor-layout.c:264



 concurrent/dualqueue.d: In member function `addTail':
 concurrent/dualqueue.d:113: internal compiler error: in simplify_gen_subreg,
at simplify-rtx.c:2752


Has it been tested with anything besides DMD and X86 ?

--anders
Dec 25 2004
parent reply Ben Hinkle <Ben_member pathlink.com> writes:
In article <cqjmtv$2am3$1 digitaldaemon.com>,
=?ISO-8859-1?Q?Anders_F_Bj=F6rklund?= says...

Ben Hinkle wrote:


 You don't mention MinTL so in case you aren't aware of it:
 http://home.comcast.net/~benhinkle/mintl/
 I'm the author of that library so any comments would be welcome. It has been
 stable for many months and I only recently updated some code in response to
 compiler changes.


One problem with MinTL is that the "Locks" sublibrary
uses X86-specific assembly - without using version(X86)
This means I would need to port that to PowerPC first...


At one point I had a non-asm code that implemented atomic memory operations
using a critical section, but I guess I took that out. I should put that back in
until someone can code up custom asm blocks for each cpu.


The other problem is that the D code itself crashes (?)
the current version of GDC compiler it seems (GDC 0.9)
At least when compiling the library in unittest mode:


 concurrent/dualstack.d: In member function `addTail':
 concurrent/dualstack.d:93: internal compiler error: in smallest_mode_for_size,
at stor-layout.c:264



 concurrent/dualqueue.d: In member function `addTail':
 concurrent/dualqueue.d:113: internal compiler error: in simplify_gen_subreg,
at simplify-rtx.c:2752


Has it been tested with anything besides DMD and X86 ?


I'll give it a try. I have access to mac at work so I'll see if I can get myself
set up to give it a whirl. If you have a patch you can also email it to me and
I'll put it in.

-Ben
Dec 25 2004
parent reply =?ISO-8859-1?Q?Anders_F_Bj=F6rklund?= <afb algonet.se> writes:
Ben Hinkle wrote:


One problem with MinTL is that the "Locks" sublibrary
uses X86-specific assembly - without using version(X86)
This means I would need to port that to PowerPC first...


 
 At one point I had a non-asm code that implemented atomic memory operations
 using a critical section, but I guess I took that out. I should put that back
in
 until someone can code up custom asm blocks for each cpu.


GDC does *not* support inline assembly (yet), so it will
have to be written in C instead. (with asm files/blocks)
That would make it able to compile for X86, at least...

There is some PPC code in libkern that comes with the XNU
kernel, only problem being the Apple Public Source License:
http://www.opensource.apple.com/darwinsource/10.3.7/xnu-517.9.5/libkern/


But the first point would be to flag the non-portable
code using "version" statements in the D source code ?

Or maybe the locking / concurrent versions can be made
optional, so that one can compile a min-minTL library ? :-)

--anders
Dec 26 2004
parent Ben Hinkle <Ben_member pathlink.com> writes:
In article <cqm2bf$1deq$1 digitaldaemon.com>,
=?ISO-8859-1?Q?Anders_F_Bj=F6rklund?= says...

Ben Hinkle wrote:


One problem with MinTL is that the "Locks" sublibrary
uses X86-specific assembly - without using version(X86)
This means I would need to port that to PowerPC first...


 
 At one point I had a non-asm code that implemented atomic memory operations
 using a critical section, but I guess I took that out. I should put that back
in
 until someone can code up custom asm blocks for each cpu.


GDC does *not* support inline assembly (yet), so it will
have to be written in C instead. (with asm files/blocks)
That would make it able to compile for X86, at least...

There is some PPC code in libkern that comes with the XNU
kernel, only problem being the Apple Public Source License:
http://www.opensource.apple.com/darwinsource/10.3.7/xnu-517.9.5/libkern/


But the first point would be to flag the non-portable
code using "version" statements in the D source code ?


good idea.


Or maybe the locking / concurrent versions can be made
optional, so that one can compile a min-minTL library ? :-)


Linking in the locks library is only needed if you use one of the concurrent
containers (in the mintl.concurrent package). I should point that out better in
the doc. Most of the time I don't link in locks since I typically only use the
non-concurrent containers. If that isn't true then I've messed something up and
I should fix it.


--anders
Dec 26 2004
prev sibling parent reply "Lynn Allan" <l_d_allan adelphia.net> writes:
Thanks for the "heads-up". MinTL appears quite close to what I'm
looking for. Thanks for providing it.

But ...

I get the following errors trying to compile/link the basic
"hello_mintl.d" program. I think I followed the instructions, and
tried various combinations of directory placements and references to
shared.d.

Can you advise what I'm doing wrong? All I want to do is link to the
prebuilt mintl.lib provided in the mintl.zip

I'm using WinXp-Home, MinTL 2.01, and dmd 0.109.
dmd -c test.d compiles fine. The problem seems to be in the linker
step.

***** error messages from linker  *****

X:\DevTools\Dmd\bin\link.exe
Test+share,,,mintl.lib+user32+kernel32/noi;

OPTLINK (R) for Win32  Release 7.50B1
Copyright (C) Digital Mars 1989 - 2001  All Rights Reserved

Test.obj(Test)
 Error 42: Symbol Undefined _assert_5mintl4list
Test.obj(Test)
 Error 42: Symbol Undefined _array_5mintl4list
--- errorlevel 2
Dec 27 2004
next sibling parent reply "Lynn Allan" <l_d_allan adelphia.net> writes:
Nevermind ...

It compiles if the mintl.lib isn't used, but rather the data structure
being used is compiled with the test program ...

dmd test.d list.d    .... works

mintl.lib doesn't seem to be usable for some reason? I suppose I'm
doing something wrong?
Dec 27 2004
parent reply Ben Hinkle <Ben_member pathlink.com> writes:
In article <cqq1md$2d3p$1 digitaldaemon.com>, Lynn Allan says...

Nevermind ...

It compiles if the mintl.lib isn't used, but rather the data structure
being used is compiled with the test program ...

dmd test.d list.d    .... works

mintl.lib doesn't seem to be usable for some reason? I suppose I'm
doing something wrong?


What does the error message say? Maybe I've seen it before. While I'm asking
questions, what version of the compiler are you using?
Dec 27 2004
parent reply "Lynn Allan" <l_d_allan adelphia.net> writes:
Here's the error messages as noted in several previous emails

**************************

Thanks for the "heads-up". MinTL appears quite close to what I'm
looking for. Thanks for providing it.

But ...

I get the following errors trying to compile/link the basic
"hello_mintl.d" program. I think I followed the instructions, and
tried various combinations of directory placements and references to
shared.d.

Can you advise what I'm doing wrong? All I want to do is link to the
prebuilt mintl.lib provided in the mintl.zip

I'm using WinXp-Home, MinTL 2.01, and dmd 0.109.
dmd -c test.d compiles fine. The problem seems to be in the linker
step.

***** error messages from linker  *****

X:\DevTools\Dmd\bin\link.exe
Test+share,,,mintl.lib+user32+kernel32/noi;

OPTLINK (R) for Win32  Release 7.50B1
Copyright (C) Digital Mars 1989 - 2001  All Rights Reserved

Test.obj(Test)
 Error 42: Symbol Undefined _assert_5mintl4list
Test.obj(Test)
 Error 42: Symbol Undefined _array_5mintl4list
--- errorlevel 2





"Ben Hinkle" <Ben_member pathlink.com> wrote in message
news:cqqf5u$2v00$1 digitaldaemon.com...

 In article <cqq1md$2d3p$1 digitaldaemon.com>, Lynn Allan says...

Nevermind ...

It compiles if the mintl.lib isn't used, but rather the data




structure

being used is compiled with the test program ...

dmd test.d list.d    .... works

mintl.lib doesn't seem to be usable for some reason? I suppose I'm
doing something wrong?


 What does the error message say? Maybe I've seen it before. While


I'm asking

 questions, what version of the compiler are you using?
Dec 28 2004
parent Ben Hinkle <Ben_member pathlink.com> writes:
In article <cqs7qt$1nsm$1 digitaldaemon.com>, Lynn Allan says...

Here's the error messages as noted in several previous emails


ok. I'll look into it when I get back to my regular machine next week. One
possible solution is try rebuilding the mintl.lib and experiment with various
compiler flags for it -g or -release etc.
The fact that it can't find assert tells me the library was built with -release
and I might need to provide debug and non-debug builds.
Dec 29 2004
prev sibling parent "Ben Hinkle" <bhinkle mathworks.com> writes:
"Lynn Allan" <l_d_allan adelphia.net> wrote in message
news:cqp3ul$1cmd$1 digitaldaemon.com...

 Thanks for the "heads-up". MinTL appears quite close to what I'm
 looking for. Thanks for providing it.

 But ...

 I get the following errors trying to compile/link the basic
 "hello_mintl.d" program. I think I followed the instructions, and
 tried various combinations of directory placements and references to
 shared.d.

 Can you advise what I'm doing wrong? All I want to do is link to the
 prebuilt mintl.lib provided in the mintl.zip


I reproduced the error and it was due to the libray being built without
debug info. I added a build of mintl.lib with debug info called
mintl_debug.lib. So to use mintl on windows run something like
 dmd foo.d mintl\mintl.lib -O -release
or
 dmd foo.d mintl\mint_debug.lib
depending on if the debug info is needed or not.

If I get off my lazy butt I'll boot into Linux and make a similar debug
build for libmintl.a

enjoy,
-Ben
Jan 04 2005