www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How should I sort a doubly linked list the D way?

reply Mirjam Akkersdijk <noreply noreply.com> writes:
Hello there,
If I had a DLL, how would I sort it judging by the node contents, 
the D way?

In C if I were to sort a piece of malloc'd memory pointing to 
node pointers, I would write my compare function and let qsort 
sort it out. In D, I tried to use std.algorithm's sort 
functionality to no avail, because my guess would be it only 
operates on arrays. This opens up another can of worms as I am 
not fond of VLAs and D desperately wants to know what the size is 
at compile time.

Let's say we this trivial implementation:

Node* get_node(DLL* list, uint index);

struct Node {
   int x;
   Node* prev, next;
};

struct DLL {
   Node* head;
   uint size;
};

Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);

and I would like to sort based on Node.t, how should I tackle it, 
preferably without resorting to C libraries?
Aug 13 2019
next sibling parent reply Mirjam Akkersdijk <noreply noreply.com> writes:
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk 
wrote:
 Hello there,
 If I had a DLL, how would I sort it judging by the node 
 contents, the D way?

 [...]
Node.t
Node.x, my bad
Aug 13 2019
parent Daniel Kozak <kozzi11 gmail.com> writes:
You can make an array from it

On Tue, Aug 13, 2019 at 12:05 PM Mirjam Akkersdijk via
Digitalmars-d-learn <digitalmars-d-learn puremagic.com> wrote:
 On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk
 wrote:
 Hello there,
 If I had a DLL, how would I sort it judging by the node
 contents, the D way?

 [...]
Node.t
Node.x, my bad
Aug 13 2019
prev sibling next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, August 13, 2019 3:48:52 AM MDT Mirjam Akkersdijk via 
Digitalmars-d-learn wrote:
 Hello there,
 If I had a DLL, how would I sort it judging by the node contents,
 the D way?

 In C if I were to sort a piece of malloc'd memory pointing to
 node pointers, I would write my compare function and let qsort
 sort it out. In D, I tried to use std.algorithm's sort
 functionality to no avail, because my guess would be it only
 operates on arrays. This opens up another can of worms as I am
 not fond of VLAs and D desperately wants to know what the size is
 at compile time.

 Let's say we this trivial implementation:

 Node* get_node(DLL* list, uint index);

 struct Node {
    int x;
    Node* prev, next;
 };

 struct DLL {
    Node* head;
    uint size;
 };

 Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);

 and I would like to sort based on Node.t, how should I tackle it,
 preferably without resorting to C libraries?
std.algorithm.sort operates on random-access ranges, not just dynamic arrays, and there's no need to know the size at compile time. I don't know why you would think that arrays would need to know their size at compile time unless you've only been using static arrays. However, a doubly-linked list definitely isn't random access, so it wouldn't work with std.algorithm.sort, and I don't think that Phobos has anything which would be able to sort it. There might be a solution somewhere on code.dlang.org, but I don't know of any that I could point you to. Either way, if there's a solution floating around that you can use to sort a doubly-linked list in place, it's not an official one. - Jonathan M Davis
Aug 13 2019
prev sibling next sibling parent ikod <geller.garry gmail.com> writes:
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk 
wrote:
 Hello there,
 If I had a DLL, how would I sort it judging by the node 
 contents, the D way?

 In C if I were to sort a piece of malloc'd memory pointing to 
 node pointers, I would write my compare function and let qsort 
 sort it out. In D, I tried to use std.algorithm's sort 
 functionality to no avail, because my guess would be it only 
 operates on arrays. This opens up another can of worms as I am 
 not fond of VLAs and D desperately wants to know what the size 
 is at compile time.
You can check std.container.rbtree which will build sorted "list" for you on every Node insert. Again, not sure how this can be done at compile time.
Aug 13 2019
prev sibling next sibling parent reply bachmeier <no spam.net> writes:
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk 
wrote:

 I would write my compare function and let qsort sort it out.
I'm confused by this statement. Are you referring to the qsort in C's stdlib? I had never heard of using that to sort a linked list, so I searched, and it is not possible. https://cboard.cprogramming.com/c-programming/64520-sorting-linked-list-qsort.html https://stackoverflow.com/questions/7091685/doesnt-qsort-c-library-function-w rk-on-linked-lists: "qsort works on plain arrays of equally sized data, not linked lists"
Aug 13 2019
parent Mirjam Akkersdijk <noreply noreply.com> writes:
On Tuesday, 13 August 2019 at 12:34:46 UTC, bachmeier wrote:
 I'm confused by this statement. Are you referring to the qsort 
 in C's stdlib? I had never heard of using that to sort a linked 
 list, so I searched, and it is not possible.
