|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r71063 - in branches/quickbook-dev/tools/quickbook: src test/unit
From: dnljms_at_[hidden]
Date: 2011-04-06 20:15:39
Author: danieljames
Date: 2011-04-06 20:15:38 EDT (Wed, 06 Apr 2011)
New Revision: 71063
URL: http://svn.boost.org/trac/boost/changeset/71063
Log:
Quickbook: Don't use null node in symbol table.
Since it isn't using a union for the value/middle pointer, there's no
need to have special terminating nodes.
Removed:
branches/quickbook-dev/tools/quickbook/test/unit/symbols_add_null.cpp
Text files modified:
branches/quickbook-dev/tools/quickbook/src/symbols.hpp | 107 ++++++++++-----------------------------
branches/quickbook-dev/tools/quickbook/test/unit/Jamfile.v2 | 1
branches/quickbook-dev/tools/quickbook/test/unit/symbols_tests.cpp | 1
3 files changed, 28 insertions(+), 81 deletions(-)
Modified: branches/quickbook-dev/tools/quickbook/src/symbols.hpp
==============================================================================
--- branches/quickbook-dev/tools/quickbook/src/symbols.hpp (original)
+++ branches/quickbook-dev/tools/quickbook/src/symbols.hpp 2011-04-06 20:15:38 EDT (Wed, 06 Apr 2011)
@@ -13,8 +13,8 @@
///////////////////////////////////////////////////////////////////////////////
#include <boost/spirit/home/classic/symbols.hpp>
-#include <boost/spirit/home/classic/core/assert.hpp>
#include <boost/intrusive_ptr.hpp>
+#include <boost/scoped_ptr.hpp>
///////////////////////////////////////////////////////////////////////////////
namespace quickbook
@@ -50,7 +50,7 @@
tst_node(CharT value_)
: reference_count(0)
, value(value_)
- , data(0)
+ , data()
{
}
@@ -60,10 +60,8 @@
, left(other.left)
, middle(other.middle)
, right(other.right)
- , data(0)
+ , data(other.data ? new T(*other.data) : 0)
{
- if (other.data)
- data = new T(*other.data);
}
tst_node& operator=(tst_node other)
@@ -72,11 +70,6 @@
return *this;
}
- ~tst_node()
- {
- delete data;
- }
-
void swap(tst_node& x, tst_node& y)
{
boost::swap(x.reference_count, y.reference_count);
@@ -92,7 +85,7 @@
boost::intrusive_ptr<tst_node> left;
boost::intrusive_ptr<tst_node> middle;
boost::intrusive_ptr<tst_node> right;
- T* data;
+ boost::scoped_ptr<T> data;
};
template <typename T, typename CharT>
@@ -121,19 +114,19 @@
root.swap(other.root);
}
+ // Adds symbol to ternary search tree.
+ // If it already exists, then replace it with new value.
+ //
+ // pre: first != last
template <typename IteratorT>
T* add(IteratorT first, IteratorT const& last, T const& data)
{
- if (first == last)
- return 0;
+ assert (first != last);
node_ptr* np = &root;
CharT ch = *first;
- BOOST_SPIRIT_ASSERT((first == last || ch != 0)
- && "Won't add string containing null character");
-
- while(ch != CharT(0))
+ for(;;)
{
if (!*np)
{
@@ -151,9 +144,8 @@
else if (ch == (*np)->value)
{
++first;
- ch = (first == last) ? CharT(0) : *first;
- BOOST_SPIRIT_ASSERT((first == last || ch != 0)
- && "Won't add string containing null character");
+ if (first == last) break;
+ ch = *first;
np = &(*np)->middle;
}
else
@@ -162,22 +154,9 @@
}
}
- if (*np && (*np)->value == CharT(0))
- {
- node_ptr new_node = new node_t(ch);
- new_node->left = (*np)->left;
- new_node->right = (*np)->right;
- *np = new_node;
- }
- else
- {
- node_ptr new_node = new node_t(ch);
- new_node->right = *np;
- *np = new_node;
- }
-
- (*np)->data = new T(data);
- return (*np)->data;
+ boost::scoped_ptr<T> new_data(new T(data));
+ boost::swap((*np)->data, new_data);
+ return (*np)->data.get();
}
template <typename ScannerT>
@@ -191,71 +170,39 @@
typedef typename ScannerT::iterator_t iterator_t;
node_ptr np = root;
CharT ch = *scan;
- iterator_t save = scan.first;
iterator_t latest = scan.first;
- std::size_t latest_len = 0;
+ std::size_t length = 0;
while (np)
{
-
if (ch < np->value) // => go left!
{
- if (np->value == 0)
- {
- result.data = np->data;
- if (result.data)
- {
- latest = scan.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)
+ ++scan;
+ ++length;
+
+ // Found a potential match.
+ if (np->data.get())
{
- result.data = np->data;
- if (result.data)
- {
- latest = scan.first;
- latest_len = result.length;
- }
- break;
+ result.data = np->data.get();
+ result.length = length;
+ latest = scan.first;
}
- ++scan;
- ch = scan.at_end() ? CharT(0) : *scan;
+ if (scan.at_end()) break;
+ ch = *scan;
np = np->middle;
- ++result.length;
}
else // (ch > np->value) => go right!
{
- if (np->value == 0)
- {
- result.data = np->data;
- if (result.data)
- {
- latest = scan.first;
- latest_len = result.length;
- }
- }
-
np = np->right;
}
}
- if (result.data == 0)
- {
- scan.first = save;
- }
- else
- {
- scan.first = latest;
- result.length = latest_len;
- }
+ scan.first = latest;
return result;
}
Modified: branches/quickbook-dev/tools/quickbook/test/unit/Jamfile.v2
==============================================================================
--- branches/quickbook-dev/tools/quickbook/test/unit/Jamfile.v2 (original)
+++ branches/quickbook-dev/tools/quickbook/test/unit/Jamfile.v2 2011-04-06 20:15:38 EDT (Wed, 06 Apr 2011)
@@ -10,5 +10,4 @@
# Copied from spirit
run symbols_tests.cpp ;
-run symbols_add_null.cpp ;
run symbols_find_null.cpp ;
\ No newline at end of file
Deleted: branches/quickbook-dev/tools/quickbook/test/unit/symbols_add_null.cpp
==============================================================================
--- branches/quickbook-dev/tools/quickbook/test/unit/symbols_add_null.cpp 2011-04-06 20:15:38 EDT (Wed, 06 Apr 2011)
+++ (empty file)
@@ -1,79 +0,0 @@
-/*=============================================================================
- Copyright (c) 2004 Joao Abecasis
- http://spirit.sourceforge.net/
-
- Use, modification and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
-=============================================================================*/
-
-// This test requires NDEBUG to be undefined, because it depends on
-// BOOST_SPIRIT_ASSERT throwing an exception.
-#ifdef NDEBUG
-# undef NDEBUG
-#endif
-
-#include <stdexcept>
-
-#define BOOST_SPIRIT_ASSERT_EXCEPTION ::spirit_exception
-
-struct spirit_exception : std::exception
-{
- spirit_exception(char const * msg)
- : message(msg)
- {
- }
- ~spirit_exception() throw() {}
-
- char const* what() const throw() { return message; }
-
- char const * message;
-};
-
-#include <boost/spirit/include/classic_scanner.hpp>
-#include <boost/utility/addressof.hpp>
-#include "symbols.hpp"
-
-#include <boost/detail/lightweight_test.hpp>
-
-typedef char char_type;
-typedef char const * iterator;
-
-char_type data_[] = "whatever";
-
-iterator begin = data_;
-iterator end = data_
- + sizeof(data_)/sizeof(char_type); // Yes, this is an intentional bug ;)
-
-char_type data2_[] = "\0something";
-iterator begin2 = data2_;
-iterator end2 = data2_ + sizeof(data2_)/sizeof(char_type) - 1;
-
-int main()
-{
- typedef BOOST_SPIRIT_CLASSIC_NS::scanner<> scanner;
- typedef quickbook::tst<void *, char_type> symbols;
-
- symbols symbols_;
-
- try
- {
- // It is not ok to add strings containing the null character.
- symbols_.add(begin, end, (void*) boost::addressof(symbols_));
- BOOST_TEST(0);
- }
- catch (spirit_exception &/*e*/)
- {
- }
-
- try
- {
- // It is not ok to add strings containing the null character.
- symbols_.add(begin2, end2, (void*) boost::addressof(symbols_));
- BOOST_TEST(0);
- }
- catch (spirit_exception &/*e*/)
- {
- }
- return boost::report_errors();
-}
Modified: branches/quickbook-dev/tools/quickbook/test/unit/symbols_tests.cpp
==============================================================================
--- branches/quickbook-dev/tools/quickbook/test/unit/symbols_tests.cpp (original)
+++ branches/quickbook-dev/tools/quickbook/test/unit/symbols_tests.cpp 2011-04-06 20:15:38 EDT (Wed, 06 Apr 2011)
@@ -401,5 +401,6 @@
wide_free_functions_tests();
free_add_find_functions_tests();
duplicate_add_tests();
+
return boost::report_errors();
}
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk