some modifications for teh code to be compiled in
[dyninst.git] / dyninstAPI / src / LineInformation.C
1 #include <stdlib.h>
2
3 #include "dyninstAPI/src/LineInformation.h"
4 #include "dyninstAPI/src/util.h"
5
6 typedef FileLineInformation::tuple tuple;
7
8 //this function implements binary search and returns the found element.
9 //besides the found element it returns the next bigger line numbered one
10 //The found element is the first same values element in the array in existence
11 //of many same values elements.
12 //in case it is not found it will RETURN NULL. if the next element
13 //is not available it will assign NULL to the reference.
14 //the next contains the entry with the first greater line number
15 tuple* binarySearchLineFirst(tuple element,tuple* array,int howMany,tuple*& next)
16 {
17         int low = 0;
18         int high = howMany-1;
19         int mid;
20         tuple* ret=NULL;
21         do{
22                 mid = (low+high)/2;
23                 if(element.lineNo < array[mid].lineNo) 
24                         high = mid - 1;
25                 else if(element.lineNo > array[mid].lineNo)
26                         low = mid + 1;
27                 else
28                         break;
29         }while(low <= high);
30
31         //if found then porepare to return and the next available
32         if(element.lineNo == array[mid].lineNo){
33                 int index = mid;
34                 for(;(index >= 0)&&(array[index].lineNo == element.lineNo);index--);
35                 ret = array+(index+1);
36                 index = mid;
37                 for(;(index < howMany)&&(array[index].lineNo == element.lineNo);index++);
38                 if(index == howMany)
39                         next = NULL;
40                 else
41                         next = array+index;
42         }
43         else if(low == howMany)
44                 next = NULL;
45         else
46                 next = array+low;
47
48         return ret;
49 }
50 //this function implements binary search and returns the found element.
51 //besides the found element it returns the previous smaller address entry
52 //The found element is the first same values element in the array in existence
53 //of many same values elements.
54 //in case it is not found it will RETURN NULL. if the next element
55 //is not available it will assign NULL to the reference.
56 //the next contains the entry with the previous smaller address
57 tuple* binarySearchAddrFirst(tuple element,tuple* array,int howMany,tuple*& next)
58 {
59         int low = 0;
60         int high = howMany-1;
61         int mid;
62         tuple* ret=NULL;
63         do{
64                 mid = (low+high)/2;
65                 if(element.codeAddress < array[mid].codeAddress) 
66                         high = mid - 1;
67                 else if(element.codeAddress > array[mid].codeAddress)
68                         low = mid + 1;
69                 else
70                         break;
71         }while(low <= high);
72
73         ////if found then porepare to return and the next available
74         if(element.codeAddress == array[mid].codeAddress){
75                 int index = mid;
76                 for(;(index>=0)&&(array[index].codeAddress == element.codeAddress);index--);
77                 ret = array+(index+1);
78                 if(index == -1)
79                         next = NULL;
80                 else{
81                         Address addr = array[index].codeAddress;
82                         for(;(index>=0) && (array[index].codeAddress == addr);index--);
83                         next = array+(index+1);
84                 }
85         }
86         else if(high == -1)
87                 next = NULL;
88         else{
89                 Address addr = array[high].codeAddress;
90                 for(;(high >=0) && (array[high].codeAddress == addr);high--);
91                 next = array+(high+1);
92         }
93         return ret;
94 }
95
96 //constructor
97 FileLineInformation::FileLineInformation(string fileName)
98         : sourceFileName(fileName),
99           size(0),
100           lineToAddr(NULL),
101           addrToLine(NULL),
102           functionCount(0),
103           functionNameList(NULL),
104           lineInformationList(NULL) {}
105
106 //destructor
107 FileLineInformation::~FileLineInformation(){
108         delete[] lineToAddr;
109         delete[] addrToLine;
110         for(int i=0;i<functionCount;i++){
111                 delete lineInformationList[i];
112                 delete functionNameList[i];
113         }
114         delete[] functionNameList;
115         delete[] lineInformationList;
116 }
117
118 //returns the function info structure
119 FileLineInformation::FunctionInfo* 
120 FileLineInformation::findFunctionInfo(string functionName){
121         for(int i=0;i<functionCount;i++)
122                 if(functionName == *functionNameList[i])
123                         return lineInformationList[i];
124         return NULL;
125 }
126
127 //inserts function wntry to the mapping from function name to its info
128 void FileLineInformation::insertFunction(string functionName){
129         FunctionInfo* fInfo = findFunctionInfo(functionName);
130         if(!fInfo){
131                 functionNameList = (string**)(functionCount ? 
132                         realloc(functionNameList,(functionCount+1)*sizeof(string*)) : 
133                         new string*[1]);
134                 lineInformationList = (FunctionInfo**)(functionCount ? 
135                         realloc(lineInformationList,(functionCount+1)*sizeof(FunctionInfo*)) : 
136                         new FunctionInfo*[1]);
137                 functionNameList[functionCount] = new string(functionName);
138                 lineInformationList[functionCount] = new FunctionInfo;
139                 functionCount++;
140         }       
141 }
142
143 //returns true if the function has an entry in the mapping
144 bool FileLineInformation::findFunction(string functionName){
145         FunctionInfo* fInfo = findFunctionInfo(functionName);
146         if(!fInfo) return false;
147         return true;
148 }
149
150
151 //insert a mapping from line number to address and address to line number
152 //to the corresponding structures and updates the records for the function
153 //given
154 void FileLineInformation::insertLineAddress(string functionName,
155                                             unsigned short lineNo,
156                                             Address codeAddress)
157 {
158
159         FunctionInfo* fInfo = findFunctionInfo(functionName);
160         if(!fInfo){
161                 cerr << "FATAL ERROR : Something wrong \n";
162                 return;
163         }
164
165         lineToAddr = !lineToAddr ? ((tuple*)malloc(sizeof(tuple))) :
166                      ((tuple*)realloc(lineToAddr,sizeof(tuple)*(size+1)));
167         addrToLine = !addrToLine ? ((tuple*)malloc(sizeof(tuple))) :
168                      ((tuple*)realloc(addrToLine,sizeof(tuple)*(size+1)));
169
170         //since the entries will come in oreder insertion sort is the best sort here
171         //to keep the list sorted and using binary search to find the entries.
172         //insertion sort comes here
173
174         short index1; 
175         for(index1=size-1;index1>=0;index1--)
176                 if(lineToAddr[index1].lineNo > lineNo)
177                         lineToAddr[index1+1] = lineToAddr[index1];
178                 else break;
179         index1++;
180         lineToAddr[index1] = tuple(lineNo,codeAddress);
181
182         short index2; 
183         //insertion sort for code address
184
185         for(index2=size-1;index2>=0;index2--)
186                 if(addrToLine[index2].codeAddress > codeAddress)
187                         addrToLine[index2+1] = addrToLine[index2];
188                 else break;
189         index2++;
190         addrToLine[index2] = tuple(lineNo,codeAddress);
191
192         size++;
193
194         if(!fInfo->validInfo){
195                 fInfo->startLinePtr = (unsigned)index1;
196                 fInfo->endLinePtr = (unsigned)index1;
197                 fInfo->startAddrPtr = (unsigned)index2;
198                 fInfo->endAddrPtr = (unsigned)index2;
199                 fInfo->validInfo = true;
200                 return;
201         }
202
203         if(lineToAddr[fInfo->startLinePtr].lineNo > lineNo)
204                 fInfo->startLinePtr = (unsigned)index1;
205         if(lineToAddr[fInfo->endLinePtr].lineNo <= lineNo)
206                 fInfo->endLinePtr = (unsigned)index1;
207
208         if(addrToLine[fInfo->startAddrPtr].codeAddress > codeAddress)
209                 fInfo->startAddrPtr = (unsigned)index2;
210         if(addrToLine[fInfo->endAddrPtr].codeAddress <= codeAddress)
211                 fInfo->endAddrPtr = (unsigned)index2;
212
213 }
214  
215 //returns true in case of success, false otherwise.
216 //this method finds the line number corresponding to an address.
217 //if name of the function is supplied and isFile is false
218 //then function level search is being applied. Otherwise file level
219 //search is applied. If there are more than 1 line found than
220 //the maximum is being returned.
221 bool FileLineInformation::getLineFromAddr(string name,unsigned short& lineNo,
222                                           Address codeAddress,bool isFile,
223                                           bool isExactMatch)
224 {
225         BPatch_Set<unsigned short> lines;
226         if(!getLineFromAddr(name,lines,codeAddress,isFile,isExactMatch))
227                 return false;
228         lineNo = lines.maximum();
229         return true;
230 }
231 //returns true in case of success, false otherwise.
232 //this method finds the line numbers corresponding to an address.
233 //if name of the function is supplied and isFile is false
234 //then function level search is being applied. Otherwise file level
235 //search is applied. All the line numbers corresponding to the address
236 //is returned in a set of addresses.
237 bool FileLineInformation::getLineFromAddr(string name,
238                                           BPatch_Set<unsigned short>& lines,
239                                           Address codeAddress,bool isFile,
240                                           bool isExactMatch)
241 {
242         tuple* beginPtr;
243         tuple* endPtr;
244         int howMany;
245
246         if(!addrToLine)
247                 return false;
248         if(isFile){
249                 beginPtr = addrToLine;
250                 endPtr = (tuple*) (addrToLine+(size-1));
251                 howMany = size;
252         }
253         else{
254                 FunctionInfo* fInfo = findFunctionInfo(name);
255                 if(!fInfo)
256                         return false;
257                 if(!fInfo->validInfo)
258                         return false;
259                 beginPtr = addrToLine+fInfo->startAddrPtr;
260                 endPtr = addrToLine+fInfo->endAddrPtr;
261                 howMany = fInfo->endAddrPtr-fInfo->startAddrPtr+1;
262         }
263
264         if((codeAddress < beginPtr->codeAddress) || (endPtr->codeAddress < codeAddress))
265                 return false;
266
267         tuple toSearch(0,codeAddress);
268         tuple* next=NULL;
269         tuple* ret = binarySearchAddrFirst(toSearch,beginPtr,howMany,next);
270         if(!ret){
271                 if(isExactMatch)
272                         return false;
273                 if(!next)
274                         return false;
275                 ret = next;
276                 codeAddress = ret->codeAddress;
277         }
278         do{
279                 lines += ret->lineNo;
280                 ret++;
281         }while((ret <= endPtr) && (ret->codeAddress == codeAddress));
282
283         return true;
284 }
285
286 //method that retuns set of addresses corresponding to a given line number
287 //the level of the search is file level if isFile flag is set.
288 //If isFile level is not set, it seraches in the given function
289 //in case of success it returns true otherwise false
290 bool FileLineInformation::getAddrFromLine(string name,
291                                           BPatch_Set<Address>& codeAddress,
292                                           unsigned short lineNo,bool isFile,
293                                           bool isExactMatch)
294 {
295         tuple* beginPtr;
296         tuple* endPtr;
297         int howMany;
298
299         if(!lineToAddr)
300                 return false;
301         if(isFile){
302                 beginPtr = lineToAddr;
303                 endPtr = (tuple*) (lineToAddr+(size-1));
304                 howMany = size;
305         }
306         else{
307                 FunctionInfo* fInfo = findFunctionInfo(name);
308                 if(!fInfo)
309                         return false;
310                 if(!fInfo->validInfo)
311                         return false;
312                 beginPtr = lineToAddr+fInfo->startLinePtr;
313                 endPtr = lineToAddr+fInfo->endLinePtr;
314                 howMany = fInfo->endLinePtr-fInfo->startLinePtr+1;
315         }
316         if(!isFile && 
317            (lineNo < beginPtr->lineNo) || (endPtr->lineNo < lineNo))
318                 return false;
319
320         tuple toSearch(lineNo,0);
321         tuple* next=NULL;
322         tuple* ret = binarySearchLineFirst(toSearch,beginPtr,howMany,next);
323         if(!ret){
324                 if(isExactMatch)
325                         return false;
326                 if(!next)
327                         return false;
328                 ret = next;
329                 lineNo = ret->lineNo;
330         }
331         do{
332                 codeAddress += ret->codeAddress;
333                 ret++;
334         }while((ret <= endPtr) && (ret->lineNo == lineNo));
335
336         return true;
337 }
338
339 //temporary function to print info about line information
340 void FileLineInformation::print(){
341         cerr << "LINE TO ADDRESS :\n";
342         for(int j=0;j<size;j++)
343                 cerr << dec << lineToAddr[j].lineNo << " ----> " << hex << lineToAddr[j].codeAddress << "\n";
344         for(int i=0;i<functionCount;i++){
345                 FunctionInfo* funcinfo = lineInformationList[i];
346                 cerr << "FUNCTION LINE : " << *functionNameList[i] << " : " ;
347                 if(!funcinfo->validInfo)
348                         continue;
349                 cerr << dec << lineToAddr[funcinfo->startLinePtr].lineNo ;
350                 cerr << " --- " << dec << lineToAddr[funcinfo->endLinePtr].lineNo << "\n";
351         }
352         
353 }
354
355 //constructor whose argument is the name of the module name
356 LineInformation::LineInformation(string mName) 
357                 : moduleName(mName),
358                   sourceFileCount(0),
359                   sourceFileList(NULL),
360                   lineInformationList(NULL) {}
361
362
363 //desctructor
364 LineInformation::~LineInformation() {
365         for(int i=0;i<sourceFileCount;i++){
366                 delete sourceFileList[i];
367                 delete lineInformationList[i];
368         }
369         delete[] sourceFileList;
370         delete[] lineInformationList;
371 }
372
373 //method to insert entries for the given file name and function name
374 //it creates the necessary structures and inserts into the maps
375 void LineInformation::insertSourceFileName(string functionName,string fileName)
376 {
377         FileLineInformation* fInfo = getFileLineInformation(fileName);
378         if(!fInfo){
379                 fInfo = new FileLineInformation(fileName);
380                 sourceFileList = (string**)(sourceFileCount ? 
381                         realloc(sourceFileList,(sourceFileCount+1)*sizeof(string*)) : 
382                         new string*[1]);
383                 lineInformationList = (FileLineInformation**)(sourceFileCount ? 
384                         realloc(lineInformationList,(sourceFileCount+1)*sizeof(FileLineInformation*)) : 
385                         new FileLineInformation*[1]);
386                 sourceFileList[sourceFileCount] = new string(fileName);
387                 lineInformationList[sourceFileCount] = fInfo;
388                 sourceFileCount++;
389         }
390         fInfo->insertFunction(functionName);
391 }
392
393 //inserts line to address and address to line mapping to the line info
394 //object of the given filename. The records for function is also updated
395 void LineInformation::insertLineAddress(string functionName,
396                                         string fileName,
397                                         unsigned short lineNo,
398                                         Address codeAddress)
399 {
400         FileLineInformation* fInfo = getFileLineInformation(fileName);
401         if(!fInfo) return;
402         fInfo->insertLineAddress(functionName,lineNo,codeAddress);
403 }
404
405 //returns line number corresponding to the the given address
406 //if isFile is set the search is file level otherwsie function level.
407 bool LineInformation::getLineFromAddr(string name,
408                                       unsigned short& lineNo,
409                                       Address codeAddress,
410                                       bool isFile,
411                                       bool isExactMatch)
412 {
413         FileLineInformation* fInfo = NULL;
414         if(isFile) 
415                 fInfo = getFileLineInformation(name);
416         else
417                 fInfo = getFunctionLineInformation(name);
418                 
419         if(!fInfo) return false;
420         
421         return fInfo->getLineFromAddr(name,lineNo,codeAddress,isFile,isExactMatch);
422 }
423
424 //returns line number corresponding to the the given address
425 //if isFile is set the search is file level otherwsie function level.
426 bool LineInformation::getLineFromAddr(string name,
427                                       BPatch_Set<unsigned short>& lines,
428                                       Address codeAddress,
429                                       bool isFile,
430                                       bool isExactMatch)
431 {
432         FileLineInformation* fInfo = NULL;
433         if(isFile) 
434                 fInfo = getFileLineInformation(name);
435         else
436                 fInfo = getFunctionLineInformation(name);
437                 
438         if(!fInfo) return false;
439         
440         return fInfo->getLineFromAddr(name,lines,codeAddress,isFile,isExactMatch);
441 }
442
443 //returns address corresponding to the the given line 
444 //if isFile is set the search is file level otherwsie function level.
445 bool LineInformation::getAddrFromLine(string name,
446                                       BPatch_Set<Address>& codeAddress,
447                                       unsigned short lineNo,
448                                       bool isFile,
449                                       bool isExactMatch)
450 {
451         FileLineInformation* fInfo = NULL;
452         if(isFile) 
453                 fInfo = getFileLineInformation(name);
454         else
455                 fInfo = getFunctionLineInformation(name);
456                 
457         if(!fInfo) return false;
458
459         return fInfo->getAddrFromLine(name,codeAddress,lineNo,isFile,isExactMatch);
460 }
461
462 bool LineInformation::getAddrFromLine(BPatch_Set<Address>& codeAddress,
463                                       unsigned short lineNo,
464                                       bool isExactMatch)
465 {
466         FileLineInformation* fInfo = getFileLineInformation(moduleName);
467         if(!fInfo){ 
468 #ifdef DEBUG_LINE
469                 cerr << "Module " << moduleName << " is not source file name\n";
470 #endif
471                 return false;
472         }
473         return fInfo->getAddrFromLine(moduleName,codeAddress,
474                                       lineNo,true,isExactMatch);
475 }
476
477 //returns the line information for the given filename
478 FileLineInformation* LineInformation::getFileLineInformation(string fileName){
479         for(int j=0;j<sourceFileCount;j++)
480                 if(fileName == *sourceFileList[j])
481                         return lineInformationList[j];
482         for(int i=0;i<sourceFileCount;i++){
483                 char* name = new char[sourceFileList[i]->length()+1];
484                 strncpy(name,sourceFileList[i]->string_of(),
485                         sourceFileList[i]->length());
486                 name[sourceFileList[i]->length()] = '\0';
487                 char* p = strrchr(name,'/');
488                 if(!p) {
489                         delete[] name;
490                         continue;
491                 }
492                 p++;
493                 string sname(p);
494                 if(fileName == sname){
495                         delete[] name;
496                         return lineInformationList[i];
497                 }
498                 delete[] name;
499         }
500                 
501         return NULL;
502
503
504 //method retuns the file line information object which the function belongs to.
505 //if there is no entry than it retuns NULL
506 FileLineInformation* 
507 LineInformation::getFunctionLineInformation(string functionName){
508         for(int i=0;i<sourceFileCount;i++)
509                 if(lineInformationList[i]->findFunction(functionName))
510                         return lineInformationList[i];
511         return NULL;
512
513
514 //method that returns true if function belongs to this object
515 //false otherwise
516 bool LineInformation::findFunction(string functionName){
517         bool ret = false;
518         for(int i=0;!ret && (i<sourceFileCount);i++)
519                 ret = lineInformationList[i]->findFunction(functionName);
520         return ret;
521 }
522
523 //print the line information kept in the map
524 void LineInformation::print(){
525         cerr << "**********************************************\n";
526         cerr << "MODULE : " << moduleName << "\n";  
527         cerr << "**********************************************\n";
528         for(int i=0;i<sourceFileCount;i++){
529                 cerr << "FILE : " << *sourceFileList[i] << "\n";
530                 lineInformationList[i]->print();
531         }
532 }
533