This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| Lightweight Profiler Submitted by

Since upgrading to Visual Studio.NET I've missed having an integrated profiling tool. VC6's profiler wasn't perfect but it was half useful and came with the product. vTune is available but is expensive. Additionally neither could give you real-time results in app testing to track down processing spikes. So, I decided to write a small profiling tool myself. Since I'm not an assembler guru (more like a cut 'n paste hack) I decided to write a reasonably lightweight profiler in C++ and ignore any processor features , like what vTune might use. My design goals were to create a profiler that:

> - Is reasonably lightweight.
> - Easy to use.
> - Real-time data access, you don't need to wait until application exits to get your data.
> - Frame aware, i.e. it can be used to collect data on a frame by frame basis or perhaps per second for averaged display.
> - Collects hierarchical data to aid in pinpointing bottlenecks

It works like this, you add a line to your code like this: Profile("Renderer"); This line will create an object that starts a timing session under the name "Renderer". You would then go about calling your rendering code. On destruction of the object it records the elapsed time against the renderer session name. If you create multiple objects of a certain name it will collate the data under the session name, for example if inside "Renderer" you have another profile timing session called "Models" to draw your models that gets called 300 times a frame it will collect these times under a single statistic. The example program also tells you how much of the renderer's time drawing models takes collectively as a percentage of the total time. Example usage is shown in Main.cpp, the examples output looks like this:
Frame : 100
Input : 5.25607
AI : 10.9641
Physics : 16.2284
Collision : 23.1993
Renderer : 43.4926
Terrain : 21.4667
Models : 21.4948 Using a technique like this makes it trivial to locate bottlenecks. When integrated in a game this might collated each second and get drawn to the screen every frame. From some basic tests I've performed I've found that the code only adds a few hundred instructions to the function The code is quite fresh and some compromises were made in the design for simplicity. The design might have flaws and the code , bugs. Because of this I'm quite keen to hear any feedback on improvements. This software is released to the public domain. Enjoy it, use it, learn from it. If you improve it I'd love to see your work. Tree.h included in the distribution is covered by GPL as indicated by the author.
Chris Brodie
http://fourth.flipcode.com

Currently browsing [PerformanceMonitor.zip] (10,407 bytes) - [Tree.h] - (24,495 bytes)

    /*

       $Id: tree_msvc.hh,v 1.3 2002/05/28 11:53:25 t16 Exp $

    	STL-like templated tree class.
    	Copyright (C) 2001  Kasper Peeters <k.peeters@damtp.cam.ac.uk>

       Microsoft VC version by Jason Avinger, see

          http://www.damtp.cam.ac.uk/user/kp229/tree/

       for the original.

    	This program is free software; you can redistribute it and/or modify
    	it under the terms of the GNU General Public License as published by
    	the Free Software Foundation; version 2.

    	This program is distributed in the hope that it will be useful,
    	but WITHOUT ANY WARRANTY; without even the implied warranty of
    	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    	GNU General Public License for more details.

    	You should have received a copy of the GNU General Public License
    	along with this program; if not, write to the Free Software
    	Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    */

    #ifndef tree_hh_
    #define tree_hh_

    #include <cassert>
    #include <memory>
    #include <stdexcept>
    #include <iterator>
    #include <set>

    #ifdef _MSC_VER // MSVC does not have HP style construct/destroy
    template <class T1, class T2>
    inline void constructor(T1* p, T2& val)
     {
     new ((void *) p) T1(val);
     }

    template <class T1>
    inline void constructor(T1* p)
     {
     new ((void *) p) T1;
     }

    template <class T1>
    inline void destructor(T1* p)
     {
     p->~T1();
     }
    #else
       #define constructor std::construct
       #define destructor  std::destroy
    #endif

    template<class T>
    struct tree_node_ {
    		tree_node_<T> *parent;
    	   tree_node_<T> *first_child, *last_child;
    		tree_node_<T> *prev_sibling, *next_sibling;
    		T data;
    };

    template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
    class tree {
    	protected:
    		typedef tree_node_<T> tree_node;
    	public:
    		typedef T value_type;

    		class iterator;
    		class sibling_iterator;

    		tree()
    		{
    		head_initialise_();
    		}
    		~tree()
    		{
    		clear();
    		alloc_.deallocate(head,1);
    		}
    		tree(const tree<T, tree_node_allocator>& other)
    		{
    		head_initialise_();
    		copy_(other);
    		}
    		void operator=(const tree<T, tree_node_allocator>& other)
    		{
    		copy_(other);
    		}

    		class iterator {
    			public:
    				typedef T                          value_type;
    				typedef T*                         pointer;
    				typedef T&                         reference;
    				typedef size_t                     size_type;
    				typedef ptrdiff_t                  difference_type;
    				typedef std::bidirectional_iterator_tag iterator_category;

    				iterator()
    				: node(0), skip_current_children_(false)
    				{
    				}

    				iterator(tree_node *tn)
    				: node(tn), skip_current_children_(false)
    				{
    				}

    				iterator(const sibling_iterator& other)
    				: node(other.node), skip_current_children_(false)
    				{
    				if(node==0) {
    					node=other.range_last();
    					skip_children();
    					increment_();
    					}
    				}

    				iterator&  operator++(void)
    				{
    				if(!increment_()) {
    					node=0;
    					}
    				return *this;
    				}

    				iterator&  operator--(void)
    				{
    				if(!decrement_()) {
    					node=0;
    					}
    				return *this;
    				}

    				iterator&  operator+=(unsigned int num)
    				{
    				while(num>0) {
    					++(*this);
    					--num;
    					}
    				return (*this);
    				}

    				iterator&  operator-=(unsigned int num)
    				{
    				while(num>0) {
    					--(*this);
    					--num;
    					}
    				return (*this);
    				}

    				T&         operator*(void) const
    				{
    				return node->data;
    				}

    				T*         operator->(void) const
    				{
    				return &(node->data);
    				}

    				bool       operator==(const iterator& other) const
    				{
    				if(other.node==node) return true;
    				else return false;
    				}

    				bool       operator!=(const iterator& other) const
    				{
    				if(other.node!=node) return true;
    				else return false;
    				}

    				iterator   operator+(int num) const
    				{
    				iterator ret(*this);
    				while(num>0) {
    					++ret;
    					--num;
    					}
    				return ret;
    				}

    				sibling_iterator begin() const
    				{
    				sibling_iterator ret(node->first_child);
    				ret.parent_=node;
    				return ret;
    				}

    				sibling_iterator end() const
    				{
    				sibling_iterator ret(0);
    				ret.parent_=node;
    				return ret;
    				}

    				// do not iterate over children of this node
    				void skip_children()
    				{
    				skip_current_children_=true;
    				}

    				bool is_valid() const
    				{
    				if(node==0) return false;
    				else return true;
    				}

    				unsigned int number_of_children() const
    				{
    				tree_node *pos=node->first_child;
    				if(pos==0) return 0;

    				unsigned int ret=1;
    				while(pos!=node->last_child) {
    					++ret;
    					pos=pos->next_sibling;
    					}
    				return ret;
    				}

    				tree_node *node;
    			private:
    				bool increment_()
    				{
    				assert(node!=0);
    				if(!skip_current_children_ && node->first_child != 0) {
    					node=node->first_child;
    					return true;
    					}
    				else {
    					skip_current_children_=false;
    					while(node->next_sibling==0) {
    						node=node->parent;
    						if(node==0)
    							return false;
    						}
    					node=node->next_sibling;
    					return true;
    					}
    				}

    				bool decrement_()
    				{
    				assert(node!=0);
    				if(node->parent==0) {
    					if(node->last_child==0)
    						node=node->prev_sibling;
    					while(node->last_child)
    						node=node->last_child;
    					if(!node) return false;
    					}
    				else {
    					if(node->prev_sibling) {
    						if(node->prev_sibling->last_child) {
    							node=node->prev_sibling->last_child;
    							}
    						else {
    							node=node->prev_sibling;
    							}
    						}
    					else {
    						node=node->parent;
    						if(node==0)
    							return false;
    						}
    					}
    				return true;
    				}

    				bool skip_current_children_;
    		};

    		class sibling_iterator {
    				friend class tree<T, tree_node_allocator>;
    				//friend class tree<T, tree_node_allocator>::iterator;
    			public:
    				typedef T                          value_type;
    				typedef T*                         pointer;
    				typedef T&                         reference;
    				typedef size_t                     size_type;
    				typedef ptrdiff_t                  difference_type;
    				typedef std::bidirectional_iterator_tag iterator_category;

    				sibling_iterator()
    				: node(0), parent_(0)
    				{
    				}

    				sibling_iterator(tree_node *tn)
    				: node(tn)
    				{
    				set_parent_();
    				}

    				sibling_iterator(const sibling_iterator& other)
    				: node(other.node), parent_(other.parent_)
    				{
    				}

    				sibling_iterator(const iterator& other)
    				: node(other.node)
    				{
    				set_parent_();
    				}

    				sibling_iterator&  operator++(void)
    				{
    				if(node)
    					node=node->next_sibling;
    				return *this;
    				}

    				sibling_iterator&  operator--(void)
    				{
    				if(node) node=node->prev_sibling;
    				else {
    					assert(parent_);
    					node=parent_->last_child;
    					}
    				return *this;
    				}

    				sibling_iterator&  operator+=(unsigned int num)
    				{
    				while(num>0) {
    					++(*this);
    					--num;
    					}
    				return (*this);
    				}

    				sibling_iterator&  operator-=(unsigned int num)
    				{
    				while(num>0) {
    					--(*this);
    					--num;
    					}
    				return (*this);
    				}

    				T&                 operator*(void) const
    				{
    				return node->data;
    				}

    				T*                 operator->(void) const
    				{
    				return &(node->data);
    				}

    				bool               operator==(const sibling_iterator& other) const
    				{
    				if(other.node==node) return true;
    				else return false;
    				}

    				bool               operator!=(const sibling_iterator& other) const
    				{
    				if(other.node!=node) return true;
    				else return false;
    				}

    				sibling_iterator   operator+(int num) const
    				{
    				sibling_iterator ret(*this);
    				while(num>0) {
    					++ret;
    					--num;
    					}
    				return ret;
    				}

    				bool       is_valid() const
    				{
    				if(node==0) return false;
    				else return true;
    				}

    				tree_node *range_first() const
    				{
    				tree_node *tmp=parent_->first_child;
    				return tmp;
    				}

    				tree_node *range_last() const
    				{
    				return parent_->last_child;
    				}

    				tree_node *node;

    			private:
    				void set_parent_()
    				{
    				parent_=0;
    				if(node==0) return;
    				if(node->parent!=0)
    					parent_=node->parent;
    				}

    				tree_node *parent_;
    		};

    		// begin/end of tree
    		iterator begin() const
    		{
    		return iterator(head->next_sibling);
    		}
    		iterator end() const
    		{
    		return iterator(head);
    		}
    		// begin/end of children of node
    		sibling_iterator begin(iterator pos) const
    		{
    		if(pos.node->first_child==0) {
    			return end(pos);
    			}
    		return pos.node->first_child;
    		}

    		sibling_iterator end(iterator pos) const
    		{
    		sibling_iterator ret(0);
    		ret.parent_= pos.node;
    		return ret;
    		}

    		iterator parent(iterator position) const
    		{
    		assert(position.node!=0);
    		return iterator(position.node->parent);
    		}

    		iterator previous_sibling(iterator position) const
    		{
    		assert(position.node!=0);
    		return iterator(position.node->prev_sibling);
    		}

    		iterator next_sibling(iterator position) const
    		{
    		assert(position.node!=0);
    		return iterator(position.node->next_sibling);
    		}

    		void clear()
    		{
    		if(head)
    			while(head->next_sibling!=head)
    				erase(head->next_sibling);
    		}

    		// erase element at position pointed to by iterator, increment iterator
    		iterator erase(iterator it)
    		{
    		tree_node *cur=it.node;
    		assert(cur!=head);
    		iterator ret=it;
    		ret.skip_children();
    		++ret;
    		erase_children(it);
    		if(cur->prev_sibling==0) {
    			cur->parent->first_child=cur->next_sibling;
    			}
    		else {
    			cur->prev_sibling->next_sibling=cur->next_sibling;
    			}
    		if(cur->next_sibling==0) {
    			cur->parent->last_child=cur->prev_sibling;
    			}
    		else {
    			cur->next_sibling->prev_sibling=cur->prev_sibling;
    			}

    		destructor(&cur->data);
    		alloc_.deallocate(cur,1);
    		return ret;
    		}
    		// erase all children of the node pointed to by iterator
    		void     erase_children(iterator it)
    		{
    		tree_node *cur=it.node->first_child;
    		tree_node *prev=0;

    		while(cur!=0) {
    			prev=cur;
    			cur=cur->next_sibling;
    			erase_children(prev);
    			destructor(&prev->data);
    			alloc_.deallocate(prev,1);
    			}
    		it.node->first_child=0;
    		it.node->last_child=0;
    		}

    		// insert node as last child of node pointed to by position
    		iterator append_child(iterator position)
     		{
    		assert(position.node!=head);

    		tree_node* tmp = alloc_.allocate(1,0);
    		constructor(&tmp->data);
    		tmp->first_child=0;
    		tmp->last_child=0;

    		tmp->parent=position.node;
    		if(position.node->last_child!=0) {
    			position.node->last_child->next_sibling=tmp;
    			}
    		else {
    			position.node->first_child=tmp;
    			}
    		tmp->prev_sibling=position.node->last_child;
    		position.node->last_child=tmp;
    		tmp->next_sibling=0;
    		return tmp;
     		}

    		iterator append_child(iterator position, const T& x)
    		{
    		// If your program fails here you probably used 'append_child' to add the top
    		// node to an empty tree. From version 1.45 the top element should be added
    		// using 'insert'. See the documentation for further information, and sorry about
    		// the API change.
    		assert(position.node!=head);

    		tree_node* tmp = alloc_.allocate(1,0);
    		constructor(&tmp->data, x);
    		tmp->first_child=0;
    		tmp->last_child=0;

    		tmp->parent=position.node;
    		if(position.node->last_child!=0) {
    			position.node->last_child->next_sibling=tmp;
    			}
    		else {
    			position.node->first_child=tmp;
    			}
    		tmp->prev_sibling=position.node->last_child;
    		position.node->last_child=tmp;
    		tmp->next_sibling=0;
    		return tmp;
    		}

    		iterator append_child(iterator position, iterator other_position)
    		{
    		assert(position.node!=head);

    		sibling_iterator aargh=append_child(position, value_type());
    		return replace(aargh, aargh+1, other, sibling_iterator(other)+1);
    		}

    		// short-hand to insert topmost node in otherwise empty tree
    		iterator set_head(const T& x)
    		{
    		assert(begin()==end());
    		return insert(begin(), x);
    		}

    		// insert node as previous sibling of node pointed to by position
    		iterator insert(iterator position, const T& x)
    		{
    		tree_node* tmp = alloc_.allocate(1,0);
    		constructor(&tmp->data, x);
    		tmp->first_child=0;
    		tmp->last_child=0;

    		tmp->parent=position.node->parent;
    		tmp->next_sibling=position.node;
    		tmp->prev_sibling=position.node->prev_sibling;
    		position.node->prev_sibling=tmp;

    		if(tmp->prev_sibling==0)
    			tmp->parent->first_child=tmp;
    		else
    			tmp->prev_sibling->next_sibling=tmp;
    		return tmp;
    		}

    		// insert node as previous sibling of node pointed to by position
    		iterator insert(sibling_iterator position, const T& x)
    		{
    		tree_node* tmp = alloc_.allocate(1,0);
    		constructor(&tmp->data, x);
    		tmp->first_child=0;
    		tmp->last_child=0;

    		tmp->next_sibling=position.node;
    		if(position.node==0) { // iterator points to end of a subtree
    			tmp->parent=position.parent_;
    			tmp->prev_sibling=position.range_last();
    			}
    		else {
    			tmp->parent=position.node->parent;
    			tmp->prev_sibling=position.node->prev_sibling;
    			position.node->prev_sibling=tmp;
    			}

    		if(tmp->prev_sibling==0)
    			tmp->parent->first_child=tmp;
    		else
    			tmp->prev_sibling->next_sibling=tmp;
    		return tmp;
    		}

    		// insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
    		iterator insert(iterator position, iterator subtree)
    		{
    		// insert dummy
    		iterator it=insert(position, value_type());
    		// replace dummy with subtree
    		return replace(it, subtree);
    		}

    		// insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
    		iterator insert(sibling_iterator position, iterator subtree)
    		{
    		// insert dummy
    		iterator it=insert(position, value_type());
    		// replace dummy with subtree
    		return replace(it, subtree);
    		}

    		// insert node as next sibling of node pointed to by position
    		iterator insert_after(iterator position, const T& x)
    		{
    		tree_node* tmp = alloc_.allocate(1,0);
    		constructor(&tmp->data, x);
    		tmp->first_child=0;
    		tmp->last_child=0;

    		tmp->parent=position.node->parent;
    		tmp->prev_sibling=position.node;
    		tmp->next_sibling=position.node->next_sibling;
    		position.node->next_sibling=tmp;

    		if(tmp->next_sibling==0) {
    			tmp->parent->last_child=tmp;
    			}
    		return tmp;
    		}

    		// replace node at 'position' with other node (keeping same children)
    		iterator replace(iterator position, const T& x)
    		{
    		destructor(&position.node->data);
    		constructor(&position.node->data, x);
    		return position;
    		}

    		// replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from')
    		iterator replace(iterator position, iterator from)
    		{
    		assert(position.node!=head);

    		tree_node *current_from=from.node;
    		tree_node *start_from=from.node;
    		tree_node *last=from.node->next_sibling;
    		tree_node *current_to  =position.node;

    		// replace the node at position with head of the replacement tree at from
    		erase_children(position);
    		tree_node* tmp = alloc_.allocate(1,0);
    		constructor(&tmp->data, (*from));
    		tmp->first_child=0;
    		tmp->last_child=0;
    		if(current_to->prev_sibling==0) {
    			current_to->parent->first_child=tmp;
    			}
    		else {
    			current_to->prev_sibling->next_sibling=tmp;
    			}
    		tmp->prev_sibling=current_to->prev_sibling;
    		if(current_to->next_sibling==0) {
    			current_to->parent->last_child=tmp;
    			}
    		else {
    			current_to->next_sibling->prev_sibling=tmp;
    			}
    		tmp->next_sibling=current_to->next_sibling;
    		tmp->parent=current_to->parent;
    		destructor(¤t_to->data);
    		alloc_.deallocate(current_to,1);
    		current_to=tmp;

    		iterator toit=tmp;

    		// copy all children
    		do {
    			assert(current_from!=0);
    			if(current_from->first_child != 0) {
    				current_from=current_from->first_child;
    				toit=append_child(toit, current_from->data);
    				}
    			else {
    				while(current_from->next_sibling==0 && current_from!=start_from) {
    					current_from=current_from->parent;
    					toit=parent(toit);
    					assert(current_from!=0);
    					}
    				current_from=current_from->next_sibling;
    				if(current_from!=last) {
    					toit=append_child(parent(toit), current_from->data);
    					}
    				}
    			} while(current_from!=last);

    		return current_to;
    		}

    		// replace string of siblings (plus their children) with copy of a new string (with children)
    		iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
    							  sibling_iterator new_begin,  sibling_iterator new_end)
    		{
    		tree_node *orig_first=orig_begin.node;
    		tree_node *new_first=new_begin.node;
    		tree_node *orig_last=orig_first;
    		while(++orig_begin!=orig_end)
    			orig_last=orig_last->next_sibling;
    		tree_node *new_last=new_first;
    		while(++new_begin!=new_end)
    			new_last=new_last->next_sibling;

    		// insert all siblings in new_first..new_last before orig_first
    		bool first=true;
    		iterator ret;
    		while(1==1) {
    			iterator tt=insert(iterator(orig_first), new_first);
    			if(first) {
    				ret=tt;
    				first=false;
    				}
    			if(new_first==new_last)
    				break;
    			new_first=new_first->next_sibling;
    			}

    		// erase old range of siblings
    		bool last=false;
    		tree_node *next=orig_first;
    		while(1==1) {
    			if(next==orig_last)
    				last=true;
    			next=next->next_sibling;
    			erase(orig_first);
    			if(last)
    				break;
    			orig_first=next;
    			}
    		return ret;
    		}

    		// move all children of node at 'position' to be siblings
    		iterator flatten(iterator position)
    		{
    		if(position.node->first_child==0)
    			return position;

    		tree_node *tmp=position.node->first_child;
    		while(tmp) {
    			tmp->parent=position.node->parent;
    			tmp=tmp->next_sibling;
    			}
    		if(position.node->next_sibling) {
    			position.node->last_child->next_sibling=position.node->next_sibling;
    			position.node->next_sibling->prev_sibling=position.node->last_child;
    			}
    		else {
    			position.node->parent->last_child=position.node->last_child;
    			}
    		position.node->next_sibling=position.node->first_child;
    		position.node->next_sibling->prev_sibling=position.node;
    		position.node->first_child=0;
    		position.node->last_child=0;

    		return position;
    		}

    		// move nodes in range to be children of 'position'
    		iterator reparent(iterator position, sibling_iterator begin, sibling_iterator end)
    		{
    		tree_node *first=begin.node;
    		tree_node *last=first;
    		while(++begin!=end) {
    			last=last->next_sibling;
    			}
    		// move subtree
    		if(first->prev_sibling==0) {
    			first->parent->first_child=last->next_sibling;
    			}
    		else {
    			first->prev_sibling->next_sibling=last->next_sibling;
    			}
    		if(last->next_sibling==0) {
    			last->parent->last_child=first->prev_sibling;
    			}
    		else {
    			last->next_sibling->prev_sibling=first->prev_sibling;
    			}
    		if(position.node->first_child==0) {
    			position.node->first_child=first;
    			position.node->last_child=last;
    			first->prev_sibling=0;
    			}
    		else {
    			position.node->last_child->next_sibling=first;
    			first->prev_sibling=position.node->last_child;
    			position.node->last_child=last;
    			}
    		last->next_sibling=0;

    		tree_node *pos=first;
    		while(1==1) {
    			pos->parent=position.node;
    			if(pos==last) break;
    			pos=pos->next_sibling;
    			}

    		return first;
    		}

    		// ditto, the range being all children of the 'from' node
    		iterator reparent(iterator position, iterator from)
    		{
    		if(from.node->first_child==0) return position;
    		return reparent(position, from.node->first_child, from.node->last_child);
    		}

    		// merge with other tree, creating new branches and leaves only if they are not already present
    		void     merge(iterator position, iterator other, bool duplicate_leaves=false)
    		{
    		sibling_iterator fnd;
    		sibling_iterator oit=other;
    		while(oit.is_valid()) {
    			if((fnd=find(position.begin(), position.end(), (*other)))!=position.end()) {
    				if(duplicate_leaves && other.begin()==other.end()) { // it's a leave
    					append_child(position, (*other));
    					}
    				else {
    					if(other.begin()!=other.end())
    						merge(fnd, other.begin(), duplicate_leaves);
    					}
    				}
    			else {
    				insert(position.end(), oit);
    				}
    			++oit;
    			}
    		}

    		// sort (std::sort only moves values of nodes, this one moves children as well)
    		void     sort(sibling_iterator from, sibling_iterator to, bool deep=false)
    		{
    		std::less<T> comp;
    		sort(from, to, comp, deep);
    		}

    		template<class StrictWeakOrdering>
    		void     sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false)
    		{
    		if(from==to) return;
    		// make list of sorted nodes
    		// CHECK: if multiset stores equivalent nodes in the order in which they
    		// are inserted, then this routine should be called 'stable_sort'.
    		std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes;
    		sibling_iterator it=from, it2=to;
    		while(it != to) {
    			nodes.insert(it.node);
    			++it;
    			}
    		// reassemble
    		--it2;
    		tree_node *prev=from.node->prev_sibling;
    		tree_node *next=it2.node->next_sibling;
    		typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
    		if(prev==0) {
    			(*nit)->parent->first_child=(*nit);
    			}
    		--eit;
    		while(nit!=eit) {
    			(*nit)->prev_sibling=prev;
    			if(prev)
    				prev->next_sibling=(*nit);
    			prev=(*nit);
    			++nit;
    			}
    		if(prev)
    			prev->next_sibling=(*eit);
    		(*eit)->next_sibling=next;
    		if(next==0) {
    			(*eit)->parent->last_child=next;
    			}

    		if(deep) {	// sort the children of each node too
    			sibling_iterator bcs(*nodes.begin());
    			sibling_iterator ecs(*eit);
    			++ecs;
    			while(bcs!=ecs) {
    				sort(begin(bcs), end(bcs), comp, deep);
    				++bcs;
    				}
    			}
    		}

    		// compare subtrees starting at the two iterators (compares nodes as well as tree structure)
    		template<class BinaryPredicate>
    		bool     equal(iterator one, iterator two, iterator three, BinaryPredicate fun) const
    		{
    		while(one!=two && three.is_valid()) {
    			if(one.number_of_children()!=three.number_of_children())
    				return false;
    			if(!fun(*one,*three))
    				return false;
    			++one;
    			++three;
    			}
    		return true;
    		}

    		// extract a new tree formed by the range of siblings plus all their children
    		tree     subtree(sibling_iterator from, sibling_iterator to) const
    		{
    		tree tmp;
    		tmp.set_head(value_type());
    		tmp.replace(tmp.begin(), tmp.end(), from, to);
    		return tmp;
    		}

    		void     subtree(tree&, sibling_iterator from, sibling_iterator to) const
    		{
    		tmp.set_head(value_type());
    		tmp.replace(tmp.begin(), tmp.end(), from, to);
    		}

    		// count the total number of nodes
    		int      size() const
    		{
    		int i=0;
    		iterator it=begin(), eit=end();
    		while(it!=eit) {
    			++i;
    			++it;
    			}
    		return i;
    		}

    		// compute the depth to the root
    		int      depth(iterator it) const
    		{
    		tree_node* pos=it.node;
    		assert(pos!=0);
    		int ret=0;
    		while(pos->parent!=0) {
    			pos=pos->parent;
    			++ret;
    			}
    		return ret;
    		}

    		// count the number of children of node at position
    		unsigned int number_of_children(iterator it) const
    		{
    		tree_node *pos=it.node->first_child;
    		if(pos==0) return 0;

    		unsigned int ret=1;
    		while(pos!=it.node->last_child) {
    			++ret;
    			pos=pos->next_sibling;
    			}
    		return ret;
    		}

    		// count the number of 'next' siblings of node at iterator
    		unsigned int number_of_siblings(iterator it) const
    		{
    		tree_node *pos=it.node;
    		unsigned int ret=1;
    		while(pos->next_sibling && pos->next_sibling!=head) {
    			++ret;
    			pos=pos->next_sibling;
    			}
    		return ret;
    		}

    		// determine whether node at position is in the subtrees with root in the range
    		bool     is_in_subtree(iterator position, iterator begin, iterator end) const
    		{
    		// FIXME: this should be optimised.
    		iterator tmp=begin;
    		while(tmp!=end) {
    			if(tmp==it) return true;
    			++tmp;
    			}
    		return false;
    		}

    		// return the n-th child of the node at position
    		T&       child(iterator position, unsigned int) const
    		{
    		tree_node *tmp=it.node->first_child;
    		while(num--) {
    			assert(tmp!=0);
    			tmp=tmp->next_sibling;
    			}
    		return tmp->data;
    		}

    	private:
    		tree_node_allocator alloc_;
    		tree_node *head;    // head is always a dummy; if an iterator points to head it is invalid
    		void head_initialise_()
    		{
    		head = alloc_.allocate(1,0); // MSVC does not have default second argument

    		head->parent=0;
    		head->first_child=0;
    		head->last_child=0;
    		head->prev_sibling=head;
    		head->next_sibling=head;
    		}

    		void copy_(const tree<T, tree_node_allocator>& other)
    		{
    		clear();
    		iterator it=other.begin(), to=begin();
    		while(it!=other.end()) {
    			to=insert(to, (*it));
    			it.skip_children();
    			++it;
    			}
    		to=begin();
    		it=other.begin();
    		while(it!=other.end()) {
    			to=replace(to, it);
    			to.skip_children();
    			it.skip_children();
    			++to;
    			++it;
    			}
    		}

    		template<class StrictWeakOrdering>
    		class compare_nodes {
    			public:
    				bool operator()(const tree_node* a, const tree_node* b)
    				{
    				static StrictWeakOrdering comp;
    				return comp(a->data, b->data);
    				}
    		};
    };

    #endif

    // Local variables:
    // default-tab-width: 3
    // End:

