summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org.ua>2009-06-28 12:58:01 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2009-06-28 12:58:01 (GMT)
commiteb6e7c7cee0c998f5b403074201992c22383a553 (patch) (unidiff)
tree08537200d56b35bbfffe37fa6a7c1e63855954d0
parent4b66e93d434d2a4fe8fd3f277e222de768475605 (diff)
downloadcflow-eb6e7c7cee0c998f5b403074201992c22383a553.tar.gz
cflow-eb6e7c7cee0c998f5b403074201992c22383a553.tar.bz2
Provide a general-purpose type for singly-linked list.
* src/cflow.h (Cons, Consptr, CAR, CDR): Remove (struct linked_list_entry): New type. (struct linked_list): New type. (linked_list_free_data_fp): New typedef. (struct symbol): Change types of ref_line, callee and caller to struct linked_list. All usages changed. (linked_list_head): New define. (linked_list_create, linked_list_destroy) (linked_list_append, linked_list_prepend): New prototypes. (cleanup, append_to_list): Remove * src/main.c (arglist): Change type to struct linked_list * src/output.c, src/parser.c, src/symbol.c: Use new linked list functions.
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--src/cflow.h34
-rw-r--r--src/main.c18
-rw-r--r--src/output.c43
-rw-r--r--src/parser.c14
-rw-r--r--src/symbol.c187
5 files changed, 123 insertions, 173 deletions
diff --git a/src/cflow.h b/src/cflow.h
index 7a38682..c6712c9 100644
--- a/src/cflow.h
+++ b/src/cflow.h
@@ -1,5 +1,5 @@
1/* This file is part of GNU cflow 1/* This file is part of GNU cflow
2 Copyright (C) 1997,2005,2007 Sergey Poznyakoff 2 Copyright (C) 1997,2005,2007,2009 Sergey Poznyakoff
3 3
4 GNU cflow is free software; you can redistribute it and/or modify 4 GNU cflow is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by 5 it under the terms of the GNU General Public License as published by
@@ -45,15 +45,19 @@
45 45
46#define NUMITEMS(a) sizeof(a)/sizeof((a)[0]) 46#define NUMITEMS(a) sizeof(a)/sizeof((a)[0])
47 47
48typedef struct cons *Consptr; 48struct linked_list_entry {
49typedef struct cons Cons; 49 struct linked_list_entry *next;
50struct cons { 50 void *data;
51 Consptr car;
52 Consptr cdr;
53}; 51};
54 52
55#define CAR(a) (a)->car 53typedef void (*linked_list_free_data_fp) (void*);
56#define CDR(a) (a)->cdr 54
55struct linked_list {
56 linked_list_free_data_fp free_data;
57 struct linked_list_entry *head, *tail;
58};
59
60#define linked_list_head(list) ((list) ? (list)->head : NULL)
57 61
58enum symtype { 62enum symtype {
59 SymUndefined, /* Undefined or deleted symbol */ 63 SymUndefined, /* Undefined or deleted symbol */
@@ -97,7 +101,7 @@ struct symbol {
97 int token_type; /* Type of the token */ 101 int token_type; /* Type of the token */
98 char *source; /* Source file */ 102 char *source; /* Source file */
99 int def_line; /* Source line */ 103 int def_line; /* Source line */
100 Consptr ref_line; /* Referenced in */ 104 struct linked_list *ref_line; /* Referenced in */
101 105
102 int level; /* Block nesting level (for local vars), 106 int level; /* Block nesting level (for local vars),
103 Parameter nesting level (for params) */ 107 Parameter nesting level (for params) */
@@ -109,8 +113,8 @@ struct symbol {
109 variables */ 113 variables */
110 114
111 int recursive; /* Is the function recursive */ 115 int recursive; /* Is the function recursive */
112 Consptr caller; /* List of callers */ 116 struct linked_list *caller; /* List of callers */
113 Consptr callee; /* List of callees */ 117 struct linked_list *callee; /* List of callees */
114}; 118};
115 119
116/* Output flags */ 120/* Output flags */
@@ -162,10 +166,12 @@ void delete_autos(int level);
162void delete_statics(void); 166void delete_statics(void);
163void delete_parms(int level); 167void delete_parms(int level);
164void move_parms(int level); 168void move_parms(int level);
165void cleanup(void);
166int collect_symbols(Symbol ***, int (*sel)()); 169int collect_symbols(Symbol ***, int (*sel)());
167Consptr append_to_list(Consptr *, void *); 170struct linked_list *linked_list_create(linked_list_free_data_fp fun);
168int symbol_in_list(Symbol *sym, Consptr list); 171void linked_list_destroy(struct linked_list **plist);
172void linked_list_append(struct linked_list **plist, void *data);
173void linked_list_prepend(struct linked_list **plist, void *data);
174int symbol_in_list(Symbol *sym, struct linked_list *list);
169 175
170int get_token(void); 176int get_token(void);
171int source(char *name); 177int source(char *name);
diff --git a/src/main.c b/src/main.c
index cbb472e..b08ccdd 100644
--- a/src/main.c
+++ b/src/main.c
@@ -218,7 +218,7 @@ int preprocess_option = 0; /* Do they want to preprocess sources? */
218 218
219char *start_name = "main"; /* Name of start symbol */ 219char *start_name = "main"; /* Name of start symbol */
220 220
221Consptr arglist; /* List of command line arguments */ 221struct linked_list *arglist; /* List of command line arguments */
222 222
223/* Given the option_type array and (possibly abbreviated) option argument 223/* Given the option_type array and (possibly abbreviated) option argument
224 * find the type corresponding to that argument. 224 * find the type corresponding to that argument.
@@ -487,7 +487,7 @@ set_level_indent(const char *str)
487static void 487static void
488add_name(const char *name) 488add_name(const char *name)
489{ 489{
490 append_to_list(&arglist, (void*) name); 490 linked_list_append(&arglist, (void*) name);
491} 491}
492 492
493static void 493static void
@@ -769,16 +769,18 @@ main(int argc, char **argv)
769 769
770 init(); 770 init();
771 771
772 if (arglist) 772 if (arglist) {
773 /* See comment to cleanup_processor */ 773 struct linked_list_entry *p;
774 for (arglist = CAR(arglist); arglist; arglist = CDR(arglist)) { 774
775 char *s = (char*)CAR(arglist); 775 for (p = arglist->head; p; p = p->next) {
776 char *s = (char*)p->data;
776 if (s[0] == '-') 777 if (s[0] == '-')
777 pp_option(s); 778 pp_option(s);
778 else if (source(s) == 0) 779 else if (source(s) == 0)
779 yyparse(); 780 yyparse();
780 } 781 }
781 782 }
783
782 argc -= index; 784 argc -= index;
783 argv += index; 785 argv += index;
784 786
@@ -790,8 +792,6 @@ main(int argc, char **argv)
790 if (input_file_count == 0) 792 if (input_file_count == 0)
791 error(1, 0, _("no input files")); 793 error(1, 0, _("no input files"));
792 794
793 cleanup();
794
795 output(); 795 output();
796 return 0; 796 return 0;
797} 797}
diff --git a/src/output.c b/src/output.c
index 7e604f4..f33d0ae 100644
--- a/src/output.c
+++ b/src/output.c
@@ -1,5 +1,5 @@
1/* This file is part of GNU cflow 1/* This file is part of GNU cflow
2 Copyright (C) 1997,2005,2007 Sergey Poznyakoff 2 Copyright (C) 1997,2005,2007,2009 Sergey Poznyakoff
3 3
4 GNU cflow is free software; you can redistribute it and/or modify 4 GNU cflow is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by 5 it under the terms of the GNU General Public License as published by
@@ -200,12 +200,13 @@ clear_active(Symbol *sym)
200 200
201/* Cross-reference output */ 201/* Cross-reference output */
202void 202void
203print_refs(char *name, Consptr cons) 203print_refs(char *name, struct linked_list *reflist)
204{ 204{
205 Ref *refptr; 205 Ref *refptr;
206 206 struct linked_list_entry *p;
207 for ( ; cons; cons = CDR(cons)) { 207
208 refptr = (Ref*)CAR(cons); 208 for (p = linked_list_head(reflist); p; p = p->next) {
209 refptr = (Ref*)p->data;
209 fprintf(outfile, "%s %s:%d\n", 210 fprintf(outfile, "%s %s:%d\n",
210 name, 211 name,
211 refptr->source, 212 refptr->source,
@@ -271,7 +272,7 @@ xref_output()
271static void 272static void
272scan_tree(int lev, Symbol *sym) 273scan_tree(int lev, Symbol *sym)
273{ 274{
274 Consptr cons; 275 struct linked_list_entry *p;
275 276
276 if (sym->type == SymUndefined) 277 if (sym->type == SymUndefined)
277 return; 278 return;
@@ -280,8 +281,8 @@ scan_tree(int lev, Symbol *sym)
280 return; 281 return;
281 } 282 }
282 sym->active = 1; 283 sym->active = 1;
283 for (cons = sym->callee; cons; cons = CDR(cons)) { 284 for (p = linked_list_head(sym->callee); p; p = p->next) {
284 scan_tree(lev+1, (Symbol*)CAR(cons)); 285 scan_tree(lev+1, (Symbol*)p->data);
285 } 286 }
286 sym->active = 0; 287 sym->active = 0;
287} 288}
@@ -293,16 +294,16 @@ set_active(Symbol *sym)
293} 294}
294 295
295static int 296static int
296is_printable(Consptr cons) 297is_printable(struct linked_list_entry *p)
297{ 298{
298 return cons != NULL && include_symbol((Symbol*)CAR(cons)); 299 return p != NULL && include_symbol((Symbol*)p->data);
299} 300}
300 301
301static int 302static int
302is_last(Consptr cons) 303is_last(struct linked_list_entry *p)
303{ 304{
304 while (cons = CDR(cons)) 305 while (p = p->next)
305 if (is_printable(cons)) 306 if (is_printable(p))
306 return 0; 307 return 0;
307 return 1; 308 return 1;
308} 309}
@@ -312,7 +313,7 @@ is_last(Consptr cons)
312static void 313static void
313direct_tree(int lev, int last, Symbol *sym) 314direct_tree(int lev, int last, Symbol *sym)
314{ 315{
315 Consptr cons; 316 struct linked_list_entry *p;
316 int rc; 317 int rc;
317 318
318 if (sym->type == SymUndefined 319 if (sym->type == SymUndefined
@@ -325,9 +326,9 @@ direct_tree(int lev, int last, Symbol *sym)
325 if (rc || sym->active) 326 if (rc || sym->active)
326 return; 327 return;
327 set_active(sym); 328 set_active(sym);
328 for (cons = sym->callee; cons; cons = CDR(cons)) { 329 for (p = linked_list_head(sym->callee); p; p = p->next) {
329 set_level_mark(lev+1, is_printable(CDR(cons))); 330 set_level_mark(lev+1, is_printable(p->next));
330 direct_tree(lev+1, is_last(cons), (Symbol*)CAR(cons)); 331 direct_tree(lev+1, is_last(p), (Symbol*)p->data);
331 } 332 }
332 clear_active(sym); 333 clear_active(sym);
333} 334}
@@ -337,7 +338,7 @@ direct_tree(int lev, int last, Symbol *sym)
337static void 338static void
338inverted_tree(int lev, int last, Symbol *sym) 339inverted_tree(int lev, int last, Symbol *sym)
339{ 340{
340 Consptr cons; 341 struct linked_list_entry *p;
341 int rc; 342 int rc;
342 343
343 if (sym->type == SymUndefined 344 if (sym->type == SymUndefined
@@ -349,9 +350,9 @@ inverted_tree(int lev, int last, Symbol *sym)
349 if (rc || sym->active) 350 if (rc || sym->active)
350 return; 351 return;
351 set_active(sym); 352 set_active(sym);
352 for (cons = sym->caller; cons; cons = CDR(cons)) { 353 for (p = linked_list_head(sym->caller); p; p = p->next) {
353 set_level_mark(lev+1, is_printable(CDR(cons))); 354 set_level_mark(lev+1, is_printable(p->next));
354 inverted_tree(lev+1, is_last(cons), (Symbol*)CAR(cons)); 355 inverted_tree(lev+1, is_last(p), (Symbol*)p->data);
355 } 356 }
356 clear_active(sym); 357 clear_active(sym);
357} 358}
diff --git a/src/parser.c b/src/parser.c
index 911bf58..26ac25d 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -1,5 +1,5 @@
1/* This file is part of GNU cflow 1/* This file is part of GNU cflow
2 Copyright (C) 1997, 2005, 2006, 2007 Sergey Poznyakoff 2 Copyright (C) 1997, 2005, 2006, 2007, 2009 Sergey Poznyakoff
3 3
4 GNU cflow is free software; you can redistribute it and/or modify 4 GNU cflow is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by 5 it under the terms of the GNU General Public License as published by
@@ -1077,7 +1077,9 @@ add_reference(char *name, int line)
1077 refptr = xmalloc(sizeof(*refptr)); 1077 refptr = xmalloc(sizeof(*refptr));
1078 refptr->source = filename; 1078 refptr->source = filename;
1079 refptr->line = line; 1079 refptr->line = line;
1080 append_to_list(&sp->ref_line, refptr); 1080 if (!sp->ref_line)
1081 sp->ref_line = linked_list_create(free);
1082 linked_list_append(&sp->ref_line, refptr);
1081 return sp; 1083 return sp;
1082} 1084}
1083 1085
@@ -1094,9 +1096,9 @@ call(char *name, int line)
1094 sp->arity = 0; 1096 sp->arity = 0;
1095 if (caller) { 1097 if (caller) {
1096 if (!symbol_in_list(caller, sp->caller)) 1098 if (!symbol_in_list(caller, sp->caller))
1097 append_to_list(&sp->caller, caller); 1099 linked_list_append(&sp->caller, caller);
1098 if (!symbol_in_list(sp, caller->callee)) 1100 if (!symbol_in_list(sp, caller->callee))
1099 append_to_list(&caller->callee, sp); 1101 linked_list_append(&caller->callee, sp);
1100 } 1102 }
1101} 1103}
1102 1104
@@ -1108,9 +1110,9 @@ reference(char *name, int line)
1108 return; 1110 return;
1109 if (caller) { 1111 if (caller) {
1110 if (!symbol_in_list(caller, sp->caller)) 1112 if (!symbol_in_list(caller, sp->caller))
1111 append_to_list(&sp->caller, caller); 1113 linked_list_append(&sp->caller, caller);
1112 if (!symbol_in_list(sp, caller->callee)) 1114 if (!symbol_in_list(sp, caller->callee))
1113 append_to_list(&caller->callee, sp); 1115 linked_list_append(&caller->callee, sp);
1114 } 1116 }
1115} 1117}
1116 1118
diff --git a/src/symbol.c b/src/symbol.c
index 4fe5f85..e3ccd7c 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -1,5 +1,5 @@
1/* This file is part of GNU cflow 1/* This file is part of GNU cflow
2 Copyright (C) 1997, 2005, 2006, 2007 Sergey Poznyakoff 2 Copyright (C) 1997, 2005, 2006, 2007, 2009 Sergey Poznyakoff
3 3
4 GNU cflow is free software; you can redistribute it and/or modify 4 GNU cflow is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by 5 it under the terms of the GNU General Public License as published by
@@ -110,18 +110,19 @@ delete_symbol(struct table_entry *tp)
110 Symbol *s = unlink_symbol(tp); 110 Symbol *s = unlink_symbol(tp);
111 /* The symbol could have been referenced even if it is static 111 /* The symbol could have been referenced even if it is static
112 in -i^s mode. See tests/static.at for details. */ 112 in -i^s mode. See tests/static.at for details. */
113 if (s->ref_line == NULL) 113 if (s->ref_line == NULL) {
114 linked_list_destroy(&s->ref_line);
115 linked_list_destroy(&s->caller);
116 linked_list_destroy(&s->callee);
114 free(s); 117 free(s);
118 }
115} 119}
116 120
117static void cleanup_symbol_refs(Symbol *sym);
118
119/* Delete from the symbol table all static symbols defined in the current 121/* Delete from the symbol table all static symbols defined in the current
120 source. 122 source.
121 If the user requested static symbols in the listing, the symbol is 123 If the user requested static symbols in the listing, the symbol is
122 not deleted, as it may have been referenced by other symbols. Instead, 124 not deleted, as it may have been referenced by other symbols. Instead,
123 it is unlinked from its table entry and cleanup_symbol_refs() is 125 it is unlinked from its table entry.
124 called, so that its reference tables become usable.
125 NOTE: This takes advantage of the fact that install() uses LIFO strategy, 126 NOTE: This takes advantage of the fact that install() uses LIFO strategy,
126 so we don't have to check the name of the source where the symbol was 127 so we don't have to check the name of the source where the symbol was
127 defined. */ 128 defined. */
@@ -137,7 +138,7 @@ static_processor(void *data, void *proc_data)
137 if (globals_only()) 138 if (globals_only())
138 delete_symbol(t); 139 delete_symbol(t);
139 else 140 else
140 cleanup_symbol_refs(unlink_symbol(t)); 141 unlink_symbol(t);
141 } 142 }
142 return true; 143 return true;
143} 144}
@@ -174,7 +175,7 @@ auto_processor(void *data, void *proc_data)
174 break; 175 break;
175 176
176 case StaticStorage: 177 case StaticStorage:
177 cleanup_symbol_refs(unlink_symbol(t)); 178 unlink_symbol(t);
178 break; 179 break;
179 180
180 default: 181 default:
@@ -193,48 +194,6 @@ delete_autos(int level)
193 hash_do_for_each (symbol_table, auto_processor, &level); 194 hash_do_for_each (symbol_table, auto_processor, &level);
194} 195}
195 196
196
197/* Make all list pointers of the SYM ready for final processing.
198 * This means for each list replace its entry point with its CAR
199 * and throw away the first cons. The first cons holds pointers
200 * to the head and tail of the list and is used to speed up appends.
201 *
202 * TODO: The memory is not reclaimed
203 */
204static void
205cleanup_symbol_refs(Symbol *sym)
206{
207 if (sym && sym->type == SymIdentifier) {
208 if (sym->ref_line)
209 sym->ref_line = CAR(sym->ref_line);
210 if (sym->caller)
211 sym->caller = CAR(sym->caller);
212 if (sym->callee)
213 sym->callee = CAR(sym->callee);
214 }
215}
216
217static bool
218cleanup_processor(void *data, void *proc_data)
219{
220 struct table_entry *t = data;
221 Symbol *sym;
222 for (sym = t->sym; sym; sym = sym->next) {
223 cleanup_symbol_refs(sym);
224 }
225 return true;
226}
227
228
229/* Clean up all symbols from the auxiliary information.
230 * See the comment for cleanup_symbol() above
231 */
232void
233cleanup()
234{
235 hash_do_for_each (symbol_table, cleanup_processor, NULL);
236}
237
238struct collect_data { 197struct collect_data {
239 Symbol **sym; 198 Symbol **sym;
240 int (*sel)(Symbol *p); 199 int (*sel)(Symbol *p);
@@ -324,97 +283,79 @@ move_parms(int level)
324} 283}
325 284
326 285
327typedef struct bucket Bucket;
328struct bucket {
329 Bucket *next; /* Next bucket */
330 int free;
331 Cons cons[1];
332};
333
334static int bucket_nodes = 512;
335static Bucket *root_bucket, *last_bucket;
336 286
337void 287static struct linked_list *
338alloc_new_bucket() 288deref_linked_list (struct linked_list **plist)
339{ 289{
340 Bucket *bp; 290 if (!*plist) {
341 291 struct linked_list *list = xmalloc(sizeof(*list));
342 bp = malloc(sizeof(*bp) + sizeof(Cons)*(bucket_nodes-1)); 292 list->free_data = NULL;
343 if (!bp) 293 list->head = list->tail = NULL;
344 return; 294 *plist = list;
345 bp->next = NULL;
346 bp->free = 0;
347 if (!root_bucket)
348 root_bucket = last_bucket = bp;
349 else {
350 last_bucket->next = bp;
351 last_bucket = bp;
352 } 295 }
296 return *plist;
353} 297}
354 298
355Consptr 299
356alloc_cons_from_bucket() 300struct linked_list *
301linked_list_create(linked_list_free_data_fp fun)
357{ 302{
358 if (!last_bucket || last_bucket->free == bucket_nodes) 303 struct linked_list *list = xmalloc(sizeof(*list));
359 return NULL; 304 list->free_data = fun;
360 return &last_bucket->cons[last_bucket->free++]; 305 list->head = list->tail = NULL;
306 return list;
361} 307}
362 308
363Consptr 309void
364alloc_cons() 310linked_list_append(struct linked_list **plist, void *data)
365{ 311{
366 Consptr cp; 312 struct linked_list *list = deref_linked_list (plist);
367 313 struct linked_list_entry *entry = xmalloc(sizeof(*entry));
368 cp = alloc_cons_from_bucket(); 314 entry->next = NULL;
369 if (!cp) { 315 entry->data = data;
370 alloc_new_bucket(); 316 if (list->tail)
371 if ((cp = alloc_cons_from_bucket()) == NULL) { 317 list->tail->next = entry;
372 error(2, 0, _("not enough core")); 318 else
373 } 319 list->head = entry;
374 } 320 list->tail = entry;
375 CAR(cp) = CDR(cp) = NULL;
376 return cp;
377} 321}
378 322
379/* Append a new cons to the tail of the list 323void
380 * ROOT_PTR points to a `root cons'. 324linked_list_prepend(struct linked_list **plist, void *data)
381 * CAR is the car value of the cons to be created.
382 *
383 * Note: Car of the root cons points to the head of the list,
384 * cdr of root cons points to the tail of the list.
385 */
386Consptr
387append_to_list(Consptr *root_ptr, void *car)
388{ 325{
389 Consptr root, cons; 326 struct linked_list *list = deref_linked_list (plist);
390 327 struct linked_list_entry *entry = xmalloc(sizeof(*entry));
391 if (!*root_ptr) { 328 entry->next = list->head;
392 *root_ptr = alloc_cons(); 329 entry->data = data;
393 /* both car and cdr are guaranteed to be NULL */ 330 list->head = entry;
331 if (!list->tail)
332 list->tail = entry;
333}
334
335void
336linked_list_destroy(struct linked_list **plist)
337{
338 if (plist && *plist) {
339 struct linked_list *list = *plist;
340 struct linked_list_entry *p;
341
342 for (p = list->head; p; p = p->next) {
343 if (list->free_data)
344 list->free_data(p->data);
345 free(p);
346 }
347 free(list);
348 *plist = NULL;
394 } 349 }
395 root = *root_ptr;
396
397 cons = alloc_cons();
398 if (!CAR(root))
399 CAR(root) = cons;
400
401 /* Maintain linked list */
402 if (CDR(root))
403 CDR(CDR(root)) = cons;
404 CDR(root) = cons;
405 CAR(cons) = car;
406 return cons;
407} 350}
408 351
409int 352int
410symbol_in_list(Symbol *sym, Consptr list) 353symbol_in_list(Symbol *sym, struct linked_list *list)
411{ 354{
412 Consptr cons; 355 struct linked_list_entry *p;
413 356
414 if (!list) 357 for (p = linked_list_head(list); p; p = p->next)
415 return 0; 358 if ((Symbol*)p->data == sym)
416 for (cons = CAR(list); cons; cons = CDR(cons))
417 if ((Symbol*)CAR(cons) == sym)
418 return 1; 359 return 1;
419 return 0; 360 return 0;
420} 361}

Return to:

Send suggestions and report system problems to the System administrator.