Algorithmen und Datenstrukturen in C: Verkettete Listen
| Algorithmen und Datenstrukturen in C: Verkettete Listen |
|
|
|
1#ifndef LIST_H__
2#define LIST_H__ 1
3
4/*--------------------*/
5
6/* $Id: List.h,v 1.9 2011/11/28 18:15:35 uwe Exp $ */
7
8#include <string.h>
9
10typedef char * Element;
11
12#define eqElement(x,y) (strcmp((x),(y)) == 0)
13#define geElement(x,y) (strcmp((x),(y)) >= 0)
14
15/*--------------------*/
16
17typedef struct Node *List;
18
19struct Node
20{
21 List next; /* alignment within structs */
22 Element info; /* next is 1. field (!?) */
23};
24
25
26/*--------------------*/
27
28#if MACROS
29
30#define mkEmptyList() ((List)0)
31#define isEmptyList(l) ((l) == (List)0)
32#define head(l) ((l)->info)
33#define tail(l) ((l)->next)
34
35#else
36
37extern List mkEmptyList(void);
38extern int isEmptyList(List l);
39extern Element head(List l);
40extern List tail(List l);
41
42#endif
43
44/*--------------------*/
45
46extern List cons(Element e, List l);
47
48extern unsigned int length(List l);
49
50extern Element at(List l,
51 unsigned int i);
52
53extern int isInList(Element e, List l);
54
55extern List insertElem(Element e,
56 List l);
57
58extern List removeHead(List l);
59
60extern List removeElem(Element e,
61 List l);
62
63extern List removeAllElems(Element e,
64 List l);
65
66extern List concat(List l1, List l2);
67
68extern List append(List l, Element e);
69
70extern List splitAt(List l,
71 unsigned int i,
72 List * rest);
73
74extern List removeAt(List l,
75 unsigned int i);
76
77extern List insertAt(List l,
78 unsigned int i,
79 Element e);
80
81extern List Union(List l1, List l2);
82
83/*--------------------*/
84
85/* consistency check for sorted lists */
86
87#if ! SORTED && DUPLICATES
88
89#define invList(l) 1
90
91#else
92
93extern int invList(List l);
94
95#endif
96
97/*--------------------*/
98
99#endif
|
|
1/*--------------------*/
2
3/* some macros and static variables
4 for making version and
5 conditional compilation flags
6 visible in assembler and object files
7 ignore in first reading
8*/
9
10static char version[]
11 = "$Id: List.c,v 1.14 2011/11/28 18:15:35 uwe Exp $";
12
13#if MACROS
14#define o1 "MACROS=1"
15#else
16#define o1 "MACROS=0"
17#endif
18
19#if NDEBUG
20#define o2 "NDEBUG=1"
21#else
22#define o2 "NDEBUG=0"
23#endif
24
25#if SORTED
26#define o3 "SORTED=1"
27#else
28#define o3 "SORTED=0"
29#endif
30
31#if DUPLICATES
32#define o4 "DUPLICATES=1"
33#else
34#define o4 "DUPLICATES=0"
35#endif
36
37#if ITERATIVE
38#define o5 "ITERATIVE=1"
39#else
40#define o5 "ITERATIVE=0"
41#endif
42
43#define optionString o1 ", " o2 ", " o3 ", " o4 ", " o5
44
45static char options[] = optionString;
46
47/*--------------------*/
48
49#include "List.h"
50
51#include <stdlib.h>
52#include <stdio.h>
53#include <assert.h>
54
55/*--------------------*/
56
57/* simple ops as functions */
58
59#if ! MACROS
60
61List
62mkEmptyList(void)
63{
64 return (List) 0;
65}
66
67/*--------------------*/
68
69int
70isEmptyList(List l)
71{
72 return l == (List) 0;
73}
74
75/*--------------------*/
76
77Element
78head(List l)
79{
80 assert(! isEmptyList(l));
81 return l->info;
82}
83
84/*--------------------*/
85
86List
87tail(List l)
88{
89 assert(! isEmptyList(l));
90 return l->next;
91}
92
93#endif
94
95/*--------------------*/
96
97List
98removeHead(List l)
99{
100 assert(! isEmptyList(l));
101 {
102 List res = l->next;
103 free(l);
104 return res;
105 }
106}
107
108List
109cons(Element e, List l)
110{
111 /* the only call of malloc */
112 List res = malloc(sizeof(*l));
113
114 if (! res)
115 {
116 perror("cons: malloc failed");
117 exit(1);
118 }
119 res->info = e;
120 res->next = l;
121
122 return res;
123}
124
125/*--------------------*/
126
127#if ! ITERATIVE
128
129unsigned int
130length(List l)
131{
132 return isEmptyList(l)
133 ? 0
134 : 1 + length(tail(l));
135}
136
137/*--------------------*/
138
139#else
140
141unsigned int
142length(List l)
143{
144 unsigned int res;
145
146 for (res = 0; ! isEmptyList(l);
147 l = l->next)
148 ++res;
149
150 return res;
151}
152
153#endif
154
155/*--------------------*/
156
157#if ! ITERATIVE
158
159Element
160at(List l, unsigned int i)
161{
162 return i == 0
163 ? head(l)
164 : at(tail(l), i - 1);
165}
166
167/*--------------------*/
168
169#else
170
171Element
172at(List l, unsigned int i)
173{
174 while (i != 0)
175 {
176 l = tail(l);
177 --i;
178 }
179 return head(l);
180}
181
182#endif
183
184/*--------------------*/
185
186#if ! ITERATIVE
187
188int
189isInList(Element e, List l)
190{
191 if (isEmptyList(l))
192 return 0;
193
194 if (eqElement(e, l->info))
195 return 1;
196
197#if SORTED
198 if (! geElement(e, l->info))
199 return 0;
200#endif
201
202 return isInList(e, l->next);
203}
204
205/*--------------------*/
206
207#else
208
209int
210isInList(Element e, List l)
211{
212 while (! isEmptyList(l)
213#if SORTED
214 &&
215 geElement(e, l->info)
216#endif
217 )
218 {
219 if (eqElement(e, l->info))
220 return 1;
221 l = l->next;
222 }
223 return 0;
224}
225
226#endif
227
228/*--------------------*/
229
230#if ! SORTED
231
232List
233insertElem(Element e, List l)
234{
235#if DUPLICATES
236 return cons(e, l);
237
238#else
239
240 return isInList(e, l)
241 ? l
242 : cons(e, l);
243#endif
244}
245
246/*--------------------*/
247
248#else
249/* sorted list */
250
251#if ! ITERATIVE
252
253List
254insertElem(Element e, List l)
255{
256 if (isEmptyList(l)
257 ||
258 ! geElement(e, l->info))
259 return cons(e, l);
260
261#if ! DUPLICATES
262 if (eqElement(e, l->info))
263 return l;
264#endif
265
266 l->next = insertElem(e, l->next);
267 return l;
268}
269
270/*--------------------*/
271
272#else
273
274List
275insertElem(Element e, List l)
276{
277 List *pl = &l;
278
279 while (! isEmptyList(*pl)
280 &&
281 ! geElement((*pl)->info, e))
282 {
283 pl = &((*pl)->next);
284 }
285
286#if ! DUPLICATES
287 if (! isEmptyList(*pl)
288 && eqElement(e, (*pl)->info))
289 return l;
290
291 *pl = cons(e, *pl);
292 return l;
293}
294#endif
295
296#endif
297
298#endif
299
300/*--------------------*/
301
302static List
303removeElem1(Element e, List l)
304{
305 if (isEmptyList(l))
306 return l;
307
308#if SORTED
309 if (! geElement(e, l->info))
310 return l;
311#endif
312
313 if (eqElement(e, l->info))
314 {
315 return
316 removeHead(l);
317 }
318
319 l->next = removeElem1(e, l->next);
320 return l;
321}
322
323/*--------------------*/
324
325/* a save version of removeElem */
326
327List
328removeElem(Element e, List l)
329{
330 List res = removeElem1(e, l);
331
332 assert(invList(res));
333 return res;
334}
335
336/*--------------------*/
337
338static List
339removeAllElems1(Element e, List l)
340{
341 if (isEmptyList(l))
342 return l;
343
344#if SORTED
345 if (! geElement(e, l->info))
346 return l;
347#endif
348
349 if (eqElement(e, l->info))
350 {
351 return
352 removeAllElems1(e, removeHead(l));
353 }
354
355 l->next = removeAllElems1(e, l->next);
356 return l;
357}
358
359/*--------------------*/
360
361/* a save version of removeAllElems */
362
363List
364removeAllElems(Element e, List l)
365{
366 List res = removeAllElems1(e, l);
367
368 assert(invList(res));
369 assert(! isInList(e, res));
370 return res;
371}
372
373/*--------------------*/
374
375List
376concat(List l1, List l2) {
377 if ( isEmptyList(l1) )
378 return l2;
379
380 l1->next = concat(l1->next, l2);
381 return l1;
382}
383
384List
385append(List l, Element e) {
386 return
387 concat(l,
388 cons(e, mkEmptyList()));
389}
390
391/*--------------------*/
392
393List
394splitAt(List l,
395 unsigned int i,
396 List * rest) {
397 if (i == 0) {
398 * rest = l;
399 return mkEmptyList();
400 }
401 l->next = splitAt(tail(l),
402 i-1,
403 rest);
404 return l;
405}
406
407List
408removeAt(List l,
409 unsigned int i) {
410 if (i == 0) {
411 return removeHead(l);
412 }
413 l->next = removeAt(tail(l),
414 i-1);
415 return l;
416}
417
418List
419insertAt(List l,
420 unsigned int i,
421 Element e) {
422 if (i == 0) {
423 return cons(e, l);
424 }
425 l->next = insertAt(tail(l),
426 i-1,
427 e);
428 return l;
429}
430
431/*--------------------*/
432
433List
434Union(List l1, List l2) {
435#if ! SORTED
436
437#if ! DUPLICATES
438
439 if ( isEmptyList(l1) )
440 return l2;
441 l2 = insertElem(l1->info, l2);
442 return Union(removeHead(l1), l2);
443
444#else
445
446 return concat(l1, l2);
447
448#endif
449
450#else
451
452 if ( isEmptyList(l1) )
453 return l2;
454
455 if ( isEmptyList(l2) )
456 return l1;
457
458#if ! DUPLICATES
459 if ( eqElement(l1->info, l2->info) )
460 return Union(removeHead(l1), l2);
461#endif
462
463 if ( geElement(l1->info, l2->info) ) {
464 l2->next = Union(l1, l2->next);
465 return l2;
466 } else {
467 l1->next = Union(l1->next, l2);
468 return l1;
469 }
470
471#endif
472}
473
474/*--------------------*/
475
476/* Invariant for sorted lists */
477
478#if SORTED
479
480int
481invList(List l)
482{
483 if (isEmptyList(l))
484 return 1;
485
486 if (isEmptyList(l->next))
487 return 1;
488
489#if ! DUPLICATES
490 if (eqElement(l->info, l->next->info))
491 return 0;
492#endif
493
494 return
495 geElement(l->next->info, l->info)
496 &&
497 invList(l->next);
498}
499
500#else
501
502#if DUPLICATES
503
504int
505invList(List l)
506{
507 if (isEmptyList(l))
508 return 1;
509
510 return
511 ! isInList(l->info, l->next)
512 &&
513 invList(l->next);
514}
515
516
517#endif
518
519#endif
520
521/*--------------------*/
|
# $Id: Makefile,v 1.4 2010/12/01 12:20:44 uwe Exp $
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 : $(OASS) $(O2ASS) $(TESTS)
##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 mkEmptyList:
2 movl $0, %eax
3 ret
4 isEmptyList:
5 testq %rdi, %rdi
6 sete %al
7 movzbl %al, %eax
8 ret
9 concat:
10 movq %rbx, -16(%rsp)
11 movq %rbp, -8(%rsp)
12 subq $24, %rsp
13 movq %rdi, %rbp
14 movq %rsi, %rbx
15 call isEmptyList
16 testl %eax, %eax
17 jne .L6
18 movq %rbx, %rsi
19 movq (%rbp), %rdi
20 call concat
21 movq %rax, (%rbp)
22 movq %rbp, %rbx
23 .L6:
24 movq %rbx, %rax
25 movq 8(%rsp), %rbx
26 movq 16(%rsp), %rbp
27 addq $24, %rsp
28 ret
29 tail:
30 pushq %rbx
31 movq %rdi, %rbx
32 call isEmptyList
33 testl %eax, %eax
34 je .L9
35 movl $__PRETTY_FUNCTION__.3005, %ecx
36 movl $89, %edx
37 movl $.LC0, %esi
38 movl $.LC1, %edi
39 call __assert_fail
40 .L9:
41 movq (%rbx), %rax
42 popq %rbx
43 ret
44 splitAt:
45 movq %rbx, -24(%rsp)
46 movq %rbp, -16(%rsp)
47 movq %r12, -8(%rsp)
48 subq $24, %rsp
49 movq %rdi, %rbx
50 movl %esi, %ebp
51 movq %rdx, %r12
52 testl %esi, %esi
53 jne .L12
54 movq %rdi, (%r12)
55 call mkEmptyList
56 movq %rax, %rbx
57 jmp .L13
58 .L12:
59 call tail
60 movq %rax, %rdi
61 leal -1(%rbp), %esi
62 movq %r12, %rdx
63 call splitAt
64 movq %rax, (%rbx)
65 .L13:
66 movq %rbx, %rax
67 movq (%rsp), %rbx
68 movq 8(%rsp), %rbp
69 movq 16(%rsp), %r12
70 addq $24, %rsp
71 ret
72 length:
73 pushq %rbx
74 movq %rdi, %rbx
75 call isEmptyList
76 movl $0, %edx
77 testl %eax, %eax
78 jne .L17
79 movq %rbx, %rdi
80 call tail
81 movq %rax, %rdi
82 call length
83 leal 1(%rax), %edx
84 .L17:
85 movl %edx, %eax
86 popq %rbx
87 ret
88 head:
89 pushq %rbx
90 movq %rdi, %rbx
91 call isEmptyList
92 testl %eax, %eax
93 je .L20
94 movl $__PRETTY_FUNCTION__.2999, %ecx
95 movl $80, %edx
96 movl $.LC0, %esi
97 movl $.LC1, %edi
98 call __assert_fail
99 .L20:
100 movq 8(%rbx), %rax
101 popq %rbx
102 ret
103 at:
104 pushq %rbx
105 movl %esi, %ebx
106 testl %esi, %esi
107 jne .L23
108 call head
109 jmp .L24
110 .L23:
111 call tail
112 movq %rax, %rdi
113 leal -1(%rbx), %esi
114 call at
115 .L24:
116 popq %rbx
117 ret
118 isInList:
119 movq %rbx, -16(%rsp)
120 movq %rbp, -8(%rsp)
121 subq $24, %rsp
122 movq %rdi, %rbp
123 movq %rsi, %rbx
124 movq %rsi, %rdi
125 call isEmptyList
126 movl $0, %edx
127 testl %eax, %eax
128 jne .L28
129 movq 8(%rbx), %rsi
130 movq %rbp, %rdi
131 call strcmp
132 movl $1, %edx
133 testl %eax, %eax
134 je .L28
135 movq (%rbx), %rsi
136 movq %rbp, %rdi
137 call isInList
138 movl %eax, %edx
139 .L28:
140 movl %edx, %eax
141 movq 8(%rsp), %rbx
142 movq 16(%rsp), %rbp
143 addq $24, %rsp
144 ret
145 cons:
146 movq %rbx, -16(%rsp)
147 movq %rbp, -8(%rsp)
148 subq $24, %rsp
149 movq %rdi, %rbx
150 movq %rsi, %rbp
151 movl $16, %edi
152 call malloc
153 testq %rax, %rax
154 jne .L32
155 movl $.LC2, %edi
156 call perror
157 movl $1, %edi
158 call exit
159 .L32:
160 movq %rbx, 8(%rax)
161 movq %rbp, (%rax)
162 movq 8(%rsp), %rbx
163 movq 16(%rsp), %rbp
164 addq $24, %rsp
165 ret
166 insertAt:
167 movq %rbx, -24(%rsp)
168 movq %rbp, -16(%rsp)
169 movq %r12, -8(%rsp)
170 subq $24, %rsp
171 movq %rdi, %rbx
172 movl %esi, %ebp
173 movq %rdx, %r12
174 testl %esi, %esi
175 jne .L35
176 movq %rdi, %rsi
177 movq %rdx, %rdi
178 call cons
179 movq %rax, %rbx
180 jmp .L36
181 .L35:
182 call tail
183 movq %rax, %rdi
184 leal -1(%rbp), %esi
185 movq %r12, %rdx
186 call insertAt
187 movq %rax, (%rbx)
188 .L36:
189 movq %rbx, %rax
190 movq (%rsp), %rbx
191 movq 8(%rsp), %rbp
192 movq 16(%rsp), %r12
193 addq $24, %rsp
194 ret
195 append:
196 movq %rbx, -16(%rsp)
197 movq %r12, -8(%rsp)
198 subq $24, %rsp
199 movq %rdi, %r12
200 movq %rsi, %rbx
201 call mkEmptyList
202 movq %rax, %rsi
203 movq %rbx, %rdi
204 call cons
205 movq %rax, %rsi
206 movq %r12, %rdi
207 call concat
208 movq 8(%rsp), %rbx
209 movq 16(%rsp), %r12
210 addq $24, %rsp
211 ret
212 insertElem:
213 movq %rbx, -16(%rsp)
214 movq %rbp, -8(%rsp)
215 subq $24, %rsp
216 movq %rdi, %rbp
217 movq %rsi, %rbx
218 call isInList
219 testl %eax, %eax
220 jne .L41
221 movq %rbx, %rsi
222 movq %rbp, %rdi
223 call cons
224 movq %rax, %rbx
225 .L41:
226 movq %rbx, %rax
227 movq 8(%rsp), %rbx
228 movq 16(%rsp), %rbp
229 addq $24, %rsp
230 ret
231 removeHead:
232 movq %rbx, -16(%rsp)
233 movq %rbp, -8(%rsp)
234 subq $24, %rsp
235 movq %rdi, %rbp
236 call isEmptyList
237 testl %eax, %eax
238 je .L44
239 movl $__PRETTY_FUNCTION__.3011, %ecx
240 movl $100, %edx
241 movl $.LC0, %esi
242 movl $.LC1, %edi
243 call __assert_fail
244 .L44:
245 movq (%rbp), %rbx
246 movq %rbp, %rdi
247 call free
248 movq %rbx, %rax
249 movq 8(%rsp), %rbx
250 movq 16(%rsp), %rbp
251 addq $24, %rsp
252 ret
253 Union:
254 movq %rbx, -16(%rsp)
255 movq %rbp, -8(%rsp)
256 subq $24, %rsp
257 movq %rdi, %rbp
258 movq %rsi, %rbx
259 call isEmptyList
260 testl %eax, %eax
261 jne .L47
262 movq 8(%rbp), %rdi
263 movq %rbx, %rsi
264 call insertElem
265 movq %rax, %rbx
266 movq %rbp, %rdi
267 call removeHead
268 movq %rax, %rdi
269 movq %rbx, %rsi
270 call Union
271 movq %rax, %rbx
272 .L47:
273 movq %rbx, %rax
274 movq 8(%rsp), %rbx
275 movq 16(%rsp), %rbp
276 addq $24, %rsp
277 ret
278 removeAt:
279 movq %rbx, -16(%rsp)
280 movq %rbp, -8(%rsp)
281 subq $24, %rsp
282 movq %rdi, %rbx
283 movl %esi, %ebp
284 testl %esi, %esi
285 jne .L50
286 call removeHead
287 movq %rax, %rbx
288 jmp .L51
289 .L50:
290 call tail
291 movq %rax, %rdi
292 leal -1(%rbp), %esi
293 call removeAt
294 movq %rax, (%rbx)
295 .L51:
296 movq %rbx, %rax
297 movq 8(%rsp), %rbx
298 movq 16(%rsp), %rbp
299 addq $24, %rsp
300 ret
301 removeAllElems1:
302 movq %rbx, -16(%rsp)
303 movq %rbp, -8(%rsp)
304 subq $24, %rsp
305 movq %rdi, %rbp
306 movq %rsi, %rbx
307 movq %rsi, %rdi
308 call isEmptyList
309 testl %eax, %eax
310 jne .L54
311 movq 8(%rbx), %rsi
312 movq %rbp, %rdi
313 call strcmp
314 testl %eax, %eax
315 jne .L55
316 movq %rbx, %rdi
317 call removeHead
318 movq %rax, %rsi
319 movq %rbp, %rdi
320 call removeAllElems1
321 movq %rax, %rbx
322 jmp .L54
323 .L55:
324 movq (%rbx), %rsi
325 movq %rbp, %rdi
326 call removeAllElems1
327 movq %rax, (%rbx)
328 .L54:
329 movq %rbx, %rax
330 movq 8(%rsp), %rbx
331 movq 16(%rsp), %rbp
332 addq $24, %rsp
333 ret
334 removeAllElems:
335 movq %rbx, -16(%rsp)
336 movq %rbp, -8(%rsp)
337 subq $24, %rsp
338 movq %rdi, %rbp
339 call removeAllElems1
340 movq %rax, %rbx
341 movq %rax, %rdi
342 call invList
343 testl %eax, %eax
344 jne .L58
345 movl $__PRETTY_FUNCTION__.3119, %ecx
346 movl $368, %edx
347 movl $.LC0, %esi
348 movl $.LC3, %edi
349 call __assert_fail
350 .L58:
351 movq %rbx, %rsi
352 movq %rbp, %rdi
353 call isInList
354 testl %eax, %eax
355 je .L59
356 movl $__PRETTY_FUNCTION__.3119, %ecx
357 movl $369, %edx
358 movl $.LC0, %esi
359 movl $.LC4, %edi
360 call __assert_fail
361 .L59:
362 movq %rbx, %rax
363 movq 8(%rsp), %rbx
364 movq 16(%rsp), %rbp
365 addq $24, %rsp
366 ret
367 removeElem1:
368 movq %rbx, -16(%rsp)
369 movq %rbp, -8(%rsp)
370 subq $24, %rsp
371 movq %rdi, %rbp
372 movq %rsi, %rbx
373 movq %rsi, %rdi
374 call isEmptyList
375 testl %eax, %eax
376 jne .L62
377 movq 8(%rbx), %rsi
378 movq %rbp, %rdi
379 call strcmp
380 testl %eax, %eax
381 jne .L63
382 movq %rbx, %rdi
383 call removeHead
384 movq %rax, %rbx
385 jmp .L62
386 .L63:
387 movq (%rbx), %rsi
388 movq %rbp, %rdi
389 call removeElem1
390 movq %rax, (%rbx)
391 .L62:
392 movq %rbx, %rax
393 movq 8(%rsp), %rbx
394 movq 16(%rsp), %rbp
395 addq $24, %rsp
396 ret
397 removeElem:
398 pushq %rbx
399 call removeElem1
400 movq %rax, %rbx
401 movq %rax, %rdi
402 call invList
403 testl %eax, %eax
404 jne .L66
405 movl $__PRETTY_FUNCTION__.3090, %ecx
406 movl $332, %edx
407 movl $.LC0, %esi
408 movl $.LC3, %edi
409 call __assert_fail
410 .L66:
411 movq %rbx, %rax
412 popq %rbx
413 ret
|
1 mkEmptyList:
2 xorl %eax, %eax
3 ret
4 isEmptyList:
5 xorl %eax, %eax
6 testq %rdi, %rdi
7 sete %al
8 ret
9 concat:
10 testq %rdi, %rdi
11 pushq %rbx
12 movq %rdi, %rbx
13 je .L6
14 movq (%rdi), %rdi
15 call concat
16 movq %rbx, %rsi
17 movq %rax, (%rbx)
18 .L6:
19 movq %rsi, %rax
20 popq %rbx
21 ret
22 tail:
23 subq $8, %rsp
24 testq %rdi, %rdi
25 je .L12
26 movq (%rdi), %rax
27 addq $8, %rsp
28 ret
29 .L12:
30 movl $__PRETTY_FUNCTION__.3005, %ecx
31 movl $89, %edx
32 movl $.LC0, %esi
33 movl $.LC1, %edi
34 call __assert_fail
35 splitAt:
36 movq %rbx, -24(%rsp)
37 movq %rbp, -16(%rsp)
38 movq %rdi, %rbx
39 movq %r12, -8(%rsp)
40 subq $24, %rsp
41 testl %esi, %esi
42 movl %esi, %ebp
43 movq %rdx, %r12
44 je .L17
45 call tail
46 leal -1(%rbp), %esi
47 movq %rax, %rdi
48 movq %r12, %rdx
49 call splitAt
50 movq %rax, (%rbx)
51 .L15:
52 movq %rbx, %rax
53 movq 8(%rsp), %rbp
54 movq (%rsp), %rbx
55 movq 16(%rsp), %r12
56 addq $24, %rsp
57 ret
58 .L17:
59 movq %rdi, (%r12)
60 xorl %ebx, %ebx
61 jmp .L15
62 length:
63 pushq %rbx
64 xorl %ebx, %ebx
65 testq %rdi, %rdi
66 je .L20
67 movb $1, %bl
68 jmp .L21
69 .L23:
70 movl %eax, %ebx
71 .L21:
72 call tail
73 movq %rax, %rdi
74 leal 1(%rbx), %eax
75 testq %rdi, %rdi
76 jne .L23
77 .L20:
78 movl %ebx, %eax
79 popq %rbx
80 ret
81 head:
82 subq $8, %rsp
83 testq %rdi, %rdi
84 je .L27
85 movq 8(%rdi), %rax
86 addq $8, %rsp
87 ret
88 .L27:
89 movl $__PRETTY_FUNCTION__.2999, %ecx
90 movl $80, %edx
91 movl $.LC0, %esi
92 movl $.LC1, %edi
93 call __assert_fail
94 at:
95 testl %esi, %esi
96 pushq %rbx
97 movl %esi, %ebx
98 je .L30
99 .L32:
100 subl $1, %ebx
101 call tail
102 testl %ebx, %ebx
103 movq %rax, %rdi
104 jne .L32
105 .L30:
106 popq %rbx
107 jmp head
108 isInList:
109 pushq %rbp
110 movq %rdi, %rbp
111 pushq %rbx
112 movq %rsi, %rbx
113 subq $8, %rsp
114 testq %rsi, %rsi
115 jne .L39
116 jmp .L34
117 .L35:
118 movq (%rbx), %rbx
119 testq %rbx, %rbx
120 je .L34
121 .L39:
122 movq 8(%rbx), %rsi
123 movq %rbp, %rdi
124 call strcmp
125 testl %eax, %eax
126 jne .L35
127 addq $8, %rsp
128 movb $1, %al
129 popq %rbx
130 popq %rbp
131 ret
132 .L34:
133 addq $8, %rsp
134 xorl %eax, %eax
135 popq %rbx
136 popq %rbp
137 ret
138 cons:
139 movq %rbx, -16(%rsp)
140 movq %rbp, -8(%rsp)
141 movq %rdi, %rbx
142 subq $24, %rsp
143 movl $16, %edi
144 movq %rsi, %rbp
145 call malloc
146 testq %rax, %rax
147 je .L44
148 movq %rbx, 8(%rax)
149 movq %rbp, (%rax)
150 movq 8(%rsp), %rbx
151 movq 16(%rsp), %rbp
152 addq $24, %rsp
153 ret
154 .L44:
155 movl $.LC2, %edi
156 call perror
157 movl $1, %edi
158 call exit
159 insertAt:
160 movq %rbx, -24(%rsp)
161 movq %rbp, -16(%rsp)
162 movq %rdi, %rbx
163 movq %r12, -8(%rsp)
164 subq $24, %rsp
165 testl %esi, %esi
166 movl %esi, %ebp
167 movq %rdx, %r12
168 je .L48
169 call tail
170 leal -1(%rbp), %esi
171 movq %r12, %rdx
172 movq %rax, %rdi
173 call insertAt
174 movq %rax, (%rbx)
175 movq %rbx, %rax
176 movq 8(%rsp), %rbp
177 movq (%rsp), %rbx
178 movq 16(%rsp), %r12
179 addq $24, %rsp
180 ret
181 .L48:
182 movq %rdi, %rsi
183 movq (%rsp), %rbx
184 movq 8(%rsp), %rbp
185 movq 16(%rsp), %r12
186 movq %rdx, %rdi
187 addq $24, %rsp
188 jmp cons
189 append:
190 pushq %rbx
191 movq %rdi, %rbx
192 movq %rsi, %rdi
193 xorl %esi, %esi
194 call cons
195 movq %rbx, %rdi
196 movq %rax, %rsi
197 popq %rbx
198 jmp concat
199 insertElem:
200 movq %rbx, -16(%rsp)
201 movq %rbp, -8(%rsp)
202 subq $24, %rsp
203 movq %rdi, %rbp
204 movq %rsi, %rbx
205 call isInList
206 testl %eax, %eax
207 je .L54
208 movq %rbx, %rax
209 movq 16(%rsp), %rbp
210 movq 8(%rsp), %rbx
211 addq $24, %rsp
212 ret
213 .L54:
214 movq %rbx, %rsi
215 movq %rbp, %rdi
216 movq 8(%rsp), %rbx
217 movq 16(%rsp), %rbp
218 addq $24, %rsp
219 jmp cons
220 removeHead:
221 testq %rdi, %rdi
222 pushq %rbx
223 je .L58
224 movq (%rdi), %rbx
225 call free
226 movq %rbx, %rax
227 popq %rbx
228 ret
229 .L58:
230 movl $__PRETTY_FUNCTION__.3011, %ecx
231 movl $100, %edx
232 movl $.LC0, %esi
233 movl $.LC1, %edi
234 call __assert_fail
235 Union:
236 pushq %rbp
237 movq %rsi, %rbp
238 pushq %rbx
239 movq %rdi, %rbx
240 subq $8, %rsp
241 testq %rdi, %rdi
242 je .L60
243 .L63:
244 movq 8(%rbx), %rdi
245 movq %rbp, %rsi
246 call insertElem
247 movq %rbx, %rdi
248 movq %rax, %rbp
249 call removeHead
250 testq %rax, %rax
251 movq %rax, %rbx
252 jne .L63
253 .L60:
254 addq $8, %rsp
255 movq %rbp, %rax
256 popq %rbx
257 popq %rbp
258 ret
259 removeAt:
260 movq %rbx, -16(%rsp)
261 movq %rbp, -8(%rsp)
262 subq $24, %rsp
263 testl %esi, %esi
264 movq %rdi, %rbx
265 movl %esi, %ebp
266 je .L68
267 call tail
268 leal -1(%rbp), %esi
269 movq %rax, %rdi
270 call removeAt
271 movq %rax, (%rbx)
272 movq %rbx, %rax
273 movq 16(%rsp), %rbp
274 movq 8(%rsp), %rbx
275 addq $24, %rsp
276 ret
277 .L68:
278 movq 8(%rsp), %rbx
279 movq 16(%rsp), %rbp
280 addq $24, %rsp
281 jmp removeHead
282 removeAllElems1:
283 pushq %rbp
284 movq %rdi, %rbp
285 pushq %rbx
286 movq %rsi, %rbx
287 subq $8, %rsp
288 testq %rsi, %rsi
289 jne .L74
290 jmp .L70
291 .L75:
292 movq %rbx, %rdi
293 call removeHead
294 testq %rax, %rax
295 movq %rax, %rbx
296 je .L70
297 .L74:
298 movq 8(%rbx), %rsi
299 movq %rbp, %rdi
300 call strcmp
301 testl %eax, %eax
302 je .L75
303 movq (%rbx), %rsi
304 movq %rbp, %rdi
305 call removeAllElems1
306 movq %rax, (%rbx)
307 .L70:
308 movq %rbx, %rax
309 addq $8, %rsp
310 popq %rbx
311 popq %rbp
312 ret
313 removeAllElems:
314 movq %rbx, -16(%rsp)
315 movq %rbp, -8(%rsp)
316 subq $24, %rsp
317 movq %rdi, %rbp
318 call removeAllElems1
319 movq %rax, %rdi
320 movq %rax, %rbx
321 call invList
322 testl %eax, %eax
323 je .L80
324 movq %rbx, %rsi
325 movq %rbp, %rdi
326 call isInList
327 testl %eax, %eax
328 jne .L81
329 movq %rbx, %rax
330 movq 16(%rsp), %rbp
331 movq 8(%rsp), %rbx
332 addq $24, %rsp
333 ret
334 .L80:
335 movl $__PRETTY_FUNCTION__.3119, %ecx
336 movl $368, %edx
337 movl $.LC0, %esi
338 movl $.LC3, %edi
339 call __assert_fail
340 .L81:
341 movl $__PRETTY_FUNCTION__.3119, %ecx
342 movl $369, %edx
343 movl $.LC0, %esi
344 movl $.LC4, %edi
345 call __assert_fail
346 removeElem1:
347 movq %rbx, -16(%rsp)
348 movq %rbp, -8(%rsp)
349 subq $24, %rsp
350 testq %rsi, %rsi
351 movq %rdi, %rbp
352 movq %rsi, %rbx
353 je .L83
354 movq 8(%rsi), %rsi
355 call strcmp
356 testl %eax, %eax
357 je .L86
358 movq (%rbx), %rsi
359 movq %rbp, %rdi
360 call removeElem1
361 movq %rax, (%rbx)
362 .L83:
363 movq %rbx, %rax
364 movq 16(%rsp), %rbp
365 movq 8(%rsp), %rbx
366 addq $24, %rsp
367 ret
368 .L86:
369 movq %rbx, %rdi
370 movq 16(%rsp), %rbp
371 movq 8(%rsp), %rbx
372 addq $24, %rsp
373 jmp removeHead
374 removeElem:
375 pushq %rbx
376 call removeElem1
377 movq %rax, %rdi
378 movq %rax, %rbx
379 call invList
380 testl %eax, %eax
381 je .L90
382 movq %rbx, %rax
383 popq %rbx
384 ret
385 .L90:
386 movl $__PRETTY_FUNCTION__.3090, %ecx
387 movl $332, %edx
388 movl $.LC0, %esi
389 movl $.LC3, %edi
390 call __assert_fail
|
| Letzte Änderung: 01.12.2010 | © Prof. Dr. Uwe Schmidt |