Currently browsing [PerformanceMonitor.zip] (10,407 bytes) - [PerformanceMonitor.cpp] - (970 bytes)

    /*-----------------------------------------------------------------------------
    Pragma's
    -----------------------------------------------------------------------------*/
    //#include "stdafx.h"

    /*-----------------------------------------------------------------------------
    Interface Include file
    -----------------------------------------------------------------------------*/
    #include "PerformanceMonitor.h"

    /*-----------------------------------------------------------------------------
    Includes for Implementation
    -----------------------------------------------------------------------------*/

    /*-----------------------------------------------------------------------------
    Globals
    -----------------------------------------------------------------------------*/
    tree<CPerformanceStatistics>					CPerformanceMonitor::Statistics;
    tree<CPerformanceStatistics>::sibling_iterator	CPerformanceMonitor::s_Parent = Statistics.begin();

Currently browsing [PerformanceMonitor.zip] (10,407 bytes) - [PerformanceMonitor.h] - (1,955 bytes)

    #pragma once
    #ifndef PERFORMANCEMONITOR_H
    #define PERFORMANCEMONITOR_H
    /*-----------------------------------------------------------------------------

    Performance Monitor.

    Creating a performance monitor object will start a sampling session. Samples
    taken within other sessions are built as a tree structure.

    -----------------------------------------------------------------------------*/

    #define PERFORMANCE_MONITOR_ENABLED

    /*-----------------------------------------------------------------------------
    Includes for Interface
    -----------------------------------------------------------------------------*/
    #include <string>
    #include "Tree.h"
    #include "Timer.h"

    /*-----------------------------------------------------------------------------
    Class
    -----------------------------------------------------------------------------*/
    class CPerformanceStatistics
    {
    public:

    	CPerformanceStatistics(const std::string& a_Name);
    	bool operator== (const CPerformanceStatistics& a_Stats) const;

    public:

    	std::string		Name;
    	float			Percent;
    	unsigned int	Min;
    	unsigned int	Max;
    	unsigned int	TotalTime;
    	unsigned int	Samples;

    };

    class CPerformanceMonitor
    {
    public:

    	CPerformanceMonitor(const char* a_Name);
    	~CPerformanceMonitor();

    	static void Reset(void);

    public:

    	static tree<CPerformanceStatistics>						Statistics;

    private:

    	CTimer													m_Timer;
    	tree<CPerformanceStatistics>::iterator					m_ThisNode;
    	static tree<CPerformanceStatistics>::sibling_iterator	s_Parent;

    };

    /*-----------------------------------------------------------------------------
    Inlined Functions
    -----------------------------------------------------------------------------*/
    #include "PerformanceMonitor.inl"

    #ifdef PERFORMANCE_MONITOR_ENABLED
    	#define Profile(Name) CPerformanceMonitor PerformanceMonitor(Name)
    #else
    	#define Profile(Name)
    #endif

    #endif //PERFORMANCEMONITOR_H

