Standard placement operator

[Sergey Grekhov]

Hello, Norman!

22.03.2013, 02:13, "Norman Feske" <norman.feske at ...1...>:
> Hello Sergey,
>
>>  My interest about STL containers has quite simple prerequisite. As far
>>  as I know Genode implementations of data structure (particularly,
>>  Avl_tree) has some issues and Genodelabs does not recommend it for usage
>>  in user applications. The reasons that issues are still not resolved is
>>  quite serious: Genode is kept as simple as possible. So, I was thinking
>
> with the term "issue", are you referring to bugs and unexpected
> behavior, or are you just finding those data structures limiting? If the
> former is the case, I would be very grateful if you shared details about
> the problems you encountered, so that we can remedy them.

Well, there are mainly two problems I know about tree:
1) it allows to change the key of the element which was already inserted and in that case no any re-balancing will be performed; if one add here the fact that each node in the tree has a link to its parent, there appears a theoretical possibility to get a cycle in the tree when searching for something
2) current implementation of AVL-tree is quite simple and it takes a lot of time to rebalance it; there are types of balanced trees (e.g. red-black tree) which has more cheap cost of operation "balance", but these types are more complex in terms of internal structures

>
> The few data structures provided by Genode do merely exist to support
> the operation of the base framework. By rigidly following the
> microkernel construction principle, they comprise only those features
> that cannot be left out. This is crucial for keeping the complexity of
> the base system low. They should not be mistaken as an application
> framework.
>
> For components where low complexity and tight control over memory
> allocations is critical (e.g., for resource multiplexers), I prefer to
> stick with the sparse facilities provided by Genode's base API. In
> contrast, for higher-level applications, the use of application-geared
> APIs (such as STL, Qt and the like) seems more appropriate.
>
>>  about making a kind of porting of STL to Genode. But, it seems that this
>>  work is redundant since it is possible to use containers by means of
>>  specifying stdcxx in makefile. The only trouble is using Genode
>>  allocators/new operator instead of native C++ ones.
>
> To integrate STL with Genode, you can define a new operator handing out
> anonymous memory as follows:
>
>   void *operator new (Genode::size_t size)
>   {
>     return Genode::env()->heap()->alloc(size);
>   }
>
> This operator will then be used by the standard C++ library and the STL
> containers. By doing that, you are of course sacrificing the ability to
> tightly guard allocations. For example, if your program is a server, it
> will not be able to use distinct heap partitions to keep track of the
> allocations performed on behalf of different clients. On the other hand,
> many components do not need such strict accounting. The decision between
> tight control (Genode API only) and convenience (Genode API + C++
> standard library) is a trade-off and comes down to a judgment case by case.

Yes, this is a trade off which is not in spirit of Genode. At least env()->heap() is guarded by the ram_quota of the started app. I will think on the possibility to insert allocator in this scheme - that looks interesting. =)

>
> Best regards
> Norman
>
> --
> Dr.-Ing. Norman Feske
> Genode Labs
>
> http://www.genode-labs.com · http://genode.org
>
> Genode Labs GmbH · Amtsgericht Dresden · HRB 28424 · Sitz Dresden
> Geschäftsführer: Dr.-Ing. Norman Feske, Christian Helmuth
>
> ------------------------------------------------------------------------------
> Everyone hates slow websites. So do we.
> Make your web apps faster with AppDynamics
> Download AppDynamics Lite for free today:
> http://p.sf.net/sfu/appdyn_d2d_mar
> _______________________________________________
> Genode-main mailing list
> Genode-main at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/genode-main

-- 
Best regards,
Sergey Grekhov