Subversion Repositories PlanixRsrch.SVN

Compare Revisions

Ignore whitespace Rev 321 → Rev 336

/tags/libmavl/1.0.0/LICENSE
0,0 → 1,26
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/tags/libmavl/1.0.0/mavtest.c
0,0 → 1,179
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include <time.h>
 
#include "mavl.h"
 
/*
* EXAMPLE 1 Create an AVL which stores just integer values.
*/
 
static float
calc_depth(int numvals)
{
int i;
unsigned int r=1;
for (i=0; i<64; i++){
if (r>(unsigned int)numvals)
return (float)((double)i*1.44);
r=r<<1;
}
return (float)0.0;
}
 
 
/* Compare function to compare integers */
static int
cmp(const void *v1, const void *v2)
{
return *((int *)v1) - *((int *)v2);
}
 
/*
* Number of integer values we want to put into our tree
*/
 
 
extern void *
mav_insert(struct mavl *t, const void *data, int *exists);
 
static void pcb(char*dst,struct mavlnode *n)
{
int *d = mavlnode_dataptr(n);
(void) sprintf(dst,"(%d) %d ",n->bal,*d);
}
 
struct mavl * the_t;
void the_print()
{
mavl_print(the_t,pcb,150);
}
 
int
main(int argc,char ** argv)
{
int i,val,prevval;
int insval;
int exists;
struct mavl *t;
void *data;
struct mavliter it;
 
int numvals = 3;
const char * alg = "mav";
int del=-1;
 
if (argc>1) {
numvals = atoi(argv[1]);
if (argc >2){
alg = argv[2];
}
 
if (argc > 3){
del = atoi(argv[3]);
}
}
 
 
/*
* Create a MAVL object which store object of size of int . Because
* we do not have to free any memory, wo don't need to define free
* function, so second argument to mavl_create is NULL.
*/
t = mavl_create(cmp, NULL, sizeof(int));
the_t = t;
if (t == NULL) {
(void)fprintf(stderr,
"Can't create struct mavl*: %s\n",
strerror(errno));
return errno;
}
 
/* Seed the random generator with current time stamp */
srand((unsigned int)time(NULL));
 
/* Put some random values into our MAVL tree */
for (i = 1; i < argc; i++) {
/*insval = rand();*/
if (strcmp(argv[i],"d")==0)
break;
insval = atoi( argv[i] );
(void)mavl_insert(t, &insval, &exists);
 
(void)printf("%d. -----------------------------------------\n",i);
mavl_print(t,pcb,150);
}
 
for(i=i+1; i<argc; i++){
del = atoi(argv[i]);
mavl_del(t,&del);
mavl_print(t,pcb,150);
}
 
printf("Real Depth: %d, Max Depth: %f (n:%d)\n",
mavl_get_depth(t),
calc_depth(t->count),t->count);
/*
if (del!=-1){
mavl_del(t,&del);
mavl_print(t,pcb,80);
}
*/
 
/* Init the iterator */
mavliter_init(&it, t);
 
/*
* Move the iteratyor to the beginning of the MAVL tree. This is not
* implied by mavliter_init and will cause your program to crash if
* you don't do it.
*/
(void)mavliter_seek_set(&it);
 
prevval=-1;
 
/* print out all integers stored in the MAVL tree */
while ((data = mavliter_get(&it)) != NULL) {
val = *((int *)data);
/* Check if values are sorted */
if (val>prevval){
(void)printf("%d ", val);
}
else {
(void)printf("ERROR: %d ", val);
}
prevval = val;
(void)mavliter_next(&it);
}
(void)printf("\n");
 
return 0;
}
/tags/libmavl/1.0.0/Makefile
0,0 → 1,55
 
OBJS=\
mavl_create.o \
mavl.o mavl_get.o \
mavl_del_all.o \
mavlnode_destroy.o \
mavl_foreach.o \
mavl_verify.o \
mavl_get_depth.o \
mavl_print.o \
mavliter_init.o \
mavliter_next.o \
mavliter_get.o \
mavliter_seek_set.o \
mavl_del.o \
mavl_destroy.o
 
LIBNAME=libmavl.a
 
PREFIX=~
 
.c.o:
$(CC) -c $(CFLAGS) $<
 
$(LIBNAME): $(OBJS)
$(AR) rcs $(LIBNAME) $(OBJS)
 
example1: $(LIBNAME) example1.o
$(CC) -o example1 example1.o $(LIBNAME)
 
example2: $(LIBNAME) example2.o
$(CC) -o example2 example2.o $(LIBNAME)
 
mavtest: $(LIBNAME) mavtest.o
$(CC) -o mavtest mavtest.o $(LIBNAME)
 
 
clean:
rm -f $(OBJS)
rm -f $(LIBNAME)
rm -f example1.o example1
rm -f example2.o example2
rm -f mavtest mavtest.o
rm -f *.core
rm -f test.o test
 
install: $(LIBNAME)
mkdir -p $(PREFIX)/lib
mkdir -p $(PREFIX)/include/libmavl
install -p $(LIBNAME) $(PREFIX)/lib/$(LIBNAME)
install -p mavl.h $(PREFIX)/include/libmavl/mavl.h
 
