[Commit-gnuradio] r4300 - gnuradio/branches/developers/eb/mb/mblock/src/lib

[eb]

Author: eb
Date: 2007-01-27 21:58:38 -0700 (Sat, 27 Jan 2007)
New Revision: 4300

Added:
   gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.cc
   gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.h
Modified:
   gnuradio/branches/developers/eb/mb/mblock/src/lib/Makefile.am
   gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_common.h
   gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_message.h
   gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.cc
   gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.h
Log:
work-in-progress: added mb_msg_queue and qa code


Modified: gnuradio/branches/developers/eb/mb/mblock/src/lib/Makefile.am
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/Makefile.am       
2007-01-28 02:27:29 UTC (rev 4299)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/Makefile.am       
2007-01-28 04:58:38 UTC (rev 4300)
@@ -38,6 +38,7 @@
        mb_mblock_impl.cc               \
        mb_message.cc                   \
        mb_msg_accepter.cc              \
+       mb_msg_queue.cc                 \
        mb_port.cc                      \
        mb_port_simple.cc               \
        mb_protocol_class.cc            \
@@ -60,6 +61,7 @@
        mb_mblock.h                     \
        mb_message.h                    \
        mb_msg_accepter.h               \
+       mb_msg_queue.cc                 \
        mb_port.h                       \
        mb_port_simple.h                \
        mb_protocol_class.h             \

Modified: gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_common.h
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_common.h       
2007-01-28 02:27:29 UTC (rev 4299)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_common.h       
2007-01-28 04:58:38 UTC (rev 4300)
@@ -28,10 +28,42 @@
 #include <boost/enable_shared_from_this.hpp>
 
 
+/*
+ * The priority type and valid range
+ */
 typedef unsigned int   mb_pri_t;
-static const mb_pri_t  MB_PRI_DEFAULT = 5;
+static const mb_pri_t  MB_PRI_BEST    = 0;
+static const mb_pri_t  MB_PRI_DEFAULT = 4; 
+static const mb_pri_t   MB_PRI_WORST   = 7;
+static const mb_pri_t  MB_NPRI = MB_PRI_WORST + 1;       // number of valid 
priorities 
 
+/*!
+ * \brief return true iff priority a is better than priority b
+ */
+inline static bool
+mb_pri_better(mb_pri_t a, mb_pri_t b)
+{
+  return a < b;
+}
 
+/*!
+ * \brief return true iff priority a is worse than priority b
+ */
+inline static bool
+mb_pri_worse(mb_pri_t a, mb_pri_t b)
+{
+  return a > b;
+}
+
+/*!
+ * \brief ensure that pri is valid
+ */
+inline static mb_pri_t
+mb_pri_clamp(mb_pri_t p)
+{
+  return p < MB_NPRI ? p : MB_NPRI - 1;
+}
+
 class mb_runtime;
 typedef boost::shared_ptr<mb_runtime> mb_runtime_sptr;
 
@@ -53,4 +85,10 @@
 class mb_msg_accepter;
 typedef boost::shared_ptr<mb_msg_accepter> mb_msg_accepter_sptr;
 
+class mb_message;
+typedef boost::shared_ptr<mb_message> mb_message_sptr;
+
+class mb_msg_queue;
+typedef boost::shared_ptr<mb_msg_queue> mb_msg_queue_sptr;
+
 #endif /* INCLUDED_MB_COMMON_H */

Modified: gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_message.h
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_message.h      
2007-01-28 02:27:29 UTC (rev 4299)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_message.h      
2007-01-28 04:58:38 UTC (rev 4300)
@@ -48,6 +48,8 @@
   mb_pri_t       d_priority;
   // foo         d_rcvd_port_id;
 
+  friend class mb_msg_queue;
+
   friend mb_message_sptr
   mb_make_message(pmt_t signal, pmt_t data, pmt_t metadata, mb_pri_t priority);
 

Added: gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.cc
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.cc           
                (rev 0)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.cc   
2007-01-28 04:58:38 UTC (rev 4300)
@@ -0,0 +1,80 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2007 Free Software Foundation, Inc.
+ * 
+ * This file is part of GNU Radio
+ * 
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+#include <mb_msg_queue.h>
+#include <mb_message.h>
+
+// FIXME turn this into a template so we can use it for the runq of mblocks too
+
+mb_msg_queue::mb_msg_queue()
+{
+}
+
+mb_msg_queue::~mb_msg_queue()
+{
+}
+
+void
+mb_msg_queue::insert(mb_message_sptr msg)
+{
+  // omni_mutex_lock   l(d_mutex);             FIXME
+  
+  mb_pri_t q = mb_pri_clamp(msg->priority());
+
+  if (d_queue[q].empty_p()){
+    d_queue[q].tail = d_queue[q].head = msg;
+    msg->d_next.reset();       //msg->d_next = 0;
+  }
+  else {
+    d_queue[q].tail->d_next = msg;
+    d_queue[q].tail = msg;
+    msg->d_next.reset();       // msg->d_next = 0;
+  }
+  // FIXME set bit in bitmap
+}
+
+mb_message_sptr
+mb_msg_queue::get_highest_pri_msg()
+{
+  // omni_mutex_lock   l(d_mutex);             FIXME
+
+  // FIXME use bitmap and ffz to find best queue in O(1)
+
+  for (mb_pri_t q = 0; q <= MB_PRI_WORST; q++){
+
+    if (!d_queue[q].empty_p()){
+      mb_message_sptr msg = d_queue[q].head;
+      d_queue[q].head = msg->d_next;
+      if (d_queue[q].head == 0){
+       d_queue[q].tail.reset();        // d_queue[q].tail = 0;
+       // FIXME clear bit in bitmap
+      }
+
+      msg->d_next.reset();             // msg->d_next = 0;
+      return msg;
+    }
+  }
+
+  return mb_message_sptr();    // equivalent of a zero pointer
+}

