boost_tst.cpp

提供了rbtree ttree avltree list hashtable等常用容器的算法,代码经过uclinux + arm44b0平台验证

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <memory>

#ifdef WIN32
	#include <winsock2.h>
#endif

extern "C"
{
	void getcallid(char * callid, size_t callid_len);
	void gettimeofday(struct timeval *ptv, void *tzp);
}

///////////////////////////////////////////////////////////////////////////////
//
//  tst class
//
//      Ternary Search Tree implementation. The data structure is faster than
//      hashing for many typical search problems especially when the search
//      interface is iterator based. Searching for a string of length k in a
//      ternary search tree with n strings will require at most O(log n+k)
//      character comparisons. TSTs are many times faster than hash tables
//      for unsuccessful searches since mismatches are discovered earlier
//      after examining only a few characters. Hash tables always examine an
//      entire key when searching.
//
//      For details see http://www.cs.princeton.edu/~rs/strings/.
//
//      *** This is a low level class and is
//          not meant for public consumption ***
//
///////////////////////////////////////////////////////////////////////////////

template <typename T, typename CharT>
struct tst_node
{
    tst_node(CharT value_)
    : value(value_)
    , left(0)
    , right(0)
    { middle.link = 0; }

    ~tst_node()
    {
        delete left;
        delete right;
        if (value)
            delete middle.link;
        else
            delete middle.data;
    }

    tst_node*
    clone() const
    {
        std::auto_ptr<tst_node> copy(new tst_node(value));

        if (left)
            copy->left = left->clone();
        if (right)
            copy->right = right->clone();

        if (value && middle.link)
        {
            copy->middle.link = middle.link->clone();
        }
        else
        {
            std::auto_ptr<T> mid_data(new T(*middle.data));
            copy->middle.data = mid_data.release();
        }

        return copy.release();
    }

    union center {

        tst_node*   link;
        T*          data;
    };

    CharT       value;
    tst_node*   left;
    center      middle;
    tst_node*   right;
};

///////////////////////////////////////////////////////////////////////////
template <typename T, typename CharT>
class tst
{
public:

    struct search_info
    {
        T*          data;
        size_t length;
    };

    tst()
    : root(0) {}

    tst(tst const& other)
    : root(other.root ? other.root->clone() : 0) {}

    ~tst()
    { delete root; }

    tst&
    operator=(tst const& other)
    {
        if (this != &other)
        {
            node_t* new_root = other.root ? other.root->clone() : 0;
            delete root;
            root = new_root;
        }
        return *this;
    }

    template <typename IteratorT>
    T* add(IteratorT first, IteratorT const& last, T const& data)
    {
        if (first == last)
            return 0;

        node_t**  np = &root;
        CharT   ch = *first;

        assert(first == last || ch != 0
            && "Won't add string containing null character");

        for (;;)
        {
            if (*np == 0 || ch == 0)
            {
                node_t* right = 0;
                if (np != 0)
                    right = *np;
                *np = new node_t(ch);
                if (right)
                    (**np).right = right;
            }

            if (ch < (**np).value)
            {
                np = &(**np).left;
            }
            else
            {
                if (ch == (**np).value)
                {
                    if (ch == 0)
                    {
                        if ((**np).middle.data == 0)
                        {
                            (**np).middle.data = new T(data);
                            return (**np).middle.data;
                        }
                        else
                        {
                            //  re-addition is disallowed
                            return 0;
                        }
                   }
                    ++first;
                    ch = (first == last) ? CharT(0) : *first;
                    assert(first == last || ch != 0
                        && "Won't add string containing null character");
                    np = &(**np).middle.link;
                }
                else
                {
                    np = &(**np).right;
                }
            }
        }
    }
	
	template <typename IteratorT>
    search_info find(IteratorT first, IteratorT const& last) const
    {
        search_info result = { 0, 0 };
        if (first == last) {
            return result;
        }

        
        node_t*     np = root;
        CharT       ch = *first;
        IteratorT  save = first;
        IteratorT  latest = first;
		IteratorT	p = first;
        size_t latest_len = 0;

        while (np)
        {

            if (ch < np->value) // => go left!
            {
                if (np->value == 0)
                {
                    result.data = np->middle.data;
                    if (result.data)
                    {
                        latest = first;
                        latest_len = result.length;
                    }
                }

                np = np->left;
            }
            else if (ch == np->value) // => go middle!
            {
                // Matching the null character is not allowed.
                if (np->value == 0)
                {
                    result.data = np->middle.data;
                    if (result.data)
                    {
                        latest = first;
                        latest_len = result.length;
                    }
                    break;
                }

                ++p;
                ch = p==last ? CharT(0) : *p;
                np = np->middle.link;
                ++result.length;
            }
            else // (ch > np->value) => go right!
            {
                if (np->value == 0)
                {
                    result.data = np->middle.data;
                    if (result.data)
                    {
                        latest = first;
                        latest_len = result.length;
                    }
                }

                np = np->right;
            }
        }

        if (result.data == 0)
        {
            first = save;
        }
        else
        {
            first = latest;
            result.length = latest_len;
        }
        return result;
    }

private:

    typedef tst_node<T, CharT> node_t;
    node_t* root;
};
#define LOOP_COUNT 100000
void test_boost()
{
	struct timeval tv1;
	struct timeval tv2;
	tst<int, char> t;
	srand(0);
	gettimeofday(&tv1, 0);
	for(int i = 0; i< LOOP_COUNT ;i++)
	{
		char k[32] = {0};
		getcallid(k, sizeof(k) - 1);
		t.add(k, k + strlen(k), i);
	}
	gettimeofday(&tv2, 0);
	printf("boost tst添加用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);

	srand(0);
	gettimeofday(&tv1, 0);
	for(int i = 0; i<LOOP_COUNT;i++)
	{
		char k[32] = {0};
		getcallid(k, sizeof(k) - 1);
		t.find(k, k + strlen(k));
	}
	gettimeofday(&tv2, 0);
	printf("boost tst查找用时:%f秒\n", tv2.tv_sec - tv1.tv_sec + (tv2.tv_usec - tv1.tv_usec)/1000000.0);
}