container.h

一个开源的Flash 播放器,可以在Windows/Linux 上运行

// container.h	-- Thatcher Ulrich <[e-mail]> 31 July 2001

// This source code has been donated to the Public Domain.  Do
// whatever you want with it.

// Generic C++ containers.  Problem: STL is murder on compile times,
// and is hard to debug.  These are substitutes that compile much
// faster and are somewhat easier to debug.  Not as featureful,
// efficient or hammered-on as STL though.  You can use STL
// implementations if you want; see _TU_USE_STL.

#ifndef CONTAINER_H
#define CONTAINER_H


#include "base/tu_config.h"
#include "base/utility.h"
#include <stdlib.h>
#include <string.h>	// for strcmp and friends
#include <new>	// for placement new


// If you prefer STL implementations of array<> (i.e. std::vector) and
// hash<> (i.e. std::hash_map) instead of home cooking, then put
// -D_TU_USE_STL=1 in your compiler flags, or do it in tu_config.h, or do
// it right here:
//#define _TU_USE_STL 1



template<class T>
class fixed_size_hash
// Computes a hash of an object's representation.
{
public:
	size_t	operator()(const T& data) const
	{
		unsigned char*	p = (unsigned char*) &data;
		int	size = sizeof(T);

		return sdbm_hash(p, size);
	}
};


template<class T>
class identity_hash
// Hash is just the input value; can use this for integer-indexed hash tables.
{
public:
	size_t	operator()(const T& data) const
	{
		return (size_t) data;
	}
};


#if _TU_USE_STL == 1


//
// Thin wrappers around STL
//


//// @@@ crap compatibility crap
//#define StlAlloc(size) malloc(size)
//#define StlFree(ptr, size) free(ptr)


#include <vector>
#include <hash_map>
#include <string>


// array<> is much like std::vector<>
//
// @@ move this towards a strict subset of std::vector ?  Compatibility is good.
template<class T> class array : public std::vector<T>
{
public:
	int	size() const { return (int) std::vector<T>::size(); }

	void	append(const array<T>& other)
	// Append the given data to our array.
	{
		std::vector<T>::insert(end(), other.begin(), other.end());
	}

	void	append(const T other[], int count)
	{
		// This will probably work.  Depends on std::vector<T>::iterator being typedef'd as T*
		std::vector<T>::insert(end(), &other[0], &other[count]);
	}

	void	remove(int index)
	{
		std::vector<T>::erase(begin() + index);
	}

	void	insert(int index, const T& val = T())
	{
		std::vector<T>::insert(begin() + index, val);
	}

	void	release()
	{
		// Drop all storage.
		std::vector<T>	temp;
		this->swap(temp);
	}
};


// hash<> is similar to std::hash_map<>
//
// @@ move this towards a strict subset of std::hash_map<> ?
template<class T, class U, class hash_functor = fixed_size_hash<T> >
class hash : public std::hash_map<T, U, hash_functor>
{
public:
	// extra convenience interfaces
	void	set(const T& key, const U& value)
	// Set a new or existing value under the key, to the value.
	{
		(*this)[key] = value;
	}

	void	add(const T& key, const U& value)
	{
		assert(find(key) == end());
		(*this)[key] = value;
	}

	bool	is_empty() const { return empty(); }

	bool	get(const T& key, U* value) const
	// Retrieve the value under the given key.
	//
	// If there's no value under the key, then return false and leave
	// *value alone.
	//
	// If there is a value, return true, and set *value to the entry's
	// value.
	//
	// If value == NULL, return true or false according to the
	// presence of the key, but don't touch *value.
	{
		const_iterator	it = find(key);
		if (it != end())
		{
			if (value) *value = it->second;
			return true;
		}
		else
		{
			return false;
		}
	}
};


// // tu_string is a subset of std::string, for the most part
// class tu_string : public std::string
// {
// public:
// 	tu_string(const char* str) : std::string(str) {}
// 	tu_string() : std::string() {}
// 	tu_string(const tu_string& str) : std::string(str) {}

// 	int	length() const { return (int) std::string::length(); }
// };


// template<class U>
// class string_hash : public hash<tu_string, U, std::hash<std::string> >
// {
// };


#else // not _TU_USE_STL


