www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - memory pool and rb-tree

reply Jeff <jeff.michels gmx.net> writes:
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?
Aug 26 2008
next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Jeff" <jeff.michels gmx.net> wrote in message 
news:g90qs7$4gl$1 digitalmars.com...

 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?


I'm not sure there's a drop-in replacement for a memory pool, but there is 
tango.util.container.RedBlack.  Unfortunately the documentation generator 
seems not to like whatever they've done in that file (wow, another bug in 
Ddoc!) so you'll have to read the docs out of the source file here: 
http://www.dsource.org/projects/tango/docs/current/source/tango.util.container.RedBlack.html

Be warned that it is a bit low-level, but it allows you to use a custom 
comparator function on finds and such.

Or, if you wanted to make it rather simple, you could just have a dynamic 
array of spot_rec*, and overload opCmp in the spot_rec structure.  Then you 
can just append records as you allocate them (and of course you can 
preallocate space or make a small templated struct on top of it or 
whatever), and just call .sort on it when you're finished.  Unless you need 
them to be sorted on-the-fly?
Aug 26 2008
prev sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"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
Aug 26 2008
parent reply BLS <nanali nospam-wanadoo.fr> writes:
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
Aug 26 2008
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"BLS" wrote

 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


At some point, I plan to investigate other means of representing trees and 
hashes, and implement those options in dcollections.  I've heard several 
suggestions for tree-implementation, and I'll probably look at all of them. 
When I have time :)

Thanks!

-Steve
Aug 28 2008
parent "Denis Koroskin" <2korden gmail.com> writes:
On Thu, 28 Aug 2008 18:46:04 +0400, Steven Schveighoffer  
<schveiguy yahoo.com> wrote:


 "BLS" wrote

 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


 At some point, I plan to investigate other means of representing trees  
 and
 hashes, and implement those options in dcollections.  I've heard several
 suggestions for tree-implementation, and I'll probably look at all of  
 them.
 When I have time :)

 Thanks!

 -Steve


Looking forward for results and good luck!
Aug 28 2008