Ah yes, maybe I should have elaborated. In C, you can just create an array (1) struct Node* nodes[buf_size]; and then loop over it, filling it with (2) nodes[i] = (DLLbuf + i * sizeof(struct Node)); subsequently calling our dear friend from stdlib (3) qsort(nodes, buf_size, sizeof(struct Node*), buf_compare_function); You can then rechain all nodes together but that's a bit out of scope for this thread unless you do really want me to work it out :) But I was looking for a more D-specific approach to solve this, as it feels archaic to do it the C way. If there is anyone with a better one please let me know.
Aug 13 2019
prev sibling next sibling parent reply Sebastiaan Koppe <mail skoppe.eu> writes:
On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk 
wrote:
 and I would like to sort based on Node.t, how should I tackle 
 it, preferably without resorting to C libraries?
Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and repair the next/prev pointers.
Aug 13 2019
parent reply Mirjam Akkersdijk <noreply noreply.com> writes:
On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe 
wrote:
 On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk 
 wrote:
 and I would like to sort based on Node.t, how should I tackle 
 it, preferably without resorting to C libraries?
Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and repair the next/prev pointers.
Thank you, this is what I eventually chose to do. It's also fairly fast, though doesn't the nature of the dynamic array slow it down a bit? Since I already know the size of the array (but just not at compile time), can't I define an array of fixed size, which is dependent on the input of the function?
Aug 13 2019
next sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via 
Digitalmars-d-learn wrote:
 On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe

 wrote:
 On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk

 wrote:
 and I would like to sort based on Node.t, how should I tackle
 it, preferably without resorting to C libraries?
Convert the nodes into an D array, sort the array with nodes.sort!"a.x < b.x" and then iterate the array and repair the next/prev pointers.
Thank you, this is what I eventually chose to do. It's also fairly fast, though doesn't the nature of the dynamic array slow it down a bit? Since I already know the size of the array (but just not at compile time), can't I define an array of fixed size, which is dependent on the input of the function?
In D, static arrays must know their length at compile time. Dynamic arrays can have their length determined at runtime. I don't know why a dynamic array would slow anything down here though - especially if you just allocate it with the correct length. Appending each element individually instead of allocating the full dynamic array and then setting each element would certainly be slower, but once the dynamic array is fully allocated, as far as accessing elements go, accessing a dynamic array and static array should be basically the same. The only real difference is that one would have its elements on the stack, whereas the other would have them on the heap. Even if you used a static array, you'd have to slice it to pass to sort, which would mean that you'd be passing it a dynamic array. A dynamic array is basically just a struct with a pointer and a length. e.g. struct DynamicArray(T) { size_t length; T* ptr; } and accessing its elements is the same as you'd get with a pointer in C except for the fact that in safe code, the bounds are checked when indexing elements. The only thing about dynamic arrays that can get slow is if you're doing a lot of appending to them, because then it has to keep checking to see whether it can expand in place or has to allocate a new block of memory and copy the elements. In that respect, it's similar to C++'s std::vector. - Jonathan M Davis
Aug 13 2019
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Aug 13, 2019 at 12:12:28PM -0600, Jonathan M Davis via
Digitalmars-d-learn wrote:
 On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via 
 Digitalmars-d-learn wrote:
[...]
 Thank you, this is what I eventually chose to do. It's also fairly
 fast, though doesn't the nature of the dynamic array slow it down a
 bit? Since I already know the size of the array (but just not at
 compile time), can't I define an array of fixed size, which is
 dependent on the input of the function?
