commit 34e545c3b4ad4f558404f812db2f1056de8d288a
parent ce58f6b82fcc98d8c8efa44e35c792f5e7f33fdd
Author: Plat <plat@stellar-nexus.ru>
Date: Fri, 7 Nov 2025 08:33:26 +0000
Added fib.c
Diffstat:
| M | Makefile | | | 4 | ++-- |
| A | fib.c | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | parser.c | | | 32 | ++------------------------------ |
| M | rb.c | | | 2 | ++ |
| M | tree.h | | | 31 | +++++++++++++++++++------------ |
5 files changed, 115 insertions(+), 44 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,11 +1,11 @@
include config.mk
-BIN = rb
+BIN = fib rb
LIBS = ${wildcard libutil/*.c}
OBJS = rb.o ${LIBS:.c=.o}
all: ${BIN}
-rb: ${OBJS}
+${BIN}: ${OBJS}
${CC} ${CFLAGS} -o $@ ${OBJS} ${LDFLAGS}
strip $@
diff --git a/fib.c b/fib.c
@@ -0,0 +1,90 @@
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "tree.h"
+
+typedef struct Fnode Node;
+
+
+inline Node *
+init(void)
+{
+ Node *root = emalloc(sizeof(Node));
+
+ root->left = NULL;
+ root->right = NULL;
+
+ return root;
+}
+
+Node *
+create(unsigned int depth)
+{
+ switch (depth) {
+ case 0:
+ return NULL;
+ case 1:
+ case 2:
+ return init();
+ default:
+ Node *root = init();
+ root->left = create(depth - 1);
+ root->right = init()
+ root->right->right = create(depth-2);
+ return root;
+ }
+}
+
+unsigned long int
+count(Node *root)
+{
+ if (!root)
+ return 0;
+ if (root->left == NULL && root->right == NULL)
+ return 1;
+
+ return count(root->left)+count(root->right);
+}
+
+static inline void
+usage(void)
+{
+ eprintf("usage: %s [c | s | -c | -s] [depth]\n", argv0);
+}
+
+int
+main(int argc, char *argv[])
+{
+ int cflag = 0, sflag = 0;
+
+ ARGBEGIN {
+ case 'c':
+ cflag = 1;
+ break;
+ case 's':
+ sflag = 1;
+ break;
+ default:
+ usage();
+ } ARGEND
+ if (argc != 2 && !(cflag || sflag))
+ usage();
+
+
+ clock_t start_time, time = 0;
+ if (cflag)
+ start_time = clock();
+ Node *root = create(strtonum(argv[1], 0, UINT_MAX));
+ time += clock() - start_time;
+
+ volatile unsigned long int fib = 0; /* to avoid optimization */
+ if (sflag) {
+ start_time = clock();
+ fib = count(root);
+ time += clock() - start_time;
+ }
+
+ printf("%f\n", (double)time/CLOCKS_PER_SEC);
+}
diff --git a/parser.c b/parser.c
@@ -1,37 +1,9 @@
-#include <stdlib.h>
+#include "tree.h"
-#include "util.h"
+typedef struct Node Node;
Node*
-init(int val)
-{
- Node *n = emalloc(sizeof(Node));
-
- n->val = val;
- n->left = NULL;
- n->right = NULL;
-
- return n;
-}
-
-void
-add(int val, Node *root)
-{
- if (val < root->val) {
- if (root->left == NULL)
- root->left = init(val);
- else
- add(val, root->left);
- } else {
- if (root->right == NULL)
- root->right = init(val);
- else
- add(val, root->right);
- }
-}
-
-Node*
parse_pre(unsigned int *index, Node *root)
{
if (!root)
diff --git a/rb.c b/rb.c
@@ -9,6 +9,8 @@
#include "config.h"
+typedef struct Node Node;
+
inline Node *
init(int val)
diff --git a/tree.h b/tree.h
@@ -9,18 +9,25 @@
#define VALUE(n) ((n)->val >> 1)
#define SET_VALUE(n,v) ((n)->val = ((v)<<1) | (((n)->val) & 1))
-typedef struct Node {
+struct Node {
int val;
struct Node *left, *right;
-} Node;
+};
+struct Fnode {
+ struct Fnode *left, *right;
+};
-static inline Node *init(int);
-Node *add(Node *, int);
-Node *parse_pre(Node *);
-Node *parse_post(Node *);
-Node *parse_inf(Node *);
-int get_height(Node *);
-Node *balance(Node *);
-Node *left_turn(Node *);
-Node *right_turn(Node *);
-Node *search(Node *, int);
+static inline struct Node *init(int);
+Node *add(struct Node *, int);
+Node *parse_pre(struct Node *);
+Node *parse_post(struct Node *);
+Node *parse_inf(struct Node *);
+int get_height(struct Node *);
+Node *balance(struct Node *);
+Node *left_turn(struct Node *);
+Node *right_turn(struct Node *);
+Node *search(struct Node *, int);
+
+static inline struct Fnode *finit(void);
+struct Fnode *create(unsigned int);
+unsigned long int search(struct Fnode *);
