diff options
| -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 | 30 |
4 files changed, 128 insertions, 126 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..3f6e2688b 100644 --- a/gruel/src/lib/pmt/qa_pmt_prims.cc +++ b/gruel/src/lib/pmt/qa_pmt_prims.cc @@ -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))); } |