Currently browsing [PerformanceMonitor.zip] (10,407 bytes) - [Timer Win32.cpp] - (1,303 bytes)

    /*-----------------------------------------------------------------------------
    Pragma's
    -----------------------------------------------------------------------------*/
    //#include "stdafx.h"

    /*-----------------------------------------------------------------------------
    Interface Include file
    -----------------------------------------------------------------------------*/
    #include "Timer.h"

    /*-----------------------------------------------------------------------------
    Includes for Implementation
    -----------------------------------------------------------------------------*/

    /*-----------------------------------------------------------------------------
    Globals
    -----------------------------------------------------------------------------*/

    /*-----------------------------------------------------------------------------
    Assumption: CPUID instruction is actually supported.
    -----------------------------------------------------------------------------*/
    unsigned int CTimer::GetTicks(void)
    {
    	unsigned int Elapsed;
    	_asm //Taken from AMD SDK
    	{
    		xor    eax, eax
    		xor    ebx, ebx
    		xor    ecx, ecx
    		xor    edx, edx
    		_emit  0x0f				// CPUID
    		_emit  0xa2
    		_emit  0x0f				// RDTSC
    		_emit  0x31
    		mov    [Elapsed], eax
    	}
    	return Elapsed;
    }

Currently browsing [PerformanceMonitor.zip] (10,407 bytes) - [Timer.h] - (1,178 bytes)

    #pragma once
    #ifndef TIMER_H
    #define TIMER_H
    /*-----------------------------------------------------------------------------

    Clock starts on construction, no cache warming takes place, no overhead is
    calculated as the aim here is to be lightweight, not accurate down to the
    individual clock cycle.

    -----------------------------------------------------------------------------*/

    /*-----------------------------------------------------------------------------
    Includes for Interface
    -----------------------------------------------------------------------------*/

    /*-----------------------------------------------------------------------------
    Class
    -----------------------------------------------------------------------------*/
    class CTimer
    {
    public:

    	CTimer();

    	void Reset(void);

    	unsigned int ElapsedTicks(void);

    private:

    	static unsigned int GetTicks(void);

    private:

    	unsigned int		m_Start;

    };

    /*-----------------------------------------------------------------------------
    Inlined Functions
    -----------------------------------------------------------------------------*/
    #include "Timer.inl"

    #endif //TIMER_H

