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 | |