updates for DA_strategies

9 files changed, 265 insertions, 78 deletions

diff --git a/ACE/ace/DA_Strategy_Base.h b/ACE/ace/DA_Strategy_Base.h
index f63e3757c39..02ac40d9ef7 100644
--- a/ACE/ace/DA_Strategy_Base.h
+++ b/ACE/ace/DA_Strategy_Base.h
@@ -29,11 +29,13 @@
 # pragma once
 #endif /* ACE_LACKS_PRAGMA_ONCE */
 
+class ACE_Event_Handler;
+
 template <typename AnnotationId>
 class DA_Strategy_Base {
 
   //The annotations consist of an identifier and a resource cost value
-/*typedef ACE_Hash_Map_Entry<ACE_Event_Handler *, int> HASH_EH_ENTRY;
+typedef ACE_Hash_Map_Entry<ACE_Event_Handler *, int> HASH_EH_ENTRY;
 
 
 typedef ACE_Hash_Map_Manager_Ex<AnnotationId,
@@ -61,35 +63,23 @@ typedef ACE_Hash_Map_Reverse_Iterator_Ex<AnnotationId,
                                          ACE_Thread_Mutex> HASH_ANNOTATIONS_REVERSE_ITER;
 
 typedef HASH_ANNOTATIONS_MAP Annotations_Table;
-*/
+
 public:
     DA_Strategy_Base(int maxThreads);
     virtual ~DA_Strategy_Base();
-
-    /*  TBD - not sure of the implications of changing the number of threads available.
-    virtual int get_max_available_threads();
-    virtual void set_max_available_threads(int newMax);
-    */
-  
+ 
     virtual bool is_deadlock_potential(AnnotationId handle)=0;
     virtual void grant(AnnotationId handle)=0;
     virtual void release(AnnotationId upcall_handle)=0;
-    int getMaxThreads() { return num_avail_threads_};
+    int get_max_threads() { return num_avail_threads_};
+    HASH_ANNOTATIONS_CONST_ITER get_annotations_iter();
     virtual int get_annotation (AnnotationId handle);
     virtual int add_annotation (AnnotationId handle, int annotation);
     virtual int remove_annotation (AnnotationId handle);
-    virtual int set_annotations_table (const ACE_Hash_Map_Reverse_Iterator_Ex<AnnotationId,
-                                         int,
-                                         ACE_Hash<AnnotationId>,
-                                         ACE_Equal_To<AnnotationId>,
-                                         ACE_Thread_Mutex> & table);
+    virtual int set_annotations_table (const HASH_ANNOTATIONS_REVERSE_ITER& table);
 
 private:
-  ACE_Hash_Map_Manager_Ex<AnnotationId,
-                          int,
-                          ACE_Hash<AnnotationId>,
-                          ACE_Equal_To<AnnotationId>,
-                          ACE_Thread_Mutex> annotations_repo_;
+  HASH_ANNOTATIONS_MAP annotations_repo_;
   ACE_RW_Thread_Mutex lock_;
   ACE_Atomic_Op<ACE_Thread_Mutex, long> num_avail_threads_;
 
diff --git a/ACE/ace/DA_Strategy_Base.inl b/ACE/ace/DA_Strategy_Base.inl
index 51d2e9cf642..e726ef2e011 100644
--- a/ACE/ace/DA_Strategy_Base.inl
+++ b/ACE/ace/DA_Strategy_Base.inl
@@ -10,24 +10,8 @@ ACE_INLINE
 DA_Strategy_Base<AnnotationId>::~DA_Strategy_Base()
 {
 }
-/*
-template <typename AnnotationId>
-ACE_INLINE
-int 
-DA_Strategy_Base<AnnotationId>::get_max_available_threads()
-{
-  return this->num_avail_threads_;
-}
 
 template <typename AnnotationId>
-ACE_INLINE void
-DA_Strategy_Base<AnnotationId>::set_max_available_threads (int num_threads)
-{
-  this->num_avail_threads_ = num_threads;
-  printf("num_avail_threads = %d\n", num_threads);
-}
-*/
-template <typename AnnotationId>
 ACE_INLINE int 
 DA_Strategy_Base<AnnotationId>::get_annotation (AnnotationId id)
 {
@@ -40,17 +24,9 @@ DA_Strategy_Base<AnnotationId>::get_annotation (AnnotationId id)
 template <typename AnnotationId>
 ACE_INLINE int 
 DA_Strategy_Base<AnnotationId>::set_annotations_table (
-        const ACE_Hash_Map_Reverse_Iterator_Ex<AnnotationId,
-                                               int,
-                                               ACE_Hash<AnnotationId>,
-                                               ACE_Equal_To<AnnotationId>,
-                                               ACE_Thread_Mutex>& table)
+        const HASH_ANNOTATIONS_REVERSE_ITER& table)
 {
-  ACE_Hash_Map_Const_Iterator_Ex<AnnotationId,
-                                 int,
-                                 ACE_Hash<AnnotationId>,
-                                 ACE_Equal_To<AnnotationId>,
-                                 ACE_Thread_Mutex>  iter(table);
+  HASH_ANNOTATIONS_CONST_ITER iter(table);
   int rc=0;
   
   for (;!(iter.done()); iter++)
@@ -80,6 +56,17 @@ DA_Strategy_Base<AnnotationId>::add_annotation (AnnotationId id, int annotation)
 }
 
 template <typename AnnotationId>
+ACE_INLINE ACE_Hash_Map_Const_Iterator_Ex<AnnotationId,
+                                       int,
+                                       ACE_Hash<AnnotationId>,
+                                       ACE_Equal_To<AnnotationId>,
+                                       ACE_Thread_Mutex>
+DA_Strategy_Base<AnnotationId>::get_annotations_iter() 
+{
+  return annotations_repo_.begin();
+}
+
+template <typename AnnotationId>
 ACE_INLINE int  
 DA_Strategy_Base<AnnotationId>::remove_annotation (AnnotationId id)
 {
diff --git a/ACE/ace/Live_P_Strategy.h b/ACE/ace/Live_P_Strategy.h
index 4f18dd3899f..420307d2348 100644
--- a/ACE/ace/Live_P_Strategy.h
+++ b/ACE/ace/Live_P_Strategy.h
@@ -24,7 +24,7 @@
 # pragma once
 #endif /* ACE_LACKS_PRAGMA_ONCE */
 
-template <typename AnnotationId>
+//forward decl
 class LivePTree;
 
 template <typename AnnotationId>
@@ -39,7 +39,7 @@ public:
     virtual void grant(AnnotationId handle);
     virtual void release(AnnotationId upcall_handle);
 private:
-   LivePTree<AnnotationId>* tree_pimpl_; 
+   LivePTree* tree_pimpl_; 
   
 };
 #if defined (__ACE_INLINE__)
diff --git a/ACE/ace/Live_P_Strategy.inl b/ACE/ace/Live_P_Strategy.inl
index 973de90d219..697c26c45b7 100644
--- a/ACE/ace/Live_P_Strategy.inl
+++ b/ACE/ace/Live_P_Strategy.inl
@@ -1,5 +1,5 @@
 #include <climits>
-
+#include "ace/RB_Tree.h"
 /*
    Much of this is credited to "Efficient Distrubuted Deadlock
    Avoidance with Liveness Guarentees" by Sanchez, Sipma, and Manna,
@@ -19,16 +19,17 @@ struct AnnotationNode {
   int larger_right;
 };
 
-class Live_P_Tree : public ACE_RB_Tree<int, AnnotationNode, ACE_Equal_To<int>, ACE_ThreadMutex> {
+class Live_P_Tree : public ACE_RB_Tree<int, AnnotationNode, ACE_Equal_To<int>, ACE_Thread_Mutex> {
 
 public:
    Live_P_Tree(int maxThreads);
    virtual ~Live_P_Tree();
-   int bind(const int& ext_id, 
-            const AnnotationNode& int_id, 
-            ACE_RB_Tree_Node<int, AnnotationNode>*& entry);
-   int unbind (const EXT_ID &ext_id);
+   int bind(const int& ext_id);
+   int unbind (const int &ext_id);
    int calc_max() const;
+protected:
+   void RB_rotate_right(ACE_RB_Tree_Node<int, AnnotationNode> *x);
+   void RB_rotate_left(ACE_RB_Tree_Node<int, AnnotationNode> *x);
 private:
    void recalculate_augmentation(ACE_RB_Tree_Node<int, AnnotationNode>* nodePtr);
    void recalculate_augmentation_up(ACE_RB_Tree_Node<int, AnnotationNode>* x);
@@ -41,7 +42,7 @@ private:
 };
 
 ACE_INLINE
-Live_P_Tree::Live_P_Tree(int maxThreads) 
+Live_P_Tree::Live_P_Tree(int maxThreads, int k) 
 :ACE_RB_Tree(),
  T_(maxThreads) {
 
@@ -52,33 +53,53 @@ Live_P_Tree::~Live_P_Tree() {
 }
 
 ACE_INLINE 
+int
 Live_P_Tree::bind(const int& ext_id) 
 {
   ACE_RB_Tree_Node<int, AnnotationNode>* entry = 0;
+  int returnVal = -1;  //return error unless we return
+                       //something else from the parent unbind
   RB_SearchResult result = LEFT;
   entry = find_node (ext_id, result);
   // If there is a matching node, don't add a new one, just mod the existing one
-  if (entry && result == EXACT) {
-    entry->item.count++;
+  if (entry && result == EXACT) {    
+    entry->item().count++;    
   } else {
-    RB_Tree::bind(ext_id, AnnotationNode(), entry);
+    returnVal = ACE_RB_Tree::bind(ext_id, AnnotationNode(), entry);
   }
   recalculate_augmentation_up(entry);
+  return returnVal;
+}
+
+void 	
+Live_P_Tree::RB_rotate_right (ACE_RB_Tree_Node<int, AnnotationNode> *x)
+{
+  ACE_RB_Tree::RB_rotate_right(x);
+  recalculate_augmentation_up(x);
 
 }
 
+void 	
+Live_P_Tree::RB_rotate_left (ACE_RB_Tree_Node<int, AnnotationNode> *x)
+{
+  ACE_RB_Tree::RB_rotate_left(x);
+  recalculate_augmentation_up(x);
+}
+
 ACE_INLINE 
+int
 Live_P_Tree::unbind(const int& ext_id) 
 {
   ACE_RB_Tree_Node<int, AnnotationNode>* entry = 0;
   RB_SearchResult result = LEFT;
+  int returnVal = -1;  //return error unless we return
+                       //something else from the parent unbind
   entry = find_node (ext_id, result);
   // If there is a matching node, don't add a new one, just mod the existing one
-  if (entry && result == EXACT) {
-    entry->item.count--;
-    if (count == 0) {
-      entry = entry->parent;
-      RB_Tree::unbind(ext_id);
+  if (entry && result == EXACT) {    
+    if (--(entry->item().count) == 0) {
+      entry = entry->parent();
+      returnVal = ACE_RB_Tree::unbind(ext_id);
     }
   } else {
     //exception?  probably bad if we try to unbind something not in the tree 
@@ -86,38 +107,38 @@ Live_P_Tree::unbind(const int& ext_id)
   if (entry) {
     recalculate_augmentation_up(entry);
   }
-
+  return returnVal;
 }
 
 
 ACE_INLINE  void
 Live_P_Tree::recalculate_augmentation(ACE_RB_Tree_Node<int, AnnotationNode>* nodePtr) {
 
-  AnnotationNode& node = n->item;
-  AnnotationNode& left =  nodePtr->left ? AnnotationNode() : nodePtr->left->item;
-  AnnotationNode& right = nodePtr->right ? AnnotationNode() : nodePtr->right->item;
+  AnnotationNode& node = nodePtr->item();
+  AnnotationNode& left =  nodePtr->left() ? AnnotationNode() : nodePtr->left()->item();
+  AnnotationNode& right = nodePtr->right() ? AnnotationNode() : nodePtr->right()->item();
 
   // (1) size
   node.size = left.size + right.size + node.count;
 
   // (2) larger_me                                            
-  node.larger_me = ProcessCount(T_) - (node.count + right.size/* + node.alpha*/);
-                                                              //^^^^^^^^^^^^^ not sure what this is for
+  node.larger_me = T_ - (node.count + right.size + nodePtr->key());
+                                                              
   // (3) larger_right
