Index: src/examples/Makefile.am =================================================================== --- src/examples/Makefile.am (revision 21995bcc5c902a2a43cb6fedb971d92bed446a37) +++ src/examples/Makefile.am (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -6,5 +6,5 @@ ## file "LICENCE" distributed with Cforall. ## -## Makefile.am -- +## Makefile.am -- ## ## Author : Peter A. Buhr @@ -19,5 +19,6 @@ CC = @CFA_BINDIR@/cfa -noinst_PROGRAMS = fstream_test vector_test # build but do not install +noinst_PROGRAMS = fstream_test vector_test avl_test # build but do not install fstream_test_SOURCES = fstream_test.c vector_test_SOURCES = vector_int.c array.c vector_test.c +avl_test_SOURCES = avltree/avl_test.c avltree/avl0.c avltree/avl1.c avltree/avl2.c avltree/avl3.c avltree/avl4.c avltree/avl-private.c Index: src/examples/Makefile.in =================================================================== --- src/examples/Makefile.in (revision 21995bcc5c902a2a43cb6fedb971d92bed446a37) +++ src/examples/Makefile.in (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -36,5 +36,6 @@ PRE_UNINSTALL = : POST_UNINSTALL = : -noinst_PROGRAMS = fstream_test$(EXEEXT) vector_test$(EXEEXT) +noinst_PROGRAMS = fstream_test$(EXEEXT) vector_test$(EXEEXT) \ + avl_test$(EXEEXT) subdir = src/examples DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in @@ -48,4 +49,9 @@ CONFIG_CLEAN_VPATH_FILES = PROGRAMS = $(noinst_PROGRAMS) +am_avl_test_OBJECTS = avl_test.$(OBJEXT) avl0.$(OBJEXT) avl1.$(OBJEXT) \ + avl2.$(OBJEXT) avl3.$(OBJEXT) avl4.$(OBJEXT) \ + avl-private.$(OBJEXT) +avl_test_OBJECTS = $(am_avl_test_OBJECTS) +avl_test_LDADD = $(LDADD) am_fstream_test_OBJECTS = fstream_test.$(OBJEXT) fstream_test_OBJECTS = $(am_fstream_test_OBJECTS) @@ -63,6 +69,8 @@ CCLD = $(CC) LINK = $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) $(LDFLAGS) -o $@ -SOURCES = $(fstream_test_SOURCES) $(vector_test_SOURCES) -DIST_SOURCES = $(fstream_test_SOURCES) $(vector_test_SOURCES) +SOURCES = $(avl_test_SOURCES) $(fstream_test_SOURCES) \ + $(vector_test_SOURCES) +DIST_SOURCES = $(avl_test_SOURCES) $(fstream_test_SOURCES) \ + $(vector_test_SOURCES) ETAGS = etags CTAGS = ctags @@ -176,4 +184,5 @@ fstream_test_SOURCES = fstream_test.c vector_test_SOURCES = vector_int.c array.c vector_test.c +avl_test_SOURCES = avltree/avl_test.c avltree/avl0.c avltree/avl1.c avltree/avl2.c avltree/avl3.c avltree/avl4.c avltree/avl-private.c all: all-am @@ -189,7 +198,7 @@ esac; \ done; \ - echo ' cd $(top_srcdir) && $(AUTOMAKE) --foreign src/examples/Makefile'; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --gnu src/examples/Makefile'; \ $(am__cd) $(top_srcdir) && \ - $(AUTOMAKE) --foreign src/examples/Makefile + $(AUTOMAKE) --gnu src/examples/Makefile .PRECIOUS: Makefile Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status @@ -213,4 +222,7 @@ clean-noinstPROGRAMS: -test -z "$(noinst_PROGRAMS)" || rm -f $(noinst_PROGRAMS) +avl_test$(EXEEXT): $(avl_test_OBJECTS) $(avl_test_DEPENDENCIES) $(EXTRA_avl_test_DEPENDENCIES) + @rm -f avl_test$(EXEEXT) + $(LINK) $(avl_test_OBJECTS) $(avl_test_LDADD) $(LIBS) fstream_test$(EXEEXT): $(fstream_test_OBJECTS) $(fstream_test_DEPENDENCIES) $(EXTRA_fstream_test_DEPENDENCIES) @rm -f fstream_test$(EXEEXT) @@ -227,4 +239,11 @@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/array.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl-private.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl0.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl1.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl2.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl3.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl4.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/avl_test.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fstream_test.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/vector_int.Po@am__quote@ @@ -244,4 +263,102 @@ @AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ @am__fastdepCC_FALSE@ $(COMPILE) -c `$(CYGPATH_W) '$<'` + +avl_test.o: avltree/avl_test.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl_test.o -MD -MP -MF $(DEPDIR)/avl_test.Tpo -c -o avl_test.o `test -f 'avltree/avl_test.c' || echo '$(srcdir)/'`avltree/avl_test.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl_test.Tpo $(DEPDIR)/avl_test.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl_test.c' object='avl_test.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl_test.o `test -f 'avltree/avl_test.c' || echo '$(srcdir)/'`avltree/avl_test.c + +avl_test.obj: avltree/avl_test.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl_test.obj -MD -MP -MF $(DEPDIR)/avl_test.Tpo -c -o avl_test.obj `if test -f 'avltree/avl_test.c'; then $(CYGPATH_W) 'avltree/avl_test.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl_test.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl_test.Tpo $(DEPDIR)/avl_test.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl_test.c' object='avl_test.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl_test.obj `if test -f 'avltree/avl_test.c'; then $(CYGPATH_W) 'avltree/avl_test.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl_test.c'; fi` + +avl0.o: avltree/avl0.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl0.o -MD -MP -MF $(DEPDIR)/avl0.Tpo -c -o avl0.o `test -f 'avltree/avl0.c' || echo '$(srcdir)/'`avltree/avl0.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl0.Tpo $(DEPDIR)/avl0.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl0.c' object='avl0.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl0.o `test -f 'avltree/avl0.c' || echo '$(srcdir)/'`avltree/avl0.c + +avl0.obj: avltree/avl0.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl0.obj -MD -MP -MF $(DEPDIR)/avl0.Tpo -c -o avl0.obj `if test -f 'avltree/avl0.c'; then $(CYGPATH_W) 'avltree/avl0.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl0.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl0.Tpo $(DEPDIR)/avl0.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl0.c' object='avl0.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl0.obj `if test -f 'avltree/avl0.c'; then $(CYGPATH_W) 'avltree/avl0.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl0.c'; fi` + +avl1.o: avltree/avl1.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl1.o -MD -MP -MF $(DEPDIR)/avl1.Tpo -c -o avl1.o `test -f 'avltree/avl1.c' || echo '$(srcdir)/'`avltree/avl1.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl1.Tpo $(DEPDIR)/avl1.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl1.c' object='avl1.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl1.o `test -f 'avltree/avl1.c' || echo '$(srcdir)/'`avltree/avl1.c + +avl1.obj: avltree/avl1.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl1.obj -MD -MP -MF $(DEPDIR)/avl1.Tpo -c -o avl1.obj `if test -f 'avltree/avl1.c'; then $(CYGPATH_W) 'avltree/avl1.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl1.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl1.Tpo $(DEPDIR)/avl1.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl1.c' object='avl1.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl1.obj `if test -f 'avltree/avl1.c'; then $(CYGPATH_W) 'avltree/avl1.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl1.c'; fi` + +avl2.o: avltree/avl2.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl2.o -MD -MP -MF $(DEPDIR)/avl2.Tpo -c -o avl2.o `test -f 'avltree/avl2.c' || echo '$(srcdir)/'`avltree/avl2.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl2.Tpo $(DEPDIR)/avl2.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl2.c' object='avl2.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl2.o `test -f 'avltree/avl2.c' || echo '$(srcdir)/'`avltree/avl2.c + +avl2.obj: avltree/avl2.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl2.obj -MD -MP -MF $(DEPDIR)/avl2.Tpo -c -o avl2.obj `if test -f 'avltree/avl2.c'; then $(CYGPATH_W) 'avltree/avl2.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl2.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl2.Tpo $(DEPDIR)/avl2.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl2.c' object='avl2.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl2.obj `if test -f 'avltree/avl2.c'; then $(CYGPATH_W) 'avltree/avl2.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl2.c'; fi` + +avl3.o: avltree/avl3.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl3.o -MD -MP -MF $(DEPDIR)/avl3.Tpo -c -o avl3.o `test -f 'avltree/avl3.c' || echo '$(srcdir)/'`avltree/avl3.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl3.Tpo $(DEPDIR)/avl3.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl3.c' object='avl3.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl3.o `test -f 'avltree/avl3.c' || echo '$(srcdir)/'`avltree/avl3.c + +avl3.obj: avltree/avl3.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl3.obj -MD -MP -MF $(DEPDIR)/avl3.Tpo -c -o avl3.obj `if test -f 'avltree/avl3.c'; then $(CYGPATH_W) 'avltree/avl3.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl3.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl3.Tpo $(DEPDIR)/avl3.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl3.c' object='avl3.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl3.obj `if test -f 'avltree/avl3.c'; then $(CYGPATH_W) 'avltree/avl3.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl3.c'; fi` + +avl4.o: avltree/avl4.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl4.o -MD -MP -MF $(DEPDIR)/avl4.Tpo -c -o avl4.o `test -f 'avltree/avl4.c' || echo '$(srcdir)/'`avltree/avl4.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl4.Tpo $(DEPDIR)/avl4.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl4.c' object='avl4.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl4.o `test -f 'avltree/avl4.c' || echo '$(srcdir)/'`avltree/avl4.c + +avl4.obj: avltree/avl4.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl4.obj -MD -MP -MF $(DEPDIR)/avl4.Tpo -c -o avl4.obj `if test -f 'avltree/avl4.c'; then $(CYGPATH_W) 'avltree/avl4.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl4.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl4.Tpo $(DEPDIR)/avl4.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl4.c' object='avl4.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl4.obj `if test -f 'avltree/avl4.c'; then $(CYGPATH_W) 'avltree/avl4.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl4.c'; fi` + +avl-private.o: avltree/avl-private.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl-private.o -MD -MP -MF $(DEPDIR)/avl-private.Tpo -c -o avl-private.o `test -f 'avltree/avl-private.c' || echo '$(srcdir)/'`avltree/avl-private.c +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl-private.Tpo $(DEPDIR)/avl-private.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl-private.c' object='avl-private.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl-private.o `test -f 'avltree/avl-private.c' || echo '$(srcdir)/'`avltree/avl-private.c + +avl-private.obj: avltree/avl-private.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -MT avl-private.obj -MD -MP -MF $(DEPDIR)/avl-private.Tpo -c -o avl-private.obj `if test -f 'avltree/avl-private.c'; then $(CYGPATH_W) 'avltree/avl-private.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl-private.c'; fi` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/avl-private.Tpo $(DEPDIR)/avl-private.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='avltree/avl-private.c' object='avl-private.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) -c -o avl-private.obj `if test -f 'avltree/avl-private.c'; then $(CYGPATH_W) 'avltree/avl-private.c'; else $(CYGPATH_W) '$(srcdir)/avltree/avl-private.c'; fi` ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) Index: src/examples/avltree/avl-private.c =================================================================== --- src/examples/avltree/avl-private.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl-private.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,134 @@ +#include "avl.h" +#include "avl-private.h" + +// AVL tree specific (internal) operations: +// rotateLeft, rotateRight, fix +// +// AVL tree enhanced height operation +// +// calcBalance is a simple computation of height(R) - height(L) + +// an AVL tree's height is easy to compute +// just follow path with the larger balance +forall(otype K | Comparable(K), otype V) +int height(tree(K, V) * t){ + int helper(tree(K, V) * t, int ht){ + if (empty(t)){ + return ht; + } else if (t->balance > 0){ + return helper(t->right, 1+ht); + } else { + // can traverse either branch to find the height + // of an AVL tree whose balance is 0 + return helper(t->left, 1+ht); + } + } + return helper(t, 0); +} + +forall(otype K | Comparable(K), otype V) +int calcBalance(tree(K, V) * t){ + int l = height(t->left); + int r = height(t->right); + t->balance = r-l; + return t->balance; +} + +// re-establish the link between parent and child +forall(otype K | Comparable(K), otype V) +void relinkToParent(tree(K, V) * t){ + tree(K, V) * parent = t->parent; // FIX ME!! + if (empty(t->parent)){ + return; + } else if (parent->key < t->key){ + parent->right = t; + } else { + parent->left = t; + } +} + +// rotate left from t +forall(otype K | Comparable(K), otype V) +tree(K, V) * rotateLeft(tree(K, V) * t){ + tree(K, V) * newRoot = t->right; + t->right = newRoot->left; + newRoot->left = t; + + // swap parents + newRoot->parent = t->parent; + t->parent = newRoot; + if (t->right != NULL) { + tree(K, V) * right = t->right; // FIX ME!! + right->parent = t; + } + // re-establish the link between newRoot and its parent + relinkToParent(newRoot); + return newRoot; +} + +// rotate right from t +forall(otype K | Comparable(K), otype V) +tree(K, V) * rotateRight(tree(K, V) * t){ + tree(K, V) * newRoot = t->left; + t->left = newRoot->right; + newRoot->right = t; + + // swap parents + newRoot->parent = t->parent; + t->parent = newRoot; + if (t->left != NULL){ + tree(K, V) * left = t->left; // FIX ME!! + left->parent = t; + } + // re-establish the link between newRoot and its parent + relinkToParent(newRoot); + return newRoot; +} + +// balances a node that has balance factor -2 or 2 +forall(otype K | Comparable(K), otype V) +tree(K, V) * fix(tree(K, V) * t){ + // ensure that t's balance factor is one of + // the appropriate values + assert(t->balance == 2 || t->balance == -2); + + if (t->balance == -2){ + tree(K, V) * left = t->left; // FIX ME!! + if (left->balance == 1){ + t->left = rotateLeft(t->left); + } + return rotateRight(t); + } else if (t->balance == 2){ + tree(K, V) * right = t->right; // FIX ME!! + if (right->balance == -1){ + t->right = rotateRight(t->right); + } + return rotateLeft(t); + } else { + // shouldn't ever get here + assert((int)0); + return t; + } +} + +// attempt to fix the tree, if necessary +forall(otype K | Comparable(K), otype V) +tree(K, V) * tryFix(tree(K, V) * t){ + int b = calcBalance(t); + + if (b == -2 || b == 2){ + t = fix(t); + } else { + assert(b == 0 || b == 1 || b == -1); + } + return t; +} + +// sets parent field of c to be p +forall(otype K | Comparable(K), otype V) +void setParent(tree(K, V) * c, tree(K, V) * p){ + if (! empty(c)){ + c->parent = p; + } +} + Index: src/examples/avltree/avl-private.h =================================================================== --- src/examples/avltree/avl-private.h (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl-private.h (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,14 @@ +#include "avl.h" + +// functions that really shouldn't be exposed, but are to reduce compilation time + +// attempt to fix the tree, if necessary +forall(otype K | Comparable(K), otype V) +tree(K, V) * tryFix(tree(K, V) * t); + +// sets parent field of c to be p +forall(otype K | Comparable(K), otype V) +void setParent(tree(K, V) * c, tree(K, V) * p); + +forall(otype K | Comparable(K), otype V) +int height(tree(K, V) * t); Index: src/examples/avltree/avl.h =================================================================== --- src/examples/avltree/avl.h (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl.h (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,108 @@ +#ifndef AVL_TREE_H +#define AVL_TREE_H + +extern "C" { +#define NULL 0 +void free(void *); +#define assert(cond) if (! (cond)) { printf("Assertion failed: (%s) at %s:%d\n", #cond, __FILE__, __LINE__); abort(); } +void abort(); +int printf(const char *, ...); +} + +// #include +// #include + +trait Comparable(otype T) { + int ??(T t1, T t2); + +forall(dtype T | { void ^?{}(T *); }) +void delete(T * x); + +// To-do: properly use height or balance factor +// Right now I'm recomputing the height for each +// node multiple times. It's Theta-log(n), but still.. + +// Balanced Binary Search Tree of void pointers; almost an AVL tree - +// just needs to make use of the balance factor properly +// Operations: +// ?{}, ^?{} +// create - allocate a new tree. Just a wrapper around malloc which also calls the tree constructor. +// find - search through the tree for the given key; return the associated value +// empty - return true if the tree is empty +// insert - insert node with key and value pair. Returns 0 on success +// remove - remove node with the given key, returns 0 on success, 1 on failure +// copy - deep copy of a tree +// for_each - applies the given function to every data element in the tree +// assumes that a non-zero return value is an error, will return +// the error code from func + +// temporary: need forward decl to get around typedef problem +forall(otype K | Comparable(K), otype V) +struct tree; + +forall(otype K | Comparable(K), otype V) +struct tree { + K key; + V value; + tree(K, V) * parent; + tree(K, V) * left; + tree(K, V) * right; + int balance; +}; + +forall(otype K | Comparable(K), otype V) +void ?{}(tree(K, V) *t, K key, V value); + +forall(otype K | Comparable(K), otype V) +void ^?{}(tree(K, V) * t); + +forall(otype K | Comparable(K), otype V) +tree(K, V) * create(K key, V value); + +forall(otype K | Comparable(K), otype V) +V * find(tree(K, V) * t, K key); + +forall(otype K | Comparable(K), otype V) +int empty(tree(K, V) * t); + +// returns the root of the tree +forall(otype K | Comparable(K), otype V) +int insert(tree(K, V) ** t, K key, V value); + +forall(otype K | Comparable(K), otype V) +int remove(tree(K, V) ** t, K key); + +forall(otype K | Comparable(K), otype V) +void copy(tree(K, V) * src, tree(K, V) ** ret); + +forall(otype K | Comparable(K), otype V) +void for_each(tree(K, V) * t, void (*func)(V)); + +// // Helper function to print trees +// forall(otype K | Comparable(K), otype V) +// void printTree(tree * t, int level){ +// if (empty(t)){ +// return; +// } + +// printTree(t->left, level+1); +// printf("key: %d, value: %s, level: %d\n", t->key, t->value, level); +// printTree(t->right, level+1); +// } + +// // inorder traversal of t +// // prints each key, followed by the value +// forall(otype K | Comparable(K), otype V) +// void printTree(tree(K, V) * t){ +// printTree(t, 0); +// } + + +#endif Index: src/examples/avltree/avl0.c =================================================================== --- src/examples/avltree/avl0.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl0.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,19 @@ +#include "avl.h" + +forall(otype T | Comparable(T)) +int ?==?(T t1, T t2) { + return !(t1 < t2) && !(t2 < t1); +} + +forall(otype T | Comparable(T)) +int ?>?(T t1, T t2) { + return t2 < t1; +} + +forall(dtype T | { void ^?{}(T *); }) +void delete(T * x) { + if (x) { + ^?{}(x); + free(x); + } +} Index: src/examples/avltree/avl1.c =================================================================== --- src/examples/avltree/avl1.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl1.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,51 @@ +#include "avl.h" +// #include "cwrap.h" + +extern "C" { + void * malloc(long int); +} + +forall(otype K | Comparable(K), otype V) +void ?{}(tree(K, V) *t, K key, V value){ + (&t->key) { key }; + (&t->value) { value }; + t->parent = NULL; + t->left = NULL; + t->right = NULL; + t->balance = 0; +} + +forall(otype K | Comparable(K), otype V) +void ^?{}(tree(K, V) * t){ + delete(t->left); + delete(t->right); + ^(&t->key){}; + ^(&t->value){}; +} + +forall(otype K | Comparable(K), otype V) +tree(K, V) * create(K key, V value) { + // infinite loop trying to resolve ... t = malloc(); + tree(K, V) * t = malloc(sizeof(tree(K,V))); + t { key, value }; + return t; +} + +// // Helper function to print trees +// forall(otype K | Comparable(K), otype V) +// void printTree(tree * t, int level){ +// if (empty(t)){ +// return; +// } + +// printTree(t->left, level+1); +// printf("key: %d, value: %s, level: %d\n", t->key, t->value, level); +// printTree(t->right, level+1); +// } + +// // inorder traversal of t +// // prints each key, followed by the value +// forall(otype K | Comparable(K), otype V) +// void printTree(tree(K, V) * t){ +// printTree(t, 0); +// } Index: src/examples/avltree/avl2.c =================================================================== --- src/examples/avltree/avl2.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl2.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,84 @@ +#include "avl.h" +#include "avl-private.h" + +forall(otype K | Comparable(K), otype V) +V * find(tree(K, V) * t, K key){ + if (empty(t)){ + return NULL; + } + + if (t->key == key){ + return &t->value; + } else if (t->key < key){ + return find(t->right, key); + } else { + // t->key > key + return find(t->left, key); + } +} + +forall(otype K | Comparable(K), otype V) +int empty(tree(K, V) * t){ + return t == NULL; +} + +// returns the root of the tree +forall(otype K | Comparable(K), otype V) +int insert(tree(K, V) ** t, K key, V value) { + // handles a non-empty tree + // problem if the following signature is used: tries to use an adapter to call helper, but shouldn't + // be necessary - seems to be a problem with helper's type variables not being renamed + // tree(K, V) * helper(tree(K, V) * t, K key, V value){ + tree(K, V) * helper(tree(K, V) * t){ + if (t->key == key){ + // ran into the same key - uh-oh + return NULL; + } else if (t->key < key){ + if (t->right == NULL){ + t->right = create(key, value); + tree(K, V) * right = t->right; // FIX ME! + right->parent = t; // !!!!!!! + return t->right; + } else { + return helper(t->right); + } + } else { + if (t->left == NULL){ + t->left = create(key, value); + tree(K, V) * left = t->left; // FIX ME! + left->parent = t; // !!!!!!! + return t->left; + } else { + return helper(t->left); + } + } + } + + if (empty(*t)){ + // be nice and return a new tree + *t = create(key, value); + return 0; + } + tree(K, V) * newTree = helper(*t); + if (newTree == NULL){ + // insert error handling code, only possibility + // currently is that the key already exists + return 99; + } + // move up the tree, updating balance factors + // if the balance factor is -1, 0, or 1 keep going + // if the balance factor is -2 or 2, call fix + while (newTree->parent != NULL){ // loop until newTree == NULL? + newTree = tryFix(newTree); + tree(K, V) * parent = newTree->parent; // FIX ME!! + assert(parent->left == newTree || + parent->right == newTree); + newTree = newTree->parent; + } + insert(t, key, value); + + // do it one more time - this is the root + newTree = tryFix(newTree); + *t = newTree; + return 0; +} Index: src/examples/avltree/avl3.c =================================================================== --- src/examples/avltree/avl3.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl3.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,117 @@ +#include "avl.h" +#include "avl-private.h" + +// from stdlib +forall(otype T) +void swap(T *, T *); + +// swaps the data within two tree nodes +forall(otype K | Comparable(K), otype V) +void node_swap(tree(K, V) * t, tree(K, V) * t2){ + swap(&t->key, &t2->key); + swap(&t->value, &t2->value); +} + +// go left as deep as possible from within the right subtree +forall(otype K | Comparable(K), otype V) +tree(K, V) * find_successor(tree(K, V) * t){ + tree(K, V) * find_successor_helper(tree(K, V) * t){ + // go left as deep as possible, return the last node + if (empty(t->left)){ + return t; + } else { + return find_successor_helper(t->left); + } + } + return find_successor_helper(t->right); +} + +// cleanup - don't want to deep delete, so set children to NULL first. +forall(otype K | Comparable(K), otype V) +void deleteSingleNode(tree(K, V) * t) { + t->left = NULL; + t->right = NULL; + deleteSingleNode(t); +} + +// does the actual remove operation once we've found the node in question +forall(otype K | Comparable(K), otype V) +tree(K, V) * remove_node(tree(K, V) * t){ + // is the node a leaf? + if (empty(t->left) && empty(t->right)){ + // yes, just delete this node + delete(t); + return NULL; + } else if (empty(t->left)){ + // if the left is empty, there is only one child -> move right up + node_swap(t, t->right); + tree(K, V) * tmp = t->right; + + // relink tree + t->left = tmp->left; + t->right = tmp->right; + + setParent(t->left, t); + setParent(t->right, t); + deleteSingleNode(tmp); + return t; + } else if (empty(t->right)){ + // if the right is empty, there is only one child -> move left up + node_swap(t, t->left); + tree(K, V) * tmp = t->left; + + // relink tree + t->left = tmp->left; + t->right = tmp->right; + + setParent(t->left, t); + setParent(t->right, t); + deleteSingleNode(tmp); + return t; + } else { + // swap with the successor + tree(K, V) * s = find_successor(t); + tree(K, V) * parent = s->parent; + + if (parent->left == s){ + parent->left = s->right; + } else { + assert(parent->right == s); + parent->right = s->right; + } + setParent(s->right, parent); + node_swap(t, s); + deleteSingleNode(s); + return t; + } +} + +// finds the node that needs to be removed +forall(otype K | Comparable(K), otype V) +tree(K, V) * remove_helper(tree(K, V) * t, K key, int * worked){ + if (empty(t)){ + // did not work because key was not found + // set the status variable and return + *worked = 1; + } else if (t->key == key) { + t = remove_node(t); + } else if (t->key < key){ + t->right = remove_helper(t->right, key, worked); + } else { + // t->key > key + t->left = remove_helper(t->left, key, worked); + } + // try to fix after deleting + if (! empty(t)) { + t = tryFix(t); + } + return t; +} + +forall(otype K | Comparable(K), otype V) +int remove(tree(K, V) ** t, K key){ + int worked = 0; + tree(K, V) * newTree = remove_helper(*t, key, &worked); + *t = newTree; + return worked; +} Index: src/examples/avltree/avl4.c =================================================================== --- src/examples/avltree/avl4.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl4.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,48 @@ +#include "avl.h" +#include "avl-private.h" + +// Perform a shallow copy of src, return the +// new tree in ret +forall(otype K | Comparable(K), otype V) +int copy(tree(K, V) * src, tree(K, V) ** ret){ + tree(K, V) * helper(tree(K, V) * t, int * worked){ + if (empty(t)){ + // given empty tree, return empty tree + return NULL; + } + + // otherwise, this is not an empty node, + // create a new node + tree(K, V) * newTree = create(t->key, t->value); + if (empty(newTree)) { + *worked = 1; + return NULL; + } + + // recursively copy the left and right branches + newTree->left = helper(t->left, worked); + newTree->right = helper(t->right, worked); + + setParent(newTree->left, newTree); + setParent(newTree->right, newTree); + return newTree; + } + + int worked = 0; + *ret = helper(src, &worked); + return worked; +} + +// Apply func to every value element in t, using an in order traversal +forall(otype K | Comparable(K), otype V) +void for_each(tree(K, V) * t, int (*func)(V)) { + if (t == NULL) { + return; + } + // recursively apply the function to the left, + // apply the function to this node, + // recursively apply the function to the right + for_each(t->left, func); + func(t->value); + for_each(t->right, func); +} Index: src/examples/avltree/avl_test.c =================================================================== --- src/examples/avltree/avl_test.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/avltree/avl_test.c (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,51 @@ +#include "avl.h" +#include "avl-private.h" + +extern "C" { + int printf(const char *, ...); + int strcmp(const char *, const char *); +} + +int main(){ + // operations: + // find(tree(K, V) *, K) + // int empty(tree(K, V) *); + // tree(K, V) * insert(tree(K, V) *, K, V); + // int remove(tree(K, V) **, K); + + // int -> int + tree(int, int) * imap = create(-1, 0); + insert(&imap, 12, 13); + insert(&imap, 2, 3); + assert( height(imap) == 2 ); + + printf("%d %d %d\n", *find(imap, 2), *find(imap, 12), *find(imap, -1)); + + remove(&imap, -1); + delete(imap); + + // int -> char * + tree(int, char *) * smap = create(-1, "baz"); + insert(&smap, 12, "bar"); + insert(&smap, 2, "foo"); + assert( height(smap) == 2 ); + + printf("%s %s %s\n", *find(smap, 2), *find(smap, 12), *find(smap, -1)); + + remove(&smap, -2); + delete(smap); + + // char* -> char* + int ? tests/$test.make.txt 2>&1; then + if ! make -j 8 $test > tests/$test.make.txt 2>&1; then echo -e "\tFAILED with build error:" | tee -a $logfile cat tests/$test.make.txt | tee -a $logfile Index: src/examples/tests/avl_test.out.txt =================================================================== --- src/examples/tests/avl_test.out.txt (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) +++ src/examples/tests/avl_test.out.txt (revision 9554d9b8896c38886ce2b6bb9384a2f1927f81d6) @@ -0,0 +1,3 @@ +3 13 0 +foo bar baz +world bar cheese