KDevPlatform Itemrepository bucket freeItems

[Matt Rogers]

On Tue, Mar 1, 2011 at 12:04 PM, floris <flo.ruijt at gmail.com> wrote:
> On Tue, 2011-03-01 at 10:15 +0100, Milian Wolff wrote:
>> you have quite some in-depth knowledge on these
>> tasks, many of us (esp. me) don't have that. I for one am just a
>> self-taught
>> programmer and hence would greatly appreciate it if you could shortly
>> outline
>> what you want to achieve an
>
> well a short introduction then :)
>
> the current structure uses a sorted linked list to manage all the free
> space in a bucket, except the space that is right at the end.
>
> I could have decided to use AVL trees too, but they require a bit more
> information(pun intended): a red black tree needs RED or !RED an AVL
> tree needs -1,0,1. and as i was tightly space bound i decided upon a
> red-black tree.
>
> a red-black tree is a binary-search-tree that guarantees that the height
> of the longer subtree will not be more than twice the height of the
> shorter subtree. see the end of this mail for a more information on
> binary search trees and red-black trees.
>
> this means searching will always stay O(log N), whereas a sorted
> linked-list has O(N/2)==O(N) on average
>
> to decide what to do with new free space, we need to know whether there
> is free space right before or right after this item, that requires a
> search over the data ON THE INDEX.
>
> to decide where to allocate a new item we need to find an item with
> sufficient or if possible exactly fitting size, this requires searching
> over the free space ON THE SIZE.
>
> therefore to profit we would need two red-black trees.
>
> which is exactly where this header comes in. by making the algorithms
> data-structure neutral we can uses indices instead of pointers and save
> *a lot* of bytes.
>
> As several of you noted, an existing implementation is to be preferred.
> the problem is, no implementation i found was capable of handling
> structs with offsets as left and rights, instead of the usual pointers,
> and no parent pointers, the closest probably is boost::intrusive, but it
> requires parent-pointers which would mean four bytes extra storage per
> node, now David set my storage limit to 10 bytes per node, which is what
> i have right now:
> ushort: size + in the 2 most significant bits the two red/black flags
>
> short: left_by_size
> short: right_by_size
> short: left_by_index
> short: right_by_index
>
> where the shorts are offsets from the current node.
> as long as parent pointers are not permissible, it's impossible to use
> boost::intrusive in a sane matter. i looked into the stl_tree header,
> which implements a red-black tree also, but it 1) uses parent pointers
> and 2) has (without modification) no support for different node types.
>
> For me the only question remaining is whether it's faster in practice.
> which i can only measure when it all works.
>
> Floris
>
>
> BINARY SEARCH TREES:
> a binary search tree has a structure like this:
>                        5
>                   /          \
>            /                       \
>        3                               9
>    /       \                       /        \
> 2               4               7               10
>
>
> that is: every node has TWO children. on the left are all nodes that are
> smaller than this node, on the right all nodes that are bigger. this
> allows for fast searching:
> say we need to find 4.
> 4<5 ?  yes look left.
> 4<3 ?  no check equal
> 4==3?  no, look right
> 4<4 ?  no check equal
> 4==4?  yes FOUND IT!
>
> this might not look that impressive but as the number of items gets
> bigger this will get more and more impressive imagine a perfectly
> balanced tree with the numbers 1..1023  this tree has 2log(1023+1)==10
> levels which means that in the worst case scenario we need 10 < and 10
> == comparisons, if, on the other hand we have a sorted linked list with
> 1..1023  we'd have to do on average 512 ==comparisons. but this speedup
> only holds if the tree is (reasonably) balanced if you inserted the
> items in a sorted order(doing no rebalancing whatsoever) then the tree
> would look like this:
>                                ...
>                        4
>                3
>        2
> 1
>
> ie. no right nodes just left nodes. this is basically a linked list with
> extra 0 bytes! so this must be avoided. (there are two other insertion
> orders in which the tree degenerates into linked list, those are left as
> an excercise to the reader)
>
> to solve this some kind of rebalancing has to be done after the
> insertion. Two noteworthy solutions are the red-black tree and the
> avl-tree.
>
>
>
> RED-BLACK TREE
> a red black tree is a binary search tree which has the following
> additional properties:
> 1. every node has a color (red or black).
> 2. the root is black
> 3. a red node has no red children
> 4. every path from the root to leave traverses the same amount of
>   black nodes
>
> these properties mean that the maximal difference between the two
> subtrees of the root can be the height of the shorter subtree:
>
>                                B
>                        R               B
>                B                               B
>        R                                               ...
> ...
>
> as the amount of blacks is equal the left node can have at most
> hight(right)-1 nodes more.
>
> insertion and deletion is tricky but possible I will not cover it here
> but the basic algorithm is: find the correct position, insert red node,
> fix red violations(property 3 violated) untill the tree is consistent.
>
> AVL TREE
> an avl tree is a binary search tree that uses the 'balance factor'. the
> balance factor is height(left_child)-height(right_child)
> an avl tree guarantees that the balance factor of everey node is
> -1,0 or 1. this guarantees a more balanced tree then the red-black tree
> at the cost of somewhat more rebalancing(gee!), to be done at insertions
> and deltions.
>
>
A bit of TL;DR going on here, since I have a decent enough background
in data structures, but out of curiousity, did you use a left-leaning
red-black tree?
--
Matt