test: $(LIBNAME) test.o
$(CC) $(LDFLAGS) -o test test.o $(LIBNAME) -lmutests
 
/tags/libmavl/1.0.0/README
0,0 → 1,0
Libmavl is a minimalistic AVL tree implementation
/tags/libmavl/1.0.0/cases.txt
0,0 → 1,15
./mavtest 50 30 60 25 35 55 24 36 d 55
./mavtest 100 50 150 40 60 120 170 171 119 121 55 62 35 42 34 36 d 40
./mavtest 100 50 150 55 120 170 121 d 55
 
# cause drot
./mavtest 100 50 150 55 120 170 121 45 110 46 160 180 105 111 d 50
 
# cause 1 drot
./mavtest 100 50 150 55 120 170 125 45 110 40 171 60 52 53 121 d 150
 
 
./mavtest 100 50 150 40 60 120 170 30 45 55 65 110 160 180 161 44 46 d 50
 
./mavtest 100 50 150 40 60 120 170 65 110 130 160 180 131 d 65
 
/tags/libmavl/1.0.0/example1.c
0,0 → 1,110
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include <time.h>
 
#include "mavl.h"
 
/*
* EXAMPLE 1 Create an AVL which stores just integer values.
*/
 
 
/* Compare function to compare integers */
static int
cmp(const void *v1, const void *v2)
{
return *((int *)v1) - *((int *)v2);
}
 
/*
* Number of integer values we want to put into our tree
*/
#define NUMVALS 100L
 
int
main(void)
{
int i,val,prevval;
int insval;
int exists;
struct mavl *t;
void *data;
struct mavliter it;
 
/*
* Create a MAVL object which store object of size of int . Because
* we do not have to free any memory, wo don't need to define free
* function, so second argument to mavl_create is NULL.
*/
t = mavl_create(cmp, NULL, sizeof(int));
if (t == NULL) {
(void)fprintf(stderr,
"Can't create struct mavl*: %s\n",
strerror(errno));
return errno;
}
 
/* Seed the random generator with current time stamp */
srand((unsigned int)time(NULL));
 
/* Put some random values into our MAVL tree */
for (i = 0; i < NUMVALS; i++) {
insval = rand();
(void)mavl_insert(t, &insval, &exists);
}
/* Init the iterator */
mavliter_init(&it, t);
 
/*
* Move the iteratyor to the beginning of the MAVL tree. This is not
* implied by mavliter_init and will cause your program to crash if
* you don't do it.
*/
(void)mavliter_seek_set(&it);
 
prevval=-1;
 
/* print out all integers stored in the MAVL tree */
while ((data = mavliter_get(&it)) != NULL) {
val = *((int *)data);
/* Check if values are sorted */
if (val>prevval){
(void)printf("%d ", val);
}
else {
(void)printf("ERROR: %d ", val);
}
prevval = val;
(void)mavliter_next(&it);
}
(void)printf("\n");
return 0;
}
/tags/libmavl/1.0.0/example2.c
0,0 → 1,150
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
#include <time.h>
 
#include "mavl.h"
 
/*
* EXAMPLE 1 Create an AVL which stores just integer values.
*/
 
 
/* Compare function to compare integers */
static int
cmp(const void *v1, const void *v2)
{
return *((int *)v1) - *((int *)v2);
}
 
/*
* Number of integer values we want to put into our tree
*/
#define NUMVALS 15000000L
 
void prnode(char *dst, struct mavlnode *n)
{
void *data = mavlnode_dataptr(n);
int v = *((int*)(data));
(void)sprintf(dst,"%d[%d]",v,n->bal);
}
 
