= Data structures =

A well-designed data structure allows a variety of critical operations to be
performed, using as little resources, both execution time and memory space, as
possible. Moreover a carefully chosen data structure will allow a more efficient
algorithm to be used; consequently such choice assume a primary importance in 
this project.
[[BR]]
The two fundamental data structures on which Phase 1 layer is founded are lists
and trees, implemented in various ways, depending on the singular case
evaluations.

Here below we are going to describe the two most significative flavour of them.

 == 1. Linear single linked list ==
This simple data structure has been choosen for trivial structures
implementation. We are talking about lists of non-allocated PCBs or SDs:
respectively pcbFree and semdFree.

In fact, because of element insertion and deletion may involve only the first
one, a stack with a ''O(1)'' computational cost is what we was looking for. And
is what we implemented with a linear single linked list, appreciating its
simplicity. 


== 2. Circular double linked list ==
List management operations, such as element insertion and deletion, require
predecessor and successor updating. Because of this, a previous element pointer
(`p_prev`) is added to the PCB standard structure, performing these operations
scanning the list only once.

Kaya Phase 1 will take advantage of double circularly linked list benefits in
every processes queue, which is widely used by operating system.


== 3. Semaphore binary tree ==
The importance of the '''choice''' of data structure increases directly with the
performance relevance and for semaphore descriptors management becomes a primary
goal. That is because semaphores queue's phisical address is obfuscated in a
higher level view, so Phase 1 layer must encapsulate the association between
semaphore address (semAdd) and its queue into the Semaphore descriptors (SDs).

Such association must be searched between them and if they are managed in a sorted
structure computational costs decrease, avoiding scanning everyone. For this
reason we opted for a data structure that is more complex and difficult to
mantain but, on the other hand, is more performant and scalable: a binary search
tree.

Let us show in detail a BSTs '''comparison''' with sorted list.
[[BR]]
The major part of mantainence costs depends on the fact that it is sorted and,
consequently, on the search cost. In fact, while a list search costs ''O(n)'', a
binary tree takes only ''O(log(n))'', because of the number of scanned elements
is at most equal to the tree height. By the way, input distribution influences
BST's height in a determining way, deciding tree balance, making ''O(log(n))''
an estimate of the average case cost. In particularly adverse situations BSTs
collapse into a ''f**ked'' list.
[[BR]]
Summing up, in order to appreciate BSTs performance improvements and scalability,
input cardinality should be sufficiently large and well-distributed.

Like often happens, performance and '''memory usage''' risk to collide and a good
compromise is needed.
[[BR]]
Therefore we tried to limit wastes, just single-linking the tree with `s_rightC`
and `s_leftC` pointers, increasing module complexity and consequent
implementation and mantainance [wiki:Design&Hacks#a1.Modulesdesign difficulties].

{{{
 ------------------------------------------------------------------------------
|                         Semaphore Tree data structure                        |
 ------------------------------------------------------------------------------

         A ctive                     _________                   Free list
         S emaphore                 |         |                  ._______.
         T ree                      |  DUMMY  |                      |
         ._________.                |_________|                     \|/
              |                     |____|____|                      V
             \|/                 .....'     `........................
   ~log(n)    V                 :                                    :
      __                      _____                                _____
     |                       |     |                              |     |
     |                       |_____|                              |_____|
     |                ........'   `.............                      .'
     |               :                          :                     :
     |             _____                      _____                 _____ 
     |            |     |                    |     |               |     |
     |            |_____|                    |_____|               |_____|
     |        .....'   `.....                     `.....               .'
     |       :               :                          :              :
     |     _____           _____                      _____          _____
     |    |     |         |     |                    |     |        |     |
     |    |_____|         |_____|                    |_____|        |_____|
     :          .         .     .                      .     .            . 
     :           .       .       .                    .       .           .
     .         .....   .....   .....                .....   .....       .....
     .        :     : :     : :     :              :     : :     :     :     :
}}}