-  Node.larger_right = right.larger;
+  node.larger_right = right.larger;
 
   // (4) larger_left
-  Node.larger_left = left.larger - (right.size  + node.count);
+  node.larger_left = left.larger - (right.size  + node.count);
 
   //(5) larger
-  Node.larger = MIN_THREE(x.larger_me, x.larger_left, x.larger_right);
+  node.larger = MIN_THREE(node.larger_me, node.larger_left, node.larger_right);
 }
 
 ACE_INLINE void
 Live_P_Tree::recalculate_augmentation_up(ACE_RB_Tree_Node<int, AnnotationNode>* x) {
   while (x) {
     recalculate_augmentation(x);
-    x = x->parent;
+    x = x->parent();
   }
 }
 
@@ -129,12 +150,12 @@ Live_P_Tree::calc_max() const {
 
 ACE_INLINE  int
 Live_P_Tree::calc_max_i(ACE_RB_Tree_Node<int, AnnotationNode>* nodePtr, int extra) const {
-  AnnotationNode n = nodePtr->item;
+  AnnotationNode& n = nodePtr->item();
 
   if ( n.larger_left - extra==0) { 
-      return calc_max_i(nodePtr->left, extra + nodePtr->right->item.size + n.count); }
-  else if (n->larger_me   - extra==0) { return (nodePtr->key); }
-  else if (n->larger_right - extra==0) { return calc_max_i(nodePtr->right, extra); }
+      return calc_max_i(nodePtr->left(), extra + nodePtr->right()->item().size + n.count); }
+  else if (n.larger_me   - extra==0) { return (nodePtr->key()); }
+  else if (n.larger_right - extra==0) { return calc_max_i(nodePtr->right(), extra); }
   else {   return T_; }
 }
 
