чување d22b9ddf144065211fda9ad4e01e0a4a04686f8c
родитељ 2b009519424711861dc3721f17547871d06064f6
Аутор: Страхиња Радић <contact@strahinja.org>
Датум: Sat, 29 Jun 2024 08:51:50 +0200
Apply optimizations
Diffstat:
| M | dtree.c | | | 205 | +++++++++++++++++++++++++++++++++++++++++++------------------------------------ |
| A | test/test-003.txt | | | 6 | ++++++ |
измењених датотека: 2, додавања: 119(+), брисања: 92(-)
diff --git a/dtree.c b/dtree.c
@@ -2,6 +2,8 @@
* any later version. Copyright (C) 2023-2024 Страхиња Радић.
* See the file LICENSE for exact copyright and license details. */
+#include <errno.h>
+#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
@@ -11,7 +13,8 @@
#include "utf8.h"
#include "version.h"
-#define BUFSIZE 4096
+#define LINE_DEFAULT 85
+#define LINE_ALLOC_DELTA ((96 - LINE_DEFAULT) + 96)
#define COPYRIGHT \
(" This program is licensed under the terms of GNU GPL v3" \
" or (at your option)\n" \
@@ -34,22 +37,24 @@ struct Node {
enum { TREE_SYMBOLS_ASCII, TREE_SYMBOLS_SINGLE, TREE_SYMBOLS_DOUBLE };
-struct Node* alloc_node(void);
-void cleanup(void);
-int error(int code, char* fmt, ...);
-void free_node(struct Node** root);
-void insert_node(struct Node** root, const int level, const char* label);
-void print_indent(void);
-void print_node(const struct Node* node);
-void set_node(struct Node* node, const int level, const char* label);
-size_t strlcat(char* dst, const char* src, size_t dsize);
-size_t strlcpy(char* dst, const char* src, size_t dsize);
-int string_to_symbol_set(const char* s);
-void usage(void);
-void version(const int full);
-void warning(char* fmt, ...);
+static struct Node* alloc_node(void);
+static void cleanup(void);
+static int error(int code, char* fmt, ...);
+static void free_node(struct Node** root);
+static void insert_node(struct Node** root, const int level, const char* label);
+static void print_indent(void);
+static void print_node(const struct Node* node);
+static void set_node(struct Node* node, const int level, const char* label);
+static void usage(void);
+static void version(const int full);
+static void warning(char* fmt, ...);
/* clang-format off */
+static const int string_to_symbol_set[] = {
+ ['a'] = TREE_SYMBOLS_ASCII,
+ ['d'] = TREE_SYMBOLS_DOUBLE,
+ ['s'] = TREE_SYMBOLS_SINGLE
+};
static const u32 tree_symbols[][5] = {
[TREE_SYMBOLS_ASCII] = {
(u32)L'`', (u32)L'+', (u32)L'-',
@@ -71,21 +76,22 @@ static u32* pindent = NULL;
static struct Node* root = NULL;
static int symbol_set = TREE_SYMBOLS_SINGLE;
-struct Node*
+static struct Node*
alloc_node(void)
{
struct Node* newnode = NULL;
- newnode = (struct Node*)calloc(sizeof(struct Node), 1);
+ newnode = malloc(sizeof(struct Node));
if (!newnode)
{
- perror("calloc");
- exit(error(1, "Cannot alloc"));
+ perror(PROGRAMNAME ": malloc");
+ exit(1);
}
newnode->level = 0;
newnode->label = NULL;
newnode->parent = NULL;
+ newnode->children = NULL;
newnode->children_count = 0;
newnode->last_child = NULL;
newnode->next = NULL;
@@ -93,18 +99,18 @@ alloc_node(void)
return newnode;
}
-void
+static void
cleanup(void)
{
free_node(&root);
- // free(root);
+ /* free(root); */
free(indent);
}
-int
+static int
error(int code, char* fmt, ...)
{
- char buf[BUFSIZE];
+ char buf[LINE_DEFAULT];
va_list args;
va_start(args, fmt);
vsnprintf(buf, sizeof buf, (const char*)fmt, args);
@@ -113,7 +119,7 @@ error(int code, char* fmt, ...)
return code;
}
-void
+static void
free_node(struct Node** root)
{
if (!root || !*root)
@@ -131,7 +137,7 @@ free_node(struct Node** root)
free(*root);
}
-void
+static void
insert_node(struct Node** root, const int level, const char* label)
{
if (!root || !*root)
@@ -155,11 +161,15 @@ insert_node(struct Node** root, const int level, const char* label)
last->next = newnode;
}
+ (*root)->last_child = newnode;
}
else if ((*root)->level + 1 < level)
{
if (!(*root)->last_child)
- exit(error(1, "Fatal: inserting node >1 levels below"));
+ exit(error(1,
+ "Fatal: inserting node '%s' >1"
+ " levels below '%s'",
+ label, (*root)->label));
insert_node(&(*root)->last_child, level, label);
}
@@ -189,7 +199,7 @@ insert_node(struct Node** root, const int level, const char* label)
}
}
-void
+static void
print_indent(void)
{
const u32* ppindent = indent;
@@ -205,7 +215,7 @@ print_indent(void)
}
}
-void
+static void
print_node(const struct Node* node)
{
if (!node)
@@ -248,55 +258,32 @@ print_node(const struct Node* node)
print_node(node->next);
}
-void
+static void
set_node(struct Node* node, const int level, const char* label)
{
size_t size;
size = strlen(label) + 1;
if (!node->label)
{
- node->label = (char*)calloc(1, size);
+ node->label = malloc(size);
if (!node->label)
{
- perror("calloc");
- exit(error(1, "Cannot alloc"));
+ perror(PROGRAMNAME ": malloc");
+ exit(1);
}
}
- if (strlcpy(node->label, label, size) >= size)
- exit(error(1, "strlcpy:%d: Overflow", __LINE__));
+ if (!memccpy(node->label, label, 0, size))
+ node->label[size - 1] = 0;
node->level = level;
}
-int
-string_to_symbol_set(const char* s)
-{
- int ret;
-
- switch (*s)
- {
- case 'a':
- ret = TREE_SYMBOLS_ASCII;
- break;
- case 's':
- ret = TREE_SYMBOLS_SINGLE;
- break;
- case 'd':
- ret = TREE_SYMBOLS_DOUBLE;
- break;
- default:
- ret = -1;
- }
-
- return ret;
-}
-
-void
+static void
usage(void)
{
printf("Usage: %s [-hVv] | [-s a|d|s] file\n", PROGRAMNAME);
}
-void
+static void
version(const int full)
{
printf("%s %s, committed on %s\n", PROGRAMNAME, VERSION, DATE);
@@ -304,10 +291,10 @@ version(const int full)
puts(COPYRIGHT);
}
-void
+static void
warning(char* fmt, ...)
{
- char buf[BUFSIZE];
+ char buf[LINE_DEFAULT];
va_list args;
va_start(args, fmt);
vsnprintf(buf, sizeof buf, (const char*)fmt, args);
@@ -320,6 +307,13 @@ main(int argc, char** argv)
{
int ch;
FILE* input = NULL;
+ char* line = NULL;
+ ssize_t line_delta;
+ ssize_t line_size;
+ char* pline = NULL;
+ char* tpline = NULL; /* Temporary */
+ char* eol = NULL;
+ int level = 0;
#ifdef __OpenBSD__
if (pledge("stdio rpath unveil", NULL) < 0)
@@ -337,7 +331,8 @@ main(int argc, char** argv)
usage();
exit(0);
case 's':
- if ((symbol_set = string_to_symbol_set(optarg)) == -1)
+ if ((symbol_set = string_to_symbol_set[(int)*optarg])
+ == -1)
exit(error(1, "Invalid symbol set: '%s'",
optarg));
break;
@@ -376,53 +371,79 @@ main(int argc, char** argv)
#endif
if (!(input = fopen(argv[optind], "r")))
{
- perror("fopen");
+ perror(PROGRAMNAME ": fopen");
exit(error(1, "Can't open '%s'", argv[optind]));
}
}
- while (!feof(input))
+ errno = 0;
+ line_delta = sysconf(_SC_LINE_MAX);
+ if (line_delta == -1)
{
- char line[BUFSIZE];
- char* pline = NULL;
- char* eol = NULL;
- int level = 0;
-
- if (!fgets(line, BUFSIZE, input))
- break;
-
- eol = strchr(line, '\n');
- if (eol)
- *eol = 0;
+ if (errno)
+ {
+ perror("sysconf");
+ exit(1);
+ }
+ line_delta = _POSIX2_LINE_MAX;
+ }
+ line_size = line_delta;
+ line = malloc(line_size);
+ pline = line;
+do_input:
+ if (feof(input))
+ goto done_input;
+ if (!fgets(pline, line_size - (pline - line), input))
+ goto done_input;
+
+ eol = strchr(line, '\n');
+ if (eol)
+ *eol = 0;
+ else
+ {
+ line_size += line_delta;
+ if (!(tpline = realloc(line, line_size)))
+ {
+ perror(PROGRAMNAME ": realloc");
+ exit(1);
+ }
+ line = tpline;
+ pline = line + (line_size - line_delta - 1);
+ goto do_input;
+ }
- pline = line;
- while (*pline)
+ pline = line;
+ level = 0;
+ while (*pline)
+ {
+ if (*pline == '\t')
+ level++;
+ else
{
- if (*pline == '\t')
- level++;
- else
+ if (!root)
{
- if (!root)
- {
- root = alloc_node();
- set_node(root, level, pline);
- }
- else
- insert_node(&root, level, pline);
- break;
+ root = alloc_node();
+ set_node(root, level, pline);
}
- pline++;
+ else
+ insert_node(&root, level, pline);
+ break;
}
+ pline++;
}
+ pline = line;
+ goto do_input;
+done_input:
+ free(line);
if (input != stdin)
fclose(input);
- indent = (u32*)calloc(sizeof(u32), BUFSIZE);
+ indent = calloc(sizeof(u32), line_size);
if (!indent)
{
- perror("calloc");
- exit(error(1, "Cannot alloc"));
+ perror(PROGRAMNAME ": calloc");
+ exit(1);
}
pindent = indent;
diff --git a/test/test-003.txt b/test/test-003.txt
@@ -0,0 +1,6 @@
+This is the root node
+ This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of |a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word This is a test of a line longer than 85 characters. The characters should be loaded correctly and no word should be "glued" to the previous word
+ Another subnode
+ Subitem 1
+ Subitem 2
+ Yet another subnode