int vals[] = {
/* 1,2,3,4,5,6,-1 */
/* 7,6,5,4,3,2,1,-1 */
1,10,5,-1
};
 
 
int
main(void)
{
int i;
int insval;
int exists;
struct mavl *t;
clock_t clk;
int rc;
 
/*
* Create a MAVL object for integers.
*/
t = mavl_create(cmp, NULL, sizeof(int));
if (t == NULL) {
(void)fprintf(stderr,
"Can't create struct mavl*: %s\n",
strerror(errno));
return errno;
}
 
(void)printf("Inserting %ld sorted intergers! ...\n", NUMVALS);
clk = clock();
for (i = 0; i<NUMVALS; i++) {
insval = i;
(void)mavl_insert(t, &insval, &exists);
}
clk = clock() - clk;
(void)printf("TIME: %0.2f SECONDS\n", (double)clk / (double)CLOCKS_PER_SEC);
(void)printf("ELEMENTS IN TREE: %d\n", t->count);
(void)printf("DEPTH = %d\n", mavl_get_depth(t));
 
(void)printf("Verifying ... ");
clk = clock();
rc = mavl_verify(t);
clk = clock() - clk;
 
if (rc)
(void)printf("ok\n");
else
(void)printf("error\n");
(void)printf("VERIFYING TOOK: %0.2f SECONDS\n", (double)clk / (double)CLOCKS_PER_SEC);
(void)printf("DELETING ALL VALUES ... \n");
clk = clock();
mavl_del_all(t);
clk = clock() - clk;
(void)printf("DELETION TOOK: %0.2f SECONDS\n", (double)clk / (double)CLOCKS_PER_SEC);
(void)printf("ELEMENTS IN TREE: %d\n", t->count);
(void)printf("DEPTH = %d\n", mavl_get_depth(t));
 
 
(void)printf("Inserting %ld random intergers ...\n", NUMVALS);
srand(time(NULL));
/*srand(1941);*/
 
clk = clock();
for (i = 0; i < NUMVALS; i++) {
insval = rand();
(void)mavl_insert(t, &insval, &exists);
}
clk = clock() - clk;
(void)printf("TIME: %0.2f SECONDS\n", (double)clk / (double)CLOCKS_PER_SEC);
(void)printf("ELEMENTS IN TREE: %d\n", t->count);
(void)printf("DEPTH = %d\n", mavl_get_depth(t));
 
(void)printf("Verifying ... ");
clk = clock();
rc = mavl_verify(t);
clk = clock() - clk;
 
if (rc)
(void)printf("ok\n");
else
(void)printf("error\n");
(void)printf("VERIFYING TOOK: %0.2f SECONDS\n", (double)clk / (double)CLOCKS_PER_SEC);
(void)printf("Deleting all values ... \n");
clk = clock();
mavl_del_all(t);
clk = clock() - clk;
(void)printf("DELETION TOOK: %0.2f SECONDS\n", (double)clk / (double)CLOCKS_PER_SEC);
(void)printf("ELEMENTS IN TREE: %d\n", t->count);
(void)printf("DEPTH = %d\n", mavl_get_depth(t));
return 0;
}
/tags/libmavl/1.0.0/man/mavl.3
0,0 → 1,18
 