In D, static arrays must know their length at compile time. Dynamic arrays can have their length determined at runtime. I don't know why a dynamic array would slow anything down here though - especially if you just allocate it with the correct length.
[...] When it comes down to fine points concerning performance like here, my default response is: are you sure this is an *actual* performance hit? Did you run a profiler to measure the actual runtimes? Static arrays have the advantage that the size is known at compile-time, so the compiler can generate better code (by hard-coding the length, optimizing the memory layout, etc.). But when you pass static arrays around, you have to either slice them, in which case they become identical to dynamic arrays anyway, or pass them on the stack, which in some cases can actually slow things down (you have to copy a potentially large amount of data to/from the stack when passing arguments to a function). Passing a dynamic array (or a slice of a static array) is very fast: it's just a pointer + size pair. Dynamic arrays could potentially incur performance hits if you're appending to them (may need a GC allocation). Static arrays don't have this problem -- but then you can't append to a static array at all. :-P Anyway, splitting hairs over whether to use static arrays or dynamic arrays sounds like premature optimization to me. Before worrying about potential performance problems with using dynamic arrays, always use a profiler to see if the bottleneck is actually in that part of the code. Otherwise it's just a waste of time and energy to "optimize" the code when it isn't even anywhere near the real bottleneck(s) in the program. Profile, profile, profile. Until then, don't sweat it over optimization. T -- Mediocrity has been pushed to extremes.
Aug 13 2019
prev sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 08/13/2019 10:33 AM, Mirjam Akkersdijk wrote:
 On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe wrote:
 Convert the nodes into an D array, sort the array with nodes.sort!"a.x
 < b.x" and then iterate the array and repair the next/prev pointers.
If possible, I would go further and ditch the linked list altogether: Just append the nodes to an array and then sort the array. It has been shown in research, conference presentations, and in personal code to be the fasted option is most (or all) cases.
 doesn't the nature of the dynamic array slow it down a bit?
Default bounds checking is going to cost a tiny bit, which you can turn off after development with a compiler flag. (I still wouldn't.) The only other option that would be faster is an array that's sitting on the stack, created with alloca. But it's only for cases where the thread will not run out of stack space and the result of the array is not going to be used.
 can't I define an array of fixed size, which is dependent on the input
 of the function?
arr.length = number_of_elements; All elements will be initialized to the element's default value, which happens to be null for pointers. (If we are back to linked list Node pointers.) However, I wouldn't bother with setting length either as the cost of automatic array resizing is amortized, meaning that it won't hurt the O(1) algorithmic complexity in the general case. In the GC case that D uses, it will be even better: because if the GC knowns that the neighboring memory block is free, it will just add that to the dynamic array's capacity without moving elements to the new location. Summary: Ditch the linked list and put the elements into an array. :) Ali
Aug 13 2019
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali «ehreli via Digitalmars-d-learn
wrote:
[...]
 Summary: Ditch the linked list and put the elements into an array. :)
[...] +1. The linked list may have been faster 20 years ago, before the advent of modern CPUs with caching hierarchies and memory access predictors. These days, with CPU multi-level caches and memory access predictors, in-place arrays are often the best option for performance, up to a certain size. In general, avoid indirection where possible, in order to avoid defeating the memory access predictor and reduce the number of cache misses. T -- "If you're arguing, you're losing." -- Mike Thomas
Aug 13 2019
parent reply Max Haughton <maxhaton gmail.com> writes:
On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote:
 On Tue, Aug 13, 2019 at 11:28:35AM -0700, Ali Çehreli via 
 Digitalmars-d-learn wrote: [...]
 Summary: Ditch the linked list and put the elements into an 
 array. :)
[...] +1. The linked list may have been faster 20 years ago, before the advent of modern CPUs with caching hierarchies and memory access predictors. These days, with CPU multi-level caches and memory access predictors, in-place arrays are often the best option for performance, up to a certain size. In general, avoid indirection where possible, in order to avoid defeating the memory access predictor and reduce the number of cache misses. T
I saw a Bjarne Stroustrup talk where he benchmarked that the for n > 1, std::vector was a lot faster than a linked list for all supported operations. I don't know how clever the caching strategies are on a modern processor (Pointer chasing), but to my knowledge the only way of getting a cache efficient linked list would be to effectively have a very contiguous allocator (Which obviously defeats the purpose of using a list in the first place) Found it: https://www.youtube.com/watch?v=YQs6IC-vgmo
Aug 13 2019
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Aug 13, 2019 at 08:42:37PM +0000, Max Haughton via Digitalmars-d-learn
wrote:
 On Tuesday, 13 August 2019 at 18:54:58 UTC, H. S. Teoh wrote:
