git.sur5r.net Git - cc65/blob - src/ca65/span.c

   1 /*****************************************************************************/
   2 /*                                                                           */
   3 /*                                  span.c                                   */
   4 /*                                                                           */
   5 /*                      A span of data within a segment                      */
   6 /*                                                                           */
   7 /*                                                                           */
   8 /*                                                                           */
   9 /* (C) 2003-2011, Ullrich von Bassewitz                                      */
  10 /*                Roemerstrasse 52                                           */
  11 /*                D-70794 Filderstadt                                        */
  12 /* EMail:         uz@cc65.org                                                */
  13 /*                                                                           */
  14 /*                                                                           */
  15 /* This software is provided 'as-is', without any expressed or implied       */
  16 /* warranty.  In no event will the authors be held liable for any damages    */
  17 /* arising from the use of this software.                                    */
  18 /*                                                                           */
  19 /* Permission is granted to anyone to use this software for any purpose,     */
  20 /* including commercial applications, and to alter it and redistribute it    */
  21 /* freely, subject to the following restrictions:                            */
  22 /*                                                                           */
  23 /* 1. The origin of this software must not be misrepresented; you must not   */
  24 /*    claim that you wrote the original software. If you use this software   */
  25 /*    in a product, an acknowledgment in the product documentation would be  */
  26 /*    appreciated but is not required.                                       */
  27 /* 2. Altered source versions must be plainly marked as such, and must not   */
  28 /*    be misrepresented as being the original software.                      */
  29 /* 3. This notice may not be removed or altered from any source              */
  30 /*    distribution.                                                          */
  31 /*                                                                           */
  32 /*****************************************************************************/
  33
  34
  35
  36 /* common */
  37 #include "hashfunc.h"
  38 #include "hashtab.h"
  39 #include "xmalloc.h"
  40
  41 /* ca65 */
  42 #include "global.h"
  43 #include "objfile.h"
  44 #include "segment.h"
  45 #include "span.h"
  46
  47
  48
  49 /*****************************************************************************/
  50 /*                                 Forwards                                  */
  51 /*****************************************************************************/
  52
  53
  54
  55 static unsigned HT_GenHash (const void* Key);
  56 /* Generate the hash over a key. */
  57
  58 static const void* HT_GetKey (const void* Entry);
  59 /* Given a pointer to the user entry data, return a pointer to the key */
  60
  61 static int HT_Compare (const void* Key1, const void* Key2);
  62 /* Compare two keys. The function must return a value less than zero if
  63  * Key1 is smaller than Key2, zero if both are equal, and a value greater
  64  * than zero if Key1 is greater then Key2.
  65  */
  66
  67
  68
  69 /*****************************************************************************/
  70 /*                                   Data                                    */
  71 /*****************************************************************************/
  72
  73
  74
  75 /* Hash table functions */
  76 static const HashFunctions HashFunc = {
  77     HT_GenHash,
  78     HT_GetKey,
  79     HT_Compare
  80 };
  81
  82 /* Span hash table */
  83 static HashTable SpanTab = STATIC_HASHTABLE_INITIALIZER (1051, &HashFunc);
  84
  85
  86
  87 /*****************************************************************************/
  88 /*                           Hash table functions                            */
  89 /*****************************************************************************/
  90
  91
  92
  93 static unsigned HT_GenHash (const void* Key)
  94 /* Generate the hash over a key. */
  95 {
  96     /* Key is a Span pointer */
  97     const Span* S = Key;
  98
  99     /* Hash over a combination of segment number, start and end */
 100     return HashInt ((S->Seg->Num << 28) ^ (S->Start << 14) ^ S->End);
 101 }
 102
 103
 104
 105 static const void* HT_GetKey (const void* Entry)
 106 /* Given a pointer to the user entry data, return a pointer to the key */
 107 {
 108     return Entry;
 109 }
 110
 111
 112
 113 static int HT_Compare (const void* Key1, const void* Key2)
 114 /* Compare two keys. The function must return a value less than zero if
 115  * Key1 is smaller than Key2, zero if both are equal, and a value greater
 116  * than zero if Key1 is greater then Key2.
 117  */
 118 {
 119     /* Convert both parameters to Span pointers */
 120     const Span* S1 = Key1;
 121     const Span* S2 = Key2;
 122
 123     /* Compare segment number, then start and end */
 124     int Res = (int)S2->Seg->Num - (int)S1->Seg->Num;
 125     if (Res == 0) {
 126         Res = (int)S2->Start - (int)S1->Start;
 127         if (Res == 0) {
 128             Res = (int)S2->End - (int)S1->End;
 129         }
 130     }
 131
 132     /* Done */
 133     return Res;
 134 }
 135
 136
 137
 138 /*****************************************************************************/
 139 /*                                   Code                                    */
 140 /*****************************************************************************/
 141
 142
 143
 144 static Span* NewSpan (Segment* Seg, unsigned long Start, unsigned long End)
 145 /* Create a new span. The segment is set to Seg, Start and End are set to the
 146  * current PC of the segment.
 147  */
 148 {
 149     /* Allocate memory */
 150     Span* S = xmalloc (sizeof (Span));
 151
 152     /* Initialize the struct */
 153     InitHashNode (&S->Node);
 154     S->Id       = ~0U;
 155     S->Seg      = Seg;
 156     S->Start    = Start;
 157     S->End      = End;
 158     S->Type     = 0;
 159
 160     /* Return the new struct */
 161     return S;
 162 }
 163
 164
 165
 166 static void FreeSpan (Span* S)
 167 /* Free a span */
 168 {
 169     xfree (S);
 170 }
 171
 172
 173
 174 static Span* MergeSpan (Span* S)
 175 /* Check if we have a span with the same data as S already. If so, free S and
 176  * return the already existing one. If not, remember S and return it.
 177  */
 178 {
 179     /* Check if we have such a span already. If so use the existing
 180      * one and free the one from the collection. If not, add the one to
 181      * the hash table and return it.
 182      */
 183     Span* E = HT_Find (&SpanTab, S);
 184     if (E) {
 185         /* If S has a type and E not, move the type */
 186         CHECK (E->Type == 0);
 187         E->Type = S->Type;
 188         S->Type = 0;
 189         /* Free S and return E */
 190         FreeSpan (S);
 191         return E;
 192     } else {
 193         /* Assign the id, insert S, then return it */
 194         S->Id = HT_GetCount (&SpanTab);
 195         HT_Insert (&SpanTab, S);
 196         return S;
 197     }
 198 }
 199
 200
 201
 202 Span* OpenSpan (void)
 203 /* Open a span for the active segment and return it. */
 204 {
 205     return NewSpan (ActiveSeg, ActiveSeg->PC, ActiveSeg->PC);
 206 }
 207
 208
 209
 210 Span* CloseSpan (Span* S)
 211 /* Close the given span. Be sure to replace the passed span by the one
 212  * returned, since the span will get deleted if it is empty or may be
 213  * replaced if a duplicate exists.
 214  */
 215 {
 216     /* Set the end offset */
 217     if (S->Start == S->Seg->PC) {
 218         /* Span is empty */
 219         FreeSpan (S);
 220         return 0;
 221     } else {
 222         /* Span is not empty */
 223         S->End = S->Seg->PC;
 224
 225         /* Check if we have such a span already. If so use the existing
 226          * one and free the one from the collection. If not, add the one to
 227          * the hash table and return it.
 228          */
 229         return MergeSpan (S);
 230     }
 231 }
 232
 233
 234
 235 void OpenSpanList (Collection* Spans)
 236 /* Open a list of spans for all existing segments to the given collection of
 237  * spans. The currently active segment will be inserted first with all others
 238  * following.
 239  */
 240 {
 241     unsigned I;
 242
 243     /* Grow the Spans collection as necessary */
 244     CollGrow (Spans, CollCount (&SegmentList));
 245
 246     /* Add the currently active segment */
 247     CollAppend (Spans, NewSpan (ActiveSeg, ActiveSeg->PC, ActiveSeg->PC));
 248
 249     /* Walk through the segment list and add all other segments */
 250     for (I = 0; I < CollCount (&SegmentList); ++I) {
 251         Segment* Seg = CollAtUnchecked (&SegmentList, I);
 252
 253         /* Be sure to skip the active segment, since it was already added */
 254         if (Seg != ActiveSeg) {
 255             CollAppend (Spans, NewSpan (Seg, Seg->PC, Seg->PC));
 256         }
 257     }
 258 }
 259
 260
 261
 262 void CloseSpanList (Collection* Spans)
 263 /* Close a list of spans. This will add new segments to the list, mark the end
 264  * of existing ones, and remove empty spans from the list.
 265  */
 266 {
 267     unsigned I, J;
 268
 269     /* Have new segments been added while the span list was open? */
 270     for (I = CollCount (Spans); I < CollCount (&SegmentList); ++I) {
 271
 272         /* Add new spans if not empty */
 273         Segment* S = CollAtUnchecked (&SegmentList, I);
 274         if (S->PC == 0) {
 275             /* Segment is empty */
 276             continue;
 277         }
 278         CollAppend (Spans, NewSpan (S, 0, S->PC));
 279     }
 280
 281     /* Walk over the spans, close open, remove empty ones */
 282     for (I = 0, J = 0; I < CollCount (Spans); ++I) {
 283
 284         /* Get the next span */
 285         Span* S = CollAtUnchecked (Spans, I);
 286
 287         /* Set the end offset */
 288         if (S->Start == S->Seg->PC) {
 289             /* Span is empty */
 290             FreeSpan (S);
 291         } else {
 292             /* Span is not empty */
 293             S->End = S->Seg->PC;
 294
 295             /* Merge duplicate spans, then insert it at the new position */
 296             CollReplace (Spans, MergeSpan (S), J++);
 297         }
 298     }
 299
 300     /* New Count is now in J */
 301     Spans->Count = J;
 302 }
 303
 304
 305
 306 void WriteSpanList (const Collection* Spans)
 307 /* Write a list of spans to the output file */
 308 {
 309     unsigned I;
 310
 311     /* We only write spans if debug info is enabled */
 312     if (DbgSyms == 0) {
 313         /* Number of spans is zero */
 314         ObjWriteVar (0);
 315     } else {
 316         /* Write the number of spans */
 317         ObjWriteVar (CollCount (Spans));
 318
 319         /* Write the spans */
 320         for (I = 0; I < CollCount (Spans); ++I) {
 321             /* Write the id of the next span */
 322             ObjWriteVar (((const Span*)CollConstAt (Spans, I))->Id);
 323         }
 324     }
 325 }
 326
 327
 328
 329 static int CollectSpans (void* Entry, void* Data)
 330 /* Collect all spans in a collection sorted by id */
 331 {
 332     /* Cast the pointers to real objects */
 333     Span* S       = Entry;
 334     Collection* C = Data;
 335
 336     /* Place the entry into the collection */
 337     CollReplaceExpand (C, S, S->Id);
 338
 339     /* Keep the span */
 340     return 0;
 341 }
 342
 343
 344
 345 void WriteSpans (void)
 346 /* Write all spans to the object file */
 347 {
 348     /* Tell the object file module that we're about to start the spans */
 349     ObjStartSpans ();
 350
 351     /* We will write scopes only if debug symbols are requested */
 352     if (DbgSyms) {
 353
 354         unsigned I;
 355
 356         /* We must first collect all items in a collection sorted by id */
 357         Collection SpanList = STATIC_COLLECTION_INITIALIZER;
 358         CollGrow (&SpanList, HT_GetCount (&SpanTab));
 359
 360         /* Walk over the hash table and fill the span list */
 361         HT_Walk (&SpanTab, CollectSpans, &SpanList);
 362
 363         /* Write the span count to the file */
 364         ObjWriteVar (CollCount (&SpanList));
 365
 366         /* Write all spans */
 367         for (I = 0; I < CollCount (&SpanList); ++I) {
 368
 369             /* Get the span and check it */
 370             const Span* S = CollAtUnchecked (&SpanList, I);
 371             CHECK (S->End > S->Start);
 372
 373             /* Write data for the span We will write the size instead of the
 374              * end offset to save some bytes, since most spans are expected
 375              * to be rather small.
 376              */
 377             ObjWriteVar (S->Seg->Num);
 378             ObjWriteVar (S->Start);
 379             ObjWriteVar (S->End - S->Start);
 380         }
 381
 382         /* Free the collection with the spans */
 383         DoneCollection (&SpanList);
 384
 385     } else {
 386
 387         /* No debug info requested */
 388         ObjWriteVar (0);
 389
 390     }
 391
 392     /* Done writing the spans */
 393     ObjEndSpans ();
 394 }
 395
 396
 397
 398