Convert pmt_dict type into an immutable data structure.

This change allows us to safely pass dicts in messages.

diff --git a/gruel/src/include/gruel/pmt.h b/gruel/src/include/gruel/pmt.h
index 3188aad1d5db76176e453c2ccda0674ea19e8b28..c371b023b539b79ec257133efe28bb36b6e837c5 100644 (file)
--- 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 &not_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 e50e218380311560a0e91249ac9a9e5c017a2cb0..aa1688d24a8b69f18fda47fb9393e3cb5b43f8a8 100644 (file)
--- 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 &not_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);
 }
 
 ////////////////////////////////////////////////////////////////////////////
@@ -977,6 +938,24 @@ pmt_eqv(const pmt_t& x, const pmt_t& y)
   return false;
 }
 
+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)
 {
@@ -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 7581845f825df373a65951c7d8241e8b60e1f5f9..50683ffb525365ec10d6d39debe350be27d4c59b 100644 (file)
--- 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 59d9e14d30a7e257b07e6975a08c490e7cf41c34..3f6e2688bc9fb555e78817d44caf93090966ae51 100644 (file)
--- 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)));
 }