Subversion Repositories PlanixRsrch.SVN

Rev

Rev 449 | Rev 464 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 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 
 
28 
#ifndef _MAVL_H
29 
#define _MAVL_H
30 
 
31 
#include <stdlib.h>
32 
 
73 7u83 33 
/** Maximum AVL tree depth.
7 7u83 34 
    The number of nodes is calculated by 2^depth.
35 
    So a value of 32 should be enough for around 4
36 
    billion nodes. This value is only used within
37 
    struct mavliter.
38 
    */
39 
#ifndef MAVL_MAX_DEPTH
73 7u83 40 
#define MAVL_MAX_DEPTH	32
7 7u83 41 
#endif
42 
 
2 7u83 43 
/**
44 
 * Defines the structure of an AVL Node.
45 
 */
46 
struct mavlnode {
73 7u83 47 
	struct mavlnode * s[2];		/* Pointer to left and right son.
48 
					   s[0] is the "left" son
49 
					   s[1] is the right son
50 
       					*/
337 7u83 51 
	int bal:3;		      	/* AVL balance factor - 3 bits*/
2 7u83 52 
};
53 
 
54 
/**
55 
 * Definition of an AVL Tree
56 
 */
57 
struct mavl {
73 7u83 58 
	struct mavlnode *root;	       	/* Pointer to root node */
19 7u83 59 
	int (*cmp) (const void *, const void *);	/* Compare function */
73 7u83 60 
	void (*del) (void *);	       	/* Delete element function */
61 
	int count;			/* Number of elements currently stored
62 
					* in the tree */
63 
	void *(*malloc) (size_t n);	/* used to allocate a new mavlnode */
64 
	void (*free) (void *ptr);      	/* used to free a mavlnode */
2 7u83 65 
 
66 
	/*
73 7u83 67 
	 * size of data appended to each mavlnode element.
68 
	 * Used to allocate space in mavl_add.
2 7u83 69 
	 */
70 
	size_t data_size;
71 
};
72 
 
449 7u83 73 
 
2 7u83 74 
void mavlnode_destroy(struct mavl *t, struct mavlnode *n);
304 7u83 75 
struct mavlnode * mavlnode_create(struct mavl *t, const void *data);
452 7u83 76 
struct mavlnode * mavlnode_get(struct mavl *t ,const void *data);
2 7u83 77 
 
78 
#define mavlnode_dataptr(node) \
79 
	((void*)(((char*)((void*)(node))) + sizeof(struct mavlnode)))
80 
 
81 
struct mavl *mavl_create(int (*cmp) (const void *, const void *),
82 
			 void (*del) (void *), size_t data_size);
83 
 
84 
void *mavl_insert(struct mavl *t, const void *data, int *exists);
16 7u83 85 
void mavl_del_all(struct mavl *t);
314 7u83 86 
void *mavl_del(struct mavl *t, const void *data);
19 7u83 87 
int mavl_get_depth(struct mavl *t);
88 
int mavl_verify(struct mavl *t);
73 7u83 89 
void mavl_print(struct mavl *t,
90 
		void (*pcb)(char*,struct mavlnode *), int width);
107 7u83 91 
void * mavl_get(struct mavl *t ,const void *data);
449 7u83 92 
 
452 7u83 93 
 
94 
 
322 7u83 95 
void mavl_destroy(struct mavl *t);
2 7u83 96 
 
97 
 
7 7u83 98 
 
99 
struct mavliter {
100 
	struct mavlnode *stack[MAVL_MAX_DEPTH * 2];
101 
	struct mavlnode *cur;
102 
	int stack_ptr;
19 7u83 103 
	struct mavlnode *root;
104 
	int (*cmp) (const void *, const void *);
7 7u83 105 
};
106 
 
19 7u83 107 
void *mavliter_get(struct mavliter *i);
108 
void mavliter_init(struct mavliter *i, struct mavl *t);
109 
void *mavliter_next(struct mavliter *i);
110 
void *mavliter_seek_set(struct mavliter *i);
7 7u83 111 
 
2 7u83 112 
#define MAVL_E_NOTFOUND	2
113 
#define MAVL_E_NOMEM	3
114 
 
19 7u83 115 
 
116 
#define mavliter_foreach(iterator)\
117 
        for ((void)mavliter_seek_set(iterator); \
118 
			NULL != mavliter_get(iterator); \
119 
		(void)mavliter_next(iterator))
120 
 
121 
 
299 7u83 122 
void mavl_rot(struct mavlnode *n, struct mavlnode **parent, int dir);
123 
void mavl_drot(struct mavlnode *n, struct mavlnode **parent, int dir);
19 7u83 124 
 
329 7u83 125 
 
126 
 
449 7u83 127 
#define MAVL_FIND_FIRST 1
128 
#define MAVL_FIND_LAST  2
129 
void * mavl_get_ext(struct mavl *t ,const void *search, int mode);
452 7u83 130 
#define mavl_get_first(tree,search) mavl_get_ext(tree,search,MAVL_FIND_FIRST)
131 
#define mavl_get_last(tree,search) mavl_get_ext(tree,search,MAVL_FIND_LAST)
329 7u83 132 
 
133 
 
134 
 
2 7u83 135 
#endif