One year after 27. DepthLists and I'm back on the subject. The old code is being replaced with new, better data structures, thanks to the hindsight gained since the first version. The basic principle doesn't change much but it now includes the outputs of the backwards and the DFF gates at the level 0. I also want to use a more unified memory allocation approach, similar to what I used for the sinklist, with a large chunk of memory containing all the lists in a compact sequential way.

I can ensure that the lists are well sorted by using "insertion sort" with linked lists for example, then the linked lists are transformed into normal lists. It's easy because we already know the number of gates and input ports. We don't know the maximum depth in advance though and temporary dynamic allocation seems necessary.

A new subtlety appears with the DFF and backwards gates : although they are counted as drivers along with the inputs, they are also sinks and should be considered as such as well. We want to know how many gates are traversed before reaching the DFF's input and this sink gate appears at the end side of the depthlist.

...

Some coding and thinking brought a new fresh idea and structure to the "depthlist" complex:

• Level 0 is the list of the input ports and a new list that contains the DFF and backwards gates (it's called pseudo_drivers_list, with pseudo_drivers_count elements)
• The other levels are stored in a large array that contains DutVectOut_length + gate_instance_counter elements, called depth_lists. The trick is that since it is some some sort of permutation of the original array, we can store the lists starting from index 0, while also fit the rolling list of gates to propagate/check at the top end. The array can be allocated early.
• The depth is not easy to get and must be allocated dynamically. There are two values to store for each index (starting at 1 because 0 is implicitly a different kind of data) : the count of elements in the current level, and the starting index in the depth_lists array. Once again it's redundant because it's another "prefix sum".
  A nice solution is to "over-allocate" the depth-lists (by how much ?) and store the individual list sizes just before the given list. A final step will simply scan the lists and compute the prefix sum to store it in a normal array, when its size is known.

The good news is I got rid of the linked lists ! Though this makes deletion/insertion less convenient.

...