svn commit: r303746 - head/usr.bin/indent
Pedro F. Giffuni
pfg at FreeBSD.org
Thu Aug 4 15:27:11 UTC 2016
Author: pfg
Date: Thu Aug 4 15:27:09 2016
New Revision: 303746
URL: https://svnweb.freebsd.org/changeset/base/303746
Log:
indent(1): Use bsearch() for looking up type keywords.
Reference:
https://github.com/pstef/freebsd_indent/commit/f3b8e6e57fd47364b2360b44011a2fad5d11adc7
Submitted by: Piotr Stefaniak
Differential Revision: https://reviews.freebsd.org/D6966
Modified:
head/usr.bin/indent/args.c
head/usr.bin/indent/indent.c
head/usr.bin/indent/indent.h
head/usr.bin/indent/lexi.c
Modified: head/usr.bin/indent/args.c
==============================================================================
--- head/usr.bin/indent/args.c Thu Aug 4 14:34:33 2016 (r303745)
+++ head/usr.bin/indent/args.c Thu Aug 4 15:27:09 2016 (r303746)
@@ -298,7 +298,7 @@ found:
char *str = strdup(param_start);
if (str == NULL)
err(1, NULL);
- addkey(str, 4);
+ add_typename(str);
}
break;
@@ -342,6 +342,7 @@ add_typedefs_from_file(const char *str)
{
FILE *file;
char line[BUFSIZ];
+ char *copy;
if ((file = fopen(str, "r")) == NULL) {
fprintf(stderr, "indent: cannot open file %s\n", str);
@@ -349,8 +350,11 @@ add_typedefs_from_file(const char *str)
}
while ((fgets(line, BUFSIZ, file)) != NULL) {
/* Remove trailing whitespace */
- *(line + strcspn(line, " \t\n\r")) = '\0';
- addkey(strdup(line), 4);
+ line[strcspn(line, " \t\n\r")] = '\0';
+ if ((copy = strdup(line)) == NULL) {
+ err(1, NULL);
+ }
+ add_typename(copy);
}
fclose(file);
}
Modified: head/usr.bin/indent/indent.c
==============================================================================
--- head/usr.bin/indent/indent.c Thu Aug 4 14:34:33 2016 (r303745)
+++ head/usr.bin/indent/indent.c Thu Aug 4 15:27:09 2016 (r303746)
@@ -119,6 +119,7 @@ main(int argc, char **argv)
tokenbuf = (char *) malloc(bufsize);
if (tokenbuf == NULL)
err(1, NULL);
+ alloc_typenames();
l_com = combuf + bufsize - 5;
l_lab = labbuf + bufsize - 5;
l_code = codebuf + bufsize - 5;
Modified: head/usr.bin/indent/indent.h
==============================================================================
--- head/usr.bin/indent/indent.h Thu Aug 4 14:34:33 2016 (r303745)
+++ head/usr.bin/indent/indent.h Thu Aug 4 15:27:09 2016 (r303746)
@@ -28,7 +28,8 @@
__FBSDID("$FreeBSD$");
#endif
-void addkey(char *, int);
+void add_typename(const char *);
+void alloc_typenames(void);
int compute_code_target(void);
int compute_label_target(void);
int count_spaces(int, char *);
Modified: head/usr.bin/indent/lexi.c
==============================================================================
--- head/usr.bin/indent/lexi.c Thu Aug 4 14:34:33 2016 (r303745)
+++ head/usr.bin/indent/lexi.c Thu Aug 4 15:27:09 2016 (r303746)
@@ -64,42 +64,49 @@ struct templ {
int rwcode;
};
-struct templ specials[16384] =
+/*
+ * This table has to be sorted alphabetically, because it'll be used in binary
+ * search. For the same reason, string must be the first thing in struct templ.
+ */
+struct templ specials[] =
{
- {"switch", 7},
- {"case", 8},
{"break", 9},
- {"struct", 3},
- {"union", 3},
- {"enum", 3},
- {"default", 8},
- {"int", 4},
+ {"case", 8},
{"char", 4},
- {"float", 4},
+ {"const", 4},
+ {"default", 8},
+ {"do", 6},
{"double", 4},
+ {"else", 6},
+ {"enum", 3},
+ {"extern", 4},
+ {"float", 4},
+ {"for", 5},
+ {"global", 4},
+ {"goto", 9},
+ {"if", 5},
+ {"int", 4},
{"long", 4},
+ {"offsetof", 1},
+ {"register", 4},
+ {"return", 9},
{"short", 4},
+ {"sizeof", 2},
+ {"static", 4},
+ {"struct", 3},
+ {"switch", 7},
{"typedef", 4},
+ {"union", 3},
{"unsigned", 4},
- {"register", 4},
- {"static", 4},
- {"global", 4},
- {"extern", 4},
{"void", 4},
- {"const", 4},
{"volatile", 4},
- {"goto", 9},
- {"return", 9},
- {"if", 5},
- {"while", 5},
- {"for", 5},
- {"else", 6},
- {"do", 6},
- {"sizeof", 2},
- {"offsetof", 1},
- {0, 0}
+ {"while", 5}
};
+const char **typenames;
+int typename_count;
+int typename_top = -1;
+
char chartype[128] =
{ /* this is used to facilitate the decision of
* what type (alphanumeric, operator) each
@@ -122,6 +129,12 @@ char chartype[128] =
1, 1, 1, 0, 3, 0, 3, 0
};
+static int
+strcmp_type(const void *e1, const void *e2)
+{
+ return (strcmp(e1, *(const char * const *)e2));
+}
+
int
lexi(void)
{
@@ -150,9 +163,6 @@ lexi(void)
/*
* we have a character or number
*/
- const char *j; /* used for searching thru list of
- *
- * reserved words */
struct templ *p;
if (isdigit(*buf_ptr) || (buf_ptr[0] == '.' && isdigit(buf_ptr[1]))) {
@@ -247,37 +257,24 @@ lexi(void)
last_code = ident; /* Remember that this is the code we will
* return */
- if (auto_typedefs) {
- const char *q = s_token;
- size_t q_len = strlen(q);
- /* Check if we have an "_t" in the end */
- if (q_len > 2 &&
- (strcmp(q + q_len - 2, "_t") == 0)) {
- ps.keyword = 4; /* a type name */
+ p = bsearch(s_token,
+ specials,
+ sizeof(specials) / sizeof(specials[0]),
+ sizeof(specials[0]),
+ strcmp_type);
+ if (p == NULL) { /* not a special keyword... */
+ char *u;
+
+ /* ... so maybe a type_t or a typedef */
+ if ((auto_typedefs && ((u = strrchr(s_token, '_')) != NULL) &&
+ strcmp(u, "_t") == 0) || (typename_top >= 0 &&
+ bsearch(s_token, typenames, typename_top + 1,
+ sizeof(typenames[0]), strcmp_type))) {
+ ps.keyword = 4; /* a type name */
ps.last_u_d = true;
- goto found_auto_typedef;
+ goto found_typename;
}
- }
-
- /*
- * This loop will check if the token is a keyword.
- */
- for (p = specials; (j = p->rwd) != NULL; p++) {
- const char *q = s_token; /* point at scanned token */
- if (*j++ != *q++ || *j++ != *q++)
- continue; /* This test depends on the fact that
- * identifiers are always at least 1 character
- * long (ie. the first two bytes of the
- * identifier are always meaningful) */
- if (q[-1] == 0)
- break; /* If its a one-character identifier */
- while (*q++ == *j)
- if (*j++ == 0)
- goto found_keyword; /* I wish that C had a multi-level
- * break... */
- }
- if (p->rwd) { /* we have a keyword */
- found_keyword:
+ } else { /* we have a keyword */
ps.keyword = p->rwcode;
ps.last_u_d = true;
switch (p->rwcode) {
@@ -295,7 +292,7 @@ lexi(void)
/* FALLTHROUGH */
case 4: /* one of the declaration keywords */
- found_auto_typedef:
+ found_typename:
if (ps.p_l_follow) {
/* inside parens: cast, param list, offsetof or sizeof */
ps.cast_mask |= (1 << ps.p_l_follow) & ~ps.not_cast_mask;
@@ -583,24 +580,43 @@ stop_lit:
return (code);
}
-/*
- * Add the given keyword to the keyword table, using val as the keyword type
- */
void
-addkey(char *key, int val)
+alloc_typenames(void)
+{
+
+ typenames = (const char **)malloc(sizeof(typenames[0]) *
+ (typename_count = 16));
+ if (typenames == NULL)
+ err(1, NULL);
+}
+
+void
+add_typename(const char *key)
{
- struct templ *p = specials;
- while (p->rwd)
- if (p->rwd[0] == key[0] && strcmp(p->rwd, key) == 0)
+ int comparison;
+
+ if (typename_top + 1 >= typename_count) {
+ typenames = realloc((void *)typenames,
+ sizeof(typenames[0]) * (typename_count *= 2));
+ if (typenames == NULL)
+ err(1, NULL);
+ }
+ if (typename_top == -1)
+ typenames[++typename_top] = key;
+ else if ((comparison = strcmp(key, typenames[typename_top])) >= 0) {
+ /* take advantage of sorted input */
+ if (comparison != 0) /* remove duplicates */
+ typenames[++typename_top] = key;
+ }
+ else {
+ int p;
+
+ for (p = 0; (comparison = strcmp(key, typenames[p])) >= 0; p++)
+ /* find place for the new key */;
+ if (comparison == 0) /* remove duplicates */
return;
- else
- p++;
- if (p >= specials + sizeof(specials) / sizeof(specials[0])) {
- fprintf(stderr, "indent: typedef table overflow\n");
- exit(1);
+ memmove(&typenames[p + 1], &typenames[p],
+ sizeof(typenames[0]) * (++typename_top - p));
+ typenames[p] = key;
}
- p->rwd = key;
- p->rwcode = val;
- p[1].rwd = NULL;
- p[1].rwcode = 0;
}
More information about the svn-src-all
mailing list