diff --git a/ACE/ace/RB_Tree.h b/ACE/ace/RB_Tree.h
index 9fc7e5e45eb..b90742f5002 100644
--- a/ACE/ace/RB_Tree.h
+++ b/ACE/ace/RB_Tree.h
@@ -440,6 +440,12 @@ public:
   /// Destroys all nodes and sets the root pointer null.
   void clear (void);
 
+  /**
+   * Returns a pointer to the current root of the tree.  Being a balanaced tree,
+   * there is no guarentee that this node will remain as the root after a rebalance operation
+   */
+  ACE_RB_Tree_Node<EXT_ID, INT_ID>* get_root() const;
+
 protected:
   /// Reinitialize constructor.
   /**
@@ -459,10 +465,10 @@ protected:
                               int measured_black_height);
 
   /// Method for right rotation of the tree about a given node.
-  void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
+  virtual void RB_rotate_right (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
 
   /// Method for left rotation of the tree about a given node.
-  void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
+  virtual void RB_rotate_left (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x);
 
   /// Method for restoring Red-Black properties after deletion.
   void RB_delete_fixup (ACE_RB_Tree_Node<EXT_ID, INT_ID> * x,
diff --git a/ACE/ace/RB_Tree.inl b/ACE/ace/RB_Tree.inl
index 2e9b266ee92..cb08b5e606c 100644
--- a/ACE/ace/RB_Tree.inl
+++ b/ACE/ace/RB_Tree.inl
@@ -712,6 +712,15 @@ ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::clear ()
   this->close_i ();
 }
 
+// Returns a pointer to the current root of the tree. 
+template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
+ACE_INLINE
+ACE_RB_Tree_Node<EXT_ID, INT_ID>* 
+ACE_RB_Tree<EXT_ID, INT_ID, COMPARE_KEYS, ACE_LOCK>::get_root() const
+{
+  return root_;
+}
+
 // Returns the current number of nodes in the tree.
 
 template <class EXT_ID, class INT_ID, class COMPARE_KEYS, class ACE_LOCK>
diff --git a/ACE/ace/k_Efficient_P_Strategy.cpp b/ACE/ace/k_Efficient_P_Strategy.cpp
new file mode 100644
index 00000000000..eabec650fca
--- /dev/null
+++ b/ACE/ace/k_Efficient_P_Strategy.cpp
@@ -0,0 +1,5 @@
+#include "ace/k_Efficient_P_Strategy.h"
+
+#if !defined (__ACE_INLINE__)
+#include "ace/k_Efficient_P_Strategy.inl"
+#endif /* __ACE_INLINE__ */
\ No newline at end of file
diff --git a/ACE/ace/k_Efficient_P_Strategy.h b/ACE/ace/k_Efficient_P_Strategy.h
new file mode 100644
index 00000000000..bce6af929f0
--- /dev/null
+++ b/ACE/ace/k_Efficient_P_Strategy.h
@@ -0,0 +1,54 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    k_Efficient_P_Strategy.h
+ *
+ *
+ *
+ *
+ *
+ *  @author Paul Oberlin <pauloberlin@gmail.com>
+ */
+//=============================================================================
+
+#ifndef ACE_K_EFFICIENT_P_STRATEGY_H
+#define ACE_K_EFFICIENT_P_STRATEGY_H
+
+#include /**/ "ace/pre.h"
+
+#include "ace/DA_Strategy_Base.h"
+
+#include <vector>
+
+#if !defined (ACE_LACKS_PRAGMA_ONCE)
+# pragma once
+#endif /* ACE_LACKS_PRAGMA_ONCE */
+
+template <typename AnnotationId, int k>
+class k_Efficient_P_Strategy : public DA_Strategy_Base<AnnotationId> {
+
+  //The annotations consist of an identifier and a resource cost value
+
+public:
+    //note: k must be less than maxThreads
+    k_Efficient_P_Strategy(int maxThreads);
+    virtual ~k_Efficient_P_Strategy();
+    virtual bool is_deadlock_potential(AnnotationId handle);
+    virtual void grant(AnnotationId handle);
+    virtual void release(AnnotationId upcall_handle);
+private:
+    int compute_min_illegal();
+    int get_min_illegal();
+    int min_illegal_;
+    bool min_illegal_is_computed_ ;
+    std::vector<int> a;
+    std::vector<int> A;
+};
+#if defined (__ACE_INLINE__)
+#include "ace/k_Efficient_P_Strategy.inl"
+#endif /* __ACE_INLINE__ */
+
+#include /**/ "ace/post.h"
+
+#endif /* ACE_BASIC_P_STRATEGY_H */
\ No newline at end of file
diff --git a/ACE/ace/k_Efficient_P_Strategy.inl b/ACE/ace/k_Efficient_P_Strategy.inl
new file mode 100644
index 00000000000..dcb575a244f
--- /dev/null
+++ b/ACE/ace/k_Efficient_P_Strategy.inl
@@ -0,0 +1,115 @@
+
+template <typename AnnotationId, int k>
+ACE_INLINE 
+k_Efficient_P_Strategy<AnnotationId, k>::k_Efficient_P_Strategy(int maxThreads)
+:DA_Strategy_Base(maxThreads),
+  {
+    a.resize(k + 1);
+    A.resize(k + 1);
+    for (unsigned i=0; i<k; ++i) {
+      a[i] = 0;
+      A[i] = 0;
+    }
+    min_ilegal_ = maxThreads;
+    min_ilegal_is_computed_ = true;
+}
+
+template <typename AnnotationId, int k>
+ACE_INLINE 
+k_Efficient_P_Strategy<AnnotationId, k>::~k_Efficient_P_Strategy()
+{
+
+}
+
+template <typename AnnotationId, int k>
+ACE_INLINE 
+bool k_Efficient_P_Strategy<AnnotationId, k>::is_deadlock_potential(AnnotationId handle)
+{
+  int annotation = get_annotation(handle);
+  return (annotation >= min_ilegal());
+}
+
+template <typename AnnotationId, int k>
+ACE_INLINE
+int
+k_Efficient_P_Strategy<AnnotationId, k>::compute_min_illegal() 
+{
+  int T = get_max_threads();
+  for (int i=0; i<k; ++i) {
+    if (!(A[i] < (T - i))) {
+      return i;
+    }
+  }
+  if (A[k]>0) {
+    return (T - A[k]);
+  } 
+  return  T;
+}
+
+template <typename AnnotationId, int k>
+ACE_INLINE
+int
+k_Efficient_P_Strategy<AnnotationId, k>::get_min_illegal() 
+{
+  if (!min_illegal_is_computed_) {
+	  min_illegal_ = compute_min_ilegal();
+	  min_illegal_is_computed_ = true;
+  }
+  return min_illegal_;
+}
+
+template <typename AnnotationId, int k>
+ACE_INLINE 
+void k_Efficient_P_Strategy<AnnotationId, k>::grant(AnnotationId handle)
+{
+    int annotation = get_annotation(handle);
+
+    if (annotation < k) 
+    {
+      a[annotation] ++;
+      for (int i=0; i<=annotation; ++i) 
+      {
+	      A[i]++;
+      }
+    } 
+    else
+    {
+      a[k] ++;
+      for (int i=0; i<=k ; ++i)
+      {
+	      A[i]++;
+      }
+    }
+    min_ilegal_is_computed_ = false;
+    return true;
+}
+
+template <typename AnnotationId, int k>
+ACE_INLINE 
+void k_Efficient_P_Strategy<AnnotationId, k>::release(AnnotationId handle)
+{
+    int annotation = get_annotation(handle);
+/*    if (annotation < k ) {
+      assert(a[annotation]>0);
+    } else {
+      assert(a[k] >0);
+    }
+*/
+    if (annotation < k)
+    {
+      a[annotation] --;
+      for (unsigned i=0; i<=annotation; ++i) 
+      {
+	      A[i]--;
+      }
+    } 
+    else 
+    {
+      a[k] --;
+      for (unsigned i=0; i<=k ; ++i) 
+      {
+	      A[i]--;
+      }
+    }
+    min_ilegal_is_computed_ = false;
+}
\ No newline at end of file