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) (side-by-side diff)
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,3 +1,3 @@
/* This file is part of GNU cflow
- Copyright (C) 1997,2005,2007 Sergey Poznyakoff
+ Copyright (C) 1997,2005,2007,2009 Sergey Poznyakoff
@@ -47,11 +47,15 @@
-typedef struct cons *Consptr;
-typedef struct cons Cons;
-struct cons {
- Consptr car;
- Consptr cdr;
+struct linked_list_entry {
+ struct linked_list_entry *next;
+ void *data;
};
-#define CAR(a) (a)->car
-#define CDR(a) (a)->cdr
+typedef void (*linked_list_free_data_fp) (void*);
+
+struct linked_list {
+ linked_list_free_data_fp free_data;
+ struct linked_list_entry *head, *tail;
+};
+
+#define linked_list_head(list) ((list) ? (list)->head : NULL)
@@ -99,3 +103,3 @@ struct symbol {
int def_line; /* Source line */
- Consptr ref_line; /* Referenced in */
+ struct linked_list *ref_line; /* Referenced in */
@@ -111,4 +115,4 @@ struct symbol {
int recursive; /* Is the function recursive */
- Consptr caller; /* List of callers */
- Consptr callee; /* List of callees */
+ struct linked_list *caller; /* List of callers */
+ struct linked_list *callee; /* List of callees */
};
@@ -164,6 +168,8 @@ void delete_parms(int level);
void move_parms(int level);
-void cleanup(void);
int collect_symbols(Symbol ***, int (*sel)());
-Consptr append_to_list(Consptr *, void *);
-int symbol_in_list(Symbol *sym, Consptr list);
+struct linked_list *linked_list_create(linked_list_free_data_fp fun);
+void linked_list_destroy(struct linked_list **plist);
+void linked_list_append(struct linked_list **plist, void *data);
+void linked_list_prepend(struct linked_list **plist, void *data);
+int symbol_in_list(Symbol *sym, struct linked_list *list);
diff --git a/src/main.c b/src/main.c
index cbb472e..b08ccdd 100644
--- a/src/main.c
+++ b/src/main.c
@@ -220,3 +220,3 @@ char *start_name = "main"; /* Name of start symbol */
-Consptr arglist; /* List of command line arguments */
+struct linked_list *arglist; /* List of command line arguments */
@@ -489,3 +489,3 @@ add_name(const char *name)
{
- append_to_list(&arglist, (void*) name);
+ linked_list_append(&arglist, (void*) name);
}
@@ -771,6 +771,7 @@ main(int argc, char **argv)
- if (arglist)
- /* See comment to cleanup_processor */
- for (arglist = CAR(arglist); arglist; arglist = CDR(arglist)) {
- char *s = (char*)CAR(arglist);
+ if (arglist) {
+ struct linked_list_entry *p;
+
+ for (p = arglist->head; p; p = p->next) {
+ char *s = (char*)p->data;
if (s[0] == '-')
@@ -780,3 +781,4 @@ main(int argc, char **argv)
}
-
+ }
+
argc -= index;
@@ -792,4 +794,2 @@ main(int argc, char **argv)
- cleanup();
-
output();
diff --git a/src/output.c b/src/output.c
index 7e604f4..f33d0ae 100644
--- a/src/output.c
+++ b/src/output.c
@@ -1,3 +1,3 @@
/* This file is part of GNU cflow
- Copyright (C) 1997,2005,2007 Sergey Poznyakoff
+ Copyright (C) 1997,2005,2007,2009 Sergey Poznyakoff
@@ -202,8 +202,9 @@ clear_active(Symbol *sym)
void
-print_refs(char *name, Consptr cons)
+print_refs(char *name, struct linked_list *reflist)
{
Ref *refptr;
-
- for ( ; cons; cons = CDR(cons)) {
- refptr = (Ref*)CAR(cons);
+ struct linked_list_entry *p;
+
+ for (p = linked_list_head(reflist); p; p = p->next) {
+ refptr = (Ref*)p->data;
fprintf(outfile, "%s %s:%d\n",
@@ -273,3 +274,3 @@ scan_tree(int lev, Symbol *sym)
{
- Consptr cons;
+ struct linked_list_entry *p;
@@ -282,4 +283,4 @@ scan_tree(int lev, Symbol *sym)
sym->active = 1;
- for (cons = sym->callee; cons; cons = CDR(cons)) {
- scan_tree(lev+1, (Symbol*)CAR(cons));
+ for (p = linked_list_head(sym->callee); p; p = p->next) {
+ scan_tree(lev+1, (Symbol*)p->data);
}
@@ -295,5 +296,5 @@ set_active(Symbol *sym)
static int
-is_printable(Consptr cons)
+is_printable(struct linked_list_entry *p)
{
- return cons != NULL && include_symbol((Symbol*)CAR(cons));
+ return p != NULL && include_symbol((Symbol*)p->data);
}
@@ -301,6 +302,6 @@ is_printable(Consptr cons)
static int
-is_last(Consptr cons)
+is_last(struct linked_list_entry *p)
{
- while (cons = CDR(cons))
- if (is_printable(cons))
+ while (p = p->next)
+ if (is_printable(p))
return 0;
@@ -314,3 +315,3 @@ direct_tree(int lev, int last, Symbol *sym)
{
- Consptr cons;
+ struct linked_list_entry *p;
int rc;
@@ -327,5 +328,5 @@ direct_tree(int lev, int last, Symbol *sym)
set_active(sym);
- for (cons = sym->callee; cons; cons = CDR(cons)) {
- set_level_mark(lev+1, is_printable(CDR(cons)));
- direct_tree(lev+1, is_last(cons), (Symbol*)CAR(cons));
+ for (p = linked_list_head(sym->callee); p; p = p->next) {
+ set_level_mark(lev+1, is_printable(p->next));
+ direct_tree(lev+1, is_last(p), (Symbol*)p->data);
}
@@ -339,3 +340,3 @@ inverted_tree(int lev, int last, Symbol *sym)
{
- Consptr cons;
+ struct linked_list_entry *p;
int rc;
@@ -351,5 +352,5 @@ inverted_tree(int lev, int last, Symbol *sym)
set_active(sym);
- for (cons = sym->caller; cons; cons = CDR(cons)) {
- set_level_mark(lev+1, is_printable(CDR(cons)));
- inverted_tree(lev+1, is_last(cons), (Symbol*)CAR(cons));
+ for (p = linked_list_head(sym->caller); p; p = p->next) {
+ set_level_mark(lev+1, is_printable(p->next));
+ inverted_tree(lev+1, is_last(p), (Symbol*)p->data);
}
diff --git a/src/parser.c b/src/parser.c
index 911bf58..26ac25d 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -1,3 +1,3 @@
/* This file is part of GNU cflow
- Copyright (C) 1997, 2005, 2006, 2007 Sergey Poznyakoff
+ Copyright (C) 1997, 2005, 2006, 2007, 2009 Sergey Poznyakoff
@@ -1079,3 +1079,5 @@ add_reference(char *name, int line)
refptr->line = line;
- append_to_list(&sp->ref_line, refptr);
+ if (!sp->ref_line)
+ sp->ref_line = linked_list_create(free);
+ linked_list_append(&sp->ref_line, refptr);
return sp;
@@ -1096,5 +1098,5 @@ call(char *name, int line)
if (!symbol_in_list(caller, sp->caller))
- append_to_list(&sp->caller, caller);
+ linked_list_append(&sp->caller, caller);
if (!symbol_in_list(sp, caller->callee))
- append_to_list(&caller->callee, sp);
+ linked_list_append(&caller->callee, sp);
}
@@ -1110,5 +1112,5 @@ reference(char *name, int line)
if (!symbol_in_list(caller, sp->caller))
- append_to_list(&sp->caller, caller);
+ linked_list_append(&sp->caller, caller);
if (!symbol_in_list(sp, caller->callee))
- append_to_list(&caller->callee, sp);
+ linked_list_append(&caller->callee, sp);
}
diff --git a/src/symbol.c b/src/symbol.c
index 4fe5f85..e3ccd7c 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -1,3 +1,3 @@
/* This file is part of GNU cflow
- Copyright (C) 1997, 2005, 2006, 2007 Sergey Poznyakoff
+ Copyright (C) 1997, 2005, 2006, 2007, 2009 Sergey Poznyakoff
@@ -112,8 +112,10 @@ delete_symbol(struct table_entry *tp)
in -i^s mode. See tests/static.at for details. */
- if (s->ref_line == NULL)
+ if (s->ref_line == NULL) {
+ linked_list_destroy(&s->ref_line);
+ linked_list_destroy(&s->caller);
+ linked_list_destroy(&s->callee);
free(s);
+ }
}
-static void cleanup_symbol_refs(Symbol *sym);
-
/* Delete from the symbol table all static symbols defined in the current
@@ -122,4 +124,3 @@ static void cleanup_symbol_refs(Symbol *sym);
not deleted, as it may have been referenced by other symbols. Instead,
- it is unlinked from its table entry and cleanup_symbol_refs() is
- called, so that its reference tables become usable.
+ it is unlinked from its table entry.
NOTE: This takes advantage of the fact that install() uses LIFO strategy,
@@ -139,3 +140,3 @@ static_processor(void *data, void *proc_data)
else
- cleanup_symbol_refs(unlink_symbol(t));
+ unlink_symbol(t);
}
@@ -176,3 +177,3 @@ auto_processor(void *data, void *proc_data)
case StaticStorage:
- cleanup_symbol_refs(unlink_symbol(t));
+ unlink_symbol(t);
break;
@@ -195,44 +196,2 @@ delete_autos(int level)
-
-/* Make all list pointers of the SYM ready for final processing.
- * This means for each list replace its entry point with its CAR
- * and throw away the first cons. The first cons holds pointers
- * to the head and tail of the list and is used to speed up appends.
- *
- * TODO: The memory is not reclaimed
- */
-static void
-cleanup_symbol_refs(Symbol *sym)
-{
- if (sym && sym->type == SymIdentifier) {
- if (sym->ref_line)
- sym->ref_line = CAR(sym->ref_line);
- if (sym->caller)
- sym->caller = CAR(sym->caller);
- if (sym->callee)
- sym->callee = CAR(sym->callee);
- }
-}
-
-static bool
-cleanup_processor(void *data, void *proc_data)
-{
- struct table_entry *t = data;
- Symbol *sym;
- for (sym = t->sym; sym; sym = sym->next) {
- cleanup_symbol_refs(sym);
- }
- return true;
-}
-
-
-/* Clean up all symbols from the auxiliary information.
- * See the comment for cleanup_symbol() above
- */
-void
-cleanup()
-{
- hash_do_for_each (symbol_table, cleanup_processor, NULL);
-}
-
struct collect_data {
@@ -326,82 +285,66 @@ move_parms(int level)
-typedef struct bucket Bucket;
-struct bucket {
- Bucket *next; /* Next bucket */
- int free;
- Cons cons[1];
-};
-
-static int bucket_nodes = 512;
-static Bucket *root_bucket, *last_bucket;
-void
-alloc_new_bucket()
+static struct linked_list *
+deref_linked_list (struct linked_list **plist)
{
- Bucket *bp;
-
- bp = malloc(sizeof(*bp) + sizeof(Cons)*(bucket_nodes-1));
- if (!bp)
- return;
- bp->next = NULL;
- bp->free = 0;
- if (!root_bucket)
- root_bucket = last_bucket = bp;
- else {
- last_bucket->next = bp;
- last_bucket = bp;
+ if (!*plist) {
+ struct linked_list *list = xmalloc(sizeof(*list));
+ list->free_data = NULL;
+ list->head = list->tail = NULL;
+ *plist = list;
}
+ return *plist;
}
-Consptr
-alloc_cons_from_bucket()
+
+struct linked_list *
+linked_list_create(linked_list_free_data_fp fun)
{
- if (!last_bucket || last_bucket->free == bucket_nodes)
- return NULL;
- return &last_bucket->cons[last_bucket->free++];
+ struct linked_list *list = xmalloc(sizeof(*list));
+ list->free_data = fun;
+ list->head = list->tail = NULL;
+ return list;
}
-Consptr
-alloc_cons()
+void
+linked_list_append(struct linked_list **plist, void *data)
{
- Consptr cp;
-
- cp = alloc_cons_from_bucket();
- if (!cp) {
- alloc_new_bucket();
- if ((cp = alloc_cons_from_bucket()) == NULL) {
- error(2, 0, _("not enough core"));
- }
- }
- CAR(cp) = CDR(cp) = NULL;
- return cp;
+ struct linked_list *list = deref_linked_list (plist);
+ struct linked_list_entry *entry = xmalloc(sizeof(*entry));
+ entry->next = NULL;
+ entry->data = data;
+ if (list->tail)
+ list->tail->next = entry;
+ else
+ list->head = entry;
+ list->tail = entry;
}
-/* Append a new cons to the tail of the list
- * ROOT_PTR points to a `root cons'.
- * CAR is the car value of the cons to be created.
- *
- * Note: Car of the root cons points to the head of the list,
- * cdr of root cons points to the tail of the list.
- */
-Consptr
-append_to_list(Consptr *root_ptr, void *car)
+void
+linked_list_prepend(struct linked_list **plist, void *data)
{
- Consptr root, cons;
-
- if (!*root_ptr) {
- *root_ptr = alloc_cons();
- /* both car and cdr are guaranteed to be NULL */
+ struct linked_list *list = deref_linked_list (plist);
+ struct linked_list_entry *entry = xmalloc(sizeof(*entry));
+ entry->next = list->head;
+ entry->data = data;
+ list->head = entry;
+ if (!list->tail)
+ list->tail = entry;
+}
+
+void
+linked_list_destroy(struct linked_list **plist)
+{
+ if (plist && *plist) {
+ struct linked_list *list = *plist;
+ struct linked_list_entry *p;
+
+ for (p = list->head; p; p = p->next) {
+ if (list->free_data)
+ list->free_data(p->data);
+ free(p);
+ }
+ free(list);
+ *plist = NULL;
}
- root = *root_ptr;
-
- cons = alloc_cons();
- if (!CAR(root))
- CAR(root) = cons;
-
- /* Maintain linked list */
- if (CDR(root))
- CDR(CDR(root)) = cons;
- CDR(root) = cons;
- CAR(cons) = car;
- return cons;
}
@@ -409,10 +352,8 @@ append_to_list(Consptr *root_ptr, void *car)
int
-symbol_in_list(Symbol *sym, Consptr list)
+symbol_in_list(Symbol *sym, struct linked_list *list)
{
- Consptr cons;
+ struct linked_list_entry *p;
- if (!list)
- return 0;
- for (cons = CAR(list); cons; cons = CDR(cons))
- if ((Symbol*)CAR(cons) == sym)
+ for (p = linked_list_head(list); p; p = p->next)
+ if ((Symbol*)p->data == sym)
return 1;

Return to:

Send suggestions and report system problems to the System administrator.