Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 25 Jun 2011
Offline Last Active Sep 20 2012 04:39 AM

Posts I've Made

In Topic: Thoughts on double link list strings?

20 September 2012 - 04:33 AM

If you really have to optimize your solution, I'd suggest this approach:

Organizing memory
Use fixed size memory blocks of chars as nodes in your rope. This allows you to pool allocate those blocks, minimizing calls to new and malloc.
When you run out of allocated blocks, allocate a bigger buffer. Don't simply memcpy your blocks to the new location but push_back each character in your new structure, filling up each block completely, starting at the beginning of the buffer (thus making the doubly linked list cache friendly again, in case you want to traverse it).

Finding insert position
For inserting text into the string, I assume you need to know where a line starts. I see multiple solutions for this:
a) Store the number of newlines a node contains in the node (and keep that number updated). Iterate over nodes to find the right block.
  • easy to implement
  • low memory usage
  • inserting newlines is O(1)
  • finding newlines is O(n) and needs to touch a lot of memory
b) Maintain a dynamic array of pointers to nodes. The pointer at index n shall point to the node containing the line with index n
  • higher memory usage
  • inserting newlines is O(n)
  • finding newlines is O(1)
c) Combination of a) and b). Use pointers to find approximate location of your line (for example, pointer n points to line 10 * n).
  • most difficult to implement
  • otherwise, same characteristics as b)

In Topic: OO Design and avoiding dynamic casts

12 September 2012 - 05:52 AM

Just one more thought, real quick...

Another place this dynamic_cast issue comes up in a lot is with publish/subscribe messaging architectures. Often, you have an abstract interface called Message, and then any time you want to send data from one part of your program to another (where nothing knows at compile time who is communicating with whom), then you just subclass Message (e.g., FooMessage, BarMessage). However, the message handler method on the receiving end will get a Message& and it needs to down-cast that to the right message type before it can deal with it.

You can automate this with templates (not tested, but the concept works):
class message_dispatcher
	struct abstract_listener
		void* listener;
		void (*handle)( void* listener , const void* message );
	template< class MessageType , class ReceivingType >
	static void handle_func( void* listener , const void* message )
		ReceivingType& typed_listener = *static_cast< ReceivingType* >( listener );
		const MessageType& typed_message = *static_cast< const MessageType* >( message );
		typed_listener.handle( typed_message );
	std::multimap< type_info , abstract_listener > listeners;
	template< class MessageType , class ReceivingType >
	void subscribe( ReceivingType& r )
		abstract_listener al{ &r , &handle_func< MessageType , ReceivingType >  };
		type_info info = typeid( MessageType );
		listeners.insert( { inf , al } );
	template< class MessageType >
	void dispatch( const MessageType& msg )
		type_info info = typeid( MessageType );
		auto range = listeners.equal_range( info );
		while( range.first != range.second )
			( *(range.first->handle_func) )( range.first->listener , &msg );
struct message_a
class specific_listener
	void handle( message_a& m )

specific_listener listener;
message_dispatcher dispatcher;
dispatcher.subscribe< message_a >( listener );
dispatcher.dispatch( message_a() );

Notice, however, that you can't use a message hierarchy. If you dispatch a B : A, a handler that has subscribed for A won't get that message.
If you need the performance, you can change std::multimap to something like a hash map and replace type_info with your own ids, e.g.
template< class T >
void* t_id()
	static char c;
	return c;
typedef void* msg_id;
msg_id id = t_id< message_a >();

//or if you need to communicate between different dlls

struct message_a
	static const unsigned int id = //some unique value

In Topic: Making a C++ Either class based on Haskell's?

03 September 2012 - 06:27 AM

template<class First, class Second>
class Either
	template<class T>
	Either<First, Second>& operator=(Either<T, Empty> either) {
		first_ = std::move( either.value() );
		hasFirst_ = true;
		return *this;
	template<class T>
	Either<First, Second>& operator=(Either<Empty, T> either) {
		second_ = std::move( either.value() );
		hasFirst_ = false;
		return *this;
	bool hasFirst() const { return hasFirst_; }
	bool hasSecond() const { return !hasFirst_; }
	const First& first() const { return first_; }
	const Second& second() const { return second_; }
	union {
		First first_;
		Second second_;
	bool hasFirst_;
This will eliminate unnecessary copies. Look at boost::variant, it does something similar.

In Topic: Using RTTI in an entity component system?

09 April 2012 - 05:51 PM

I mentioned JavaScript above:

var Enemy = function() {
  this.velocity = [1.0, 2.0, 3.0];
  this.mass = 200.0;


With some template magic and type erasure this can actually be emulated in c++, for example, I use this:
prototype p = system_manager.new_prototype();
p.add_component( velocitity{ x , y , z } );
p.add_component( mass{ 200 } );
entity a = system_manager.new_entity( p );
entity b = system_manager.new_entity( p );
which doesn't look that much worse. The idea is to have references to base_system s in your system_manager. During its initialization, you create a map< typeinfo , unsigned int >, where the value type is unsigned int. When adding a component to a prototype (usually while loading a level) you lookup that system_index in the map once and store it with the component. To create an entity from a prototype you simply iterate over all components in it and do
systems[ system_id ].insert( component );

Maybe I'll refactor my implementation a bit and upload it somewhere, it is, as you said, quite some work to implement a generic component system in c++.

In Topic: Smart pointers question

05 April 2012 - 03:55 PM

boost::shared_ptr has the same thread-safety as a normal pointer.
You're not allowed to do

Thread 1: a = null;
Thread 2: shared_ptr<T> b = a;

with normal pointers either.