/tags/libmavl/1.1.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.1.0/Makefile |
---|
0,0 → 1,80 |
OBJS=\ |
mavl_create.o \ |
mavl_del_all.o \ |
mavlnode_destroy.o \ |
mavlnode_get.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 \ |
mavl_get_ext.o \ |
mavl.o mavl_get.o \ |
LIBNAME=libmavl.a |
DLIBNAME=libmavl.so |
PREFIX=~ |
INSTALL_LIB_DIR=/lib |
INSTALL_INCLUDE_DIR=/include |
-include LocalDefs.mak |
all: $(LIBNAME) $(DLIBNAME) |
static: $(LIBNAME) |
dynamic: $(DLIBNAME) |
.c.o: |
$(CC) -c $(CFLAGS) $< |
$(LIBNAME): $(OBJS) |
$(AR) rcs $(LIBNAME) $(OBJS) |
$(DLIBNAME): $(OBJS) |
$(LD) $(LDFLAGS) -shared -o $(DLIBNAME) $(OBJS) |
example1: $(LIBNAME) example1.o |
$(CC) $(LDFLAGS) -o example1 example1.o $(LIBNAME) |
example2: $(LIBNAME) example2.o |
$(CC) $(LDFLAGS) -o example2 example2.o $(LIBNAME) |
example3: $(LIBNAME) example3.o |
$(CC) $(LDFLAGS) -o example3 example3.o $(LIBNAME) |
mavtest: $(LIBNAME) mavtest.o |
$(CC) $(LDFLAGS) -o mavtest mavtest.o $(LIBNAME) |
clean: |
rm -f $(OBJS) |
rm -f $(LIBNAME) |
rm -f $(DLIBNAME) |
rm -f example1.o example1 |
rm -f example2.o example2 |
rm -f example3.o example3 |
rm -f mavtest mavtest.o |
rm -f *.core |
rm -f test.o test |
install: $(LIBNAME) |
mkdir -p $(PREFIX)$(INSTALL_INCLUDE_DIR) |
install -p mavl.h $(PREFIX)$(INSTALL_INCLUDE_DIR)/mavl.h |
mkdir -p $(PREFIX)$(INSTALL_LIB_DIR) |
install -p $(LIBNAME) $(PREFIX)$(INSTALL_LIB_DIR)/$(LIBNAME) |
install -p $(LIBNAME) $(PREFIX)$(INSTALL_LIB_DIR)/$(DLIBNAME) |
uninstall: |
rm -f $(PREFIX)$(INSTALL_LIB_DIR)/$(LIBNAME) |
rm -f $(PREFIX)$(INSTALL_LIB_DIR)/$(DLIBNAME) |
rm -f $(PREFIX)$(INSTALL_INCLUDE_DIR)/mavl.h |
test: $(LIBNAME) test.o |
$(CC) $(LDFLAGS) -o test test.o $(LIBNAME) -lmutests |
/tags/libmavl/1.1.0/README |
---|
0,0 → 1,15 |
Libmavl is a minimalistic AVL tree implementation |
CHANGES |
======= |
Version 1.1.0 |
Some bug fixes in mavl_del |
new functions: |
mavlnode_get, mavl_get_ext and macros mavl_get_first, mavl_get_last |
/tags/libmavl/1.1.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.1.0/example1.c |
---|
0,0 → 1,112 |
/* |
* 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"); |
mavl_destroy(t); |
return 0; |
} |
/tags/libmavl/1.1.0/example2.c |
---|
0,0 → 1,152 |
/* |
* 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((unsigned int)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)); |
mavl_destroy(t); |
return 0; |
} |
/tags/libmavl/1.1.0/example3.c |
---|
0,0 → 1,95 |
/* |
* 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 3 Create an AVL which stores integer values and we check |
* mavl_get_ext. |
*/ |
/* 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; |
int search; |
int *result; |
/* |
* 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+=2) { |
insval = i; |
(void)mavl_insert(t, &insval, &exists); |
} |
search = 3; |
result = |
mavl_get_ext(t , &search, MAVL_FIND_LAST); |
printf("Resul is %d\n",*result); |
mavl_destroy(t); |
return 0; |
} |
/tags/libmavl/1.1.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.1.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.1.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.1.0/mavl.h |
---|
0,0 → 1,135 |
/* |
* 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); |
struct mavlnode * mavlnode_get(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); |
#define MAVL_FIND_FIRST 1 |
#define MAVL_FIND_LAST 2 |
void * mavl_get_ext(struct mavl *t ,const void *search, int mode); |
#define mavl_get_first(tree,search) mavl_get_ext(tree,search,MAVL_FIND_FIRST) |
#define mavl_get_last(tree,search) mavl_get_ext(tree,search,MAVL_FIND_LAST) |
#endif |
/tags/libmavl/1.1.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.1.0/mavl_del.c |
---|
0,0 → 1,186 |
/* |
* 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]) { |
*parent = n->s[1]; |
mavlnode_destroy(t, n); |
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; |
} else { |
dir = rc < 0 ? 0 : 1; |
if (!n->s[dir]) |
return MAVL_E_NOTFOUND; |
bal = mavl_del0(t, &n->s[dir], data); |
if (bal == MAVL_E_NOTFOUND) |
return bal; |
} |
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.1.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.1.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.1.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.1.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.1.0/mavl_get.c |
---|
0,0 → 1,44 |
/* |
* 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; |
n = mavlnode_get(t,data); |
if (n) |
return mavlnode_dataptr(n); |
return NULL; |
} |
/tags/libmavl/1.1.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.1.0/mavl_get_ext.c |
---|
0,0 → 1,49 |
#include "mavl.h" |
void * mavl_get_ext(struct mavl *t ,const void *search, int mode) |
{ |
struct mavlnode *n,/**lastl,*/*last; |
last = NULL; /*lastl=NULL;*/ |
n = t->root; |
while(n){ |
int rc; |
rc = t->cmp(search,mavlnode_dataptr(n)); |
/*printf("Compare: %s %s = %d\n",c1->key,c2->key, rc);*/ |
if (rc==0){ |
return mavlnode_dataptr(n); |
} |
if (rc<0){ |
if (mode == MAVL_FIND_FIRST) |
last = n; |
if (n->s[0]==NULL){ |
if (last == NULL) |
return NULL; |
return mavlnode_dataptr(last); |
} |
n=n->s[0]; |
} |
else{ |
if (mode == MAVL_FIND_LAST) |
last=n; |
if(n->s[1]==NULL){ |
if (last == NULL) |
return NULL; |
return mavlnode_dataptr(last); |
} |
n=n->s[1]; |
} |
} |
return NULL; |
} |
/tags/libmavl/1.1.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)strcpy(buffer+x,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.1.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.1.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.1.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.1.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.1.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.1.0/mavtest.c |
---|
0,0 → 1,177 |
/* |
* 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 |
*/ |
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.1.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.1.0/mavlnode_get.c |
---|
0,0 → 1,45 |
/* |
* 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" |
struct mavlnode * mavlnode_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 n; |
if (rc<0) |
n=n->s[0]; |
else |
n=n->s[1]; |
} |
return NULL; |
} |
/tags/libmavl/1.1.0/test.c |
---|
0,0 → 1,246 |
#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,existed; |
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)); |
existed=0; |
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); |
if (exists) |
existed++; |
} |
rc = mavl_verify(t); |
mu_assert(rc,"Verify (%s)",name); |
mu_assert(t->count+existed == numvals, |
"%s %d != %d",name,t->count+existed, 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,existed; |
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)); |
existed=0; |
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); |
if (exists) |
existed++; |
} |
rc = mavl_verify(t); |
mu_assert(rc,"Verify (%s)",name); |
mu_assert(t->count+existed == numvals, |
"%s %d != %d",name,t->count+existed, 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; |
(void)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); |
free(vals); |
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.1.0 |
---|
Property changes: |
Added: svn:mergeinfo |
Merged /branches/smavel/libmavl:r27-65 |
Merged /branches/ai/libmavl:r59-72 |
Merged /branches/bnf/libmavl:r79-106 |
Merged /branches/dq/libmavl:r41-288 |