1 /*****************************************************************************/
5 /* A span of data within a segment */
9 /* (C) 2003-2011, Ullrich von Bassewitz */
10 /* Roemerstrasse 52 */
11 /* D-70794 Filderstadt */
12 /* EMail: uz@cc65.org */
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. */
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: */
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 */
32 /*****************************************************************************/
50 /*****************************************************************************/
52 /*****************************************************************************/
56 static unsigned HT_GenHash (const void* Key);
57 /* Generate the hash over a key. */
59 static const void* HT_GetKey (const void* Entry);
60 /* Given a pointer to the user entry data, return a pointer to the key */
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.
70 /*****************************************************************************/
72 /*****************************************************************************/
76 /* Hash table functions */
77 static const HashFunctions HashFunc = {
84 static HashTable SpanTab = STATIC_HASHTABLE_INITIALIZER (1051, &HashFunc);
88 /*****************************************************************************/
89 /* Hash table functions */
90 /*****************************************************************************/
94 static unsigned HT_GenHash (const void* Key)
95 /* Generate the hash over a key. */
97 /* Key is a Span pointer */
100 /* Hash over a combination of segment number, start and end */
101 return HashInt ((S->Seg->Num << 28) ^ (S->Start << 14) ^ S->End);
106 static const void* HT_GetKey (const void* Entry)
107 /* Given a pointer to the user entry data, return a pointer to the key */
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.
120 /* Convert both parameters to Span pointers */
121 const Span* S1 = Key1;
122 const Span* S2 = Key2;
124 /* Compare segment number, then start and end */
125 int Res = (int)S2->Seg->Num - (int)S1->Seg->Num;
127 Res = (int)S2->Start - (int)S1->Start;
129 Res = (int)S2->End - (int)S1->End;
139 /*****************************************************************************/
141 /*****************************************************************************/
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.
150 /* Allocate memory */
151 Span* S = xmalloc (sizeof (Span));
153 /* Initialize the struct */
154 InitHashNode (&S->Node);
159 S->Type = EMPTY_STRING_ID;
161 /* Return the new struct */
167 static void FreeSpan (Span* S)
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.
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.
184 Span* E = HT_Find (&SpanTab, S);
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);
192 /* Free S and return E */
196 /* Assign the id, insert S, then return it */
197 S->Id = HT_GetCount (&SpanTab);
198 HT_Insert (&SpanTab, S);
205 void SetSpanType (Span* S, const StrBuf* Type)
206 /* Set the generic type of the span to Type */
208 /* Ignore the call if we won't generate debug infos */
210 S->Type = GetStrBufId (Type);
216 Span* OpenSpan (void)
217 /* Open a span for the active segment and return it. */
219 return NewSpan (ActiveSeg, ActiveSeg->PC, ActiveSeg->PC);
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.
230 /* Set the end offset */
231 if (S->Start == S->Seg->PC) {
236 /* Span is not empty */
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.
243 return MergeSpan (S);
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
257 /* Grow the Spans collection as necessary */
258 CollGrow (Spans, CollCount (&SegmentList));
260 /* Add the currently active segment */
261 CollAppend (Spans, NewSpan (ActiveSeg, ActiveSeg->PC, ActiveSeg->PC));
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);
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));
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.
283 /* Have new segments been added while the span list was open? */
284 for (I = CollCount (Spans); I < CollCount (&SegmentList); ++I) {
286 /* Add new spans if not empty */
287 Segment* S = CollAtUnchecked (&SegmentList, I);
289 /* Segment is empty */
292 CollAppend (Spans, NewSpan (S, 0, S->PC));
295 /* Walk over the spans, close open, remove empty ones */
296 for (I = 0, J = 0; I < CollCount (Spans); ++I) {
298 /* Get the next span */
299 Span* S = CollAtUnchecked (Spans, I);
301 /* Set the end offset */
302 if (S->Start == S->Seg->PC) {
306 /* Span is not empty */
309 /* Merge duplicate spans, then insert it at the new position */
310 CollReplace (Spans, MergeSpan (S), J++);
314 /* New Count is now in J */
320 void WriteSpanList (const Collection* Spans)
321 /* Write a list of spans to the output file */
325 /* We only write spans if debug info is enabled */
327 /* Number of spans is zero */
330 /* Write the number of spans */
331 ObjWriteVar (CollCount (Spans));
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);
343 static int CollectSpans (void* Entry, void* Data)
344 /* Collect all spans in a collection sorted by id */
346 /* Cast the pointers to real objects */
348 Collection* C = Data;
350 /* Place the entry into the collection */
351 CollReplaceExpand (C, S, S->Id);
359 void WriteSpans (void)
360 /* Write all spans to the object file */
362 /* Tell the object file module that we're about to start the spans */
365 /* We will write scopes only if debug symbols are requested */
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));
374 /* Walk over the hash table and fill the span list */
375 HT_Walk (&SpanTab, CollectSpans, &SpanList);
377 /* Write the span count to the file */
378 ObjWriteVar (CollCount (&SpanList));
380 /* Write all spans */
381 for (I = 0; I < CollCount (&SpanList); ++I) {
383 /* Get the span and check it */
384 const Span* S = CollAtUnchecked (&SpanList, I);
385 CHECK (S->End > S->Start);
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.
391 ObjWriteVar (S->Seg->Num);
392 ObjWriteVar (S->Start);
393 ObjWriteVar (S->End - S->Start);
394 ObjWriteVar (S->Type);
397 /* Free the collection with the spans */
398 DoneCollection (&SpanList);
402 /* No debug info requested */
407 /* Done writing the spans */