memory pool and rb-tree

[BLS]

Steven Schveighoffer schrieb:
> "Jeff" wrote
>> Hi,
>>
>> i'm learning D and i'm trying to translate my C++ code to D. But i hit 
>> some problems.
>>
>> My C++ code looks like:
>>
>> struct spot_rec
>> {
>> char id[20];
>> int  value1;
>> int  value2;
>> int  value3;
>> bool changed;
>>
>> spot_rec() {...}; //init
>> const spot_rec& operator=(const spot_rec& r) {...}; //copy-operator
>> };
>>
>> struct less_spot_record : public std::binary_function<spot_rec *,spot_rec 
>> *,bool>
>> {
>>  bool operator()(const spot_rec *a, const spot_rec *b) const { return 
>> stricmp(a->id, b->id); }
>> };
>>
>> typedef set < spot_rec*, less_spot_record >  TableSpotRecords;
>> typedef set < spot_rec*, less_spot_record >::iterator 
>> TableSpotRecordsIter;
>>
>> boost::my_object_pool< spot_rec > pool_spot_rec;
>> TableSpotRecords table_spot_rec;  //ordered RB-Tree
>>
>> bool shutdown = false;
>> int thread_save_data()
>> {
>> while(!shutdown)
>> {
>> TableSpotRecordsIter iter = table_spot_rec.begin();
>> while(iter != table_spot_rec.end())
>> {
>> spot_rec *r = *iter;
>> if(r->changed)
>> {
>> mutex.lock();
>> save_record(r);
>> r->changed = false;
>> mutex.unlock();
>> }
>> if(shutdown) return 0;
>> ++iter; // is thread save
>> }
>> }
>> return 0;
>> }
>>
>> void update_spot(spot_rec *r)
>> {
>>    TableSpotRecordsIter iter = table_spot_rec.find(r);
>>    if(iter==table_spot_rec.end())
>> {   //add new record
>> spot_rec *p = pool_spot_rec.construct();
>> *p = *r;
>> table_spot_rec.insert(p) // is thread save
>> }
>> else
>> { //update record
>> spot_rec *p = *iter;
>> mutex.lock();
>> *p = *r;
>> mutex.unlock();
>> }
>> }
>>
>> main
>> {
>> create_thread(thread_save_data);
>> ...
>> //read from udp socket
>> char buf[1024];
>> while( recvfrom(socket,buf,sizeof(buf),from,fromlen)>0 )
>> {
>> spot_rec r;
>> if(parse_record(buf,r))
>> update_spot(&r);
>> }
>>
>> shutdown=true;
>> join_thread();
>> table_spot_rec.purge_memory();
>> ...
>> }
>>
>> This program processes realtime data.
>> I can't find a D replacement for boost::my_object_pool and stlport-set.
>> I looked at tango and dcollections, but i can't find any example that use 
>> RB-Trees and where i can set my own compare function.
>>
>> Can somebody help me?
> 
> As far as TreeSet in dcollections, you can replace the compare function 
> (although, I admit the docs aren't fully filled out, there should eventually 
> be a tutorial that covers this kind of stuff):
> 
> int myCompare(ref spot_rec sr1, ref spot_rec sr2) {/*your compare impl 
> here*/}
> ....
> TreeSet!(spot_rec).Impl.parameters p;
> p.compareFunction = &myCompare;
> auto tset = new TreeSet!(spot_rec)(p);
> 
> That's kinda ugly, I probably should work on the syntax to make that 
> easier...  but it does work :)
> 
> -Steve 
> 
> 

Hi Steve
In 2008, Sedgewick introduced a simpler version of red-black trees.
So called Left-Leaning Red-Black Trees. Remarkable enough : This algo. 
requires just a few lines of code (compared to traditional 
implementations), is dammned fast, and looks pretty smart. Probabely 
interesting for you / DCollections. So here two links.

PDF describing the Algorithm :
http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

Java source:
http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java
hope you'll find it usefull,Bjoern