Module Name: src
Committed By: rillig
Date: Mon Sep 27 18:21:47 UTC 2021
Modified Files:
src/usr.bin/indent: indent.c indent.h lexi.c
Log Message:
indent: use binary instead of linear search when adding types
No functional change.
To generate a diff of this commit:
cvs rdiff -u -r1.89 -r1.90 src/usr.bin/indent/indent.c
cvs rdiff -u -r1.25 -r1.26 src/usr.bin/indent/indent.h
cvs rdiff -u -r1.63 -r1.64 src/usr.bin/indent/lexi.c
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/usr.bin/indent/indent.c
diff -u src/usr.bin/indent/indent.c:1.89 src/usr.bin/indent/indent.c:1.90
--- src/usr.bin/indent/indent.c:1.89 Mon Sep 27 16:56:35 2021
+++ src/usr.bin/indent/indent.c Mon Sep 27 18:21:47 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: indent.c,v 1.89 2021/09/27 16:56:35 rillig Exp $ */
+/* $NetBSD: indent.c,v 1.90 2021/09/27 18:21:47 rillig Exp $ */
/*-
* SPDX-License-Identifier: BSD-4-Clause
@@ -43,7 +43,7 @@ static char sccsid[] = "@(#)indent.c 5.1
#include <sys/cdefs.h>
#if defined(__NetBSD__)
-__RCSID("$NetBSD: indent.c,v 1.89 2021/09/27 16:56:35 rillig Exp $");
+__RCSID("$NetBSD: indent.c,v 1.90 2021/09/27 18:21:47 rillig Exp $");
#elif defined(__FreeBSD__)
__FBSDID("$FreeBSD: head/usr.bin/indent/indent.c 340138 2018-11-04 19:24:49Z oshogbo $");
#endif
@@ -379,7 +379,6 @@ main_init_globals(void)
buf_init(&lab);
buf_init(&code);
buf_init(&token);
- alloc_typenames();
opt.else_if = true; /* XXX: redundant? */
in_buffer = xmalloc(10);
Index: src/usr.bin/indent/indent.h
diff -u src/usr.bin/indent/indent.h:1.25 src/usr.bin/indent/indent.h:1.26
--- src/usr.bin/indent/indent.h:1.25 Sat Sep 25 22:14:21 2021
+++ src/usr.bin/indent/indent.h Mon Sep 27 18:21:47 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: indent.h,v 1.25 2021/09/25 22:14:21 rillig Exp $ */
+/* $NetBSD: indent.h,v 1.26 2021/09/27 18:21:47 rillig Exp $ */
/*-
* SPDX-License-Identifier: BSD-2-Clause-FreeBSD
@@ -42,7 +42,6 @@ __FBSDID("$FreeBSD: head/usr.bin/indent/
#endif
void add_typename(const char *);
-void alloc_typenames(void);
int compute_code_indent(void);
int compute_label_indent(void);
int indentation_after_range(int, const char *, const char *);
Index: src/usr.bin/indent/lexi.c
diff -u src/usr.bin/indent/lexi.c:1.63 src/usr.bin/indent/lexi.c:1.64
--- src/usr.bin/indent/lexi.c:1.63 Mon Sep 27 17:33:07 2021
+++ src/usr.bin/indent/lexi.c Mon Sep 27 18:21:47 2021
@@ -1,4 +1,4 @@
-/* $NetBSD: lexi.c,v 1.63 2021/09/27 17:33:07 rillig Exp $ */
+/* $NetBSD: lexi.c,v 1.64 2021/09/27 18:21:47 rillig Exp $ */
/*-
* SPDX-License-Identifier: BSD-4-Clause
@@ -43,7 +43,7 @@ static char sccsid[] = "@(#)lexi.c 8.1 (
#include <sys/cdefs.h>
#if defined(__NetBSD__)
-__RCSID("$NetBSD: lexi.c,v 1.63 2021/09/27 17:33:07 rillig Exp $");
+__RCSID("$NetBSD: lexi.c,v 1.64 2021/09/27 18:21:47 rillig Exp $");
#elif defined(__FreeBSD__)
__FBSDID("$FreeBSD: head/usr.bin/indent/lexi.c 337862 2018-08-15 18:19:45Z pstef $");
#endif
@@ -106,9 +106,11 @@ static const struct keyword {
{"while", kw_for_or_if_or_while}
};
-static const char **typenames;
-static int typename_count;
-static int typename_top = -1;
+struct {
+ const char **items;
+ unsigned int len;
+ unsigned int cap;
+} typenames;
/*
* The transition table below was rewritten by hand from lx's output, given
@@ -344,10 +346,10 @@ is_typename(void)
return true;
}
- if (typename_top < 0)
+ if (typenames.len == 0)
return false;
- return bsearch(token.s, typenames, (size_t)typename_top + 1,
- sizeof(typenames[0]), cmp_type_by_name) != NULL;
+ return bsearch(token.s, typenames.items, (size_t)typenames.len,
+ sizeof(typenames.items[0]), cmp_type_by_name) != NULL;
}
/* Reads the next token, placing it in the global variable "token". */
@@ -662,38 +664,38 @@ lexi(struct parser_state *state)
return lexi_end(ttype);
}
-void
-alloc_typenames(void)
-{
-
- typenames = xmalloc(sizeof(typenames[0]) * (typename_count = 16));
+static int
+insert_pos(const char *key, const char **arr, unsigned int len) {
+ int lo = 0;
+ int hi = (int)len - 1;
+
+ while (lo <= hi) {
+ int mid = (lo + hi) >> 1;
+ int cmp = strcmp(arr[mid], key);
+ if (cmp < 0)
+ lo = mid + 1;
+ else if (cmp > 0)
+ hi = mid - 1;
+ else
+ return mid;
+ }
+ return -(lo + 1);
}
void
-add_typename(const char *key)
+add_typename(const char *name)
{
- int comparison;
-
- if (typename_top + 1 >= typename_count) {
- typenames = xrealloc((void *)typenames,
- sizeof(typenames[0]) * (typename_count *= 2));
- }
- if (typename_top == -1)
- typenames[++typename_top] = xstrdup(key);
- else if ((comparison = strcmp(key, typenames[typename_top])) >= 0) {
- /* take advantage of sorted input */
- if (comparison == 0) /* remove duplicates */
- return;
- typenames[++typename_top] = xstrdup(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;
- memmove(&typenames[p + 1], &typenames[p],
- sizeof(typenames[0]) * (++typename_top - p));
- typenames[p] = xstrdup(key);
+ if (typenames.len >= typenames.cap) {
+ typenames.cap = 16 + 2 * typenames.cap;
+ typenames.items = xrealloc(typenames.items,
+ sizeof(typenames.items[0]) * typenames.cap);
}
+
+ int pos = insert_pos(name, typenames.items, typenames.len);
+ if (pos >= 0)
+ return; /* already in the list */
+ pos = -(pos + 1);
+ memmove(typenames.items + pos + 1, typenames.items + pos,
+ sizeof(typenames.items[0]) * (typenames.len++ - pos));
+ typenames.items[pos] = xstrdup(name);
}
