AfanasevGad7

This is a task for our favourite professor
git clone git://git.stellar-nexus.ru/AfanasevGad7
Log | Files | Refs | README

rb.c (2965B)

      1 #include <ctype.h>
      2 #include <limits.h>
      3 #include <stdio.h>
      4 #include <stdint.h>
      5 #include <stdlib.h>
      6 #include <time.h>
      7 
      8 #include "tree.h"
      9 
     10 #include "config.h"
     11 
     12 typedef struct Node Node;
     13 
     14 
     15 inline Node *
     16 init(int val)
     17 {
     18 	Node *root = emalloc(sizeof(Node));
     19 	
     20 	SET_COLOR(root, RED);
     21 	SET_VALUE(root, val);
     22 	root->left = NULL;
     23 	root->right = NULL;
     24 
     25 	return root;
     26 }
     27 
     28 Node *
     29 add(Node *root, int val)
     30 {
     31 	if (!root)
     32 		return init(val);
     33 	
     34 	if (val < VALUE(root))
     35 		root->left = add(root->left, val);
     36 	else if (val > VALUE(root))
     37 		root->right = add(root->right, val);
     38 
     39 	return balance(root);
     40 }
     41 
     42 Node *
     43 left_turn(Node *root)
     44 {
     45 	Node *n = root->right;
     46 	root->right = n->left;
     47 	n->left = root;
     48 	SET_COLOR(n, COLOR(root));
     49 	SET_COLOR(root, RED);
     50 	return n;
     51 }
     52 
     53 Node *
     54 right_turn(Node *root) 
     55 {
     56 	Node *n = root->left;
     57 	root->left = n->right;
     58 	n->right = root;
     59 	SET_COLOR(n, COLOR(root));
     60 	SET_COLOR(root, RED);
     61 	return n;
     62 }
     63 
     64 Node *
     65 balance(Node *root)
     66 {
     67 	if (COLOR(root->right) && !COLOR(root->left))
     68 		root = left_turn(root);
     69 
     70 	if (COLOR(root->left) && COLOR(root->left->left))
     71 		root = right_turn(root);
     72 	
     73 	if (COLOR(root->left) && COLOR(root->right)) {
     74 		SET_COLOR(root, !COLOR(root));
     75 		SET_COLOR(root->left, BLACK);
     76 		SET_COLOR(root->right, BLACK);
     77 	}
     78 	
     79 	return root;
     80 }
     81 
     82 
     83 Node *
     84 search(Node *root, int val)
     85 {
     86 	if (VALUE(root) == val)
     87 		return root;
     88 
     89 	if (VALUE(root) > val)
     90 		return search(root->left, val);
     91 	
     92 	return search(root->right, val);
     93 }
     94 
     95 static inline void
     96 usage(void)
     97 {
     98 	eprintf("usage: %s [-c] [-s] [-d] [filename]\n", argv0);
     99 }
    100 
    101 int
    102 main(int argc, char *argv[])
    103 {
    104 	int cflag = 0, sflag = 0, dflag = 0;
    105 	ARGBEGIN {
    106 	case 'c':
    107 		cflag = 1;
    108 		break;
    109 	case 's':
    110 		sflag = 1;
    111 		break;
    112 	case 'd':
    113 		eprintf("Not implemented\n");
    114 		dflag = 1;
    115 		break;
    116 	} ARGEND
    117 	if (argc > 1 || (cflag + sflag + dflag) < 1)
    118 		usage();
    119 	const char *filename;
    120 	if (argc == 1)
    121 		filename = argv[0];
    122 	else
    123 		filename = FILENAME;
    124 	
    125 	FILE *file;
    126 	if (!(file = fopen(filename, "r")))
    127 		eprintf("fopen %s:", filename);
    128 	
    129 	int arr[TESTNUMBER+1], ch;
    130 	char w[64];
    131 	int len = 0, wi = 0;
    132 	do {
    133 		ch = fgetc(file);
    134 		if (!isspace(ch) && ch != EOF) {
    135 			w[wi++] = ch;
    136 		} else if (wi > 0) {
    137 			w[wi] = '\0';
    138 			arr[len++] = estrtonum(w, 0, INT_MAX);
    139 			wi = 0;
    140 		}
    141 	} while (ch != EOF && len <= TESTNUMBER);
    142 	efshut(file, filename);
    143 	if (len < TESTNUMBER)
    144 		eprintf("Array too small\n");
    145 	if (len > TESTNUMBER)
    146 		weprintf("Array too big - using only the first %d elements\n", TESTNUMBER);
    147 
    148 	Node *root = NULL;
    149 	clock_t start_time, elapsed = 0;
    150 
    151 	if (cflag)
    152 		start_time = clock();
    153 	for (int i = 0; i < TESTNUMBER; ++i) {
    154 		root = add(root, arr[i]);
    155 		SET_COLOR(root, BLACK);
    156 	}
    157 	if (cflag)
    158 		elapsed += clock() - start_time;
    159 	
    160 	volatile uintptr_t checksum = 0; /* to avoid optimization */
    161 	if (sflag) {
    162 		start_time = clock();
    163 		for (int i = 0; i < TESTNUMBER; ++i)
    164 			checksum = (uintptr_t)search(root, arr[i]);
    165 		elapsed += clock() - start_time;
    166 	}
    167 
    168 	printf("%f\n", (double)elapsed/CLOCKS_PER_SEC);
    169 }