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; } _______________________________________________ svn-src-all@freebsd.org mailing list https://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