//
// Homemade containers; almost strict subsets of STL.
//


#ifdef _WIN32
#pragma warning(disable : 4345)	// in MSVC 7.1, warning about placement new POD default initializer
#endif // _WIN32




template<class T>
class array {
// Resizable array.  Don't put anything in here that can't be moved
// around by bitwise copy.  Don't keep the address of an element; the
// array contents will move around as it gets resized.
//
// Default constructor and destructor get called on the elements as
// they are added or removed from the active part of the array.
public:
	array() : m_buffer(0), m_size(0), m_buffer_size(0) {}
	array(int size_hint) : m_buffer(0), m_size(0), m_buffer_size(0) { resize(size_hint); }
	array(const array<T>& a)
		:
		m_buffer(0),
		m_size(0),
		m_buffer_size(0)
	{
		operator=(a);
	}
	~array() {
		clear();
	}

	// Basic array access.
	T&	operator[](int index) { assert(index >= 0 && index < m_size); return m_buffer[index]; }
	const T&	operator[](int index) const { assert(index >= 0 && index < m_size); return m_buffer[index]; }
	int	size() const { return m_size; }

	void	push_back(const T& val)
	// Insert the given element at the end of the array.
	{
		// DO NOT pass elements of your own vector into
		// push_back()!  Since we're using references,
		// resize() may munge the element storage!
		assert(&val < &m_buffer[0] || &val > &m_buffer[m_buffer_size]);

		int	new_size = m_size + 1;
		resize(new_size);
		(*this)[new_size-1] = val;
	}

	void	pop_back()
	// Remove the last element.
	{
		assert(m_size > 0);
		resize(m_size - 1);
	}

	// Access the first element.
	T&	front() { return (*this)[0]; }
	const T&	front() const { return (*this)[0]; }

	// Access the last element.
	T&	back() { return (*this)[m_size-1]; }
	const T&	back() const { return (*this)[m_size-1]; }

	void	clear()
	// Empty and destruct all elements.
	{
		resize(0);
	}

	void	release() { clear(); }

	void	operator=(const array<T>& a)
	// Array copy.  Copies the contents of a into this array.
	{
		resize(a.size());
		for (int i = 0; i < m_size; i++) {
			*(m_buffer + i) = a[i];
		}
	}


	void	remove(int index)
	// Removing an element from the array is an expensive operation!
	// It compacts only after removing the last element.
	{
		assert(index >= 0 && index < m_size);

		if (m_size == 1)
		{
			clear();
		}
		else
		{
			m_buffer[index].~T();	// destructor

			memmove(m_buffer+index, m_buffer+index+1, sizeof(T) * (m_size - 1 - index));
			m_size--;
		}
	}


	void	insert(int index, const T& val = T())
	// Insert the given object at the given index shifting all the elements up.
	{
		assert(index >= 0 && index <= m_size);

		resize(m_size + 1);

		if (index < m_size - 1)
		{
			// is it safe to use memmove?
			memmove(m_buffer+index+1, m_buffer+index, sizeof(T) * (m_size - 1 - index));
		}

		// Copy-construct into the newly opened slot.
		new (m_buffer + index) T(val);
	}


	void	append(const array<T>& other)
	// Append the given data to our array.
	{
		append(other.m_buffer, other.size());
	}


	void	append(const T other[], int count)
	// Append the given data to our array.
	{
		if (count > 0)
		{
			int	size0 = m_size;
			resize(m_size + count);
			// Must use operator=() to copy elements, in case of side effects (e.g. ref-counting).
			for (int i = 0; i < count; i++)
			{
				m_buffer[i + size0] = other[i];
			}
		}
	}


	void	resize(int new_size)
	// Preserve existing elements via realloc.
	// 
	// Newly created elements are initialized with default element
	// of T.  Removed elements are destructed.
	{
		assert(new_size >= 0);

		int	old_size = m_size;
		m_size = new_size;

		// Destruct old elements (if we're shrinking).
		{for (int i = new_size; i < old_size; i++) {
			(m_buffer + i)->~T();
		}}

		if (new_size == 0) {
			m_buffer_size = 0;
			reserve(m_buffer_size);
		} else if (m_size <= m_buffer_size && m_size > m_buffer_size >> 1) {
			// don't compact yet.
			assert(m_buffer != 0);
		} else {
			int	new_buffer_size = m_size + (m_size >> 2);
			reserve(new_buffer_size);
		}

		// Copy default T into new elements.
		{for (int i = old_size; i < new_size; i++) {
			new (m_buffer + i) T();	// placement new
		}}
	}

