Subversion Repositories PlanixRsrch.SVN

Rev

Rev 329 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
307 7u83 1 
/*
2 
 * Copyright 2019, The PLANIX Project
3 
 *
4 
 * Redistribution and use in source and binary forms, with or without
5 
 * modification, are permitted provided that the following conditions are
6 
 * met:
7 
 *
8 
 * 1. Redistributions of source code must retain the above copyright notice,
9 
 * this list of conditions and the following disclaimer.
10 
 *
11 
 * 2. Redistributions in binary form must reproduce the above copyright
12 
 * notice, this list of conditions and the following disclaimer in the
13 
 * documentation and/or other materials provided with the distribution.
14 
 *
15 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16 
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17 
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23 
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24 
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 
 */
27 
#include <stdio.h>
28 
#include <string.h>
29 
#include <errno.h>
30 
#include <stdlib.h>
31 
#include <time.h>
32 
 
33 
#include "mavl.h"
34 
 
35 
/*
36 
 * EXAMPLE 1 Create an AVL which stores just integer values.
37 
 */
38 
 
329 7u83 39 
static float
40 
calc_depth(int numvals)
41 
{
42 
	int i;
43 
	unsigned int r=1;
44 
	for (i=0; i<64; i++){
45 
		if (r>(unsigned int)numvals)
46 
			return (float)((double)i*1.44);
47 
		r=r<<1;
48 
	}
49 
	return (float)0.0;
50 
}
307 7u83 51 
 
329 7u83 52 
 
307 7u83 53 
/* Compare function to compare integers */
54 
static int
55 
cmp(const void *v1, const void *v2)
56 
{
57 
	return *((int *)v1) - *((int *)v2);
58 
}
59 
 
60 
/*
61 
 * Number of integer values we want to put into our tree
62 
 */
63 
 
312 7u83 64 
 
307 7u83 65 
 
66 
static void pcb(char*dst,struct mavlnode *n)
67 
{
68 
	int *d = mavlnode_dataptr(n);
329 7u83 69 
	(void) sprintf(dst,"(%d) %d ",n->bal,*d);
307 7u83 70 
}
71 
 
329 7u83 72 
struct mavl * the_t;
73 
void the_print()
74 
{
75 
	mavl_print(the_t,pcb,150);
76 
}
307 7u83 77 
 
78 
int
311 7u83 79 
main(int argc,char ** argv)
307 7u83 80 
{
81 
	int i,val,prevval;
82 
	int insval;
83 
	int exists;
84 
	struct mavl *t;
85 
	void *data;
86 
	struct mavliter it;
87 
 
312 7u83 88 
	int numvals = 3;
89 
	const char * alg = "mav";
315 7u83 90 
	int del=-1;
311 7u83 91 
 
312 7u83 92 
	if (argc>1) {
93 
		numvals = atoi(argv[1]);
315 7u83 94 
		if (argc >2){
312 7u83 95 
			alg = argv[2];
96 
		}
315 7u83 97 
 
98 
		if (argc > 3){
99 
			del = atoi(argv[3]);
100 
		}
312 7u83 101 
	}
311 7u83 102 
 
312 7u83 103 
 
307 7u83 104 
	/*
105 
	 * Create a MAVL object which store object of size of int . Because
106 
	 * we do not have to free any memory, wo don't need to define free
107 
	 * function, so second argument to mavl_create is NULL.
108 
	 */
109 
	t = mavl_create(cmp, NULL, sizeof(int));
329 7u83 110 
	the_t = t;
307 7u83 111 
	if (t == NULL) {
112 
		(void)fprintf(stderr,
113 
			      "Can't create struct mavl*: %s\n",
114 
			      strerror(errno));
115 
		return errno;
116 
	}
117 
 
118 
	/* Seed the random generator with current time stamp */
119 
	srand((unsigned int)time(NULL));
120 
 
121 
	/* Put some random values into our MAVL tree */
326 7u83 122 
	for (i = 1; i < argc; i++) {
307 7u83 123 
		/*insval = rand();*/
326 7u83 124 
		if (strcmp(argv[i],"d")==0)
125 
			break;
126 
		insval = atoi( argv[i] );
127 
		(void)mavl_insert(t, &insval, &exists);
311 7u83 128 
 
307 7u83 129 
		(void)printf("%d. -----------------------------------------\n",i);
329 7u83 130 
		mavl_print(t,pcb,150);
307 7u83 131 
	}
132 
 
326 7u83 133 
	for(i=i+1; i<argc; i++){
134 
		del = atoi(argv[i]);
135 
		mavl_del(t,&del);
329 7u83 136 
		mavl_print(t,pcb,150);
326 7u83 137 
	}
329 7u83 138 
 
139 
	printf("Real Depth: %d, Max Depth: %f (n:%d)\n",
140 
			mavl_get_depth(t),
141 
			calc_depth(t->count),t->count);
326 7u83 142 
/*
315 7u83 143 
	if (del!=-1){
144 
		mavl_del(t,&del);
145 
		mavl_print(t,pcb,80);
146 
	}
326 7u83 147 
*/
307 7u83 148 
 
149 
	/* Init the iterator */
150 
	mavliter_init(&it, t);
151 
 
152 
	/*
153 
	 * Move the iteratyor to the beginning of the MAVL tree. This is not
154 
	 * implied by mavliter_init and will cause your program to crash if
155 
	 * you don't do it.
156 
	 */
157 
	(void)mavliter_seek_set(&it);
158 
 
159 
	prevval=-1;
160 
 
161 
	/* print out all integers stored in the MAVL tree */
162 
	while ((data = mavliter_get(&it)) != NULL) {
163 
		val = *((int *)data);
164 
		/* Check if values are sorted */
165 
		if (val>prevval){
166 
			(void)printf("%d ", val);
167 
		}
168 
		else {
169 
			(void)printf("ERROR: %d ", val);
170 
		}
171 
		prevval = val;
172 
		(void)mavliter_next(&it);
173 
	}
174 
	(void)printf("\n");
329 7u83 175 
 
307 7u83 176 
	return 0;
177 
}