From f80de9f4107a01ab3a917eddf15eaaf4a1c998a2 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Tue, 18 Sep 2012 10:28:51 +0200 Subject: Add building blocks for multi-index containers --- tests/container/makefile | 17 ++ tests/container/multi-index/driver.cxx | 292 +++++++++++++++++++++++++++++++++ tests/container/multi-index/makefile | 69 ++++++++ tests/makefile | 2 +- 4 files changed, 379 insertions(+), 1 deletion(-) create mode 100644 tests/container/makefile create mode 100644 tests/container/multi-index/driver.cxx create mode 100644 tests/container/multi-index/makefile (limited to 'tests') diff --git a/tests/container/makefile b/tests/container/makefile new file mode 100644 index 0000000..5f537db --- /dev/null +++ b/tests/container/makefile @@ -0,0 +1,17 @@ +# file : tests/container/makefile +# copyright : Copyright (c) 2009-2012 Code Synthesis Tools CC +# license : MIT; see accompanying LICENSE file + +include $(dir $(lastword $(MAKEFILE_LIST)))../../build/bootstrap.make + +tests := multi-index + +default := $(out_base)/ +test := $(out_base)/.test +clean := $(out_base)/.clean + +$(default): $(addprefix $(out_base)/,$(addsuffix /,$(tests))) +$(test): $(addprefix $(out_base)/,$(addsuffix /.test,$(tests))) +$(clean): $(addprefix $(out_base)/,$(addsuffix /.clean,$(tests))) + +$(foreach t,$(tests),$(call import,$(src_base)/$t/makefile)) diff --git a/tests/container/multi-index/driver.cxx b/tests/container/multi-index/driver.cxx new file mode 100644 index 0000000..9ddf73d --- /dev/null +++ b/tests/container/multi-index/driver.cxx @@ -0,0 +1,292 @@ +// file : tests/container/multi-index/driver.cxx +// copyright : Copyright (c) 2009-2012 Code Synthesis Tools CC +// license : MIT; see accompanying LICENSE file + +#include +#include +#include +#include +#include + +#include + +using namespace std; +using namespace cutl::container; + +struct person +{ + person (const string& e, const string& f, const string& l, unsigned short a) + : email (e), first (f), last (l), age (a) {} + + const string email; + const string first; + const string last; + unsigned short age; +}; + +struct person_email_set +{ + typedef map, person> email_map; + typedef map_const_iterator const_iterator; + + pair + insert (const person& v) + { + pair r ( + email_map_.insert (email_map::value_type (v.email, v))); + + const_iterator i (r.first); + + if (r.second) + r.first->first.assign (i->email); + + return make_pair (i, r.second); + } + + const_iterator + find (const string& email) const + { + return email_map_.find (email); + } + + const_iterator begin () const {return email_map_.begin ();} + const_iterator end () const {return email_map_.end ();} + +private: + email_map email_map_; +}; + +struct person_name_set +{ + typedef key name_key; + typedef map name_map; + typedef map_const_iterator const_iterator; + + pair + insert (const person& v) + { + pair r ( + name_map_.insert ( + name_map::value_type (name_key (v.first, v.last), v))); + + const_iterator i (r.first); + + if (r.second) + r.first->first.assign (i->first, i->last); + + return make_pair (i, r.second); + } + + const_iterator + find (const string& first, const string& last) const + { + return name_map_.find (name_key (first, last)); + } + + const_iterator begin () const {return name_map_.begin ();} + const_iterator end () const {return name_map_.end ();} + +private: + name_map name_map_; +}; + +struct person_email_name_set +{ + typedef key name_key; + typedef map name_map; + typedef map_iterator iterator; + typedef map_const_iterator const_iterator; + + typedef map, iterator> email_map; + + pair + insert (const person& v) + { + // First check that we don't have any collisions in the secondary + // indexes. + // + { + email_map::iterator i (email_map_.find (v.email)); + + if (i != email_map_.end ()) + return make_pair (i->second, false); + } + + pair r ( + name_map_.insert ( + name_map::value_type (name_key (v.first, v.last), v))); + + iterator i (r.first); + + if (r.second) + { + r.first->first.assign (i->first, i->last); + email_map_.insert (email_map::value_type (i->email, i)); + } + + return make_pair (i, r.second); + } + + iterator + find (const string& first, const string& last) + { + return name_map_.find (name_key (first, last)); + } + + const_iterator + find (const string& first, const string& last) const + { + return name_map_.find (name_key (first, last)); + } + + iterator + find (const string& email) + { + email_map::iterator i (email_map_.find (email)); + return i != email_map_.end () ? i->second : end (); + } + + const_iterator + find (const string& email) const + { + email_map::const_iterator i (email_map_.find (email)); + return i != email_map_.end () ? i->second : end (); + } + + void + erase (iterator i ) + { + email_map_.erase (i->email); + name_map_.erase (i); + } + + iterator begin () {return name_map_.begin ();} + const_iterator begin () const {return name_map_.begin ();} + + iterator end () {return name_map_.end ();} + const_iterator end () const {return name_map_.end ();} + +private: + name_map name_map_; + email_map email_map_; +}; + +struct person_list_email_set +{ + typedef list person_list; + typedef person_list::iterator iterator; + typedef person_list::const_iterator const_iterator; + + typedef map, iterator> email_map; + + pair + insert (const person& v) + { + // First check that we don't have any collisions in the secondary + // indexes. + // + { + email_map::iterator i (email_map_.find (v.email)); + + if (i != email_map_.end ()) + return make_pair (i->second, false); + } + + iterator i (person_list_.insert (end (), v)); + email_map_.insert (email_map::value_type (i->email, i)); + return make_pair (i, true); + } + + iterator + find (const string& email) + { + email_map::iterator i (email_map_.find (email)); + return i != email_map_.end () ? i->second : end (); + } + + const_iterator + find (const string& email) const + { + email_map::const_iterator i (email_map_.find (email)); + return i != email_map_.end () ? i->second : end (); + } + + iterator begin () {return person_list_.begin ();} + const_iterator begin () const {return person_list_.begin ();} + + iterator end () {return person_list_.end ();} + const_iterator end () const {return person_list_.end ();} + +private: + person_list person_list_; + email_map email_map_; +}; + +int +main () +{ + { + person_email_set s; + + assert (s.insert (person ("john@doe.com", "John", "Doe", 20)).second); + assert (s.insert (person ("jane@doe.com", "Jane", "Doe", 21)).second); + assert (!s.insert (person ("john@doe.com", "Johnny", "Doe", 22)).second); + + assert (s.find ("john@doe.com") != s.end ()); + assert (s.find ("jane@doe.com") != s.end ()); + assert (s.find ("john@doe.org") == s.end ()); + } + + { + person_name_set s; + + assert (s.insert (person ("john@doe.com", "John", "Doe", 20)).second); + assert (s.insert (person ("jane@doe.com", "Jane", "Doe", 21)).second); + assert (!s.insert (person ("john@doe.org", "John", "Doe", 22)).second); + + assert (s.find ("John", "Doe") != s.end ()); + assert (s.find ("Jane", "Doe") != s.end ()); + assert (s.find ("Johnny", "Doe") == s.end ()); + } + + { + person_email_name_set s; + person_email_name_set const& cs (s); + + assert (s.insert (person ("john@doe.com", "John", "Doe", 20)).second); + assert (s.insert (person ("jane@doe.com", "Jane", "Doe", 21)).second); + assert (!s.insert (person ("john@doe.org", "John", "Doe", 22)).second); + assert (!s.insert (person ("john@doe.com", "Johnny", "Doe", 23)).second); + + assert (s.find ("John", "Doe") != s.end ()); + assert (cs.find ("Jane", "Doe") != cs.end ()); + assert (s.find ("john@doe.com") != s.end ()); + assert (cs.find ("jane@doe.com") != s.end ()); + assert (s.find ("Johnny", "Doe") == s.end ()); + assert (cs.find ("john@doe.org") == s.end ()); + + person_email_name_set::iterator i (s.find ("John", "Doe")); + i->age++; + + s.erase (i); + assert (s.find ("John", "Doe") == s.end ()); + assert (s.find ("john@doe.com") == s.end ()); + } + + { + person_list_email_set s; + + assert (s.insert (person ("john@doe.com", "John", "Doe", 20)).second); + assert (s.insert (person ("jane@doe.com", "Jane", "Doe", 21)).second); + assert (!s.insert (person ("john@doe.com", "Johnny", "Doe", 22)).second); + + assert (s.find ("john@doe.com") != s.end ()); + assert (s.find ("jane@doe.com") != s.end ()); + assert (s.find ("jane@doe.org") == s.end ()); + + person_list_email_set::iterator i (s.begin ()); + assert (i != s.end () && i->email == "john@doe.com"); + assert (++i != s.end () && i->email == "jane@doe.com"); + assert (++i == s.end ()); + } +} diff --git a/tests/container/multi-index/makefile b/tests/container/multi-index/makefile new file mode 100644 index 0000000..fd70e3f --- /dev/null +++ b/tests/container/multi-index/makefile @@ -0,0 +1,69 @@ +# file : tests/container/multi-index/makefile +# copyright : Copyright (c) 2009-2012 Code Synthesis Tools CC +# license : MIT; see accompanying LICENSE file + +include $(dir $(lastword $(MAKEFILE_LIST)))../../../build/bootstrap.make + +cxx_tun := driver.cxx + +# +# +cxx_obj := $(addprefix $(out_base)/,$(cxx_tun:.cxx=.o)) +cxx_od := $(cxx_obj:.o=.o.d) + +cutl.l := $(out_root)/cutl/cutl.l +cutl.l.cpp-options := $(out_root)/cutl/cutl.l.cpp-options + +driver := $(out_base)/driver +test := $(out_base)/.test +clean := $(out_base)/.clean + +# Build. +# +$(driver): $(cxx_obj) $(cutl.l) +$(cxx_obj) $(cxx_od): $(cutl.l.cpp-options) + + +$(call include-dep,$(cxx_od)) + + +# Alias for default target. +# +$(out_base)/: $(driver) + + +# Test. +# +$(test): $(driver) + $(call message,test $<,$<) + + +# Clean. +# +$(clean): \ + $(driver).o.clean \ + $(addsuffix .cxx.clean,$(cxx_obj)) \ + $(addsuffix .cxx.clean,$(cxx_od)) + + +# Generated .gitignore. +# +ifeq ($(out_base),$(src_base)) +$(driver): | $(out_base)/.gitignore + +$(out_base)/.gitignore: files := driver +$(clean): $(out_base)/.gitignore.clean + +$(call include,$(bld_root)/git/gitignore.make) +endif + + +# How to. +# +$(call include,$(bld_root)/cxx/o-e.make) +$(call include,$(bld_root)/cxx/cxx-o.make) +$(call include,$(bld_root)/cxx/cxx-d.make) + +# Dependencies. +# +$(call import,$(src_root)/cutl/makefile) diff --git a/tests/makefile b/tests/makefile index b09b947..8d16183 100644 --- a/tests/makefile +++ b/tests/makefile @@ -4,7 +4,7 @@ include $(dir $(lastword $(MAKEFILE_LIST)))../build/bootstrap.make -tests := compiler fs re shared-ptr +tests := compiler container fs re shared-ptr default := $(out_base)/ test := $(out_base)/.test -- cgit v1.1