Currently browsing [PerformanceMonitor.zip] (10,407 bytes) - [Main.cpp] - (1,735 bytes)

    #include <iostream>
    #include "PerformanceMonitor.h"

    using namespace std;

    void main(void)
    {
    	try
    	{
    		for (int j=0; j<5; ++j)
    		{
    			Profile("Frame");

    			{
    				Profile("Input");
    				for(int k=0; k<8000; ++k);
    			}

    			{
    				Profile("AI");
    				for(int k=0; k<20000; ++k);
    			}

    			{
    				Profile("Physics");
    				for(int k=0; k<30000; ++k);
    			}

    			{
    				Profile("Collision");
    				for(int k=0; k<40000; ++k);
    			}

    			{
    				Profile("Renderer");
    				{
    					Profile("Terrain");
    					for(int k=0; k<40000; ++k);
    				}
    				{
    					Profile("Models");
    					for(int k=0; k<40000; ++k);
    				}
    			}
    		}
    	}
    	catch(...)
    	{

    	}

    	//Dummy reporting process.
    	std::string Tabs;
    	for (tree<CPerformanceStatistics>::iterator itr = CPerformanceMonitor::Statistics.begin(); itr != CPerformanceMonitor::Statistics.end(); ++itr)
    	{
    		Tabs.resize(CPerformanceMonitor::Statistics.depth(itr) * 4);

    		tree<CPerformanceStatistics>::iterator Parent = CPerformanceMonitor::Statistics.parent(itr);
    		if (Parent == 0)
    			std::cout << Tabs << itr->Name << " : 100" << std::endl;
    		else
    		{
    			itr->Percent = ((float)itr->TotalTime / (float)Parent->TotalTime) * Parent->Percent;
    			std::cout << Tabs << itr->Name << " : " << itr->Percent * 100 << std::endl;
    		}

    		//std::cout << Tabs << itr->Name << " Minimum : " << itr->Min << std::endl;
    		//std::cout << Tabs << itr->Name << " Maximum : " << itr->Max << std::endl;
    		//std::cout << Tabs << itr->Name << " Average : " << itr->TotalTime/itr->Samples << std::endl;
    		//std::cout << Tabs << itr->Name << " Total   : " << itr->TotalTime << std::endl;
    		//std::cout << Tabs << itr->Name << " Samples : " << itr->Samples << std::endl;
    	}

    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.