Subversion Repositories PlanixRsrch.SVN

Rev

Rev 16 | Rev 22 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 16 Rev 19
Line 37... Line 37...
37 
    So a value of 32 should be enough for around 4
 37 
    So a value of 32 should be enough for around 4
38 
    billion nodes. This value is only used within
 38 
    billion nodes. This value is only used within
39 
    struct mavliter.
 39 
    struct mavliter.
40 
    */
 40 
    */
41 
#ifndef MAVL_MAX_DEPTH
 41 
#ifndef MAVL_MAX_DEPTH
42 
#define MAVL_MAX_DEPTH	32
 42 
#define MAVL_MAX_DEPTH	64
43 
#endif
 43 
#endif
44 
 
 44 
 
45 
/**
 45 
/**
46 
 * Defines the structure of an AVL Node.
 46 
 * Defines the structure of an AVL Node.
47 
 */
 47 
 */
48 
struct mavlnode {
 48 
struct mavlnode {
49 
	struct mavlnode *left;			 /* Pointer to left son */
 49 
	struct mavlnode *left;	       /* Pointer to left son */
50 
	struct mavlnode *right;			 /* Pointer to right son */
 50 
	struct mavlnode *right;	       /* Pointer to right son */
51 
	int bal:3;				 /* AVL balance factor */
 51 
	int bal:3;		       /* AVL balance factor */
52 
};
 52 
};
53 
 
 53 
 
54 
/**
 54 
/**
55 
 * Definition of an AVL Tree
 55 
 * Definition of an AVL Tree
56 
 */
 56 
 */
57 
struct mavl {
 57 
struct mavl {
58 
	struct mavlnode *root;			 /* Pointer to root node */
 58 
	struct mavlnode *root;	       /* Pointer to root node */
59 
	int (*cmp) (const void *, const void *); /* Compare function */
 59 
	int (*cmp) (const void *, const void *);	/* Compare function */
60 
	void (*del) (void *);			 /* Delete element function */
 60 
	void (*del) (void *);	       /* Delete element function */
61 
	int count;				 /* Number of elements
 61 
	int count;		       /* Number of elements currently stored
62 
						  * currently stored in the
 - 
 
63 
						  * tree */
 62 
				        * in the tree */
64 
	void *(*malloc) (size_t n);		 /* used to allocate a new
 63 
void *(*malloc) (size_t n);	       /* used to allocate a new mavlnode */
65 
						  * mavlnode */
 - 
 
66 
	void (*free) (void *ptr);		 /* used to free a mavlnode */
 64 
	void (*free) (void *ptr);      /* used to free a mavlnode */
67 
 
 65 
 
68 
	/*
 66 
	/*
69 
	 * size of data appended to each mavlnode element. used to allocate
 67 
	 * size of data appended to each mavlnode element. used to allocate
70 
	 * space in mavl_add.
 68 
	 * space in mavl_add.
71 
	 */
 69 
	 */
Line 80... Line 78...
80 
struct mavl *mavl_create(int (*cmp) (const void *, const void *),
 78 
struct mavl *mavl_create(int (*cmp) (const void *, const void *),
81 
			 void (*del) (void *), size_t data_size);
 79 
			 void (*del) (void *), size_t data_size);
82 
 
 80 
 
83 
void *mavl_insert(struct mavl *t, const void *data, int *exists);
 81 
void *mavl_insert(struct mavl *t, const void *data, int *exists);
84 
void mavl_del_all(struct mavl *t);
 82 
void mavl_del_all(struct mavl *t);
85 
int mavl_get_depth( struct mavl *t );
 83 
int mavl_get_depth(struct mavl *t);
- 
 
 84 
int mavl_verify(struct mavl *t);
86 
 
 85 
 
87 
 
 86 
 
88 
 
 87 
 
89 
struct mavliter {
 88 
struct mavliter {
90 
	struct mavlnode *stack[MAVL_MAX_DEPTH * 2];
 89 
	struct mavlnode *stack[MAVL_MAX_DEPTH * 2];
91 
	struct mavlnode *cur;
 90 
	struct mavlnode *cur;
92 
	int stack_ptr;
 91 
	int stack_ptr;
93 
	struct mavlnode * root;
 92 
	struct mavlnode *root;
94 
	int ( *cmp ) ( const void *, const void * );
 93 
	int (*cmp) (const void *, const void *);
95 
};
 94 
};
96 
 
 95 
 
97 
void * mavliter_get(struct mavliter *i);
 96 
void *mavliter_get(struct mavliter *i);
98 
void mavliter_init(struct mavliter * i, struct mavl * t);
 97 
void mavliter_init(struct mavliter *i, struct mavl *t);
99 
void * mavliter_next ( struct mavliter *i );
 98 
void *mavliter_next(struct mavliter *i);
100 
void * mavliter_seek_set ( struct mavliter *i );
 99 
void *mavliter_seek_set(struct mavliter *i);
101 
 
 100 
 
102 
#define MAVL_E_NOTFOUND	2
 101 
#define MAVL_E_NOTFOUND	2
103 
#define MAVL_E_NOMEM	3
 102 
#define MAVL_E_NOMEM	3
- 
 
 103 
 
- 
 
 104 
 
- 
 
 105 
#define mavliter_foreach(iterator)\
- 
 
 106 
        for ((void)mavliter_seek_set(iterator); \
- 
 
 107 
			NULL != mavliter_get(iterator); \
- 
 
 108 
		(void)mavliter_next(iterator))
- 
 
 109 
 
- 
 
 110 
 
104 
 
 111 
 
105 
#endif
 112 
#endif