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
next sibling 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 "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
prev sibling 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