diff options
Diffstat (limited to 'gruel')
-rw-r--r-- | gruel/src/include/gruel/pmt.h | 21 | ||||
-rw-r--r-- | gruel/src/lib/pmt/pmt.cc | 176 | ||||
-rw-r--r-- | gruel/src/lib/pmt/pmt_int.h | 27 | ||||
-rw-r--r-- | gruel/src/lib/pmt/qa_pmt_prims.cc | 112 |
4 files changed, 169 insertions, 167 deletions
diff --git a/gruel/src/include/gruel/pmt.h b/gruel/src/include/gruel/pmt.h index 3188aad1d..c371b023b 100644 --- a/gruel/src/include/gruel/pmt.h +++ b/gruel/src/include/gruel/pmt.h @@ -1,6 +1,6 @@ /* -*- c++ -*- */ /* - * Copyright 2006,2009 Free Software Foundation, Inc. + * Copyright 2006,2009,2010 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -465,23 +465,30 @@ std::complex<double> *pmt_c64vector_writable_elements(pmt_t v, size_t &len); //< /* * ------------------------------------------------------------------------ * Dictionary (a.k.a associative array, hash, map) + * + * This is a functional data structure that is persistent. Updating a + * functional data structure does not destroy the existing version, but + * rather creates a new version that coexists with the old. * ------------------------------------------------------------------------ */ //! Return true if \p obj is a dictionary -bool pmt_is_dict(pmt_t obj); +bool pmt_is_dict(const pmt_t &obj); -//! make an empty dictionary +//! Make an empty dictionary pmt_t pmt_make_dict(); -//! dict[key] = value -void pmt_dict_set(pmt_t dict, pmt_t key, pmt_t value); +//! Return a new dictionary with \p key associated with \p value. +pmt_t pmt_dict_add(const pmt_t &dict, const pmt_t &key, const pmt_t &value); + +//! Return a new dictionary with \p key removed. +pmt_t pmt_dict_delete(const pmt_t &dict, const pmt_t &key); //! Return true if \p key exists in \p dict -bool pmt_dict_has_key(pmt_t dict, pmt_t key); +bool pmt_dict_has_key(const pmt_t &dict, const pmt_t &key); //! If \p key exists in \p dict, return associated value; otherwise return \p not_found. -pmt_t pmt_dict_ref(pmt_t dict, pmt_t key, pmt_t not_found); +pmt_t pmt_dict_ref(const pmt_t &dict, const pmt_t &key, const pmt_t ¬_found); //! Return list of (key . value) pairs pmt_t pmt_dict_items(pmt_t dict); diff --git a/gruel/src/lib/pmt/pmt.cc b/gruel/src/lib/pmt/pmt.cc index e50e21838..aa1688d24 100644 --- a/gruel/src/lib/pmt/pmt.cc +++ b/gruel/src/lib/pmt/pmt.cc @@ -1,6 +1,6 @@ /* -*- c++ -*- */ /* - * Copyright 2006,2009 Free Software Foundation, Inc. + * Copyright 2006,2009,2010 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -141,12 +141,6 @@ _uniform_vector(pmt_t x) return dynamic_cast<pmt_uniform_vector*>(x.get()); } -static pmt_dict * -_dict(pmt_t x) -{ - return dynamic_cast<pmt_dict*>(x.get()); -} - static pmt_any * _any(pmt_t x) { @@ -728,124 +722,91 @@ pmt_uniform_vector_writable_elements(pmt_t vector, size_t &len) // Dictionaries //////////////////////////////////////////////////////////////////////////// -pmt_dict::pmt_dict() - : d_alist(PMT_NIL) -{ -} - -void -pmt_dict::set(pmt_t key, pmt_t value) -{ - pmt_t p = pmt_assv(key, d_alist); // look for (key . value) pair - if (pmt_is_pair(p)){ // found existing pair... - pmt_set_cdr(p, value); // overrwrite cdr with new value - } - else { // not in the dict - d_alist = pmt_cons(pmt_cons(key, value), d_alist); // add new (key . value) pair - } -} - -pmt_t -pmt_dict::ref(pmt_t key, pmt_t not_found) const -{ - pmt_t p = pmt_assv(key, d_alist); // look for (key . value) pair - if (pmt_is_pair(p)) - return pmt_cdr(p); - else - return not_found; -} +/* + * This is an a-list implementation. + * + * When we need better performance for large dictionaries, consider implementing + * persistent Red-Black trees as described in "Purely Functional Data Structures", + * Chris Okasaki, 1998, section 3.3. + */ bool -pmt_dict::has_key(pmt_t key) const +pmt_is_dict(const pmt_t &obj) { - return pmt_is_pair(pmt_assv(key, d_alist)); + return pmt_is_null(obj) || pmt_is_pair(obj); } pmt_t -pmt_dict::items() const +pmt_make_dict() { - return d_alist; + return PMT_NIL; } pmt_t -pmt_dict::keys() const +pmt_dict_add(const pmt_t &dict, const pmt_t &key, const pmt_t &value) { - return pmt_map(pmt_car, d_alist); -} + if (pmt_is_null(dict)) + return pmt_acons(key, value, PMT_NIL); -pmt_t -pmt_dict::values() const -{ - return pmt_map(pmt_cdr, d_alist); -} + if (pmt_dict_has_key(dict, key)) + return pmt_acons(key, value, pmt_dict_delete(dict, key)); -bool -pmt_is_dict(pmt_t obj) -{ - return obj->is_dict(); + return pmt_acons(key, value, dict); } pmt_t -pmt_make_dict() +pmt_dict_delete(const pmt_t &dict, const pmt_t &key) { - return pmt_t(new pmt_dict()); + if (pmt_is_null(dict)) + return dict; + + if (pmt_eqv(pmt_caar(dict), key)) + return pmt_cdr(dict); + + return pmt_cons(pmt_car(dict), pmt_dict_delete(pmt_cdr(dict), key)); } -void -pmt_dict_set(pmt_t dict, pmt_t key, pmt_t value) +pmt_t +pmt_dict_ref(const pmt_t &dict, const pmt_t &key, const pmt_t ¬_found) { - pmt_dict* d = _dict(dict); - if (!d) - throw pmt_wrong_type("pmt_dict_set", dict); - - d->set(key, value); + pmt_t p = pmt_assv(key, dict); // look for (key . value) pair + if (pmt_is_pair(p)) + return pmt_cdr(p); + else + return not_found; } bool -pmt_dict_has_key(pmt_t dict, pmt_t key) +pmt_dict_has_key(const pmt_t &dict, const pmt_t &key) { - pmt_dict* d = _dict(dict); - if (!d) - throw pmt_wrong_type("pmt_dict_has_key", dict); - - return d->has_key(key); -} - -pmt_t -pmt_dict_ref(pmt_t dict, pmt_t key, pmt_t not_found) -{ - pmt_dict* d = _dict(dict); - if (!d) - throw pmt_wrong_type("pmt_dict_ref", dict); - - return d->ref(key, not_found); + return pmt_is_pair(pmt_assv(key, dict)); } pmt_t pmt_dict_items(pmt_t dict) { - if (!dict->is_dict()) - throw pmt_wrong_type("pmt_dict_items", dict); + if (!pmt_is_dict(dict)) + throw pmt_wrong_type("pmt_dict_values", dict); - return _dict(dict)->items(); + return dict; // equivalent to dict in the a-list case } pmt_t pmt_dict_keys(pmt_t dict) { - if (!dict->is_dict()) + if (!pmt_is_dict(dict)) throw pmt_wrong_type("pmt_dict_keys", dict); - return _dict(dict)->keys(); + return pmt_map(pmt_car, dict); } pmt_t pmt_dict_values(pmt_t dict) { - if (!dict->is_dict()) - throw pmt_wrong_type("pmt_dict_values", dict); + if (!pmt_is_dict(dict)) + throw pmt_wrong_type("pmt_dict_keys", dict); - return _dict(dict)->values(); + return pmt_map(pmt_cdr, dict); } //////////////////////////////////////////////////////////////////////////// @@ -978,6 +939,24 @@ pmt_eqv(const pmt_t& x, const pmt_t& y) } bool +pmt_eqv_raw(pmt_base *x, pmt_base *y) +{ + if (x == y) + return true; + + if (x->is_integer() && y->is_integer()) + return _integer(x)->value() == _integer(y)->value(); + + if (x->is_real() && y->is_real()) + return _real(x)->value() == _real(y)->value(); + + if (x->is_complex() && y->is_complex()) + return _complex(x)->value() == _complex(y)->value(); + + return false; +} + +bool pmt_equal(const pmt_t& x, const pmt_t& y) { if (pmt_eqv(x, y)) @@ -1082,6 +1061,35 @@ pmt_assq(pmt_t obj, pmt_t alist) return PMT_F; } +/* + * This avoids a bunch of shared_pointer reference count manipulation. + */ +pmt_t +pmt_assv_raw(pmt_base *obj, pmt_base *alist) +{ + while (alist->is_pair()){ + pmt_base *p = ((pmt_pair *)alist)->d_car.get(); + if (!p->is_pair()) // malformed alist + return PMT_F; + + if (pmt_eqv_raw(obj, ((pmt_pair *)p)->d_car.get())) + return ((pmt_pair *)alist)->d_car; + + alist = (((pmt_pair *)alist)->d_cdr).get(); + } + return PMT_F; +} + +#if 1 + +pmt_t +pmt_assv(pmt_t obj, pmt_t alist) +{ + return pmt_assv_raw(obj.get(), alist.get()); +} + +#else + pmt_t pmt_assv(pmt_t obj, pmt_t alist) { @@ -1098,6 +1106,9 @@ pmt_assv(pmt_t obj, pmt_t alist) return PMT_F; } +#endif + + pmt_t pmt_assoc(pmt_t obj, pmt_t alist) { @@ -1322,7 +1333,6 @@ pmt_dump_sizeof() printf("sizeof(pmt_null) = %3zd\n", sizeof(pmt_null)); printf("sizeof(pmt_pair) = %3zd\n", sizeof(pmt_pair)); printf("sizeof(pmt_vector) = %3zd\n", sizeof(pmt_vector)); - printf("sizeof(pmt_dict) = %3zd\n", sizeof(pmt_dict)); printf("sizeof(pmt_uniform_vector) = %3zd\n", sizeof(pmt_uniform_vector)); } diff --git a/gruel/src/lib/pmt/pmt_int.h b/gruel/src/lib/pmt/pmt_int.h index 7581845f8..50683ffb5 100644 --- a/gruel/src/lib/pmt/pmt_int.h +++ b/gruel/src/lib/pmt/pmt_int.h @@ -1,6 +1,6 @@ /* -*- c++ -*- */ /* - * Copyright 2006,2009 Free Software Foundation, Inc. + * Copyright 2006,2009,2010 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -107,9 +107,9 @@ public: class pmt_integer : public pmt_base { +public: long d_value; -public: pmt_integer(long value); //~pmt_integer(){} @@ -120,9 +120,9 @@ public: class pmt_real : public pmt_base { +public: double d_value; -public: pmt_real(double value); //~pmt_real(){} @@ -133,9 +133,9 @@ public: class pmt_complex : public pmt_base { +public: std::complex<double> d_value; -public: pmt_complex(std::complex<double> value); //~pmt_complex(){} @@ -155,10 +155,10 @@ public: class pmt_pair : public pmt_base { +public: pmt_t d_car; pmt_t d_cdr; -public: pmt_pair(const pmt_t& car, const pmt_t& cdr); //~pmt_pair(){}; @@ -203,23 +203,6 @@ public: void _set(size_t k, pmt_t v) { d_v[k] = v; } }; -class pmt_dict : public pmt_base -{ - pmt_t d_alist; // list of (key . value) pairs - -public: - pmt_dict(); - //~pmt_dict(); - - bool is_dict() const { return true; } - void set(pmt_t key, pmt_t value); - pmt_t ref(pmt_t key, pmt_t default_value) const; - bool has_key(pmt_t key) const; - pmt_t items() const; - pmt_t keys() const; - pmt_t values() const; -}; - class pmt_any : public pmt_base { boost::any d_any; diff --git a/gruel/src/lib/pmt/qa_pmt_prims.cc b/gruel/src/lib/pmt/qa_pmt_prims.cc index 59d9e14d3..f2414c72c 100644 --- a/gruel/src/lib/pmt/qa_pmt_prims.cc +++ b/gruel/src/lib/pmt/qa_pmt_prims.cc @@ -1,6 +1,6 @@ /* -*- c++ -*- */ /* - * Copyright 2006,2009 Free Software Foundation, Inc. + * Copyright 2006,2009,2010 Free Software Foundation, Inc. * * This file is part of GNU Radio * @@ -36,14 +36,14 @@ qa_pmt_prims::test_symbols() CPPUNIT_ASSERT(!pmt_is_symbol(PMT_F)); CPPUNIT_ASSERT_THROW(pmt_symbol_to_string(PMT_F), pmt_wrong_type); - pmt_t sym1 = pmt_string_to_symbol("test"); + pmt_t sym1 = mp("test"); CPPUNIT_ASSERT(pmt_is_symbol(sym1)); CPPUNIT_ASSERT_EQUAL(std::string("test"), pmt_symbol_to_string(sym1)); CPPUNIT_ASSERT(pmt_is_true(sym1)); CPPUNIT_ASSERT(!pmt_is_false(sym1)); - pmt_t sym2 = pmt_string_to_symbol("foo"); - pmt_t sym3 = pmt_string_to_symbol("test"); + pmt_t sym2 = mp("foo"); + pmt_t sym3 = mp("test"); CPPUNIT_ASSERT_EQUAL(sym1, sym3); CPPUNIT_ASSERT(sym1 != sym2); CPPUNIT_ASSERT(sym1 == sym3); @@ -56,7 +56,7 @@ qa_pmt_prims::test_symbols() for (int i = 0; i < N; i++){ char buf[100]; snprintf(buf, sizeof(buf), "test-%d", i); - v1[i] = pmt_string_to_symbol(buf); + v1[i] = mp(buf); } // confirm that they are all unique @@ -68,7 +68,7 @@ qa_pmt_prims::test_symbols() for (int i = 0; i < N; i++){ char buf[100]; snprintf(buf, sizeof(buf), "test-%d", i); - v2[i] = pmt_string_to_symbol(buf); + v2[i] = mp(buf); } // confirm that we get the same ones back @@ -79,7 +79,7 @@ qa_pmt_prims::test_symbols() void qa_pmt_prims::test_booleans() { - pmt_t sym = pmt_string_to_symbol("test"); + pmt_t sym = mp("test"); CPPUNIT_ASSERT(pmt_is_bool(PMT_T)); CPPUNIT_ASSERT(pmt_is_bool(PMT_F)); CPPUNIT_ASSERT(!pmt_is_bool(sym)); @@ -137,9 +137,9 @@ qa_pmt_prims::test_pairs() { CPPUNIT_ASSERT(pmt_is_null(PMT_NIL)); CPPUNIT_ASSERT(!pmt_is_pair(PMT_NIL)); - pmt_t s1 = pmt_string_to_symbol("s1"); - pmt_t s2 = pmt_string_to_symbol("s2"); - pmt_t s3 = pmt_string_to_symbol("s3"); + pmt_t s1 = mp("s1"); + pmt_t s2 = mp("s2"); + pmt_t s3 = mp("s3"); CPPUNIT_ASSERT_EQUAL((size_t)0, pmt_length(PMT_NIL)); @@ -174,9 +174,9 @@ qa_pmt_prims::test_vectors() static const size_t N = 3; pmt_t v1 = pmt_make_vector(N, PMT_NIL); CPPUNIT_ASSERT_EQUAL(N, pmt_length(v1)); - pmt_t s0 = pmt_string_to_symbol("s0"); - pmt_t s1 = pmt_string_to_symbol("s1"); - pmt_t s2 = pmt_string_to_symbol("s2"); + pmt_t s0 = mp("s0"); + pmt_t s1 = mp("s1"); + pmt_t s2 = mp("s2"); pmt_vector_set(v1, 0, s0); pmt_vector_set(v1, 1, s1); @@ -213,7 +213,7 @@ qa_pmt_prims::test_tuples() for (size_t i = 0; i < 10; i++){ std::ostringstream os; os << "s" << i; - s[i] = pmt_string_to_symbol(os.str()); + s[i] = mp(os.str()); pmt_vector_set(v, i, s[i]); } @@ -282,9 +282,9 @@ qa_pmt_prims::test_tuples() void qa_pmt_prims::test_equivalence() { - pmt_t s0 = pmt_string_to_symbol("s0"); - pmt_t s1 = pmt_string_to_symbol("s1"); - pmt_t s2 = pmt_string_to_symbol("s2"); + pmt_t s0 = mp("s0"); + pmt_t s1 = mp("s1"); + pmt_t s2 = mp("s2"); pmt_t list0 = pmt_cons(s0, pmt_cons(s1, pmt_cons(s2, PMT_NIL))); pmt_t list1 = pmt_cons(s0, pmt_cons(s1, pmt_cons(s2, PMT_NIL))); pmt_t i0 = pmt_from_long(42); @@ -324,13 +324,13 @@ qa_pmt_prims::test_equivalence() void qa_pmt_prims::test_misc() { - pmt_t k0 = pmt_string_to_symbol("k0"); - pmt_t k1 = pmt_string_to_symbol("k1"); - pmt_t k2 = pmt_string_to_symbol("k2"); - pmt_t k3 = pmt_string_to_symbol("k3"); - pmt_t v0 = pmt_string_to_symbol("v0"); - pmt_t v1 = pmt_string_to_symbol("v1"); - pmt_t v2 = pmt_string_to_symbol("v2"); + pmt_t k0 = mp("k0"); + pmt_t k1 = mp("k1"); + pmt_t k2 = mp("k2"); + pmt_t k3 = mp("k3"); + pmt_t v0 = mp("v0"); + pmt_t v1 = mp("v1"); + pmt_t v2 = mp("v2"); pmt_t p0 = pmt_cons(k0, v0); pmt_t p1 = pmt_cons(k1, v1); pmt_t p2 = pmt_cons(k2, v2); @@ -351,29 +351,31 @@ qa_pmt_prims::test_dict() pmt_t dict = pmt_make_dict(); CPPUNIT_ASSERT(pmt_is_dict(dict)); - pmt_t k0 = pmt_string_to_symbol("k0"); - pmt_t k1 = pmt_string_to_symbol("k1"); - pmt_t k2 = pmt_string_to_symbol("k2"); - pmt_t k3 = pmt_string_to_symbol("k3"); - pmt_t v0 = pmt_string_to_symbol("v0"); - pmt_t v1 = pmt_string_to_symbol("v1"); - pmt_t v2 = pmt_string_to_symbol("v2"); - pmt_t v3 = pmt_string_to_symbol("v3"); + pmt_t k0 = mp("k0"); + pmt_t k1 = mp("k1"); + pmt_t k2 = mp("k2"); + pmt_t k3 = mp("k3"); + pmt_t v0 = mp("v0"); + pmt_t v1 = mp("v1"); + pmt_t v2 = mp("v2"); + pmt_t v3 = mp("v3"); pmt_t not_found = pmt_cons(PMT_NIL, PMT_NIL); CPPUNIT_ASSERT(!pmt_dict_has_key(dict, k0)); - pmt_dict_set(dict, k0, v0); + dict = pmt_dict_add(dict, k0, v0); CPPUNIT_ASSERT(pmt_dict_has_key(dict, k0)); CPPUNIT_ASSERT(pmt_eqv(pmt_dict_ref(dict, k0, not_found), v0)); CPPUNIT_ASSERT(pmt_eqv(pmt_dict_ref(dict, k1, not_found), not_found)); - pmt_dict_set(dict, k1, v1); - pmt_dict_set(dict, k2, v2); + dict = pmt_dict_add(dict, k1, v1); + dict = pmt_dict_add(dict, k2, v2); CPPUNIT_ASSERT(pmt_eqv(pmt_dict_ref(dict, k1, not_found), v1)); - pmt_dict_set(dict, k1, v3); + dict = pmt_dict_add(dict, k1, v3); CPPUNIT_ASSERT(pmt_eqv(pmt_dict_ref(dict, k1, not_found), v3)); - pmt_t keys = pmt_cons(k2, pmt_cons(k1, pmt_cons(k0, PMT_NIL))); - pmt_t vals = pmt_cons(v2, pmt_cons(v3, pmt_cons(v0, PMT_NIL))); + pmt_t keys = pmt_list3(k1, k2, k0); + pmt_t vals = pmt_list3(v3, v2, v0); + //std::cout << "pmt_dict_keys: " << pmt_dict_keys(dict) << std::endl; + //std::cout << "pmt_dict_values: " << pmt_dict_values(dict) << std::endl; CPPUNIT_ASSERT(pmt_equal(keys, pmt_dict_keys(dict))); CPPUNIT_ASSERT(pmt_equal(vals, pmt_dict_values(dict))); } @@ -381,10 +383,10 @@ qa_pmt_prims::test_dict() void qa_pmt_prims::test_io() { - pmt_t k0 = pmt_string_to_symbol("k0"); - pmt_t k1 = pmt_string_to_symbol("k1"); - pmt_t k2 = pmt_string_to_symbol("k2"); - pmt_t k3 = pmt_string_to_symbol("k3"); + pmt_t k0 = mp("k0"); + pmt_t k1 = mp("k1"); + pmt_t k2 = mp("k2"); + pmt_t k3 = mp("k3"); CPPUNIT_ASSERT_EQUAL(std::string("k0"), pmt_write_string(k0)); } @@ -392,10 +394,10 @@ qa_pmt_prims::test_io() void qa_pmt_prims::test_lists() { - pmt_t s0 = pmt_intern("s0"); - pmt_t s1 = pmt_intern("s1"); - pmt_t s2 = pmt_intern("s2"); - pmt_t s3 = pmt_intern("s3"); + pmt_t s0 = mp("s0"); + pmt_t s1 = mp("s1"); + pmt_t s2 = mp("s2"); + pmt_t s3 = mp("s3"); pmt_t l1 = pmt_list4(s0, s1, s2, s3); pmt_t l2 = pmt_list3(s0, s1, s2); @@ -466,7 +468,7 @@ qa_pmt_msg_accepter_nop::~qa_pmt_msg_accepter_nop(){} void qa_pmt_prims::test_msg_accepter() { - pmt_t sym = pmt_intern("my-symbol"); + pmt_t sym = mp("my-symbol"); boost::any a0; a0 = std::string("Hello!"); @@ -493,16 +495,16 @@ void qa_pmt_prims::test_serialize() { std::stringbuf sb; // fake channel - pmt_t a = pmt_intern("a"); - pmt_t b = pmt_intern("b"); - pmt_t c = pmt_intern("c"); + pmt_t a = mp("a"); + pmt_t b = mp("b"); + pmt_t c = mp("c"); sb.str(""); // reset channel to empty // write stuff to channel pmt_serialize(PMT_NIL, sb); - pmt_serialize(pmt_intern("foobarvia"), sb); + pmt_serialize(mp("foobarvia"), sb); pmt_serialize(pmt_from_long(123456789), sb); pmt_serialize(pmt_from_long(-123456789), sb); pmt_serialize(pmt_cons(PMT_NIL, PMT_NIL), sb); @@ -517,7 +519,7 @@ qa_pmt_prims::test_serialize() // read it back CPPUNIT_ASSERT(pmt_equal(pmt_deserialize(sb), PMT_NIL)); - CPPUNIT_ASSERT(pmt_equal(pmt_deserialize(sb), pmt_intern("foobarvia"))); + CPPUNIT_ASSERT(pmt_equal(pmt_deserialize(sb), mp("foobarvia"))); CPPUNIT_ASSERT(pmt_equal(pmt_deserialize(sb), pmt_from_long(123456789))); CPPUNIT_ASSERT(pmt_equal(pmt_deserialize(sb), pmt_from_long(-123456789))); CPPUNIT_ASSERT(pmt_equal(pmt_deserialize(sb), pmt_cons(PMT_NIL, PMT_NIL))); @@ -540,9 +542,9 @@ qa_pmt_prims::test_serialize() void qa_pmt_prims::test_sets() { - pmt_t s1 = pmt_intern("s1"); - pmt_t s2 = pmt_intern("s2"); - pmt_t s3 = pmt_intern("s3"); + pmt_t s1 = mp("s1"); + pmt_t s2 = mp("s2"); + pmt_t s3 = mp("s3"); pmt_t l1 = pmt_list1(s1); pmt_t l2 = pmt_list2(s2,s3); |