commit 0d970c5c1305d0c5c3f194a0195e07b1479038ec
parent c2dc57bf94fe35d30194710065eb1ee4ec6ff6d3
Author: Plat <plat@stellar-nexus.ru>
Date: Thu, 6 Nov 2025 20:04:13 +0000
Changed main logic to suit testing
Diffstat:
| A | libutil/LICENSE | | | 63 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | libutil/fshut.c | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| M | rb.c | | | 55 | ++++++++++++++++++++++++++++++++++--------------------- |
3 files changed, 140 insertions(+), 21 deletions(-)
diff --git a/libutil/LICENSE b/libutil/LICENSE
@@ -0,0 +1,63 @@
+MIT License
+
+© 2011 Connor Lane Smith <cls@lubutu.com>
+© 2011-2016 Dimitris Papastamos <sin@2f30.org>
+© 2014-2016 Laslo Hunhold <dev@frign.de>
+
+Permission is hereby granted, free of charge, to any person obtaining a
+copy of this software and associated documentation files (the "Software"),
+to deal in the Software without restriction, including without limitation
+the rights to use, copy, modify, merge, publish, distribute, sublicense,
+and/or sell copies of the Software, and to permit persons to whom the
+Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
+
+Authors/contributors include:
+
+© 2011 Kamil Cholewiński <harry666t@gmail.com>
+© 2011 Rob Pilling <robpilling@gmail.com>
+© 2011 Hiltjo Posthuma <hiltjo@codemadness.org>
+© 2011 pancake <pancake@youterm.com>
+© 2011 Random832 <random832@fastmail.us>
+© 2012 William Haddon <william@haddonthethird.net>
+© 2012 Kurt H. Maier <khm@sciops.net>
+© 2012 Christoph Lohmann <20h@r-36.net>
+© 2012 David Galos <galosd83@students.rowan.edu>
+© 2012 Robert Ransom <rransom.8774@gmail.com>
+© 2013 Jakob Kramer <jakob.kramer@gmx.de>
+© 2013 Anselm R Garbe <anselm@garbe.us>
+© 2013 Truls Becken <truls.becken@gmail.com>
+© 2013 dsp <dsp@2f30.org>
+© 2013 Markus Teich <markus.teich@stusta.mhn.de>
+© 2013 Jesse Ogle <jesse.p.ogle@gmail.com>
+© 2013 Lorenzo Cogotti <miciamail@hotmail.it>
+© 2013 Federico G. Benavento <benavento@gmail.com>
+© 2013 Roberto E. Vargas Caballero <k0ga@shike2.com>
+© 2013 Christian Hesse <mail@eworm.de>
+© 2013 Markus Wichmann <nullplan@gmx.net>
+© 2014 Silvan Jegen <s.jegen@gmail.com>
+© 2014 Daniel Bainton <dpb@driftaway.org>
+© 2014 Tuukka Kataja <stuge@xor.fi>
+© 2014 Jeffrey Picard <jeff@jeffreypicard.com>
+© 2014 Evan Gates <evan.gates@gmail.com>
+© 2014 Michael Forney <mforney@mforney.org>
+© 2014 Ari Malinen <ari.malinen@gmail.com>
+© 2014 Brandon Mulcahy <brandon@jangler.info>
+© 2014 Adria Garriga <rhaps0dy@installgentoo.com>
+© 2014-2015 Greg Reagle <greg.reagle@umbc.edu>
+© 2015 Tai Chi Minh Ralph Eastwood <tcmreastwood@gmail.com>
+© 2015 Quentin Rameau <quinq@quinq.eu.org>
+© 2015 Dionysis Grigoropoulos <info@erethon.com>
+© 2015 Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
+© 2016 Mattias Andrée <maandree@kth.se>
+© 2016 Eivind Uggedal <eivind@uggedal.com>
diff --git a/libutil/fshut.c b/libutil/fshut.c
@@ -0,0 +1,43 @@
+/* See LICENSE file for copyright and license details. */
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "../util.h"
+
+int
+fshut(FILE *fp, const char *fname)
+{
+ int ret = 0;
+
+ /* fflush() is undefined for input streams by ISO C,
+ * but not POSIX 2008 if you ignore ISO C overrides.
+ * Leave it unchecked and rely on the following
+ * functions to detect errors.
+ */
+ fflush(fp);
+
+ if (ferror(fp) && !ret) {
+ weprintf("ferror %s:", fname);
+ ret = 1;
+ }
+
+ if (fclose(fp) && !ret) {
+ weprintf("fclose %s:", fname);
+ ret = 1;
+ }
+
+ return ret;
+}
+
+void
+enfshut(int status, FILE *fp, const char *fname)
+{
+ if (fshut(fp, fname))
+ exit(status);
+}
+
+void
+efshut(FILE *fp, const char *fname)
+{
+ enfshut(1, fp, fname);
+}
diff --git a/rb.c b/rb.c
@@ -1,11 +1,10 @@
+#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
-#include <limits.h>
+#include <time.h>
#include "tree.h"
-unsigned int steps;
-
inline Node *
init(int val)
{
@@ -77,8 +76,6 @@ balance(Node *root)
Node *
search(Node *root, int val)
{
- ++steps;
-
if (VALUE(root) == val)
return root;
@@ -91,33 +88,49 @@ search(Node *root, int val)
static inline void
usage(void)
{
- eprintf("usage: %s [data_limit] [search_value]\n", argv0);
+ eprintf("usage: %s [filename]\n", argv0);
}
int
main(int argc, char *argv[])
{
argv0 = argv[0];
- if (argc != 3)
+ if (argc > 2)
usage();
- unsigned int data_limit = estrtonum(argv[1], 1, UINT_MAX);
+ if (argc == 2)
+ char filename[] = argv[2];
+ else
+ char filename[] = FILENAME;
+
+ if (!(FILE *file = fopen(filename, "r")))
+ eprintf("fopen %s:", filename);
+
+ int arr[1000000], ch;
+ char w[64];
+ for (int i = 0, wi = 0; (ch = fgetc(file)) != EOF; ) {
+ if (ch != ' ') {
+ w[wi++] = ch;
+ } else {
+ w[wi] = '\0';
+ arr[i++] = estrtonum(n, 0, INT_MAX);
+ wi = 0;
+ }
+ }
- Node *root = NULL;
+ efshut(file, filename);
+ Node *root = NULL;
- for (unsigned int k = 1; k <= data_limit; ++k) {
- root = add(root, k);
+ for (int i = 0; i < 1000000; ++i) {
+ root = add(root, arr[i]);
SET_COLOR(root, BLACK);
}
- int search_value, attempt;
- for (search_value = attempt = 0; search_value < 1 || search_value > data_limit; ++attempt) {
- if (attempt)
- eprintf("Impossible value\n");
- search_value = estrtonum(argv[2], 1, INT_MAX);
- }
-
- Node *s = search(root, search_value);
-
- printf("Found value: %d\nStep amount: %u\n", VALUE(s), steps);
+ /* Searching for every possible value */
+ clock_t start_time, end_time;
+ start_time = clock();
+ for (int i = 0; i <= INT_MAX; ++i)
+ search(root, i);
+ end_time = clock();
+ printf("%f\n", (start_time-end_time)/CLOCKS_PER_SEC);
}
