Systemnahe Programmierung in C: Verkettete Listen
| Systemnahe Programmierung in C: Verkettete Listen |
|
|
|
1#ifndef LIST_H__
2#define LIST_H__ 1
3
4/*--------------------*/
5
6#include <string.h>
7
8typedef char * Element;
9
10#define eqElement(x,y) (strcmp((x),(y)) == 0)
11#define geElement(x,y) (strcmp((x),(y)) >= 0)
12
13/*--------------------*/
14
15typedef struct Node *List;
16
17struct Node
18{
19 List next; /* alignment within structs */
20 Element info; /* next is 1. field (!?) */
21};
22
23
24/*--------------------*/
25
26#if MACROS
27
28#define mkEmptyList() ((List)0)
29#define isEmptyList(l) ((l) == (List)0)
30#define head(l) ((l)->info)
31#define tail(l) ((l)->next)
32
33#else
34
35extern List mkEmptyList(void);
36extern int isEmptyList(List l);
37extern Element head(List l);
38extern List tail(List l);
39
40#endif
41
42/*--------------------*/
43
44extern List cons(Element e, List l);
45
46extern unsigned int length(List l);
47
48extern Element at(List l,
49 unsigned int i);
50
51extern int isInList(Element e, List l);
52
53extern List insertElem(Element e,
54 List l);
55
56extern List removeHead(List l);
57
58extern List removeElem(Element e,
59 List l);
60
61extern List removeAllElems(Element e,
62 List l);
63
64extern List concat(List l1, List l2);
65
66extern List append(List l, Element e);
67
68extern List splitAt(List l,
69 unsigned int i,
70 List * rest);
71
72extern List removeAt(List l,
73 unsigned int i);
74
75extern List insertAt(List l,
76 unsigned int i,
77 Element e);
78
79extern List Union(List l1, List l2);
80
81/*--------------------*/
82
83/* consistency check for sorted lists */
84
85#if ! SORTED && DUPLICATES
86
87#define invList(l) 1
88
89#else
90
91extern int invList(List l);
92
93#endif
94
95/*--------------------*/
96
97/* space performance measurements */
98
99extern unsigned spaceUsed(List l);
100
101extern unsigned spaceNecc(List l);
102
103extern double spaceOverhead(List l);
104
105/*--------------------*/
106
107#endif
|
|
1/*--------------------*/
2
3#include <stdlib.h>
4#include <stdio.h>
5#include <assert.h>
6
7#include "List.h"
8
9/*--------------------*/
10
11/* simple ops as functions */
12
13#if ! MACROS
14
15List
16mkEmptyList(void)
17{
18 return (List) 0;
19}
20
21/*--------------------*/
22
23int
24isEmptyList(List l)
25{
26 return l == (List) 0;
27}
28
29/*--------------------*/
30
31Element
32head(List l)
33{
34 assert(! isEmptyList(l));
35 return l->info;
36}
37
38/*--------------------*/
39
40List
41tail(List l)
42{
43 assert(! isEmptyList(l));
44 return l->next;
45}
46
47#endif
48
49/*--------------------*/
50
51List
52removeHead(List l)
53{
54 assert(! isEmptyList(l));
55 {
56 List res = l->next;
57 free(l);
58 return res;
59 }
60}
61
62List
63cons(Element e, List l)
64{
65 /* the only call of malloc */
66 List res = malloc(sizeof(*l));
67
68 if (! res)
69 {
70 perror("cons: malloc failed");
71 exit(1);
72 }
73 res->info = e;
74 res->next = l;
75
76 return res;
77}
78
79/*--------------------*/
80
81#if ! ITERATIVE
82
83unsigned int
84length(List l)
85{
86 return isEmptyList(l)
87 ? 0
88 : 1 + length(tail(l));
89}
90
91/*--------------------*/
92
93#else
94
95unsigned int
96length(List l)
97{
98 unsigned int res;
99
100 for (res = 0; ! isEmptyList(l);
101 l = l->next)
102 ++res;
103
104 return res;
105}
106
107#endif
108
109/*--------------------*/
110
111#if ! ITERATIVE
112
113Element
114at(List l, unsigned int i)
115{
116 return i == 0
117 ? head(l)
118 : at(tail(l), i - 1);
119}
120
121/*--------------------*/
122
123#else
124
125Element
126at(List l, unsigned int i)
127{
128 while (i != 0)
129 {
130 l = tail(l);
131 --i;
132 }
133 return head(l);
134}
135
136#endif
137
138/*--------------------*/
139
140#if ! ITERATIVE
141
142int
143isInList(Element e, List l)
144{
145 if (isEmptyList(l))
146 return 0;
147
148 if (eqElement(e, l->info))
149 return 1;
150
151#if SORTED
152 if (! geElement(e, l->info))
153 return 0;
154#endif
155
156 return isInList(e, l->next);
157}
158
159/*--------------------*/
160
161#else
162
163int
164isInList(Element e, List l)
165{
166 while (! isEmptyList(l)
167#if SORTED
168 &&
169 geElement(e, l->info)
170#endif
171 )
172 {
173 if (eqElement(e, l->info))
174 return 1;
175 l = l->next;
176 }
177 return 0;
178}
179
180#endif
181
182/*--------------------*/
183
184#if ! SORTED
185
186List
187insertElem(Element e, List l)
188{
189#if DUPLICATES
190 return cons(e, l);
191
192#else
193
194 return isInList(e, l)
195 ? l
196 : cons(e, l);
197#endif
198}
199
200/*--------------------*/
201
202#else
203/* sorted list */
204
205#if ! ITERATIVE
206
207List
208insertElem(Element e, List l)
209{
210 if (isEmptyList(l)
211 ||
212 ! geElement(e, l->info))
213 return cons(e, l);
214
215#if ! DUPLICATES
216 if (eqElement(e, l->info))
217 return l;
218#endif
219
220 l->next = insertElem(e, l->next);
221 return l;
222}
223
224/*--------------------*/
225
226#else
227
228List
229insertElem(Element e, List l)
230{
231 List *pl = &l;
232
233 while (! isEmptyList(*pl)
234 &&
235 ! geElement((*pl)->info, e))
236 {
237 pl = &((*pl)->next);
238 }
239
240#if ! DUPLICATES
241 if (! isEmptyList(*pl)
242 && eqElement(e, (*pl)->info))
243 return l;
244#endif
245
246 *pl = cons(e, *pl);
247 return l;
248}
249#endif
250
251#endif
252
253/*--------------------*/
254
255static List
256removeElem1(Element e, List l)
257{
258 if (isEmptyList(l))
259 return l;
260
261#if SORTED
262 if (! geElement(e, l->info))
263 return l;
264#endif
265
266 if (eqElement(e, l->info))
267 {
268 return
269 removeHead(l);
270 }
271
272 l->next = removeElem1(e, l->next);
273 return l;
274}
275
276/*--------------------*/
277
278/* a save version of removeElem */
279
280List
281removeElem(Element e, List l)
282{
283 List res = removeElem1(e, l);
284
285 assert(invList(res));
286 return res;
287}
288
289/*--------------------*/
290
291static List
292removeAllElems1(Element e, List l)
293{
294 if (isEmptyList(l))
295 return l;
296
297#if SORTED
298 if (! geElement(e, l->info))
299 return l;
300#endif
301
302 if (eqElement(e, l->info))
303 {
304 return
305 removeAllElems1(e, removeHead(l));
306 }
307
308 l->next = removeAllElems1(e, l->next);
309 return l;
310}
311
312/*--------------------*/
313
314/* a save version of removeAllElems */
315
316List
317removeAllElems(Element e, List l)
318{
319 List res = removeAllElems1(e, l);
320
321 assert(invList(res));
322 assert(! isInList(e, res));
323 return res;
324}
325
326/*--------------------*/
327
328List
329concat(List l1, List l2) {
330 if ( isEmptyList(l1) )
331 return l2;
332
333 l1->next = concat(l1->next, l2);
334 return l1;
335}
336
337List
338append(List l, Element e) {
339 return
340 concat(l,
341 cons(e, mkEmptyList()));
342}
343
344/*--------------------*/
345
346List
347splitAt(List l,
348 unsigned int i,
349 List * rest) {
350 if (i == 0) {
351 * rest = l;
352 return mkEmptyList();
353 }
354 l->next = splitAt(tail(l),
355 i-1,
356 rest);
357 return l;
358}
359
360List
361removeAt(List l,
362 unsigned int i) {
363 if (i == 0) {
364 return removeHead(l);
365 }
366 l->next = removeAt(tail(l),
367 i-1);
368 return l;
369}
370
371List
372insertAt(List l,
373 unsigned int i,
374 Element e) {
375 if (i == 0) {
376 return cons(e, l);
377 }
378 l->next = insertAt(tail(l),
379 i-1,
380 e);
381 return l;
382}
383
384/*--------------------*/
385
386List
387Union(List l1, List l2) {
388#if ! SORTED
389
390#if ! DUPLICATES
391
392 if ( isEmptyList(l1) )
393 return l2;
394 l2 = insertElem(l1->info, l2);
395 return Union(removeHead(l1), l2);
396
397#else
398
399 return concat(l1, l2);
400
401#endif
402
403#else
404
405 if ( isEmptyList(l1) )
406 return l2;
407
408 if ( isEmptyList(l2) )
409 return l1;
410
411#if ! DUPLICATES
412 if ( eqElement(l1->info, l2->info) )
413 return Union(removeHead(l1), l2);
414#endif
415
416 if ( geElement(l1->info, l2->info) ) {
417 l2->next = Union(l1, l2->next);
418 return l2;
419 } else {
420 l1->next = Union(l1->next, l2);
421 return l1;
422 }
423
424#endif
425}
426
427/*--------------------*/
428
429/* Invariant for sorted lists */
430
431#if SORTED
432
433int
434invList(List l)
435{
436 if (isEmptyList(l))
437 return 1;
438
439 if (isEmptyList(l->next))
440 return 1;
441
442#if ! DUPLICATES
443 if (eqElement(l->info, l->next->info))
444 return 0;
445#endif
446
447 return
448 geElement(l->next->info, l->info)
449 &&
450 invList(l->next);
451}
452
453#else
454
455#if DUPLICATES
456
457int
458invList(List l)
459{
460 if (isEmptyList(l))
461 return 1;
462
463 return
464 ! isInList(l->info, l->next)
465 &&
466 invList(l->next);
467}
468
469
470#endif
471
472#endif
473
474/*--------------------*/
475
476unsigned spaceUsed(List l)
477{
478 return length(l) * sizeof (*l);
479}
480
481unsigned spaceNecc(List l)
482{
483 return length(l) * sizeof (l->info);
484}
485
486double spaceOverhead(List l)
487{
488 return
489 (double)spaceUsed(l) /
490 (double)spaceNecc(l);
491}
492
493/*--------------------*/
|
SRC = List.c
TESTS =
include ../rules.mk
help :
##all_variants
## make all_variants targets
## for normal version: all
## without debug: ndebug
## and for iterative versions: iterative
all_variants :
$(MAKE) clean all
$(MAKE) clean macros
$(MAKE) clean iterative
$(MAKE) clean dups
$(MAKE) clean sorted
$(MAKE) clean sorteddups
$(MAKE) clean iterativesorted
$(MAKE) clean iterativesorteddups
all : asm $(TESTS)
##ass
## assembler examples
asm :
$(MAKE) $(OASS) $(O2ASS) CCFLAGS='$(CCFLAGS) -DMACROS=1 -DNDEBUG=1'
##ndebug
## compile without assertions
ndebug :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DNDEBUG=1'
##macros
## compile with macros and without assertions
macros :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DMACROS=1 -DNDEBUG=1'
##iterative
## compile with iterative functions
iterative :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DNDEBUG=1 -DITERATIVE=1'
##duplicates
## compile with duplictes
dups :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DDUPLICATES=1'
##sorted
## compile for sorted linked list
sorted :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DSORTED=1'
##sorteddups
## compile for sorted linked list with duplicates
sorteddups :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DSORTED=1 -DDUPLICATES'
##iterativesorted
## compile iterative versions for sorted linked list
iterativesorted :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DSORTED=1 -DITERATIVE=1'
##iterativesorteddups
## compile iterative versions for sorted linked list with duplicates
iterativesorteddups :
$(MAKE) all CCFLAGS='$(CCFLAGS) -DSORTED=1 -DITERATIVE=1 -DITERATIVE=1'
|
1 removeHead:
2 pushq %rbx
3 movq (%rdi), %rbx
4 call free
5 movq %rbx, %rax
6 popq %rbx
7 ret
8 removeAllElems1:
9 movq %rbx, -16(%rsp)
10 movq %rbp, -8(%rsp)
11 subq $24, %rsp
12 movq %rsi, %rbx
13 testq %rsi, %rsi
14 je .L4
15 movq %rdi, %rbp
16 movq 8(%rsi), %rsi
17 call strcmp
18 testl %eax, %eax
19 jne .L5
20 movq %rbx, %rdi
21 call removeHead
22 movq %rax, %rsi
23 movq %rbp, %rdi
24 call removeAllElems1
25 movq %rax, %rbx
26 jmp .L4
27 .L5:
28 movq (%rbx), %rsi
29 movq %rbp, %rdi
30 call removeAllElems1
31 movq %rax, (%rbx)
32 .L4:
33 movq %rbx, %rax
34 movq 8(%rsp), %rbx
35 movq 16(%rsp), %rbp
36 addq $24, %rsp
37 ret
38 removeElem1:
39 movq %rbx, -16(%rsp)
40 movq %rbp, -8(%rsp)
41 subq $24, %rsp
42 movq %rsi, %rbx
43 testq %rsi, %rsi
44 je .L8
45 movq %rdi, %rbp
46 movq 8(%rsi), %rsi
47 call strcmp
48 testl %eax, %eax
49 jne .L9
50 movq %rbx, %rdi
51 call removeHead
52 movq %rax, %rbx
53 jmp .L8
54 .L9:
55 movq (%rbx), %rsi
56 movq %rbp, %rdi
57 call removeElem1
58 movq %rax, (%rbx)
59 .L8:
60 movq %rbx, %rax
61 movq 8(%rsp), %rbx
62 movq 16(%rsp), %rbp
63 addq $24, %rsp
64 ret
65 cons:
66 movq %rbx, -16(%rsp)
67 movq %rbp, -8(%rsp)
68 subq $24, %rsp
69 movq %rdi, %rbp
70 movq %rsi, %rbx
71 movl $16, %edi
72 call malloc
73 testq %rax, %rax
74 jne .L12
75 movl $.LC0, %edi
76 call perror
77 movl $1, %edi
78 call exit
79 .L12:
80 movq %rbp, 8(%rax)
81 movq %rbx, (%rax)
82 movq 8(%rsp), %rbx
83 movq 16(%rsp), %rbp
84 addq $24, %rsp
85 ret
86 length:
87 movl $0, %eax
88 testq %rdi, %rdi
89 je .L19
90 subq $8, %rsp
91 movq (%rdi), %rdi
92 call length
93 addl $1, %eax
94 addq $8, %rsp
95 .L19:
96 rep
97 ret
98 at:
99 testl %esi, %esi
100 jne .L21
101 movq 8(%rdi), %rax
102 ret
103 .L21:
104 subq $8, %rsp
105 subl $1, %esi
106 movq (%rdi), %rdi
107 call at
108 addq $8, %rsp
109 ret
110 isInList:
111 movq %rbx, -16(%rsp)
112 movq %rbp, -8(%rsp)
113 subq $24, %rsp
114 movq %rsi, %rbx
115 testq %rsi, %rsi
116 je .L26
117 movq %rdi, %rbp
118 movq 8(%rsi), %rsi
119 call strcmp
120 movl $1, %edx
121 testl %eax, %eax
122 je .L25
123 movq (%rbx), %rsi
124 movq %rbp, %rdi
125 call isInList
126 movl %eax, %edx
127 jmp .L25
128 .L26:
129 movl $0, %edx
130 .L25:
131 movl %edx, %eax
132 movq 8(%rsp), %rbx
133 movq 16(%rsp), %rbp
134 addq $24, %rsp
135 ret
136 insertElem:
137 movq %rbx, -16(%rsp)
138 movq %rbp, -8(%rsp)
139 subq $24, %rsp
140 movq %rdi, %rbp
141 movq %rsi, %rbx
142 call isInList
143 testl %eax, %eax
144 jne .L30
145 movq %rbx, %rsi
146 movq %rbp, %rdi
147 call cons
148 movq %rax, %rbx
149 .L30:
150 movq %rbx, %rax
151 movq 8(%rsp), %rbx
152 movq 16(%rsp), %rbp
153 addq $24, %rsp
154 ret
155 removeElem:
156 subq $8, %rsp
157 call removeElem1
158 addq $8, %rsp
159 ret
160 removeAllElems:
161 subq $8, %rsp
162 call removeAllElems1
163 addq $8, %rsp
164 ret
165 concat:
166 pushq %rbx
167 movq %rdi, %rbx
168 testq %rdi, %rdi
169 je .L37
170 movq (%rdi), %rdi
171 call concat
172 movq %rax, (%rbx)
173 movq %rbx, %rsi
174 .L37:
175 movq %rsi, %rax
176 popq %rbx
177 ret
178 append:
179 pushq %rbx
180 movq %rdi, %rbx
181 movq %rsi, %rdi
182 movl $0, %esi
183 call cons
184 movq %rax, %rsi
185 movq %rbx, %rdi
186 call concat
187 popq %rbx
188 ret
189 splitAt:
190 pushq %rbx
191 movq %rdi, %rbx
192 testl %esi, %esi
193 jne .L42
194 movq %rdi, (%rdx)
195 movl $0, %ebx
196 jmp .L43
197 .L42:
198 subl $1, %esi
199 movq (%rdi), %rdi
200 call splitAt
201 movq %rax, (%rbx)
202 .L43:
203 movq %rbx, %rax
204 popq %rbx
205 ret
206 removeAt:
207 pushq %rbx
208 movq %rdi, %rbx
209 testl %esi, %esi
210 jne .L46
211 call removeHead
212 movq %rax, %rbx
213 jmp .L47
214 .L46:
215 subl $1, %esi
216 movq (%rdi), %rdi
217 call removeAt
218 movq %rax, (%rbx)
219 .L47:
220 movq %rbx, %rax
221 popq %rbx
222 ret
223 insertAt:
224 pushq %rbx
225 movq %rdi, %rbx
226 testl %esi, %esi
227 jne .L50
228 movq %rdi, %rsi
229 movq %rdx, %rdi
230 call cons
231 movq %rax, %rbx
232 jmp .L51
233 .L50:
234 subl $1, %esi
235 movq (%rdi), %rdi
236 call insertAt
237 movq %rax, (%rbx)
238 .L51:
239 movq %rbx, %rax
240 popq %rbx
241 ret
242 Union:
243 movq %rbx, -16(%rsp)
244 movq %rbp, -8(%rsp)
245 subq $24, %rsp
246 movq %rdi, %rbx
247 movq %rsi, %rax
248 testq %rdi, %rdi
249 je .L54
250 movq 8(%rdi), %rdi
251 call insertElem
252 movq %rax, %rbp
253 movq %rbx, %rdi
254 call removeHead
255 movq %rbp, %rsi
256 movq %rax, %rdi
257 call Union
258 .L54:
259 movq 8(%rsp), %rbx
260 movq 16(%rsp), %rbp
261 addq $24, %rsp
262 ret
263 spaceUsed:
264 subq $8, %rsp
265 call length
266 sall $4, %eax
267 addq $8, %rsp
268 ret
269 spaceNecc:
270 subq $8, %rsp
271 call length
272 sall $3, %eax
273 addq $8, %rsp
274 ret
275 spaceOverhead:
276 movq %rbx, -16(%rsp)
277 movq %rbp, -8(%rsp)
278 subq $24, %rsp
279 movq %rdi, %rbx
280 call spaceUsed
281 movl %eax, %ebp
282 movq %rbx, %rdi
283 call spaceNecc
284 movl %ebp, %edx
285 cvtsi2sdq %rdx, %xmm0
286 movl %eax, %eax
287 cvtsi2sdq %rax, %xmm1
288 divsd %xmm1, %xmm0
289 movq 8(%rsp), %rbx
290 movq 16(%rsp), %rbp
291 addq $24, %rsp
292 ret
|
1 removeAllElems1:
2 pushq %r12
3 testq %rsi, %rsi
4 movq %rdi, %r12
5 pushq %rbp
6 pushq %rbx
7 movq %rsi, %rbx
8 jne .L9
9 jmp .L5
10 .L13:
11 movq (%rbx), %rbp
12 movq %rbx, %rdi
13 call free
14 testq %rbp, %rbp
15 je .L5
16 movq %rbp, %rbx
17 .L9:
18 movq 8(%rbx), %rsi
19 movq %r12, %rdi
20 call strcmp
21 testl %eax, %eax
22 je .L13
23 movq (%rbx), %rsi
24 movq %r12, %rdi
25 call removeAllElems1
26 movq %rax, (%rbx)
27 movq %rbx, %rax
28 popq %rbx
29 popq %rbp
30 popq %r12
31 ret
32 .L5:
33 xorl %ebx, %ebx
34 movq %rbx, %rax
35 popq %rbx
36 popq %rbp
37 popq %r12
38 ret
39 removeElem1:
40 movq %rbx, -16(%rsp)
41 movq %rbp, -8(%rsp)
42 subq $24, %rsp
43 testq %rsi, %rsi
44 movq %rsi, %rbx
45 je .L15
46 movq 8(%rsi), %rsi
47 movq %rdi, %rbp
48 call strcmp
49 testl %eax, %eax
50 je .L21
51 movq (%rbx), %rsi
52 movq %rbp, %rdi
53 call removeElem1
54 movq %rax, (%rbx)
55 .L15:
56 movq %rbx, %rax
57 movq 16(%rsp), %rbp
58 movq 8(%rsp), %rbx
59 addq $24, %rsp
60 ret
61 .L21:
62 movq (%rbx), %rbp
63 movq %rbx, %rdi
64 call free
65 movq %rbp, %rbx
66 jmp .L15
67 removeHead:
68 pushq %rbx
69 movq (%rdi), %rbx
70 call free
71 movq %rbx, %rax
72 popq %rbx
73 ret
74 cons:
75 movq %rbx, -16(%rsp)
76 movq %rbp, -8(%rsp)
77 movq %rdi, %rbx
78 subq $24, %rsp
79 movl $16, %edi
80 movq %rsi, %rbp
81 call malloc
82 testq %rax, %rax
83 je .L27
84 movq %rbx, 8(%rax)
85 movq %rbp, (%rax)
86 movq 8(%rsp), %rbx
87 movq 16(%rsp), %rbp
88 addq $24, %rsp
89 ret
90 .L27:
91 movl $.LC0, %edi
92 call perror
93 movl $1, %edi
94 call exit
95 length:
96 testq %rdi, %rdi
97 je .L31
98 movl $1, %eax
99 jmp .L30
100 .L32:
101 movl %edx, %eax
102 .L30:
103 movq (%rdi), %rdi
104 leal 1(%rax), %edx
105 testq %rdi, %rdi
106 jne .L32
107 rep
108 ret
109 .L31:
110 xorl %eax, %eax
111 ret
112 at:
113 testl %esi, %esi
114 je .L35
115 .L39:
116 subl $1, %esi
117 movq (%rdi), %rdi
118 jne .L39
119 .L35:
120 movq 8(%rdi), %rax
121 ret
122 isInList:
123 pushq %rbp
124 movq %rdi, %rbp
125 pushq %rbx
126 movq %rsi, %rbx
127 subq $8, %rsp
128 testq %rsi, %rsi
129 jne .L47
130 jmp .L45
131 .L50:
132 movq (%rbx), %rbx
133 testq %rbx, %rbx
134 je .L45
135 .L47:
136 movq 8(%rbx), %rsi
137 movq %rbp, %rdi
138 call strcmp
139 testl %eax, %eax
140 jne .L50
141 addq $8, %rsp
142 movl $1, %eax
143 popq %rbx
144 popq %rbp
145 ret
146 .L45:
147 addq $8, %rsp
148 xorl %eax, %eax
149 popq %rbx
150 popq %rbp
151 ret
152 insertElem:
153 movq %rbx, -16(%rsp)
154 movq %rbp, -8(%rsp)
155 subq $24, %rsp
156 movq %rdi, %rbp
157 movq %rsi, %rbx
158 call isInList
159 testl %eax, %eax
160 je .L54
161 movq %rbx, %rax
162 movq 16(%rsp), %rbp
163 movq 8(%rsp), %rbx
164 addq $24, %rsp
165 ret
166 .L54:
167 movq %rbx, %rsi
168 movq %rbp, %rdi
169 movq 8(%rsp), %rbx
170 movq 16(%rsp), %rbp
171 addq $24, %rsp
172 jmp cons
173 removeElem:
174 jmp removeElem1
175 removeAllElems:
176 jmp removeAllElems1
177 concat:
178 testq %rdi, %rdi
179 pushq %rbx
180 movq %rdi, %rbx
181 je .L58
182 movq (%rdi), %rdi
183 call concat
184 movq %rbx, %rsi
185 movq %rax, (%rbx)
186 .L58:
187 movq %rsi, %rax
188 popq %rbx
189 ret
190 append:
191 pushq %rbx
192 movq %rdi, %rbx
193 movq %rsi, %rdi
194 xorl %esi, %esi
195 call cons
196 movq %rbx, %rdi
197 movq %rax, %rsi
198 popq %rbx
199 jmp concat
200 splitAt:
201 testl %esi, %esi
202 pushq %rbx
203 movq %rdi, %rbx
204 je .L69
205 movq (%rdi), %rdi
206 subl $1, %esi
207 call splitAt
208 movq %rax, (%rbx)
209 movq %rbx, %rax
210 popq %rbx
211 ret
212 .L69:
213 xorl %ebx, %ebx
214 movq %rdi, (%rdx)
215 movq %rbx, %rax
216 popq %rbx
217 ret
218 removeAt:
219 movq %rbx, -16(%rsp)
220 movq %rbp, -8(%rsp)
221 subq $24, %rsp
222 testl %esi, %esi
223 movq %rdi, %rbx
224 je .L74
225 movq (%rdi), %rdi
226 subl $1, %esi
227 call removeAt
228 movq %rax, (%rbx)
229 .L72:
230 movq %rbx, %rax
231 movq 16(%rsp), %rbp
232 movq 8(%rsp), %rbx
233 addq $24, %rsp
234 ret
235 .L74:
236 movq (%rdi), %rbp
237 call free
238 movq %rbp, %rbx
239 jmp .L72
240 insertAt:
241 testl %esi, %esi
242 pushq %rbx
243 movq %rdi, %rbx
244 je .L78
245 movq (%rdi), %rdi
246 subl $1, %esi
247 call insertAt
248 movq %rax, (%rbx)
249 movq %rbx, %rax
250 popq %rbx
251 ret
252 .L78:
253 popq %rbx
254 movq %rdi, %rsi
255 movq %rdx, %rdi
256 jmp cons
257 Union:
258 pushq %r12
259 testq %rdi, %rdi
260 pushq %rbp
261 movq %rsi, %rbp
262 pushq %rbx
263 movq %rdi, %rbx
264 je .L80
265 .L84:
266 movq 8(%rbx), %rdi
267 movq %rbp, %rsi
268 call insertElem
269 movq (%rbx), %r12
270 movq %rbx, %rdi
271 movq %rax, %rbp
272 call free
273 testq %r12, %r12
274 movq %r12, %rbx
275 jne .L84
276 .L80:
277 popq %rbx
278 movq %rbp, %rax
279 popq %rbp
280 popq %r12
281 ret
282 spaceUsed:
283 testq %rdi, %rdi
284 je .L91
285 movl $1, %eax
286 jmp .L90
287 .L92:
288 movl %edx, %eax
289 .L90:
290 movq (%rdi), %rdi
291 leal 1(%rax), %edx
292 testq %rdi, %rdi
293 jne .L92
294 sall $4, %eax
295 ret
296 .L91:
297 xorl %eax, %eax
298 ret
299 spaceNecc:
300 testq %rdi, %rdi
301 je .L96
302 movl $1, %eax
303 jmp .L95
304 .L97:
305 movl %edx, %eax
306 .L95:
307 movq (%rdi), %rdi
308 leal 1(%rax), %edx
309 testq %rdi, %rdi
310 jne .L97
311 sall $3, %eax
312 ret
313 .L96:
314 xorl %eax, %eax
315 ret
316 spaceOverhead:
317 testq %rdi, %rdi
318 je .L107
319 movq %rdi, %rax
320 movl $1, %edx
321 jmp .L100
322 .L108:
323 movl %ecx, %edx
324 .L100:
325 movq (%rax), %rax
326 leal 1(%rdx), %ecx
327 testq %rax, %rax
328 jne .L108
329 sall $4, %edx
330 movl $1, %eax
331 cvtsi2sdq %rdx, %xmm0
332 jmp .L102
333 .L109:
334 movl %edx, %eax
335 .L102:
336 movq (%rdi), %rdi
337 leal 1(%rax), %edx
338 testq %rdi, %rdi
339 jne .L109
340 sall $3, %eax
341 cvtsi2sdq %rax, %xmm1
342 .L99:
343 divsd %xmm1, %xmm0
344 ret
345 .L107:
346 xorpd %xmm1, %xmm1
347 movapd %xmm1, %xmm0
348 jmp .L99
|
| Letzte Änderung: 14.01.2013 | © Prof. Dr. Uwe Schmidt |