[...]
 These days, with CPU multi-level caches and memory access
 predictors, in-place arrays are often the best option for
 performance, up to a certain size.  In general, avoid indirection
 where possible, in order to avoid defeating the memory access
 predictor and reduce the number of cache misses.
[...]
 I saw a Bjarne Stroustrup talk where he benchmarked that the for n >
 1, std::vector was a lot faster than a linked list for all supported
 operations. I don't know how clever the caching strategies are on a
 modern processor (Pointer chasing), but to my knowledge the only way
 of getting a cache efficient linked list would be to effectively have
 a very contiguous allocator (Which obviously defeats the purpose of
 using a list in the first place)
 
 Found it: https://www.youtube.com/watch?v=YQs6IC-vgmo
A contiguous allocator doesn't help after the list has undergone a large number of insertions/deletions, because of fragmentation. You can still get a cache-efficient linked list by chunking. I.e., instead of a linked-list of individual elements, group the elements into blocks (arrays) that are then linked into a linked list. Then you can still insert/delete elements with sub-O(1) complexity by updating only the affected block, and only occasionally you need to delete a block or allocate a new block. As long as the block size is suitably-sized, it will be cache-coherent most of the time and enjoy the associated performance boosts from the cache hierarchy. For small lists, it will be equivalent to using a single array. For very large lists, you'll also reap the cheap insert/delete flexibility of a linked list. To minimize space wastage from unused slots in the blocks, you could have a list rebalancing based on some desired utilization factor (e.g., if <50% of a block is used, redistribute elements among adjacent blocks). Redistribution should be pretty cache-coherent (except perhaps for some corner cases), because it mostly involves linear copying of elements from one block to another. T -- I am not young enough to know everything. -- Oscar Wilde
Aug 13 2019
parent Mirjam Akkersdijk <noreply noreply.com> writes:
On Tuesday, 13 August 2019 at 21:11:41 UTC, H. S. Teoh wrote:
 A contiguous allocator doesn't help after the list has 
 undergone a large number of insertions/deletions, because of 
 fragmentation.
Fragmentation should not be an issue, I insist on keep using a DLL for the base structure in my application and create an array just for sorting operations. No new nodes are added and no nodes are permanently removed.
 You can still get a cache-efficient linked list by chunking. 
 [...]
I very much appreciate this thought, as I was thinking of adding such kind of cache to my implementation. It's still in the early stages and I have yet to see when this would make a considerable impact. I will remember this.
Aug 13 2019
prev sibling next sibling parent Sebastiaan Koppe <mail skoppe.eu> writes:
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli wrote:
 On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe
 wrote:
 Convert the nodes into an D array, sort the array with 
 nodes.sort!"a.x < b.x" and then iterate the array and repair 
 the next/prev pointers.
If possible, I would go further and ditch the linked list altogether: Just append the nodes to an array and then sort the array. It has been shown in research, conference presentations, and in personal code to be the fasted option is most (or all) cases.
Yeah, very likely. Although in this case there already is an array; it's going to be close :)
Aug 13 2019
prev sibling next sibling parent reply Mirjam Akkersdijk <noreply noreply.com> writes:
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli wrote:
 can't I define an array of fixed size, which is dependent on
the input
 of the function?
