Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/xlint/xlint lint: turn O(n^2) to O(n) for list of ar...
details: https://anonhg.NetBSD.org/src/rev/69ddfa715a8f
branches: trunk
changeset: 373062:69ddfa715a8f
user: rillig <rillig%NetBSD.org@localhost>
date: Sun Jan 15 15:20:18 2023 +0000
description:
lint: turn O(n^2) to O(n) for list of arguments to lint child processes
Previously, adding an argument to the lint child processes (cpp, lint1,
lint2) each time searched the list of arguments for the terminating
null pointer and then reallocated the memory for storing the strings.
Replace the above with a standard resizable array implementation and
give it a proper name, to avoid 'char ***' in the code.
The terminating null pointer in the lists is only required when passing
the list to execvp. In all other cases it's not needed, so drop it.
No functional change.
diffstat:
usr.bin/xlint/xlint/xlint.c | 223 +++++++++++++++++--------------------------
1 files changed, 90 insertions(+), 133 deletions(-)
diffs (truncated from 466 to 300 lines):
diff -r 17caf71a089d -r 69ddfa715a8f usr.bin/xlint/xlint/xlint.c
--- a/usr.bin/xlint/xlint/xlint.c Sun Jan 15 14:43:39 2023 +0000
+++ b/usr.bin/xlint/xlint/xlint.c Sun Jan 15 15:20:18 2023 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: xlint.c,v 1.98 2023/01/15 14:43:39 rillig Exp $ */
+/* $NetBSD: xlint.c,v 1.99 2023/01/15 15:20:18 rillig Exp $ */
/*
* Copyright (c) 1996 Christopher G. Demetriou. All Rights Reserved.
@@ -38,7 +38,7 @@
#include <sys/cdefs.h>
#if defined(__RCSID)
-__RCSID("$NetBSD: xlint.c,v 1.98 2023/01/15 14:43:39 rillig Exp $");
+__RCSID("$NetBSD: xlint.c,v 1.99 2023/01/15 15:20:18 rillig Exp $");
#endif
#include <sys/param.h>
@@ -62,25 +62,31 @@
#define DEFAULT_PATH _PATH_DEFPATH
+typedef struct {
+ char **items;
+ size_t len;
+ size_t cap;
+} list;
+
/* Parameters for the C preprocessor. */
static struct {
- char **flags; /* flags always passed */
- char **lcflags; /* flags, controlled by sflag/tflag */
+ list flags; /* flags always passed */
+ list lcflags; /* flags, controlled by sflag/tflag */
char *outfile; /* path name for preprocessed C source */
int outfd; /* file descriptor for outfile */
-} cpp = { NULL, NULL, NULL, -1 };
+} cpp = { .outfd = -1 };
/* Parameters for lint1, which checks an isolated translation unit. */
static struct {
- char **flags;
- char **outfiles;
+ list flags;
+ list outfiles;
} lint1;
/* Parameters for lint2, which performs cross-translation-unit checks. */
static struct {
- char **flags;
- char **infiles; /* input files (without libraries) */
- char **inlibs; /* input libraries */
+ list flags;
+ list infiles; /* input files (without libraries) */
+ list inlibs; /* input libraries */
char *outlib; /* output library that will be created */
} lint2;
@@ -88,13 +94,13 @@
static const char *tmpdir;
/* default libraries */
-static char **deflibs;
+static list deflibs;
/* additional libraries */
-static char **libs;
+static list libs;
/* search path for libraries */
-static char **libsrchpath;
+static list libsrchpath;
static const char *libexec_dir;
@@ -122,84 +128,54 @@
static const char target_prefix[] = TARGET_PREFIX;
static void fname(const char *);
-static void run_child(const char *, char *const *, const char *, int);
-static void find_libs(char *const *);
+static void run_child(const char *, list *, const char *, int);
+static void find_libs(const list *);
static bool file_is_readable(const char *);
static void run_lint2(void);
-static void cat(char *const *, const char *);
-
-static char **
-list_new(void)
-{
- char **list;
-
- list = xcalloc(1, sizeof(*list));
- return list;
-}
+static void cat(const list *, const char *);
static void
-list_add_ref(char ***lstp, char *s)
-{
- char **lst, **olst;
- int i;
-
- olst = *lstp;
- for (i = 0; olst[i] != NULL; i++)
- continue;
- lst = xrealloc(olst, (i + 2) * sizeof(*lst));
- lst[i] = s;
- lst[i + 1] = NULL;
- *lstp = lst;
-}
-
-static void
-list_add(char ***lstp, const char *s)
+list_add_ref(list *l, char *s)
{
- list_add_ref(lstp, xstrdup(s));
+ if (l->len >= l->cap) {
+ l->cap = 2 * l->len + 16;
+ l->items = xrealloc(l->items, sizeof(*l->items) * l->cap);
+ }
+ l->items[l->len++] = s;
}
static void
-list_add_unique(char ***lstp, const char *s)
+list_add(list *l, const char *s)
{
- for (char **p = *lstp; *p != NULL; p++)
- if (strcmp(*p, s) == 0)
- return;
- list_add(lstp, s);
+ list_add_ref(l, xstrdup(s));
}
static void
-list_add_all(char ***destp, char *const *src)
+list_add_unique(list *l, const char *s)
{
- int i, k;
- char **dest, **odest;
- odest = *destp;
- for (i = 0; odest[i] != NULL; i++)
- continue;
- for (k = 0; src[k] != NULL; k++)
- continue;
- dest = xrealloc(odest, (i + k + 1) * sizeof(*dest));
- for (k = 0; src[k] != NULL; k++)
- dest[i + k] = xstrdup(src[k]);
- dest[i + k] = NULL;
- *destp = dest;
+ for (size_t i = 0; i < l->len; i++)
+ if (strcmp(l->items[i], s) == 0)
+ return;
+ list_add(l, s);
}
static void
-list_clear(char ***lstp)
+list_add_all(list *dst, const list *src)
{
- char *s;
- int i;
+
+ for (size_t i = 0; i < src->len; i++)
+ list_add(dst, src->items[i]);
+}
- for (i = 0; (*lstp)[i] != NULL; i++)
- continue;
- while (i-- > 0) {
- s = (*lstp)[i];
- (*lstp)[i] = NULL;
- free(s);
- }
+static void
+list_clear(list *l)
+{
+
+ while (l->len > 0)
+ free(l->items[--l->len]);
}
static void
@@ -256,7 +232,6 @@
static void __attribute__((__noreturn__))
terminate(int signo)
{
- int i;
if (cpp.outfd != -1)
(void)close(cpp.outfd);
@@ -268,10 +243,8 @@
(void)remove(cpp.outfile);
}
- if (lint1.outfiles != NULL) {
- for (i = 0; lint1.outfiles[i] != NULL; i++)
- (void)remove(lint1.outfiles[i]);
- }
+ for (size_t i = 0; i < lint1.outfiles.len; i++)
+ (void)remove(lint1.outfiles.items[i]);
if (lint2.outlib != NULL)
(void)remove(lint2.outlib);
@@ -357,17 +330,6 @@
terminate(-1);
}
- lint1.outfiles = list_new();
- lint2.infiles = list_new();
- cpp.flags = list_new();
- cpp.lcflags = list_new();
- lint1.flags = list_new();
- lint2.flags = list_new();
- lint2.inlibs = list_new();
- deflibs = list_new();
- libs = list_new();
- libsrchpath = list_new();
-
pass_to_cpp("-E");
pass_to_cpp("-x");
pass_to_cpp("c");
@@ -435,7 +397,7 @@
break;
case 'p':
- if (*deflibs != NULL) {
+ if (deflibs.len > 0) {
list_clear(&deflibs);
list_add(&deflibs, "c");
}
@@ -569,23 +531,23 @@
const char *arg = argv[0];
if (arg[0] == '-') {
- char ***list;
+ list *lp;
/* option */
if (arg[1] == 'l')
- list = &libs;
+ lp = &libs;
else if (arg[1] == 'L')
- list = &libsrchpath;
+ lp = &libsrchpath;
else {
usage("Unknown late option '%s'", arg);
/* NOTREACHED */
}
if (arg[2] != '\0')
- list_add_unique(list, arg + 2);
+ list_add_unique(lp, arg + 2);
else if (argc > 1) {
argc--;
- list_add_unique(list, *++argv);
+ list_add_unique(lp, *++argv);
} else
usage("Missing argument for l or L");
} else {
@@ -607,14 +569,14 @@
if ((ks = getenv("LIBDIR")) == NULL || strlen(ks) == 0)
ks = PATH_LINTLIB;
list_add(&libsrchpath, ks);
- find_libs(libs);
- find_libs(deflibs);
+ find_libs(&libs);
+ find_libs(&deflibs);
}
run_lint2();
if (oflag)
- cat(lint2.infiles, outputfn);
+ cat(&lint2.infiles, outputfn);
if (Cflag)
lint2.outlib = NULL;
@@ -630,9 +592,8 @@
static void
fname(const char *name)
{
- const char *bn, *suff;
- char **args, *ofn, *pathname;
- const char *CC;
+ const char *bn, *suff, *CC;
+ char *ofn, *pathname;
size_t len;
int fd;
@@ -675,8 +636,6 @@
if (!iflag)
list_add(&lint1.outfiles, ofn);
- args = list_new();
-
Home |
Main Index |
Thread Index |
Old Index