	void	reserve(int rsize)
	// @@ TODO change this to use ctor, dtor, and operator=
	// instead of preserving existing elements via binary copy via
	// realloc?
	{
		assert(m_size >= 0);

		int	old_size = m_buffer_size;
		old_size = old_size;	// don't warn that this is unused.
		m_buffer_size = rsize;

		// Resize the buffer.
		if (m_buffer_size == 0) {
			if (m_buffer) {
				tu_free(m_buffer, sizeof(T) * old_size);
			}
			m_buffer = 0;
		} else {
			if (m_buffer) {
				m_buffer = (T*) tu_realloc(m_buffer, sizeof(T) * m_buffer_size, sizeof(T) * old_size);
			} else {
				m_buffer = (T*) tu_malloc(sizeof(T) * m_buffer_size);
				memset(m_buffer, 0, (sizeof(T) * m_buffer_size));
			}
			assert(m_buffer);	// need to throw (or something) on malloc failure!
		}			
	}

	void	transfer_members(array<T>* a)
	// UNSAFE!  Low-level utility function: replace this array's
	// members with a's members.
	{
		m_buffer = a->m_buffer;
		m_size = a->m_size;
		m_buffer_size = a->m_buffer_size;

		a->m_buffer = 0;
		a->m_size = 0;
		a->m_buffer_size = 0;
	}

private:
	T*	m_buffer;
	int	m_size;
	int	m_buffer_size;
};


template<class T, class U, class hash_functor = fixed_size_hash<T> >
class hash {
// Hash table, linear probing, internal chaining.  One
// interesting/nice thing about this implementation is that the table
// itself is a flat chunk of memory containing no pointers, only
// relative indices.  If the key and value types of the hash contain
// no pointers, then the hash can be serialized using raw IO.  Could
// come in handy.
//
// Never shrinks, unless you explicitly clear() it.  Expands on
// demand, though.  For best results, if you know roughly how big your
// table will be, default it to that size when you create it.
public:
	hash() : m_table(NULL) { }
	hash(int size_hint) : m_table(NULL) { set_capacity(size_hint); }
	~hash() { clear(); }

	hash(const hash<T,U,hash_functor>& src)
		:
		m_table(NULL)
	{
		*this = src;
	}

	void	operator=(const hash<T,U,hash_functor>& src)
	{
		clear();
		if (src.is_empty() == false)
		{
			set_capacity(src.size());

			for (iterator it = src.begin(); it != src.end(); it++)
			{
				add(it->first, it->second);
			}
		}
	}

	// @@ need a "remove()"

	void	set(const T& key, const U& value)
	// Set a new or existing value under the key, to the value.
	{
		int	index = find_index(key);
		if (index >= 0)
		{
			E(index).second = value;
			return;
		}

		// Entry under key doesn't exist.
		add(key, value);
	}

	void	add(const T& key, const U& value)
	// Add a new value to the hash table, under the specified key.
	{
		assert(find_index(key) == -1);

		check_expand();
		assert(m_table);
		m_table->m_entry_count++;

		unsigned int	hash_value = hash_functor()(key);
		int	index = hash_value & m_table->m_size_mask;

		entry*	natural_entry = &(E(index));
		
		if (natural_entry->is_empty())
		{
			// Put the new entry in.
			new (natural_entry) entry(key, value, -1, hash_value);
		}
		else
		{
			// Find a blank spot.
			int	blank_index = index;
			for (;;)
			{
				blank_index = (blank_index + 1) & m_table->m_size_mask;
				if (E(blank_index).is_empty()) break;	// found it
			}
			entry*	blank_entry = &E(blank_index);

			if (int(natural_entry->m_hash_value & m_table->m_size_mask) == index)
			{
				// Collision.  Link into this chain.

				// Move existing list head.
				new (blank_entry) entry(*natural_entry);	// placement new, copy ctor

				// Put the new info in the natural entry.
				natural_entry->first = key;
				natural_entry->second = value;
				natural_entry->m_next_in_chain = blank_index;
				natural_entry->m_hash_value = hash_value;
			}
			else
			{
				// Existing entry does not naturally
				// belong in this slot.  Existing
				// entry must be moved.

				// Find natural location of collided element (i.e. root of chain)
				int	collided_index = natural_entry->m_hash_value & m_table->m_size_mask;
				for (;;)
				{
					entry*	e = &E(collided_index);
					if (e->m_next_in_chain == index)
					{
						// Here's where we need to splice.
						new (blank_entry) entry(*natural_entry);
						e->m_next_in_chain = blank_index;
						break;
					}
					collided_index = e->m_next_in_chain;
					assert(collided_index >= 0 && collided_index <= m_table->m_size_mask);
				}

				// Put the new data in the natural entry.
				natural_entry->first = key;
				natural_entry->second = value;
				natural_entry->m_hash_value = hash_value;
				natural_entry->m_next_in_chain = -1;
			}
		}
	}

