fix IBSTree-fast: add missing decl and missing unlock on one path
[dyninst.git] / common / h / IBSTree-fast.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  *
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  *
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  *
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  *
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  *
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #if !defined(IBSTREE_FAST_H)
32 #define IBSTREE_FAST_H
33 #include "IBSTree.h"
34 #include <boost/multi_index_container.hpp>
35 #include <boost/multi_index/ordered_index.hpp>
36 #include <boost/multi_index/mem_fun.hpp>
37 #include <boost/multi_index/identity.hpp>
38 #include <boost/multi_index/member.hpp>
39 #include <boost/multi_index/composite_key.hpp>
40 #include <boost/mpl/insert_range.hpp>
41 #include <boost/mpl/inherit_linearly.hpp>
42 #include <boost/mpl/inherit.hpp>
43 #include <iostream>
44
45 #include "pfq-rwlock.h"
46
47 namespace Dyninst
48 {
49
50     template <typename ITYPE >
51     class IBSTree_fast {
52     private:
53         // reader-writer lock to coordinate concurrent operations
54         mutable pfq_rwlock_t rwlock;
55
56     public:
57         typedef typename ITYPE::type interval_type;
58
59         IBSTree<ITYPE> overlapping_intervals;
60         typedef boost::multi_index_container<ITYPE*,
61                 boost::multi_index::indexed_by<
62                         boost::multi_index::ordered_unique<
63                                 boost::multi_index::const_mem_fun<ITYPE, interval_type, &ITYPE::high> >
64                 > > interval_set;
65
66         //typedef std::set<ITYPE*, order_by_lower<ITYPE> > interval_set;
67         interval_set unique_intervals;
68
69         IBSTree_fast()
70         {
71             pfq_rwlock_init(rwlock);
72         }
73         ~IBSTree_fast()
74         {
75             //std::cerr << "Fast interval tree had " << unique_intervals.size() << " unique intervals and " << overlapping_intervals.size() << " overlapping" << std::endl;
76         }
77         int size() const
78         {
79             pfq_rwlock_read_lock(rwlock);
80             int result = overlapping_intervals.size() + unique_intervals.size();
81             pfq_rwlock_read_unlock(rwlock);
82             return result;
83         }
84         bool empty() const
85         {
86             pfq_rwlock_read_lock(rwlock);
87             bool result = unique_intervals.empty() && overlapping_intervals.empty();
88             pfq_rwlock_read_unlock(rwlock);
89             return result;
90         }
91         void insert(ITYPE*);
92         void remove(ITYPE*);
93         int find(interval_type, std::set<ITYPE*> &) const;
94         int find(ITYPE* I, std::set<ITYPE*>&) const;
95         void successor(interval_type X, std::set<ITYPE*>& ) const;
96         ITYPE* successor(interval_type X) const;
97         void clear();
98         friend std::ostream& operator<<(std::ostream& stream, const IBSTree_fast<ITYPE>& tree)
99         {
100             pfq_rwlock_read_lock(tree.rwlock);
101             std::copy(tree.unique_intervals.begin(), tree.unique_intervals.end(),
102                       std::ostream_iterator<typename Dyninst::IBSTree_fast<ITYPE>::interval_set::value_type>(stream, "\n"));
103             stream << tree.overlapping_intervals;
104             pfq_rwlock_read_unlock(tree.rwlock);
105             return stream;
106         }
107
108     };
109
110     template <class ITYPE>
111     void IBSTree_fast<ITYPE>::insert(ITYPE* entry)
112     {
113         pfq_rwlock_node_t me;
114         pfq_rwlock_write_lock(rwlock, me);
115
116         do {
117         // find in overlapping first
118         std::set<ITYPE*> dummy;
119         if(overlapping_intervals.find(entry, dummy))
120         {
121             overlapping_intervals.insert(entry);
122         } else { 
123           typename interval_set::iterator lower =
124             unique_intervals.upper_bound(entry->low());
125           // lower.high first >= entry.low
126           if (lower != unique_intervals.end() && (**lower == *entry)) break;
127           typename interval_set::iterator upper = lower;
128           while(upper != unique_intervals.end() &&
129                 (*upper)->low() <= entry->high())
130             {
131               overlapping_intervals.insert(*upper);
132               ++upper;
133             }
134           if(upper != lower)
135             {
136               unique_intervals.erase(lower, upper);
137               overlapping_intervals.insert(entry);
138             }
139           else
140             {
141               unique_intervals.insert(entry);
142             }
143         }
144         } while(0);
145
146         pfq_rwlock_write_unlock(rwlock, me);
147     }
148     template <class ITYPE>
149     void IBSTree_fast<ITYPE>::remove(ITYPE* entry)
150     {
151         pfq_rwlock_node_t me;
152         pfq_rwlock_write_lock(rwlock, me);
153
154         overlapping_intervals.remove(entry);
155         typename interval_set::iterator found = unique_intervals.find(entry->high());
156         if(found != unique_intervals.end() && *found == entry) unique_intervals.erase(found);
157         pfq_rwlock_write_unlock(rwlock, me);
158     }
159     template<class ITYPE>
160     int IBSTree_fast<ITYPE>::find(interval_type X, std::set<ITYPE*> &results) const
161     {
162       int count = 0;
163       pfq_rwlock_read_lock(rwlock);
164       do {
165         int num_old_results = results.size();
166
167         int num_overlapping = overlapping_intervals.find(X, results);
168         if(num_overlapping > 0) { count = num_overlapping; break; }
169
170         typename interval_set::const_iterator found_unique = unique_intervals.upper_bound(X);
171         if(found_unique != unique_intervals.end())
172         {
173           if((*found_unique)->low() > X) { count = 0; break; }
174             results.insert(*found_unique);
175         }
176         count = results.size() - num_old_results;
177       } while (0);
178       pfq_rwlock_read_unlock(rwlock);
179       return count;
180     }
181     template <typename ITYPE>
182     int IBSTree_fast<ITYPE>::find(ITYPE* I, std::set<ITYPE*>&results) const
183     {
184         pfq_rwlock_read_lock(rwlock);
185         int num_old_results = results.size();
186         int num_overlapping = overlapping_intervals.find(I, results);
187         if(num_overlapping) return num_overlapping;
188         typename interval_set::const_iterator lb = unique_intervals.upper_bound(I->low());
189         typename interval_set::iterator  ub = lb;
190         while(ub != unique_intervals.end() && (*ub)->low() < I->high())
191         {
192             results.insert(*ub);
193             ++ub;
194         }
195         int result = results.size() - num_old_results;
196         pfq_rwlock_read_unlock(rwlock);
197         return result;
198     }
199     template<typename ITYPE>
200     void IBSTree_fast<ITYPE>::successor(interval_type X, std::set<ITYPE*>& results) const
201     {
202         pfq_rwlock_read_lock(rwlock);
203         ITYPE* overlapping_ub = overlapping_intervals.successor(X);
204
205         typename interval_set::const_iterator unique_ub = unique_intervals.upper_bound(X);
206         if(overlapping_ub && (unique_ub != unique_intervals.end()))
207         {
208             results.insert(overlapping_ub->low() < (*unique_ub)->low() ? overlapping_ub : *unique_ub);
209         }
210         else if(overlapping_ub)
211         {
212             results.insert(overlapping_ub);
213         }
214         else if(unique_ub != unique_intervals.end())
215         {
216             results.insert(*unique_ub);
217         }
218         pfq_rwlock_read_unlock(rwlock);
219     }
220     template <typename ITYPE>
221     ITYPE* IBSTree_fast<ITYPE>::successor(interval_type X) const
222     {
223         std::set<ITYPE*> tmp;
224         successor(X, tmp);
225         assert(tmp.size() <= 1);
226         if(tmp.empty()) return NULL;
227         return *tmp.begin();
228     }
229     template <typename ITYPE>
230     void IBSTree_fast<ITYPE>::clear()
231     {
232         pfq_rwlock_node_t me;
233         pfq_rwlock_write_lock(rwlock, me);
234         overlapping_intervals.clear();
235         unique_intervals.clear();
236         pfq_rwlock_write_unlock(rwlock, me);
237     }
238
239 }
240
241
242 #endif