.TH MAVL 3
.SH NAME
\fBprogname\fR \(en one line about what it does
.\" .SH LIBRARY
.\" For sections 2, 3, and 9 only.
.\" Not used in OpenBSD.
mavl_create, mavl_del, mavl_insert \- work with AVL trees.
.SH SYNOPSIS
\fBprogname\fR [\fB\-options\fR] \fIfile ...\fR
.B #include <stdio.h>
.TP abc
Set our bits to 0 as long as it works
You e
ui helo world
.IR function
/tags/libmavl/1.0.0/mav.c
0,0 → 1,137
#include <stdio.h>
 
#include "mavl.h"
 
static int
getbal(struct mavlnode *n)
{
return n==NULL ? 0 : n->bal;
}
 
static int
recalc(struct mavlnode *n){
int b0,b1;
b0 = getbal( n->s[0] );
b1 = getbal( n->s[1] );
return (b1>b0 ? b1 : b0)+1;
 
/* n->bal = n->s[ (getbal(n->s[0])->bal > n->s[1]->bal) ? 0 : 1 ]->bal+1;*/
}
 
/* p p
* / /
* n ----> b
* / \ / \
* b n 2
* / \ . / \
* 1 2 1
*/
 
/*
2
\
1
\
0
*/
 
/*
* dir = 1 rot left
* dir = 0 rot right
*/
static struct mavlnode *
rot(struct mavlnode *n, int dir)
{
struct mavlnode * r;
r = n->s[dir];
n->s[dir]=r->s[1-dir];
r->s[1-dir]=n;
/* n->bal = recalc(n);*/
/* r->bal = recalc(r);*/
n->bal=0;
r->bal=0;
return r;
}
 
 
static struct mavlnode *
balance ( struct mavlnode *n) {
int b,d;
/* b = n->s[1]->bal - n->s[0]->bal;*/
 
/* b = getbal(n->s[1]) - getbal( n->s[0] );*/
 
b = n->bal;
 
if (b>-2 && b<2)
return n;
 
printf("should rotate! %d\n",b);
return rot(n,1);
 
/* d = b<0 ? 1:0;
if (n->s[d]->bal - n->s[1-d]->bal == -d/2)
n->s[d]=rot(n->s[d],parent,d);
return rot(n,parent,1-d);*/
 
}
 
static struct mavlnode *
mav_insert0(struct mavl *t, struct mavlnode *root, const void **data)
{
struct mavlnode * nnn;
 
int rc,dir;
if (root==NULL){
root = mavlnode_create(t, *data);
if (root==NULL)
return NULL;
*data = mavlnode_dataptr(root);
/*return MAVL_E_NOMEM;*/
t->count++;
root->bal=0;
return root;
}
 
rc = t->cmp(*data, mavlnode_dataptr(root));
if (rc == 0) {
/* element exists */
*data = mavlnode_dataptr(root);
return NULL;
}
 
/* rc is > 0 here */
dir = rc>0 ? 1:0;
/* root->bal +=dir;*/ /*recalc(root); */
root->s[dir] = mav_insert0(t, root->s[dir], data);
 
nnn = balance(root);
printf("Return %p === %p\n",root,nnn);
return balance(nnn);
 
/* return root; */
/* recalc(n);*/
}
 
void *
mav_insert(struct mavl *t, const void *data, int *exists)
{
const void *d;
int rc;
 
d = data;
t->root = mav_insert0(t, t->root, &d);
 
/* if (rc >= 3)
return NULL;
 
if (exists != NULL) {
if (rc == 2)
*exists = 1;
else
*exists = 0;
} */
return (void *)d;
}
 
/tags/libmavl/1.0.0/mavl.c
0,0 → 1,149
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <string.h>
 
#include "mavl.h"
 
void
mavl_rot(struct mavlnode *n, struct mavlnode **parent, int dir)
{
struct mavlnode *tmp;
*parent = n->s[dir];
tmp = n->s[dir]->s[1-dir];
n->s[dir]->s[1-dir]=n;
n->s[dir]=tmp;
}
 
void
mavl_drot(struct mavlnode *n, struct mavlnode **parent, int dir)
{
mavl_rot(n->s[dir],&n->s[dir],1-dir);
mavl_rot(n,parent,dir);
}
 
struct mavlnode *
mavlnode_create(struct mavl *t, const void *data)
{
struct mavlnode *n = t->malloc(sizeof(struct mavlnode) + t->data_size);
if (!n)
return NULL;
 
n->s[0] = n->s[1] = NULL;
n->bal = 0;
 
(void)memcpy(mavlnode_dataptr(n), data, t->data_size);
 
return n;
}
 
static int
mavl_insert0(struct mavl *t, struct mavlnode **parent, const void **data)
{
struct mavlnode *n;
int rc, bal,b;
int dir,sdir;
 
if (*parent==NULL){
*parent = mavlnode_create(t, *data);
*data = mavlnode_dataptr(*parent);
if (*parent==NULL)
return MAVL_E_NOMEM;
t->count++;
return 1;
}
 
n = *parent;
rc = t->cmp(*data, mavlnode_dataptr(n));
 
if (rc == 0) {
*data = mavlnode_dataptr(n);
return 2;
}
 
dir = rc>0 ? 1:0;
 
/* rc is > 0 here */
bal = mavl_insert0(t, &n->s[dir], data);
 
if (bal > 1)
return bal;
 
sdir = dir ? 1:-1;
n->bal += bal*sdir;
 
if (n->bal == 0)
return 0;
 
if (n->bal == 2*sdir) {
if (n->s[dir]->bal == sdir) {
n->bal = 0;
n->s[dir]->bal = 0;
mavl_rot(n, parent,dir);
return 0;
}
b = n->s[dir]->s[1-dir]->bal;
if (b==-sdir){
n->bal = 0;
n->s[dir]->bal = sdir;
}else if (b==sdir){
n->bal = -sdir;
n->s[dir]->bal = 0;
}else{
n->bal = 0;
n->s[dir]->bal = 0;
}
 
n->s[dir]->s[1-dir]->bal = 0;
mavl_drot(n, parent,dir);
return 0;
}
return bal;
}
 
void *
mavl_insert(struct mavl *t, const void *data, int *exists)
{
const void *d;
int rc;
 
d = data;
rc = mavl_insert0(t, &t->root, &d);
 
if (rc >= 3)
return NULL;
 
if (exists != NULL) {
if (rc == 2)
*exists = 1;
else
*exists = 0;
}
return (void *)d;
}
 
/tags/libmavl/1.0.0/mavl.h
0,0 → 1,126
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#ifndef _MAVL_H
#define _MAVL_H
 
#include <stdlib.h>
 
/** Maximum AVL tree depth.
The number of nodes is calculated by 2^depth.
So a value of 32 should be enough for around 4
billion nodes. This value is only used within
struct mavliter.
*/
#ifndef MAVL_MAX_DEPTH
#define MAVL_MAX_DEPTH 32
#endif
 
/**
* Defines the structure of an AVL Node.
*/
struct mavlnode {
struct mavlnode * s[2]; /* Pointer to left and right son.
s[0] is the "left" son
s[1] is the right son
*/
int bal; /*:3; * AVL balance factor - 3 bits*/
};
 
/**
* Definition of an AVL Tree
*/
struct mavl {
struct mavlnode *root; /* Pointer to root node */
int (*cmp) (const void *, const void *); /* Compare function */
void (*del) (void *); /* Delete element function */
int count; /* Number of elements currently stored
* in the tree */
void *(*malloc) (size_t n); /* used to allocate a new mavlnode */
void (*free) (void *ptr); /* used to free a mavlnode */
 
/*
* size of data appended to each mavlnode element.
* Used to allocate space in mavl_add.
*/
size_t data_size;
};
 
void mavlnode_destroy(struct mavl *t, struct mavlnode *n);
struct mavlnode * mavlnode_create(struct mavl *t, const void *data);
 
#define mavlnode_dataptr(node) \
((void*)(((char*)((void*)(node))) + sizeof(struct mavlnode)))
 
struct mavl *mavl_create(int (*cmp) (const void *, const void *),
void (*del) (void *), size_t data_size);
 
void *mavl_insert(struct mavl *t, const void *data, int *exists);
void mavl_del_all(struct mavl *t);
void *mavl_del(struct mavl *t, const void *data);
int mavl_get_depth(struct mavl *t);
int mavl_verify(struct mavl *t);
void mavl_print(struct mavl *t,
void (*pcb)(char*,struct mavlnode *), int width);
void * mavl_get(struct mavl *t ,const void *data);
void mavl_destroy(struct mavl *t);
 
 
 
struct mavliter {
struct mavlnode *stack[MAVL_MAX_DEPTH * 2];
struct mavlnode *cur;
int stack_ptr;
struct mavlnode *root;
int (*cmp) (const void *, const void *);
};
 
void *mavliter_get(struct mavliter *i);
void mavliter_init(struct mavliter *i, struct mavl *t);
void *mavliter_next(struct mavliter *i);
void *mavliter_seek_set(struct mavliter *i);
 
#define MAVL_E_NOTFOUND 2
#define MAVL_E_NOMEM 3
 
 
#define mavliter_foreach(iterator)\
for ((void)mavliter_seek_set(iterator); \
NULL != mavliter_get(iterator); \
(void)mavliter_next(iterator))
 
 
void mavl_rot(struct mavlnode *n, struct mavlnode **parent, int dir);
void mavl_drot(struct mavlnode *n, struct mavlnode **parent, int dir);
 
 
 
 
void *mavl_odel(struct mavl *t, const void *data);
 
 
#endif
/tags/libmavl/1.0.0/mavl_create.c
0,0 → 1,55
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
 
#include "mavl.h"
 
/**
* Create a simple AVL tree
* @param cmp pointer to compare function
* @param del pointer to delete function which is called when an element
* will be deletet
* @param dta_size size of a data element
* @return pointer to a #mavl struct. If the return value is NULL something
* went wrong, and you should consult errno to get details.
*/
struct mavl *
mavl_create(int (*cmp) (const void *, const void *),
void (*del) (void *), size_t data_size){
struct mavl *t = malloc(sizeof(struct mavl));
if (!t)
return NULL;
t->root = NULL;
t->count = 0;
t->cmp = cmp;
t->del = del;
t->data_size = data_size;
 
t->malloc = malloc;
t->free = free;
return t;
}
/tags/libmavl/1.0.0/mavl_del.c
0,0 → 1,195
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include <string.h>
#include <stdio.h>
#include <assert.h>
 
#include "mavl.h"
 
 
/*
* dir == 0 adj_bal_r
* dir == 1 adj_bal_l
*/
 
static int
adj_bal(struct mavlnode *n, struct mavlnode **parent, int dir, int sdir)
{
int b;
if (n->s[dir]->bal == 0) {
n->bal = sdir;
n->s[dir]->bal = -sdir;
mavl_rot(n, parent,dir);
return 0;
}
if (n->s[dir]->bal == sdir) {
n->bal = 0;
n->s[dir]->bal = 0;
mavl_rot(n, parent,dir);
return 1;
}
 
if (n->s[dir]->bal == -sdir) {
 
b = n->s[dir]->s[1-dir]->bal;
 
if (b == 0){
n->s[dir]->bal = 0;
n->bal=0;
} else if (b == sdir) {
n->bal = -sdir;
n->s[dir]->bal = 0 ;
} else if (b == -sdir){
n->s[dir]->bal = sdir;
n->bal=0;
} else{
assert(0*sdir);
}
 
 
n->s[dir]->s[1-dir]->bal = 0;
 
mavl_drot(n, parent,dir);
return 1;
}
 
assert(0*sdir);
return 0;
}
 
static int
mavl_del_lo(struct mavl * t, struct mavlnode **parent, void *data)
{
struct mavlnode *n = *parent;
/* walk down left */
if (n->s[0]) {
int dir=0,sdir;
int bal = mavl_del_lo(t, &n->s[0], data);
sdir = dir ? 1:-1;
n->bal -= bal*sdir;
if (n->bal == -sdir)
return 0;
if (n->bal == -2*sdir){
return adj_bal(n,parent,1-dir,-sdir);
}
return bal;
}
 
/* found the lowest element */
*parent = n->s[1];
(void) memcpy(data,mavlnode_dataptr(n),t->data_size);
t->free(n);
return 1;
 
 
}
 
 
int
mavl_del0(struct mavl *t, struct mavlnode **parent, void *data)
{
struct mavlnode *n = *parent;
int rc;
int bal;
int dir,sdir;
 
rc = t->cmp(data, mavlnode_dataptr(n));
 
if (rc == 0) {
if (!n->s[0] && !n->s[1]) {
*parent = NULL;
mavlnode_destroy(t, n);
return 1;
}
 
if (n->s[0] && !n->s[1]) {
*parent = n->s[0];
mavlnode_destroy(t, n);
return 1;
}
 
if (!n->s[0] && n->s[1]) {
mavlnode_destroy(t, n);
*parent = n->s[1];
return 1;
}
 
/* node has two children */
if (t->del) {
t->del(mavlnode_dataptr(n));
}
t->count--;
bal = mavl_del_lo(t,&n->s[1], mavlnode_dataptr(n));
dir = 1;
sdir = dir ? 1:-1;
n->bal -= bal*sdir;
if (n->bal == -sdir)
return 0;
if (n->bal == -2*sdir){
return adj_bal(n,parent,1-dir,-sdir);
}
return bal;
 
}
 
dir = rc < 0 ? 0 : 1;
sdir = dir ? -1:1;
 
/* if (!n->s[dir]){
printf("wrongdir\n");
exit(0);
}
*/
bal = mavl_del0(t, &n->s[dir], data);
sdir = dir ? 1:-1;
n->bal -= bal*sdir;
if (n->bal == -sdir)
return 0;
if (n->bal == -2*sdir){
return adj_bal(n,parent,1-dir,-sdir);
}
return bal;
}
 
 
void
*mavl_del(struct mavl *t, const void *data)
{
void *d;
int rc;
 
if (!t->root)
return NULL;
 
d = (void*)data;
rc = mavl_del0(t, &t->root, d);
 
if (rc == 2)
return NULL;
return (void*)data;
}
 
/tags/libmavl/1.0.0/mavl_del_all.c
0,0 → 1,48
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include "mavl.h"
 
static void mavl_del_all0(struct mavl *t ,struct mavlnode * n)
{
if (!n)
return;
mavl_del_all0(t,n->s[0]);
mavl_del_all0(t,n->s[1]);
mavlnode_destroy(t,n);
}
 
/**
* Delete all elemets of a mavl object
* @parm t mavl object
*/
void mavl_del_all(struct mavl *t)
{
mavl_del_all0(t,t->root);
t->root=NULL;
}
 
/tags/libmavl/1.0.0/mavl_destroy.c
0,0 → 1,9
#include "mavl.h"
 
void mavl_destroy(struct mavl *t)
{
mavl_del_all(t);
free (t);
}
 
 
/tags/libmavl/1.0.0/mavl_foreach.c
0,0 → 1,59
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "mavl.h"
 
int mavl_foreach_lr(struct mavlnode *n, int (*callback)(void *,void *),void *cbpriv)
{
if (!n)
return 1;
if (!mavl_foreach_lr(n->s[0],callback,cbpriv))
return 0;
if (!callback(cbpriv,mavlnode_dataptr(n)))
return 0;
return mavl_foreach_lr(n->s[1],callback,cbpriv);
 
}
 
int mavl_foreach_rl(struct mavlnode *n, int (*callback)(void *,void *),void *cbpriv)
{
if (!n)
return 1;
if (!mavl_foreach_rl(n->s[1],callback,cbpriv))
return 0;
if (!callback(cbpriv,mavlnode_dataptr(n)))
return 0;
return mavl_foreach_rl(n->s[0],callback,cbpriv);
}
 
void mavl_foreach(struct mavl *t, int (*callback)(void *,void *),void * cbpriv,int dir)
{
if (dir)
(void)mavl_foreach_lr(t->root,callback,cbpriv);
else
(void)mavl_foreach_rl(t->root,callback,cbpriv);
}
 
/tags/libmavl/1.0.0/mavl_foreach_lr.c
0,0 → 1,15
#include "mavl.h"
 
int mavl_foreach_lr(struct mavlnode *n, int (*callback)(void *,void *),void *cbpriv)
{
if (!n)
return 1;
if (!mavl_foreach_lr(n->left,callback,cbpriv))
return 0;
if (!callback(cbpriv,mavlnode_dataptr(n)))
return 0;
return mavl_foreach_lr(n->right,callback,cbpriv);
 
}
 
 
/tags/libmavl/1.0.0/mavl_get.c
0,0 → 1,50
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include "mavl.h"
 
/**
* Get an AVL tree element.
* @param t pointer to mavl_t
* @param data Element to get
* @return pointer to element or NULL if not found.
*/
void * mavl_get(struct mavl *t ,const void *data)
{
struct mavlnode *n = t->root;
while(n){
int rc=t->cmp(data,mavlnode_dataptr(n));
if (rc==0)
return mavlnode_dataptr(n);
if (rc<0)
n=n->s[0];
else
n=n->s[1];
}
return NULL;
}
 
/tags/libmavl/1.0.0/mavl_get_depth.c
0,0 → 1,50
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "mavl.h"
 
static int get_depth( struct mavlnode *n, int d )
{
int dl,dr;
if (!n)
return d;
 
dl = get_depth(n->s[0],d+1);
dr = get_depth(n->s[1],d+1);
 
return dl>dr ? dl : dr;
}
 
/**
* Calculate the depth of an AVL tree
*/
int
mavl_get_depth( struct mavl *t )
{
return get_depth(t->root,0);
}
 
 
/tags/libmavl/1.0.0/mavl_print.c
0,0 → 1,74
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
 
#include "mavl.h"
 
 
static void
print0(struct mavlnode *n, int depth, int cdepth, int x,
char *buffer,int width,
void (*pcb)(char*,struct mavlnode *))
{
char temp[180];
int de;
de = cdepth;
if (!n)
return;
if (cdepth==depth){
pcb(temp,n);
(void)strncpy(buffer+x,temp,strlen(temp));
return ;
}
if (cdepth>depth)
return;
print0(n->s[0],depth,cdepth+1,x-width/(2<<(de+1)),buffer,width,pcb);
print0(n->s[1],depth,cdepth+1,x+width/(2<<(de+1)),buffer,width,pcb);
 
}
 
void
mavl_print(struct mavl *t, void (*pcb)(char*,struct mavlnode *), int width)
{
int de;
char * buffer;
buffer = malloc(sizeof(char)*(width+1));
 
for (de=0;de<10;de++){
(void)memset(buffer,' ',(size_t)width);
print0(t->root,de,0,width/2,buffer,width,pcb);
buffer[width+1]=0;
(void)printf("%s\n",buffer);
}
 
free(buffer);
}
 
 
/tags/libmavl/1.0.0/mavl_verify.c
0,0 → 1,49
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include "mavl.h"
 
int
mavl_verify(struct mavl *t)
{
struct mavliter it;
void *data, *last;
 
mavliter_init(&it, t);
 
last = NULL;
mavliter_foreach(&it){
data = mavliter_get(&it);
if (last){
if (t->cmp(last,data)>0)
return 0;
}
last = data;
}
return 1;
 
}
/tags/libmavl/1.0.0/mavliter_get.c
0,0 → 1,41
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "mavl.h"
 
/**
* Get the element, where AVL Iterator currently is positioned.
* @param i AVL Iterator
* @return element or NULL if not found.
*/
void *
mavliter_get(struct mavliter *i)
{
if (!i->cur)
return NULL;
return mavlnode_dataptr(i->cur);
}
/tags/libmavl/1.0.0/mavliter_init.c
0,0 → 1,46
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include "mavl.h"
 
/**
* Init an AVL Tree Iterator.
*
* After initialization #mavliter_next would return the first element.
* The behavior of #mavliter_get would still be undefined.
* @param i AVL Iterator to initialize
* @param t correspondending AVL Tree
*
* @See struct mavliter,
*/
void
mavliter_init(struct mavliter * i, struct mavl * t)
{
i->root = t->root;
i->stack_ptr = 0;
i->cmp = t->cmp;
}
/tags/libmavl/1.0.0/mavliter_next.c
0,0 → 1,76
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
/**
*@file
*@brief Implementation of mavliter_next
*/
 
#include "mavl.h"
 
/**
* Get the next element within an AVL Tree.
* @param i pointer to AVL Iterator
* @return the element or NULL if there is no next elemeent.
*/
 
void *
mavliter_next ( struct mavliter *i )
{
while ( i->stack_ptr ) {
i->stack_ptr--;
i->cur = i->stack[i->stack_ptr];
if ( !i->cur )
continue;
if ( ( i->stack_ptr ) & 1 )
return mavlnode_dataptr ( i->cur );
break;
}
 
 
if ( !i->cur )
return NULL;
 
while ( i->cur->s[0] ) {
 
/* push s[1] branch */
i->stack[i->stack_ptr++] = i->cur->s[1];
/* push node */
i->stack[i->stack_ptr++] = i->cur;
i->cur = i->cur->s[0];
}
i->stack[i->stack_ptr++] = i->cur->s[1];
return mavlnode_dataptr ( i->cur );
}
 
/tags/libmavl/1.0.0/mavliter_seek_set.c
0,0 → 1,35
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "mavl.h"
 
void *
mavliter_seek_set ( struct mavliter *i )
{
i->stack_ptr = 0;
i->cur = i->root;
return mavliter_next ( i );
}
/tags/libmavl/1.0.0/mavlnode_destroy.c
0,0 → 1,39
 
/*
* Copyright 2019, The PLANIX Project
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are
* met:
*
* 1. Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
* IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
 
#include "mavl.h"
 
void mavlnode_destroy(struct mavl *t, struct mavlnode *n)
{
if (t->del) {
t->del(mavlnode_dataptr(n));
}
t->free(n);
t->count--;
}
/tags/libmavl/1.0.0/test.c
0,0 → 1,234
#include <stdarg.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include <time.h>
 
#include <mutests.h>
 
#include "mavl.h"
 
/* Compare function to compare integers */
static int
cmp(const void *v1, const void *v2)
{
return *((int *)v1) - *((int *)v2);
}
 
static float
calc_depth(int numvals)
{
int i;
unsigned int r=1;
for (i=0; i<64; i++){
if (r>(unsigned int)numvals)
return (float)((double)i*1.44);
r=r<<1;
}
return (float)0.0;
}
 
static int
test_mavl(const char * name,int numvals,int type)
{
int i;
int insval;
int exists;
struct mavl *t;
int rc;
float depth, maxdepth;
 
(void) printf ("Running insert %s: numvals=%d, type=%d\n"
,name, numvals,type);
 
 
/* Create a MAVL object which store object of size of int. */
t = mavl_create(cmp, NULL, sizeof(int));
mu_assert (t!=NULL, "mavl_create(%s): %s", name,strerror(errno));
 
srand((unsigned int)time(NULL));
for (i = 0; i < numvals; i++) {
switch (type) {
case 0:
insval = rand();
break;
case -1:
insval = numvals-i;
break;
default:
insval = i;
break;
 
};
(void)mavl_insert(t, &insval, &exists);
}
rc = mavl_verify(t);
mu_assert(rc,"Verify (%s)",name);
 
mu_assert(t->count == numvals,
"%s %d != %d",name,t->count, numvals);
 
depth = (float)mavl_get_depth(t);
maxdepth = calc_depth(numvals);
mu_assert(depth < maxdepth,
"%s Depth %f >= %f",name,depth,maxdepth);
 
mavl_destroy(t);
return 1;
}
 
static int
test_mavl_del(const char * name,int numvals,int type)
{
int i;
int insval,delval;
int exists;
struct mavl *t;
int rc;
float depth, maxdepth;
int * vals;
 
(void) printf ("Running insert and del %s: numvals=%d, type=%d\n"
,name, numvals,type);
 
vals = malloc(sizeof(int)*(size_t)numvals);
mu_assert(vals != NULL,"%s - allocate vals",
name);
 
/* Create a MAVL object which store object of size of int. */
t = mavl_create(cmp, NULL, sizeof(int));
mu_assert (t!=NULL, "mavl_create(%s): %s", name,strerror(errno));
 
srand((unsigned int)time(NULL));
for (i = 0; i < numvals; i++) {
switch (type) {
case 0:
insval = rand();
break;
case -1:
insval = numvals-i;
break;
default:
insval = i;
break;
 
};
vals[i]=insval;
(void)mavl_insert(t, &insval, &exists);
}
rc = mavl_verify(t);
mu_assert(rc,"Verify (%s)",name);
 
mu_assert(t->count == numvals,
"%s %d != %d",name,t->count, numvals);
 
depth = (float)mavl_get_depth(t);
maxdepth = calc_depth(numvals);
mu_assert(depth < maxdepth,
"%s Depth %f >= %f",name,depth,maxdepth);
 
/* { FILE * outfile;
int i1;
outfile = fopen("error.dat","wt");
for (i1=0; i1<numvals; i1++){
fprintf(outfile, "%d ",vals[i1]);
}
fclose(outfile);
}
*/ for (i=0; i<numvals; i++){
int before_count;
delval = vals[i];
before_count = t->count;
mavl_del(t,&delval);
 
mu_assert(before_count != t->count-1,"%s count %d != %d",
name, before_count,t->count-1);
depth = (float)mavl_get_depth(t);
maxdepth = calc_depth(t->count);
if (!(depth<=maxdepth)){
}
 
mu_assert(depth <= maxdepth,
"%s Del Depth %f >= %f (N: %d)",name,depth,maxdepth,t->count);
 
}
mavl_destroy(t);
return 1;
}
 
 
 
 
 
static int test0(void)
{
const char * name = "test0";
int type = 0;
int i;
for (i=0; i<1000; i++){
(void)test_mavl(name,i+1,type);
}
(void)test_mavl(name,1024,type);
(void)test_mavl(name,31871,type);
(void)test_mavl(name,123456,type);
(void)test_mavl(name,1000000,type);
return 1;
}
 
static int test1(void)
{
const char * name = "test1";
int type = -1;
(void)test_mavl(name,1,type);
(void)test_mavl(name,2,type);
(void)test_mavl(name,3,type);
(void)test_mavl(name,10,type);
(void)test_mavl(name,1024,type);
(void)test_mavl(name,31871,type);
(void)test_mavl(name,123456,type);
(void)test_mavl(name,1000000,type);
return 1;
}
 
static int test2(void)
{
const char * name = "test2";
int type = 1;
(void)test_mavl(name,1,type);
(void)test_mavl(name,2,type);
(void)test_mavl(name,3,type);
(void)test_mavl(name,10,type);
(void)test_mavl(name,1024,type);
(void)test_mavl(name,31871,type);
(void)test_mavl(name,123456,type);
(void)test_mavl(name,1000000,type);
return 1;
}
 
static int test0_del(void)
{
int i;
const char * name = "test0_del";
int type = 0;
for(i=0; i<1500; i++)
(void)test_mavl_del(name,i+1,type);
 
for (i=0; i<2; i++)
(void)test_mavl_del(name,16300,type);
return 1;
}
int
main(void)
{
mutests tf = {
test0_del,
test0,
test1,
test2,
NULL
};
return mutests_run(tf);
}
/tags/libmavl/1.0.0
Property changes:
Added: svn:mergeinfo
## -0,0 +0,4 ##
Merged /branches/smavel/libmavl:r27-65
Merged /branches/ai/libmavl:r59-72
Merged /branches/bnf/libmavl:r79-106
Merged /branches/dq/libmavl:r41-288