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
56static unsigned HT_GenHash (const void* Key);
57/* Generate the hash over a key. */
58
59static const void* HT_GetKey (const void* Entry);
60/* Given a pointer to the user entry data, return a pointer to the key */
61
62static 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 */
77static const HashFunctions HashFunc = {
78 HT_GenHash,
79 HT_GetKey,
80 HT_Compare
81};
82
83/* Span hash table */
84static HashTable SpanTab = STATIC_HASHTABLE_INITIALIZER (1051, &HashFunc);
85
86
87
88/*****************************************************************************/
89/* Hash table functions */
90/*****************************************************************************/
91
92
93
94static 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
106static 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
114static 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
145static 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
167static void FreeSpan (Span* S)
168/* Free a span */
169{
170 xfree (S);
171}
172
173
174
175static 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
205void 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
216Span* 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
224Span* 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
249void 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
276void 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
320void 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
343static 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
359void 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