arr.length = number_of_elements; All elements will be initialized to the element's default value, which happens to be null for pointers. (If we are back to linked list Node pointers.) However, I wouldn't bother with setting length either as the cost of automatic array resizing is amortized, meaning that it won't hurt the O(1) algorithmic complexity in the general case. In the GC case that D uses, it will be even better: because if the GC knowns that the neighboring memory block is free, it will just add that to the dynamic array's capacity without moving elements to the new location.
For the application I am writing, it makes very much sense to use a DLL. The approach I am using right now is to: (as stated in the first post) void bsort(DLL* list) { Node*[] nodes; foreach (i; 0 .. list.size) nodes ~= get_node(list, i); nodes.sort!("a.x < b.x"); // (unrelated data structure cleaning up goes here) } My concern was that using a dynamic array, continuously appending to it despite known size, would greatly impact overall performance. My goal is to make this operation as fast as possible, the D way. I tried setting the length first and iterating through it with `nodes[i] = ...` and the implementation did not run noticeably faster (10 trials), per Teoh's advice to test out the difference. For now, I consider this a success and would like to thank everyone in the thread for assistance and valuable insights. Though, it left me with some semi-offtopic questions unanswered: (1) Ali, do you mean that from an optimization viewpoint, it's better to keep appending like `nodes ~= ...` instead of setting the length first? I would like to have some more background on that claim. (2) I watched the talk and read the paper [1] to be sure. Many contributors to this thread claim (C++) vectors are nearly always the preferred choice compared to DLLs, but how come they are much faster compared to DLLs, given they have nearly the same functionality? (3) And I sense this is very closely related to what Ali is on? [1] http://www.stroustrup.com/Software-for-infrastructure.pdf
Aug 13 2019
next sibling parent Mike Parker <aldacron gmail.com> writes:
On Tuesday, 13 August 2019 at 22:12:23 UTC, Mirjam Akkersdijk 
wrote:

 Though, it left me with some semi-offtopic questions unanswered:

 (1) Ali, do you mean that from an optimization viewpoint, it's 
 better to keep appending like `nodes ~= ...` instead of setting 
 the length first? I would like to have some more background on 
 that claim.
He's not saying it will be better, but that the cost will be negligible. On every append, the GC allocates new memory only if the current capacity == 0. When it does allocate, it allocates more space than it actually needs based on the current length of the array, so you don't actually have an allocation on every append. Also, when the adjacent memory block is free and can hold the additional elements, the allocation consists of extending the array's memory block and no copying is performed, making the cost of the allocation even cheaper than it could be. Anyway, you can use `reserve` when appending rather than setting the length. This will allocate enough memory without default-initializing anything and you don't have to worry about bounds checking. int[] ints; ints.reserve(100); foreach(i; 0..100) { ints ~= i; } See Steve Schveighoffer's array article for details: https://dlang.org/articles/d-array-article.html
Aug 13 2019
prev sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 08/13/2019 03:12 PM, Mirjam Akkersdijk wrote:

 For the application I am writing, it makes very much sense to use a DLL.
Yes, Dynamically Linked Libraries can be useful. Oh wait... You mean Doubly-Linked List. :o)
 I tried setting the length first and iterating through it with `nodes[i]
 = ...`
As Mike Parker said, it should be .reserve.
 and the implementation did not run noticeably faster (10 trials),
That's the most important part: You profiled and it was the same. (Although, profiling is tricky business as well; it can be difficult to measure the operation that you are interested in.) The performance will depend on many factors: * First, if there aren't many number of nodes it shouldn't matter. (That's why I would choose the simpler arrays.) * Doubly-linked list nodes will have two extra pointers per element. As a general rule, larger the data slower the data structure. * Pointer chasing through 'next' pointers will make the program jump around in memory. This will be slower compared to consecutive elements that arrays provide. But if processing the elements cause pointer chasing anyway, then it shouldn't matter much. Another topic to read and watch is "data oriented programming". This talk by Mike Acton is eye opening: https://www.youtube.com/watch?v=rX0ItVEVjHc * Is data appended and removed throughout the life of the program or are the nodes set once in the beginning and then only used? * Are elements accessed randomly or always in sequence. (If the latter, modern CPUs promise that arrays will be better.) * etc. Ali
Aug 14 2019
prev sibling parent Patrick Schluter <Patrick.Schluter bbox.fr> writes:
On Tuesday, 13 August 2019 at 18:28:35 UTC, Ali Çehreli wrote:
 On 08/13/2019 10:33 AM, Mirjam Akkersdijk wrote:
 On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe
wrote:
 Convert the nodes into an D array, sort the array with
nodes.sort!"a.x
 < b.x" and then iterate the array and repair the next/prev
pointers. If possible, I would go further and ditch the linked list altogether: Just append the nodes to an array and then sort the array. It has been shown in research, conference presentations, and in personal code to be the fasted option is most (or all) cases.
 doesn't the nature of the dynamic array slow it down a bit?