Added: gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.h
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.h            
                (rev 0)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/mb_msg_queue.h    
2007-01-28 04:58:38 UTC (rev 4300)
@@ -0,0 +1,59 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2007 Free Software Foundation, Inc.
+ * 
+ * This file is part of GNU Radio
+ * 
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#ifndef INCLUDED_MB_MSG_QUEUE_H
+#define INCLUDED_MB_MSG_QUEUE_H
+
+#include <mb_common.h>
+//#include <omnithread.h>      FIXME
+
+/*!
+ * \brief priority queue for mblock messages
+ */
+class mb_msg_queue : boost::noncopyable
+{
+  // When empty both head and tail are zero.
+  struct subq {
+    mb_message_sptr    head;
+    mb_message_sptr    tail;
+
+    bool empty_p() const { return head == 0; }
+  };
+
+  // omni_mutex        d_mutex;        FIXME
+
+  // FIXME add bitmap to indicate which queues are non-empty.
+  subq         d_queue[MB_NPRI];
+
+public:
+  mb_msg_queue();
+  ~mb_msg_queue();
+
+  //! Insert \p msg into priority queue.
+  void insert(mb_message_sptr msg);
+
+  /*
+   * \brief Delete highest pri message from the queue and return it.
+   * Returns equivalent of zero pointer if queue is empty.
+   */
+  mb_message_sptr get_highest_pri_msg();
+};
+
+#endif /* INCLUDED_MB_MSG_QUEUE_H */

Modified: gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.cc
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.cc        
2007-01-28 02:27:29 UTC (rev 4299)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.cc        
2007-01-28 04:58:38 UTC (rev 4300)
@@ -26,6 +26,8 @@
 #include <mb_runtime.h>
 #include <mb_protocol_class.h>
 #include <mb_exception.h>
+#include <mb_msg_queue.h>
+#include <mb_message.h>
 #include <stdio.h>
 
 static pmt_t s_cs = pmt_intern("cs");
@@ -329,3 +331,58 @@
   mb_runtime_sptr      rt = mb_make_runtime();
   mb_mblock_sptr       mb0 = mb_mblock_sptr(new tc_0());
 }
+
+////////////////////////////////////////////////////////////////
+
+void
+qa_mblock_prims::test_msg_queue()
+{
+  mb_msg_queue q;
+
+  // check initial state
+  CPPUNIT_ASSERT(q.get_highest_pri_msg() == 0);
+
+  CPPUNIT_ASSERT(MB_NPRI >= 5);        // sanity check for this test
+
+  // insert three messages at the same pri and ensure that they come out in 
order
+  //                       signal       data          metadata     pri
+  q.insert(mb_make_message(PMT_NIL, pmt_from_long(0), PMT_NIL, MB_PRI_BEST + 
2));
+  q.insert(mb_make_message(PMT_NIL, pmt_from_long(1), PMT_NIL, MB_PRI_BEST + 
2));
+  q.insert(mb_make_message(PMT_NIL, pmt_from_long(2), PMT_NIL, MB_PRI_BEST + 
2));
+  
+  CPPUNIT_ASSERT_EQUAL(0L, pmt_to_long(q.get_highest_pri_msg()->data()));
+  CPPUNIT_ASSERT_EQUAL(1L, pmt_to_long(q.get_highest_pri_msg()->data()));
+  CPPUNIT_ASSERT_EQUAL(2L, pmt_to_long(q.get_highest_pri_msg()->data()));
+
+  CPPUNIT_ASSERT(q.get_highest_pri_msg() == 0);
+
+
+  // insert messages of different priorities in pseudo-random order
+  //                       signal   data     metadata     pri
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 3));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 2));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 4));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 0));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 1));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 3));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 2));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 4));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 0));
+  q.insert(mb_make_message(PMT_NIL, PMT_NIL, PMT_NIL, MB_PRI_BEST + 1));
+
+  // confirm that they come out in order
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 0, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 0, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 1, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 1, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 2, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 2, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 3, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 3, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 4, q.get_highest_pri_msg()->priority());
+  CPPUNIT_ASSERT_EQUAL(MB_PRI_BEST + 4, q.get_highest_pri_msg()->priority());
+  
+  // check final state
+  CPPUNIT_ASSERT(q.get_highest_pri_msg() == 0);
+}
+

Modified: gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.h
===================================================================
--- gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.h 
2007-01-28 02:27:29 UTC (rev 4299)
+++ gnuradio/branches/developers/eb/mb/mblock/src/lib/qa_mblock_prims.h 
2007-01-28 04:58:38 UTC (rev 4300)
@@ -31,12 +31,14 @@
   CPPUNIT_TEST(test_define_ports);
   CPPUNIT_TEST(test_define_components);
   CPPUNIT_TEST(test_connect);
+  CPPUNIT_TEST(test_msg_queue);
   CPPUNIT_TEST_SUITE_END();
 
  private:
   void test_define_ports();
   void test_define_components();
   void test_connect();
+  void test_msg_queue();
 };
 
 #endif /* INCLUDED_QA_MBLOCK_PRIMS_H */