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