	void	clear()
	// Remove all entries from the hash table.
	{
		if (m_table)
		{
			// Delete the entries.
			for (int i = 0, n = m_table->m_size_mask; i <= n; i++)
			{
				entry*	e = &E(i);
				if (e->is_empty() == false)
				{
					e->clear();
				}
			}
			tu_free(m_table, sizeof(table) + sizeof(entry) * (m_table->m_size_mask + 1));
			m_table = NULL;
		}
	}

	bool	is_empty() const
	// Returns true if the hash is empty.
	{
		return m_table == NULL || m_table->m_entry_count == 0;
	}


	bool	get(const T& key, U* value) const
	// Retrieve the value under the given key.
	//
	// If there's no value under the key, then return false and leave
	// *value alone.
	//
	// If there is a value, return true, and set *value to the entry's
	// value.
	//
	// If value == NULL, return true or false according to the
	// presence of the key, but don't touch *value.
	{
		int	index = find_index(key);
		if (index >= 0)
		{
			if (value) {
				*value = E(index).second;
			}
			return true;
		}
		return false;
	}


	int	size()
	{
		return m_table == NULL ? 0 : m_table->m_entry_count;
	}


	void	check_expand()
	// Resize the hash table to fit one more entry.  Often this
	// doesn't involve any action.
	{
		if (m_table == NULL) {
			// Initial creation of table.  Make a minimum-sized table.
			set_raw_capacity(16);
		} else if (m_table->m_entry_count * 3 > (m_table->m_size_mask + 1) * 2) {
			// Table is more than 2/3rds full.  Expand.
			set_raw_capacity((m_table->m_size_mask + 1) * 2);
		}
	}


	void	resize(size_t n)
	// Hint the bucket count to >= n.
	{
		// Not really sure what this means in relation to
		// STLport's hash_map... they say they "increase the
		// bucket count to at least n" -- but does that mean
		// their real capacity after resize(n) is more like
		// n*2 (since they do linked-list chaining within
		// buckets?).
		set_capacity(n);
	}

	void	set_capacity(int new_size)
	// Size the hash so that it can comfortably contain the given
	// number of elements.  If the hash already contains more
	// elements than new_size, then this may be a no-op.
	{
		int	new_raw_size = (new_size * 3) / 2;
		if (new_raw_size < size()) { return; }

		set_raw_capacity(new_raw_size);
	}

	// Behaves much like std::pair
	struct entry
	{
		int	m_next_in_chain;	// internal chaining for collisions
		size_t	m_hash_value;		// avoids recomputing.  Worthwhile?
		T	first;
		U	second;

		entry() : m_next_in_chain(-2) {}
		entry(const entry& e)
			: m_next_in_chain(e.m_next_in_chain), m_hash_value(e.m_hash_value), first(e.first), second(e.second)
		{
		}
		entry(const T& key, const U& value, int next_in_chain, int hash_value)
			: m_next_in_chain(next_in_chain), m_hash_value(hash_value), first(key), second(value)
		{
		}
		bool	is_empty() const { return m_next_in_chain == -2; }
		bool	is_end_of_chain() const { return m_next_in_chain == -1; }

		void	clear()
		{
			first.~T();	// placement delete
			second.~U();	// placement delete
			m_next_in_chain = -2;
		}