Default bounds checking is going to cost a tiny bit, which you can turn off after development with a compiler flag. (I still wouldn't.) The only other option that would be faster is an array that's sitting on the stack, created with alloca. But it's only for cases where the thread will not run out of stack space and the result of the array is not going to be used.
 can't I define an array of fixed size, which is dependent on
the input
 of the function?
arr.length = number_of_elements; All elements will be initialized to the element's default value, which happens to be null for pointers. (If we are back to linked list Node pointers.) However, I wouldn't bother with setting length either as the cost of automatic array resizing is amortized, meaning that it won't hurt the O(1) algorithmic complexity in the general case. In the GC case that D uses, it will be even better: because if the GC knowns that the neighboring memory block is free, it will just add that to the dynamic array's capacity without moving elements to the new location. Summary: Ditch the linked list and put the elements into an array. :)
There are mainly three reasons why arrays are nowadays faster than double linked lists: - pointer chasing can difficultly be paralized and defeats prefetching. Each pointer load may cost the full latency to memory (hundreds of cycles). In a multiprocessor machine may also trigger a lot of coherency trafic. - on 64 bit systems 2 pointers cost 16 bytes. If the payload is small, there is more memory used in the pointer than in the data. - when looping in an array the OO machinery will be able to parallelize execution beyond loop limits. - reduced allocation, i.e. allocation is done in bulk => faster GC for D. It is only when there are a lot of external references to the payload in the list that using an array may become too unwieldy, i.e. if moving an element in memory requires the update of other pointers outside of the list.
Aug 14 2019
prev sibling parent Johannes Loher <johannes.loher fg4f.de> writes:
Am 13.08.19 um 11:48 schrieb Mirjam Akkersdijk:
 Hello there,
 If I had a DLL, how would I sort it judging by the node contents, the D
 way?
 
 In C if I were to sort a piece of malloc'd memory pointing to node
 pointers, I would write my compare function and let qsort sort it out.
 In D, I tried to use std.algorithm's sort functionality to no avail,
 because my guess would be it only operates on arrays. This opens up
 another can of worms as I am not fond of VLAs and D desperately wants to
 know what the size is at compile time.
 
 Let's say we this trivial implementation:
 
 Node* get_node(DLL* list, uint index);
 
 struct Node {
   int x;
   Node* prev, next;
 };
 
 struct DLL {
   Node* head;
   uint size;
 };
 
 Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);
 
 and I would like to sort based on Node.t, how should I tackle it,
 preferably without resorting to C libraries?
I'd do something along the lines of this: ``` import std; struct Node(T) { private: typeof(this)* prev, next; public: T data; } struct DoublyLinkedList(T) { private: Node!T* head = null; Node!T* tail = null; public: void pushFront(T t) { auto n = new Node!T; if (head != null) { head.prev = n; } else { tail = n; } n.data = t; n.next = head; head = n; } T front() const property { return head.data; } void popFront() { head = head.next; if (head != null) { head.prev = null; } else { tail = null; } } void pushBack(T t) { auto n = new Node!T; if (tail != null) { tail.next = n; } else { head = n; } n.data = t; n.prev = tail; tail = n; } T back() const property { return tail.data; } void popBack() { tail = tail.prev; if (tail != null) { tail.next = null; } else { head = null; } } size_t empty() const property { return head == null; } auto nodes() property { static struct NodePointerRange { private: Node!T* head; public: Node!T* front() property { return head; } void popFront() { head = head.next; } bool empty() const property { return head == null; } } return NodePointerRange(head); } } auto doublyLinkedList(R)(R r) if (isInputRange!R) { DoublyLinkedList!(ElementType!R) list; foreach (e; r) { list.pushBack(e); } return list; } auto doublyLinkedListFromNodePointerRange(R)(R r) if (isInputRange!R && isPointer!(ElementType!R) && isInstanceOf!(Node, PointerTarget!(ElementType!R))) { DoublyLinkedList!(TemplateArgsOf!(PointerTarget!(ElementType!R))) list; foreach (n; r) { n.prev = list.tail; if (list.tail != null) { list.tail.next = n; } else { list.head = n; } list.tail = n; } list.tail.next = null; return list; } void main() { auto list = doublyLinkedList([5, 3, 7, 24, 1]); // looks natural but allocates new nodes auto sortedList = list.array.sort.doublyLinkedList; sortedList.each!writeln; writeln; auto anotherList = doublyLinkedList([54, 23, 8]); // looks a bit uglier but reuses the already allocated nodes auto anotherSortedList = anotherList.nodes .array .sort!((n1, n2) => n1.data < n2.data) .doublyLinkedListFromNodePointerRange; anotherSortedList.each!writeln; } ``` Modulo bugs of course ;) This uses the GC. If you want to avoid it in favor of malloc (or std.experimental.allocator), you need to add `free`s (and possibly referece counting) accordingly.
Aug 13 2019