first version of DA strategies

11 files changed, 642 insertions, 0 deletions

diff --git a/ACE/ace/Basic_P_Strategy.cpp b/ACE/ace/Basic_P_Strategy.cpp
new file mode 100644
index 00000000000..02e6df1d6f7
--- /dev/null
+++ b/ACE/ace/Basic_P_Strategy.cpp
@@ -0,0 +1,5 @@
+#include "ace/Basic_P_Strategy.h"
+
+#if !defined (__ACE_INLINE__)
+#include "ace/Basic_P_Strategy.inl"
+#endif /* __ACE_INLINE__ */
\ No newline at end of file
diff --git a/ACE/ace/Basic_P_Strategy.h b/ACE/ace/Basic_P_Strategy.h
new file mode 100644
index 00000000000..f374b2616c9
--- /dev/null
+++ b/ACE/ace/Basic_P_Strategy.h
@@ -0,0 +1,46 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    Basic_P_Strategy.h
+ *
+ *
+ *
+ *
+ *
+ *  @author Paul Oberlin <pauloberlin@gmail.com>
+ */
+//=============================================================================
+
+#ifndef ACE_BASIC_P_STRATEGY_H
+#define ACE_BASIC_P_STRATEGY_H
+
+#include /**/ "ace/pre.h"
+
+#include "ace/DA_Strategy_Base.h"
+
+#if !defined (ACE_LACKS_PRAGMA_ONCE)
+# pragma once
+#endif /* ACE_LACKS_PRAGMA_ONCE */
+
+template <typename AnnotationId>
+class Basic_P_Strategy : public DA_Strategy_Base<AnnotationId> {
+
+  //The annotations consist of an identifier and a resource cost value
+
+public:
+    Basic_P_Strategy(int maxThreads);
+    virtual ~Basic_P_Strategy();
+    virtual bool is_deadlock_potential(AnnotationId handle);
+    virtual void grant(AnnotationId handle);
+    virtual void release(AnnotationId upcall_handle);
+private:
+    int t_r;
+};
+#if defined (__ACE_INLINE__)
+#include "ace/Basic_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/Basic_P_Strategy.inl b/ACE/ace/Basic_P_Strategy.inl
new file mode 100644
index 00000000000..656dcbd8a29
--- /dev/null
+++ b/ACE/ace/Basic_P_Strategy.inl
@@ -0,0 +1,37 @@
+
+template <typename AnnotationId>
+ACE_INLINE 
+Basic_P_Strategy<AnnotationId>::Basic_P_Strategy(int maxThreads)
+:DA_Strategy_Base(maxThreads)
+ t_r(maxThreads)
+{
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+Basic_P_Strategy<AnnotationId>::~Basic_P_Strategy()
+{
+
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+bool Basic_P_Strategy<AnnotationId>::is_deadlock_potential(AnnotationId handle)
+{
+  int annotation = get_annotation(handle);
+  return !(annotation < t_r);
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+void Basic_P_Strategy<AnnotationId>::grant(AnnotationId handle)
+{
+  --t_r;
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+void Basic_P_Strategy<AnnotationId>::release(AnnotationId upcall_handle)
+{
+  ++t_r;
+}
\ No newline at end of file
diff --git a/ACE/ace/DA_Strategy_Base.cpp b/ACE/ace/DA_Strategy_Base.cpp
new file mode 100644
index 00000000000..ad32725cdea
--- /dev/null
+++ b/ACE/ace/DA_Strategy_Base.cpp
@@ -0,0 +1,5 @@
+#include "ace/DA_Strategy_Base.h"
+
+#if !defined (__ACE_INLINE__)
+#include "ace/DA_Strategy_Base.inl"
+#endif /* __ACE_INLINE__ */
\ No newline at end of file
diff --git a/ACE/ace/DA_Strategy_Base.h b/ACE/ace/DA_Strategy_Base.h
new file mode 100644
index 00000000000..f63e3757c39
--- /dev/null
+++ b/ACE/ace/DA_Strategy_Base.h
@@ -0,0 +1,100 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    DA_Strategy_Base.h
+ *
+ *
+ *
+ *  The Deadlock Avoidance Strategy Base (DA_Strategy_Base) class
+ *  is an abstract base class for Strategies that implement deadlock
+ *  avoidance algorithms.  This class provides interfaces for passing
+ *  annotations for call graph annotations, number of available threads, as well 
+ *  as methods to determine whether a call is safe to make.
+ *
+ *
+ *  @author Paul Oberlin <pauloberlin@gmail.com>
+ */
+//=============================================================================
+
+#ifndef DA_STRATEGY_BASE_H
+#define DA_STRATEGY_BASE_H
+
+#include /**/ "ace/pre.h"
+#include "ace/Hash_Map_Manager_T.h"
+#include "ace/Thread_Mutex.h"
+#include "ace/Atomic_Op_T.h"
+
+#if !defined (ACE_LACKS_PRAGMA_ONCE)
+# pragma once
+#endif /* ACE_LACKS_PRAGMA_ONCE */
+
+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_Manager_Ex<AnnotationId,
+                                int,
+                                ACE_Hash<AnnotationId>,
+                                ACE_Equal_To<AnnotationId>,
+                                ACE_Thread_Mutex> HASH_ANNOTATIONS_MAP;
+
+typedef ACE_Hash_Map_Iterator_Ex<AnnotationId,
+                                 int,
+                                 ACE_Hash<AnnotationId>,
+                                 ACE_Equal_To<AnnotationId>,
+                                 ACE_Thread_Mutex> HASH_ANNOTATIONS_ITER;
+
+typedef ACE_Hash_Map_Const_Iterator_Ex<AnnotationId,
+                                       int,
+                                       ACE_Hash<AnnotationId>,
+                                       ACE_Equal_To<AnnotationId>,
+                                       ACE_Thread_Mutex> HASH_ANNOTATIONS_CONST_ITER;
+
+typedef ACE_Hash_Map_Reverse_Iterator_Ex<AnnotationId,
+                                         int,
+                                         ACE_Hash<AnnotationId>,
+                                         ACE_Equal_To<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_};
+    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);
+
+private:
+  ACE_Hash_Map_Manager_Ex<AnnotationId,
+                          int,
+                          ACE_Hash<AnnotationId>,
+                          ACE_Equal_To<AnnotationId>,
+                          ACE_Thread_Mutex> annotations_repo_;
+  ACE_RW_Thread_Mutex lock_;
+  ACE_Atomic_Op<ACE_Thread_Mutex, long> num_avail_threads_;
+
+};
+
+#include /**/ "ace/post.h"
+
+#endif /* DA_STRATEGY_BASE_H */
\ No newline at end of file
diff --git a/ACE/ace/DA_Strategy_Base.inl b/ACE/ace/DA_Strategy_Base.inl
new file mode 100644
index 00000000000..51d2e9cf642
--- /dev/null
+++ b/ACE/ace/DA_Strategy_Base.inl
@@ -0,0 +1,88 @@
+template <typename AnnotationId>
+ACE_INLINE 
+DA_Strategy_Base<AnnotationId>::DA_Strategy_Base (int maxThreads)
+  :num_avail_threads_ (maxThreads)
+{
+}
+
+template <typename AnnotationId>
+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)
+{
+  int annotation;
+  if (annotations_repo_.find (id, annotation) == -1)
+    return -1;
+  else return annotation;
+}
+
+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)
+{
+  ACE_Hash_Map_Const_Iterator_Ex<AnnotationId,
+                                 int,
+                                 ACE_Hash<AnnotationId>,
+                                 ACE_Equal_To<AnnotationId>,
+                                 ACE_Thread_Mutex>  iter(table);
+  int rc=0;
+  
+  for (;!(iter.done()); iter++)
+    {
+      rc = annotations_repo_.bind((*iter).ext_id_, (*iter).int_id_);
+      if (rc != 0) break;
+    }
+
+  return rc;
+}
+
+template <typename AnnotationId>
+ACE_INLINE int 
+DA_Strategy_Base<AnnotationId>::add_annotation (AnnotationId id, int annotation)
+{
+  int rc;
+  rc = annotations_repo_.bind (id, annotation);
+  /*  
+    ACE_DEBUG ((LM_DEBUG, "In add_annotation\n"));
+  HASH_ANNOTATIONS_CONST_ITER iter(annotations_repo_);
+  for (;!(iter.done()); iter++)
+    {
+      ACE_DEBUG ((LM_DEBUG, "%d-%d\n", (*iter).ext_id_, (*iter).int_id_));
+    }
+  */
+  return rc;
+}
+
+template <typename AnnotationId>
+ACE_INLINE int  
+DA_Strategy_Base<AnnotationId>::remove_annotation (AnnotationId id)
+{
+  return annotations_repo_.unbind (id);
+}
+
diff --git a/ACE/ace/Efficient_P_Strategy.cpp b/ACE/ace/Efficient_P_Strategy.cpp
new file mode 100644
index 00000000000..719de4c9fcc
--- /dev/null
+++ b/ACE/ace/Efficient_P_Strategy.cpp
@@ -0,0 +1,5 @@
+#include "ace/Efficient_P_Strategy.h"
+
+#if !defined (__ACE_INLINE__)
+#include "ace/Efficient_P_Strategy.inl"
+#endif /* __ACE_INLINE__ */
\ No newline at end of file
diff --git a/ACE/ace/Efficient_P_Strategy.h b/ACE/ace/Efficient_P_Strategy.h
new file mode 100644
index 00000000000..c40caf0d513
--- /dev/null
+++ b/ACE/ace/Efficient_P_Strategy.h
@@ -0,0 +1,49 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    Efficient_P_Strategy.h
+ *
+ *
+ *
+ *
+ *
+ *  @author Paul Oberlin <pauloberlin@gmail.com>
+ */
+//=============================================================================
+
+#ifndef ACE_EFFICIENT_P_STRATEGY_H
+#define ACE_EFFICIENT_P_STRATEGY_H
+
+#include /**/ "ace/pre.h"
+
+#include "ace/DA_Strategy_Base.h"
+#include "ace/Thread_Mutex.h"
+
+#if !defined (ACE_LACKS_PRAGMA_ONCE)
+# pragma once
+#endif /* ACE_LACKS_PRAGMA_ONCE */
+
+template <typename AnnotationId>
+class Efficient_P_Strategy : public DA_Strategy_Base<AnnotationId> {
+
+  //The annotations consist of an identifier and a resource cost value
+
+public:
+    Efficient_P_Strategy(int maxThreads);
+    virtual ~Efficient_P_Strategy();
+    virtual bool is_deadlock_potential(AnnotationId handle);
+    virtual void grant(AnnotationId handle);
+    virtual void release(AnnotationId upcall_handle);
+private:
+    int t_r;
+    int p_r;
+    ACE_Thread_Mutex _lock;
+};
+#if defined (__ACE_INLINE__)
+#include "ace/Efficient_P_Strategy.inl"
+#endif /* __ACE_INLINE__ */
+
+#include /**/ "ace/post.h"
+
+#endif /* ACE_EFFICIENT_P_STRATEGY_H */
\ No newline at end of file
diff --git a/ACE/ace/Efficient_P_Strategy.inl b/ACE/ace/Efficient_P_Strategy.inl
new file mode 100644
index 00000000000..e42a2330f8e
--- /dev/null
+++ b/ACE/ace/Efficient_P_Strategy.inl
@@ -0,0 +1,62 @@
+
+template <typename AnnotationId>
+ACE_INLINE 
+Efficient_P_Strategy<AnnotationId>::Efficient_P_Strategy(int maxThreads)
+:DA_Strategy_Base(maxThreads),
+ t_r(maxThreads),
+ p_r(maxThreads),
+ _lock()
+{
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+Efficient_P_Strategy<AnnotationId>::~Efficient_P_Strategy()
+{
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+bool 
+Efficient_P_Strategy<AnnotationId>::is_deadlock_potential(AnnotationId handle)
+{
+  int annotation = get_annotation(handle);
+  int min_illegal = 0;
+  if (t_r != 0) {
+    min_illegal = p_r;
+  }
+  return !(annotation < min_illegal);
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+void 
+Efficient_P_Strategy<AnnotationId>::grant(AnnotationId handle)
+{
+  int annotation = get_annotation(handle);
+  {
+    ACE_Guard<ACE_Thread_Mutex> guard(_lock);
+    t_r--;
+    if (annotation > 1) 
+    {
+      p_r--;
+    }   
+  }
+  return true;
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+void 
+Efficient_P_Strategy<AnnotationId>::release(AnnotationId upcall_handle)
+{
+  int annotation = get_annotation(handle);
+  {
+    ACE_Guard<ACE_Thread_Mutex> guard(_lock);
+    t_r ++;
+    if (annotation > 1) 
+    {
+      p_r ++;
+    }  
+  }
+}
\ No newline at end of file
diff --git a/ACE/ace/Live_P_Strategy.h b/ACE/ace/Live_P_Strategy.h
new file mode 100644
index 00000000000..4f18dd3899f
--- /dev/null
+++ b/ACE/ace/Live_P_Strategy.h
@@ -0,0 +1,51 @@
+// -*- C++ -*-
+
+//=============================================================================
+/**
+ *  @file    Live_P_Strategy.h
+ *
+ *
+ *
+ *
+ *
+ *  @author Paul Oberlin <pauloberlin@gmail.com>
+ */
+//=============================================================================
+
+#ifndef ACE_LIVE_P_STRATEGY_H
+#define ACE_LIVE_P_STRATEGY_H
+
+#include /**/ "ace/pre.h"
+
+#include "ace/DA_Strategy_Base.h"
+#include "ace/RB_Tree.h"
+
+#if !defined (ACE_LACKS_PRAGMA_ONCE)
+# pragma once
+#endif /* ACE_LACKS_PRAGMA_ONCE */
+
+template <typename AnnotationId>
+class LivePTree;
+
+template <typename AnnotationId>
+class Live_P_Strategy : public DA_Strategy_Base<AnnotationId> {
+
+  //The annotations consist of an identifier and a resource cost value
+
+public:
+    Live_P_Strategy(int maxThreads);
+    virtual ~Live_P_Strategy();
+    virtual bool is_deadlock_potential(AnnotationId handle);
+    virtual void grant(AnnotationId handle);
+    virtual void release(AnnotationId upcall_handle);
+private:
+   LivePTree<AnnotationId>* tree_pimpl_; 
+  
+};
+#if defined (__ACE_INLINE__)
+#include "ace/Live_P_Strategy.inl"
+#endif /* __ACE_INLINE__ */
+
+#include /**/ "ace/post.h"
+
+#endif /* ACE_LIVE_P_STRATEGY_H */
\ No newline at end of file
diff --git a/ACE/ace/Live_P_Strategy.inl b/ACE/ace/Live_P_Strategy.inl
new file mode 100644
index 00000000000..973de90d219
--- /dev/null
+++ b/ACE/ace/Live_P_Strategy.inl
@@ -0,0 +1,194 @@
+#include <climits>
+
+/*
+   Much of this is credited to "Efficient Distrubuted Deadlock
+   Avoidance with Liveness Guarentees" by Sanchez, Sipma, and Manna,
+   EMSOFT 2006
+*/
+
+struct AnnotationNode {
+  AnnotationNode() 
+    :count(0), size(0), larger(0), larger_me(0), larger_left(INT_MAX), larger_right(INT_MAX)
+  {
+  }
+  int count;  //number of processes with this annotation
+  int size;  //total number of processes in subtree including this node
+  int larger;  //minimum of larger_left, larger_me, and, larger_right
+  int larger_me;
+  int larger_left;
+  int larger_right;
+};
+
+class Live_P_Tree : public ACE_RB_Tree<int, AnnotationNode, ACE_Equal_To<int>, ACE_ThreadMutex> {
+
+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 calc_max() const;
+private:
+   void recalculate_augmentation(ACE_RB_Tree_Node<int, AnnotationNode>* nodePtr);
+   void recalculate_augmentation_up(ACE_RB_Tree_Node<int, AnnotationNode>* x);
+   int calc_max_i(ACE_RB_Tree_Node<int, AnnotationNode>* nodePtr, int extra) const;
+   static int MIN(int a, int b) { return (a<b)?a:b; }
+   static int MIN_THREE(int a, int b, int c) {
+     return (a<b)?MIN(a,c):MIN(b,c);
+   }
+   int T_;
+};
+
+ACE_INLINE
+Live_P_Tree::Live_P_Tree(int maxThreads) 
+:ACE_RB_Tree(),
+ T_(maxThreads) {
+
+}
+
+ACE_INLINE
+Live_P_Tree::~Live_P_Tree() {
+}
+
+ACE_INLINE 
+Live_P_Tree::bind(const int& ext_id) 
+{
+  ACE_RB_Tree_Node<int, AnnotationNode>* entry = 0;
+  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++;
+  } else {
+    RB_Tree::bind(ext_id, AnnotationNode(), entry);
+  }
+  recalculate_augmentation_up(entry);
+
+}
+
+ACE_INLINE 
+Live_P_Tree::unbind(const int& ext_id) 
+{
+  ACE_RB_Tree_Node<int, AnnotationNode>* entry = 0;
+  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 (count == 0) {
+      entry = entry->parent;
+      RB_Tree::unbind(ext_id);
+    }
+  } else {
+    //exception?  probably bad if we try to unbind something not in the tree 
+  } 
+  if (entry) {
+    recalculate_augmentation_up(entry);
+  }
+
+}
+
+
+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;
+
+  // (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
+  // (3) larger_right
+  Node.larger_right = right.larger;
+
+  // (4) larger_left
+  Node.larger_left = left.larger - (right.size  + node.count);
+
+  //(5) larger
+  Node.larger = MIN_THREE(x.larger_me, x.larger_left, x.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;
+  }
+}
+
+ACE_INLINE  int
+Live_P_Tree::calc_max() const {
+   //note: need to add get_root method to RB_Tree
+   return calc_max_i(get_root(), 0);
+}
+
+ACE_INLINE  int
+Live_P_Tree::calc_max_i(ACE_RB_Tree_Node<int, AnnotationNode>* nodePtr, int extra) const {
+  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); }
+  else {   return T_; }
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+Live_P_Strategy<AnnotationId>::Live_P_Strategy(int maxThreads)
+:DA_Strategy_Base(maxThreads)
+{
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+Live_P_Strategy<AnnotationId>::~Live_P_Strategy()
+{
+}
+
+
+
+template <typename AnnotationId>
+ACE_INLINE 
+bool 
+Live_P_Strategy<AnnotationId>::is_deadlock_potential(AnnotationId handle)
+{
+    int min_illegal = getMaxThreads();
+    int annotation = getAnnotation(handle);
+
+    if (!min_ilegal_is_computed_) 
+    {
+      if (tree_->current_size() > 1) 
+      {	    
+	      min_ilegal_ = calc_max();
+      }
+      min_ilegal_is_computed_ = true;
+    }
+
+    return annotation >= min_ilegal_;
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+void 
+Live_P_Strategy<AnnotationId>::grant(AnnotationId handle)
+{
+  int annotation = getAnnotation(handle);
+  tree_pimpl_->bind(annotation);
+  min_ilegal_is_computed_ = false;
+}
+
+template <typename AnnotationId>
+ACE_INLINE 
+void 
+Live_P_Strategy<AnnotationId>::release(AnnotationId handle)
+{
+  min_ilegal_is_computed_ = false;
+  int annotation = getAnnotation(handle);
+  tree_pimpl_->unbind(annotation);
+}
\ No newline at end of file