Update copyright to LGPL on all files
[dyninst.git] / symtabAPI / h / RangeLookup.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #if ! defined( RANGE_LOOKUP_H )
33 #define RANGE_LOOKUP_H
34
35 #include <map>
36 #include <vector>
37 #include <list>
38 #include <assert.h>
39 #include "dyntypes.h"
40 #include "util.h"
41
42 namespace Dyninst
43 {
44 namespace SymtabAPI
45 {
46
47 /* The Windows C++ compiler is broken and won't instantiate this function when it's in RangeLookup proper. */
48
49 class SYMTAB_EXPORT RangeLookupImpl 
50 {
51         public:
52                 typedef std::pair< Offset, Offset >     AddressRange;
53
54                 /* Explicit comparison functors seems slightly less confusing than using
55                    operator <() via an implicit Less<> template argument to the maps. */
56
57                 struct AddressRangeLess {
58                         bool operator()(const AddressRange &lhs, const AddressRange &rhs) const
59                         {
60                                 if ( lhs.first < rhs.first ) 
61                                 { 
62                                         return true; 
63                                 }
64                                 else if ( lhs.first == rhs.first ) 
65                                 {
66                                         if ( lhs.second < rhs.second ) 
67                                         {
68                                                 return true;
69                                         }
70                                         else
71                                         {
72                                                 return false; 
73                                         }
74                                 }
75
76                                 return false; 
77                         } /* end AddressRangeLess() */
78                 };
79
80 }; /* end class RangeLookupImpl */
81
82 template< class Value, class ValueLess > 
83 class SYMTAB_EXPORT RangeLookup 
84 {
85         protected:
86                 typedef RangeLookupImpl::AddressRange AddressRange;
87                 typedef RangeLookupImpl::AddressRangeLess AddressRangeLess;
88
89                 typedef std::multimap< Value, AddressRange, ValueLess > AddressRangeByValue;
90                 typedef std::multimap< AddressRange, Value, AddressRangeLess > ValueByAddressRange;
91
92         public:         
93                 typedef typename ValueByAddressRange::const_iterator const_iterator;
94
95                 RangeLookup();
96
97                 /* Values are copied: a RangeLookup considers itself the primary repository. */
98                 bool addValue( Value v, Offset lowInclusiveAddr, Offset highExclusiveAddr );
99                 bool addAddressRange( Offset lowInclusiveAddr, Offset highExclusiveAddr, Value v );
100
101                 /* Likewise, copies of the values are returned. */
102                 bool getValues( Offset addressInRange, std::vector< Value *> & values );
103                 bool getAddressRanges( Value v, std::vector< AddressRange > & ranges );
104
105                 const_iterator begin() const;
106                 const_iterator end() const;
107
108                 ~RangeLookup();
109
110                 // /* DEBUG */ void dump( FILE * stream );
111                 // /* DEBUG */ static void testInsertionSpeed();
112
113         protected:
114                 ValueByAddressRange valuesByAddressRangeMap;
115                 AddressRangeByValue addressRangesByValueMap;
116 }; /* end class RangeLookup */
117
118 template< class Value, class ValueRange > RangeLookup< Value, ValueRange >::RangeLookup() :
119         valuesByAddressRangeMap(),
120         addressRangesByValueMap() {}
121
122 /* Private refactoring function: erase()s value from map. */
123 template< class M >
124 bool removeByValue( M & map, const typename M::value_type & value ) 
125 {
126         std::pair< typename M::iterator, typename M::iterator > range = map.equal_range( value.first ); 
127 #if 0
128 #if ! defined( os_windows )
129         std::pair< typename M::iterator, typename M::iterator > range = map.equal_range( value.first ); 
130 #else
131         std::pair< M::iterator, M::iterator > range = map.equal_range( value.first );   
132 #endif
133 #endif
134
135         for ( ; range.first != range.second && range.first != map.end(); ++range.first ) 
136         {
137                 typename M::value_type &cmp = *range.first;
138                 if (cmp == value ) 
139                 {
140                         map.erase( range.first );
141                         return true;
142                 }
143         }
144
145         return false;
146         
147 } /* end removeByValue() */
148
149 /* We maintain the invariant that low and high address sort orders are the same.  (If we
150    didn't, we could only find one of the two endpoints of the range of ranges we should
151    check.  If we find one endpoint and iterate over the other sort order until we found
152    the other, a range contained by another range would change the sort order and cause
153    ranges containing the search target to be skippped.)  So we check, whenever we insert
154    a new range, if it contains or is contained by any other range.
155
156    Since we insert elements one at a time, we can assume that no range already present
157    contains another range.  Furthermore, if no range contains another range, then any
158    range (B) between the inserted range (I) and a range which might contain it (A)
159    must also contain I.  (Where ranges are ordered by their low address.)
160
161    (Proof by contradiction: suppose there exists a B not containing I.  Because B is between
162    I and A, B's low address is lower than I's.  Therefore, because B does not contain I, its
163    high address must be lower than I's.  Because I is contained by A, its high address is
164    lower than A's.  By transitivity, B's high address is lower than A's.  Since B's low
165    address is higher than A's (because B is between A and I), B is contained by A.  Contradiction.)
166
167    Therefore, we only need to check ranges lower than I until one of them does not contain it.
168    If we split each containing range in the middle of I, we can insert I and maintain our
169    no-overlap invariant.
170
171    Similar logic applies in reverse direction: if I contains a range, it contains every
172    range between it and I.
173
174    Furthermore, the same range can't be both contained and contained-by: if it's contained-by,
175    its container contains whatever it does.
176
177    We want to split ranges so that their low and high addresses sort in the same order.  (Strictly
178    speaking, the above conditions ought to be "not a range which will cause the low and high address
179    sort order to be different, but it ends up not mattering, AFAICT.)
180
181    If we're inserting a contained range, we split the containing ranges on the contained range's right edge.
182
183    If we're inserted a containing range, we split it and the other ranges on the least upper address in
184    each group of contained ranges.
185  */
186
187 template <class Value, class ValueRange> 
188 bool RangeLookup< Value, ValueRange >::addValue(Value v, 
189                 Offset lowInclusiveAddr, 
190                 Offset highExclusiveAddr) 
191 {
192         /* Verify the input. */
193         if ( lowInclusiveAddr >= highExclusiveAddr ) 
194         { 
195                 return false; 
196         }
197
198         /* If we've already got this range, it's safe to insert it. */
199
200         typedef typename ValueByAddressRange::iterator RangeIterator;
201         std::pair< RangeIterator, RangeIterator > rangeOfRanges;
202
203         rangeOfRanges = valuesByAddressRangeMap.equal_range(AddressRange(lowInclusiveAddr, 
204                                 highExclusiveAddr));
205
206         if (   (rangeOfRanges.first != rangeOfRanges.second) 
207                         || (valuesByAddressRangeMap.size() == 0) ) 
208         {
209                 // insert() is amortized constant time if the new value is inserted 
210                 // immediately before the hint. 
211
212                 valuesByAddressRangeMap.insert( rangeOfRanges.second, 
213                                 std::make_pair(AddressRange(lowInclusiveAddr, 
214                                                 highExclusiveAddr), v));
215
216                 addressRangesByValueMap.insert( std::make_pair( v, AddressRange(lowInclusiveAddr, 
217                                                 highExclusiveAddr)));
218                 return true;
219         }
220
221         /* Otherwise, we need to look for containing ranges. */
222
223         typedef std::pair< AddressRange, Value > Range;
224         typedef std::list< Range > RangeList;
225         RangeIterator downIterator = rangeOfRanges.second;
226
227         if (rangeOfRanges.second != valuesByAddressRangeMap.begin()) 
228         {
229                 --downIterator; 
230         }
231
232         RangeList containingRangeList;
233         for (; ( (downIterator->first.first <= lowInclusiveAddr)
234                                 && (highExclusiveAddr < downIterator->first.second) )
235                         ; --downIterator ) 
236         {
237
238                 // /* DEBUG */ fprintf( stderr, "%s[%d]: found containing range [0x%lx, 0x%lx) while inserting [0x%lx, 0x%lx) (%s, %d)\n", __FILE__, __LINE__, downIterator->first.first, downIterator->first.second, lowInclusiveAddr, highExclusiveAddr, lineSourceInternal, lineNo );
239
240                 containingRangeList.push_back( * downIterator );
241
242                 if ( downIterator == valuesByAddressRangeMap.begin() ) 
243                         break; 
244         }
245
246         /* We also need to look for contained ranges. */        
247         RangeIterator upIterator = rangeOfRanges.second;        
248         RangeList containedRangeList;
249
250         for (; (upIterator != valuesByAddressRangeMap.end()) 
251                         && ((lowInclusiveAddr <= upIterator->first.first)
252                                 && (upIterator->first.second < highExclusiveAddr) )
253                         ; ++upIterator ) 
254         {
255
256                 // /* DEBUG */ fprintf( stderr, "%s[%d]: found contained range [0x%lx, 0x%lx) while inserting [0x%lx, 0x%lx) (%s, %d)\n", __FILE__, __LINE__, upIterator->first.first, upIterator->first.second, lowInclusiveAddr, highExclusiveAddr, lineSourceInternal, lineNo );
257
258                 containedRangeList.push_back( * upIterator );
259         } /* end iteration looking for contained ranges */
260
261         if (containingRangeList.size() == 0 && containedRangeList.size() == 0 ) 
262         {
263                 /* insert() is amortized constant time if the new value is inserted immediately before the hint. */
264                 valuesByAddressRangeMap.insert(rangeOfRanges.second, 
265                                 std::make_pair(AddressRange(lowInclusiveAddr, 
266                                                 highExclusiveAddr), v));
267                 addressRangesByValueMap.insert( std::make_pair(v,AddressRange(lowInclusiveAddr, 
268                                                 highExclusiveAddr)));
269                 return true;
270         }
271
272         /* TODO: combine lists; if wasContaining, splitaddrlist is just highExclusiveAddr */
273
274         if (containingRangeList.size() != 0) 
275         {
276                 Offset splitAddress = highExclusiveAddr;
277
278                 /* Remove the old (containing) ranges, split them, insert the new ones. */
279                 typename RangeList::const_iterator containingIterator = containingRangeList.begin();
280
281                 for ( ; containingIterator != containingRangeList.end(); ++containingIterator ) 
282                 {
283                         AddressRange ar = containingIterator->first;
284                         Value lnt = containingIterator->second;
285
286                         // /* DEBUG */ fprintf( stderr, "%s[%d]: removing range [0x%lx, 0x%lx) (%s, %u)...\n", __FILE__, __LINE__, ar.first, ar.second, lnt.first, lnt.second );
287
288                         assert( removeByValue( valuesByAddressRangeMap, * containingIterator ) );
289                         assert( removeByValue( addressRangesByValueMap, std::make_pair( lnt, ar ) ) );
290
291                         // /* DEBUG */ fprintf( stderr, "%s[%d]: ... done removing range [0x%lx, 0%lx) (%s, %u)\n", __FILE__, __LINE__, ar.first, ar.second, lnt.first, lnt.second );
292                         // /* DEBUG */ fprintf( stderr, "%s[%d]: inserting range [0x%lx, 0x%lx) (%s, %u)\n", __FILE__, __LINE__, ar.first, splitAddress, lnt.first, lnt.second );
293
294                         valuesByAddressRangeMap.insert(std::make_pair(AddressRange(ar.first, 
295                                                         splitAddress), lnt));
296                         addressRangesByValueMap.insert( std::make_pair(lnt,AddressRange(ar.first, 
297                                                         splitAddress)));
298
299                         // /* DEBUG */ fprintf( stderr, "%s[%d]: inserting range [0x%lx, 0x%lx) (%s, %u)\n", __FILE__, __LINE__, splitAddress, ar.second, lnt.first, lnt.second );
300
301                         valuesByAddressRangeMap.insert(std::make_pair(AddressRange(splitAddress, 
302                                                         ar.second ), lnt ) );
303                         addressRangesByValueMap.insert(std::make_pair(lnt, AddressRange(splitAddress, 
304                                                         ar.second ) ) );
305                 } /* end removes/split/insert iteration */
306
307                 // /* DEBUG */ fprintf( stderr, "%s[%d]: inserting new range [0x%lx, 0x%lx) (%s, %u)\n\n", __FILE__, __LINE__, lowInclusiveAddr, highExclusiveAddr, lineSourceInternal, lineNo );
308
309                 /* Insert the new range. */
310                 valuesByAddressRangeMap.insert(std::make_pair(AddressRange(lowInclusiveAddr, 
311                                                 highExclusiveAddr ), v ) );
312                 addressRangesByValueMap.insert(std::make_pair(v, AddressRange(lowInclusiveAddr, 
313                                                 highExclusiveAddr ) ) );
314                 return true;
315         } /* end if the range to be inserted is contained by other ranges. */
316
317         if (containedRangeList.size() != 0 ) 
318         {
319                 /* We'll split the ranges at these points. */
320                 typedef std::list< Offset > AddressList;
321                 AddressList splitAddressList;
322
323                 /* Overlapping ranges overlap until a discontuity, so we only need to
324                    know about one of them. */
325
326                 typename RangeList::const_iterator containedIterator = containedRangeList.begin();
327                 Offset splitAddress = containedIterator->first.second;
328                 ++containedIterator;
329
330                 for ( ; containedIterator != containedRangeList.end(); ++containedIterator ) 
331                 {
332                         /* Is there a discontinuity? */
333
334                         if (containedIterator->first.first >= splitAddress) 
335                         {
336                                 // /* DEBUG */ fprintf( stderr, "%s[%d]: will split at 0x%lx\n", __FILE__, __LINE__, splitAddress );
337
338                                 /* If there is, our current splitAddress should be a split, */
339                                 splitAddressList.push_back( splitAddress );                             
340
341                                 /* and the high end of the next contained range will be our next split point. */
342                                 splitAddress = containedIterator->first.second;                         
343                         }
344                         else 
345                         {
346                                 splitAddress = containedIterator->first.second; 
347                         }
348                 } /* end split point determination iteration */
349
350                 // /* DEBUG */ fprintf( stderr, "%s[%d]: will split at 0x%lx\n", __FILE__, __LINE__, splitAddress );
351
352                 splitAddressList.push_back( splitAddress );
353
354                 /* Split the range to be inserted. */
355
356                 Offset lowAddress = lowInclusiveAddr;
357                 AddressList::const_iterator splitAddressIterator = splitAddressList.begin();
358                 Offset highAddress = 0;
359
360                 for ( ; splitAddressIterator != splitAddressList.end(); ++ splitAddressIterator ) 
361                 {
362                         highAddress = * splitAddressIterator;
363
364                         // /* DEBUG */ fprintf( stderr, "%s[%d]: inserting range [0x%lx, 0x%lx) (%s, %u)\n", __FILE__, __LINE__, lowAddress, highAddress, lnt.first, lnt.second );
365
366                         valuesByAddressRangeMap.insert(std::make_pair(AddressRange(lowAddress, highAddress ), v ) );
367                         addressRangesByValueMap.insert(std::make_pair(v, AddressRange(lowAddress, highAddress ) ) );
368
369                         lowAddress = highAddress;
370                 } /* end iteration to split range to be inserted. */
371
372                 // /* DEBUG */ fprintf( stderr, "%s[%d]: inserting range [0x%lx, 0x%lx) (%s, %u)\n", __FILE__, __LINE__, highAddress, highExclusiveAddr, lnt.first, lnt.second );
373
374                 valuesByAddressRangeMap.insert(std::make_pair(AddressRange( highAddress, highExclusiveAddr ), v ) );
375                 addressRangesByValueMap.insert(std::make_pair(v, AddressRange( highAddress, highExclusiveAddr ) ) );    
376
377                 /* We done did it. */
378                 return true;
379         } /* end if the range to be inserted contains other ranges. */
380
381         /* Something Terrible happened. */
382         return false;
383 } /* end addValue() */
384
385 template< class Value, class ValueRange > 
386 bool RangeLookup< Value, ValueRange >::addAddressRange( Offset lowInclusiveAddr, 
387                 Offset highExclusiveAddr, 
388                 Value v ) 
389 {
390         return addValue( v, lowInclusiveAddr, highExclusiveAddr );
391 } /* end addAddressRange() */
392
393
394 /*      We maintain the invariant that the ranges sort in the same order on
395         their low and high addresses.  In this case, we only need to search from
396         the range whose low address is the least too large down to the range
397         whose high address is the first too small to find all ranges which
398         contain the desired address.    
399  */        
400 template< class Value, class ValueRange > 
401 bool RangeLookup< Value, ValueRange >::getValues( Offset addressInRange, 
402                 std::vector< Value *> & values ) 
403 {
404         /* We can't find an address if we have no ranges. */
405         if ( valuesByAddressRangeMap.size() == 0 ) 
406                 return false;
407
408         /* Because the sort order of the low and high addresses is the same, we know every range
409            which could contain addressInRange must be below the range whose low address is one
410            larger, and above the range whose high address is the same.  We use addressInRange + 1
411            to make sure we find one past the end of a span of ranges with the same low address,
412            so we decrement the iterator to point it at the first range which could contain
413            addressInRange.  If equal_range() returns end(), then decrementing the iterator
414            ensures we start checking with a real range. */
415
416         typedef typename ValueByAddressRange::const_iterator RangeIterator;
417         std::pair< RangeIterator, RangeIterator > lowRange 
418                 = valuesByAddressRangeMap.equal_range( AddressRange( addressInRange + 1, 0 ) );
419
420         assert( lowRange.first == lowRange.second );
421         RangeIterator hHighEnd = --(lowRange.second);
422
423         /* Some implementations get stuck on valuesByAddressRangeMap.begin(), apparently. */
424
425         for ( ; hHighEnd->first.second > addressInRange && hHighEnd != valuesByAddressRangeMap.end();
426                         --hHighEnd ) 
427         {
428                 if (   (hHighEnd->first.first <= addressInRange)
429                                 && (addressInRange < hHighEnd->first.second) ) 
430                 {
431                         values.push_back( const_cast<Value *> (& hHighEnd->second) );
432                 }
433
434                 if (hHighEnd == valuesByAddressRangeMap.begin() ) 
435                         break; 
436         } /* end iteration over possible range matches. */
437
438         if ( values.size() == 0 ) 
439                 return false; 
440
441         return true;
442 } /* end getLinesFromAddress() */
443
444 template< class Value, class ValueRange > 
445 bool RangeLookup< Value, ValueRange >::getAddressRanges(Value v, 
446                 std::vector<AddressRange> &ranges) 
447 {
448         /* Look for the specified lineSource:lineNo. */
449         typedef typename AddressRangeByValue::const_iterator IteratorType;
450         std::pair< IteratorType, IteratorType > range = addressRangesByValueMap.equal_range( v );
451
452         /* If equal_range() doesn't find anything, range.first and range.second will be equal. */
453
454         if ( range.first == range.second ) 
455         {
456                 return false;
457         }
458
459         /* Otherwise, copy out the found ranges. */
460         for ( IteratorType i = range.first; i != range.second; ++i ) 
461         {
462                 //    ranges.push_back( AddressRange(i->second));
463                 ranges.push_back(i->second);
464         } /* end iteration over located address ranges. */
465
466         return true;
467 } /* end getAddressRangesFromLine() */
468
469 template< class Value, class ValueRange > 
470 typename RangeLookup< Value, ValueRange >::const_iterator RangeLookup< Value, ValueRange >::begin() const 
471 {
472         return valuesByAddressRangeMap.begin();
473 } /* end begin() */
474
475 template< class Value, class ValueRange > 
476 typename RangeLookup< Value, ValueRange >::const_iterator RangeLookup< Value, ValueRange >::end() const 
477 {
478         return valuesByAddressRangeMap.end();
479 } /* end begin() */
480
481 template< class Value, class ValueRange > 
482 RangeLookup< Value, ValueRange >::~RangeLookup() 
483 {
484 } /* end RangeLookup destructor */
485
486
487 } //  namespace SymtabAPI
488 } // namespace Dyninst
489 #endif