diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/Makefile.am | 16 | ||||
| -rw-r--r-- | src/Makefile.in | 554 | ||||
| -rw-r--r-- | src/itzam.h | 709 | ||||
| -rw-r--r-- | src/itzam_btree.c | 1993 | ||||
| -rw-r--r-- | src/itzam_data.c | 1573 | ||||
| -rw-r--r-- | src/itzam_util.c | 308 |
6 files changed, 5153 insertions, 0 deletions
diff --git a/src/Makefile.am b/src/Makefile.am new file mode 100644 index 0000000..181ad4f --- /dev/null +++ b/src/Makefile.am @@ -0,0 +1,16 @@ +INCLUDES = -I$(top_srcdir) +CFLAGS = @CFLAGS@ -std=gnu99 + +h_sources = itzam.h + +cpp_sources = itzam_util.c itzam_data.c itzam_btree.c + +lib_LTLIBRARIES = libitzam.la + +libitzam_la_SOURCES = $(h_sources) $(cpp_sources) +libitzam_la_LDFLAGS= -version-info $(GENERIC_LIBRARY_VERSION) -release $(GENERIC_RELEASE) + +library_includedir=$(includedir)/$(GENERIC_LIBRARY_NAME) +library_include_HEADERS = $(h_sources) + +DEFS = -I. -I$(srcdir) diff --git a/src/Makefile.in b/src/Makefile.in new file mode 100644 index 0000000..7bbf01c --- /dev/null +++ b/src/Makefile.in @@ -0,0 +1,554 @@ +# Makefile.in generated by automake 1.11.1 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, +# 2003, 2004, 2005, 2006, 2007, 2008, 2009 Free Software Foundation, +# Inc. +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + + +VPATH = @srcdir@ +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_triplet = @build@ +host_triplet = @host@ +subdir = src +DIST_COMMON = $(library_include_HEADERS) $(srcdir)/Makefile.am \ + $(srcdir)/Makefile.in +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +mkinstalldirs = $(install_sh) -d +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +am__vpath_adj_setup = srcdirstrip=`echo "$(srcdir)" | sed 's|.|.|g'`; +am__vpath_adj = case $$p in \ + $(srcdir)/*) f=`echo "$$p" | sed "s|^$$srcdirstrip/||"`;; \ + *) f=$$p;; \ + esac; +am__strip_dir = f=`echo $$p | sed -e 's|^.*/||'`; +am__install_max = 40 +am__nobase_strip_setup = \ + srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*|]/\\\\&/g'` +am__nobase_strip = \ + for p in $$list; do echo "$$p"; done | sed -e "s|$$srcdirstrip/||" +am__nobase_list = $(am__nobase_strip_setup); \ + for p in $$list; do echo "$$p $$p"; done | \ + sed "s| $$srcdirstrip/| |;"' / .*\//!s/ .*/ ./; s,\( .*\)/[^/]*$$,\1,' | \ + $(AWK) 'BEGIN { files["."] = "" } { files[$$2] = files[$$2] " " $$1; \ + if (++n[$$2] == $(am__install_max)) \ + { print $$2, files[$$2]; n[$$2] = 0; files[$$2] = "" } } \ + END { for (dir in files) print dir, files[dir] }' +am__base_list = \ + sed '$$!N;$$!N;$$!N;$$!N;$$!N;$$!N;$$!N;s/\n/ /g' | \ + sed '$$!N;$$!N;$$!N;$$!N;s/\n/ /g' +am__installdirs = "$(DESTDIR)$(libdir)" \ + "$(DESTDIR)$(library_includedir)" +LTLIBRARIES = $(lib_LTLIBRARIES) +libitzam_la_LIBADD = +am__objects_1 = +am__objects_2 = itzam_util.lo itzam_data.lo itzam_btree.lo +am_libitzam_la_OBJECTS = $(am__objects_1) $(am__objects_2) +libitzam_la_OBJECTS = $(am_libitzam_la_OBJECTS) +libitzam_la_LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \ + $(libitzam_la_LDFLAGS) $(LDFLAGS) -o $@ +DEFAULT_INCLUDES = -I.@am__isrc@ +depcomp = $(SHELL) $(top_srcdir)/depcomp +am__depfiles_maybe = depfiles +am__mv = mv -f +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +LTCOMPILE = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ + --mode=compile $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) \ + $(AM_CPPFLAGS) $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +CCLD = $(CC) +LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ + --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \ + $(LDFLAGS) -o $@ +SOURCES = $(libitzam_la_SOURCES) +DIST_SOURCES = $(libitzam_la_SOURCES) +HEADERS = $(library_include_HEADERS) +ETAGS = etags +CTAGS = ctags +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +ACLOCAL = @ACLOCAL@ +AMTAR = @AMTAR@ +AR = @AR@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CFLAGS = @CFLAGS@ -std=gnu99 +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFS = -I. -I$(srcdir) +DEPDIR = @DEPDIR@ +DSYMUTIL = @DSYMUTIL@ +DUMPBIN = @DUMPBIN@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +FGREP = @FGREP@ +GENERIC_LIBRARY_NAME = @GENERIC_LIBRARY_NAME@ +GENERIC_LIBRARY_VERSION = @GENERIC_LIBRARY_VERSION@ +GENERIC_RELEASE = @GENERIC_RELEASE@ +GENERIC_VERSION = @GENERIC_VERSION@ +GREP = @GREP@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +LD = @LD@ +LDFLAGS = @LDFLAGS@ +LIBOBJS = @LIBOBJS@ +LIBS = @LIBS@ +LIBTOOL = @LIBTOOL@ +LIPO = @LIPO@ +LN_S = @LN_S@ +LTLIBOBJS = @LTLIBOBJS@ +MAKEINFO = @MAKEINFO@ +MKDIR_P = @MKDIR_P@ +NM = @NM@ +NMEDIT = @NMEDIT@ +OBJDUMP = @OBJDUMP@ +OBJEXT = @OBJEXT@ +OTOOL = @OTOOL@ +OTOOL64 = @OTOOL64@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +RANLIB = @RANLIB@ +SED = @SED@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +STRIP = @STRIP@ +VERSION = @VERSION@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_CC = @ac_ct_CC@ +ac_ct_DUMPBIN = @ac_ct_DUMPBIN@ +am__include = @am__include@ +am__leading_dot = @am__leading_dot@ +am__quote = @am__quote@ +am__tar = @am__tar@ +am__untar = @am__untar@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_vendor = @build_vendor@ +builddir = @builddir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +host = @host@ +host_alias = @host_alias@ +host_cpu = @host_cpu@ +host_os = @host_os@ +host_vendor = @host_vendor@ +htmldir = @htmldir@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +libdir = @libdir@ +libexecdir = @libexecdir@ +localedir = @localedir@ +localstatedir = @localstatedir@ +lt_ECHO = @lt_ECHO@ +mandir = @mandir@ +mkdir_p = @mkdir_p@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +sysconfdir = @sysconfdir@ +target_alias = @target_alias@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +INCLUDES = -I$(top_srcdir) +h_sources = itzam.h +cpp_sources = itzam_util.c itzam_data.c itzam_btree.c +lib_LTLIBRARIES = libitzam.la +libitzam_la_SOURCES = $(h_sources) $(cpp_sources) +libitzam_la_LDFLAGS = -version-info $(GENERIC_LIBRARY_VERSION) -release $(GENERIC_RELEASE) +library_includedir = $(includedir)/$(GENERIC_LIBRARY_NAME) +library_include_HEADERS = $(h_sources) +all: all-am + +.SUFFIXES: +.SUFFIXES: .c .lo .o .obj +$(srcdir)/Makefile.in: $(srcdir)/Makefile.am $(am__configure_deps) + @for dep in $?; do \ + case '$(am__configure_deps)' in \ + *$$dep*) \ + ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \ + && { if test -f $@; then exit 0; else break; fi; }; \ + exit 1;; \ + esac; \ + done; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --foreign src/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --foreign src/Makefile +.PRECIOUS: Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ + esac; + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): +install-libLTLIBRARIES: $(lib_LTLIBRARIES) + @$(NORMAL_INSTALL) + test -z "$(libdir)" || $(MKDIR_P) "$(DESTDIR)$(libdir)" + @list='$(lib_LTLIBRARIES)'; test -n "$(libdir)" || list=; \ + list2=; for p in $$list; do \ + if test -f $$p; then \ + list2="$$list2 $$p"; \ + else :; fi; \ + done; \ + test -z "$$list2" || { \ + echo " $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $$list2 '$(DESTDIR)$(libdir)'"; \ + $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $$list2 "$(DESTDIR)$(libdir)"; \ + } + +uninstall-libLTLIBRARIES: + @$(NORMAL_UNINSTALL) + @list='$(lib_LTLIBRARIES)'; test -n "$(libdir)" || list=; \ + for p in $$list; do \ + $(am__strip_dir) \ + echo " $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=uninstall rm -f '$(DESTDIR)$(libdir)/$$f'"; \ + $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=uninstall rm -f "$(DESTDIR)$(libdir)/$$f"; \ + done + +clean-libLTLIBRARIES: + -test -z "$(lib_LTLIBRARIES)" || rm -f $(lib_LTLIBRARIES) + @list='$(lib_LTLIBRARIES)'; for p in $$list; do \ + dir="`echo $$p | sed -e 's|/[^/]*$$||'`"; \ + test "$$dir" != "$$p" || dir=.; \ + echo "rm -f \"$${dir}/so_locations\""; \ + rm -f "$${dir}/so_locations"; \ + done +libitzam.la: $(libitzam_la_OBJECTS) $(libitzam_la_DEPENDENCIES) + $(libitzam_la_LINK) -rpath $(libdir) $(libitzam_la_OBJECTS) $(libitzam_la_LIBADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/itzam_btree.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/itzam_data.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/itzam_util.Plo@am__quote@ + +.c.o: +@am__fastdepCC_TRUE@ $(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(COMPILE) -c $< + +.c.obj: +@am__fastdepCC_TRUE@ $(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ `$(CYGPATH_W) '$<'` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(COMPILE) -c `$(CYGPATH_W) '$<'` + +.c.lo: +@am__fastdepCC_TRUE@ $(LTCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Plo +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=yes @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(LTCOMPILE) -c -o $@ $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs +install-library_includeHEADERS: $(library_include_HEADERS) + @$(NORMAL_INSTALL) + test -z "$(library_includedir)" || $(MKDIR_P) "$(DESTDIR)$(library_includedir)" + @list='$(library_include_HEADERS)'; test -n "$(library_includedir)" || list=; \ + for p in $$list; do \ + if test -f "$$p"; then d=; else d="$(srcdir)/"; fi; \ + echo "$$d$$p"; \ + done | $(am__base_list) | \ + while read files; do \ + echo " $(INSTALL_HEADER) $$files '$(DESTDIR)$(library_includedir)'"; \ + $(INSTALL_HEADER) $$files "$(DESTDIR)$(library_includedir)" || exit $$?; \ + done + +uninstall-library_includeHEADERS: + @$(NORMAL_UNINSTALL) + @list='$(library_include_HEADERS)'; test -n "$(library_includedir)" || list=; \ + files=`for p in $$list; do echo $$p; done | sed -e 's|^.*/||'`; \ + test -n "$$files" || exit 0; \ + echo " ( cd '$(DESTDIR)$(library_includedir)' && rm -f" $$files ")"; \ + cd "$(DESTDIR)$(library_includedir)" && rm -f $$files + +ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + mkid -fID $$unique +tags: TAGS + +TAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + set x; \ + here=`pwd`; \ + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + shift; \ + if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \ + test -n "$$unique" || unique=$$empty_fix; \ + if test $$# -gt 0; then \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + "$$@" $$unique; \ + else \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + $$unique; \ + fi; \ + fi +ctags: CTAGS +CTAGS: $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + test -z "$(CTAGS_ARGS)$$unique" \ + || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \ + $$unique + +GTAGS: + here=`$(am__cd) $(top_builddir) && pwd` \ + && $(am__cd) $(top_srcdir) \ + && gtags -i $(GTAGS_ARGS) "$$here" + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done +check-am: all-am +check: check-am +all-am: Makefile $(LTLIBRARIES) $(HEADERS) +installdirs: + for dir in "$(DESTDIR)$(libdir)" "$(DESTDIR)$(library_includedir)"; do \ + test -z "$$dir" || $(MKDIR_P) "$$dir"; \ + done +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + `test -z '$(STRIP)' || \ + echo "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'"` install +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES) + -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." +clean: clean-am + +clean-am: clean-generic clean-libLTLIBRARIES clean-libtool \ + mostlyclean-am + +distclean: distclean-am + -rm -rf ./$(DEPDIR) + -rm -f Makefile +distclean-am: clean-am distclean-compile distclean-generic \ + distclean-tags + +dvi: dvi-am + +dvi-am: + +html: html-am + +html-am: + +info: info-am + +info-am: + +install-data-am: install-library_includeHEADERS + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: install-libLTLIBRARIES + +install-html: install-html-am + +install-html-am: + +install-info: install-info-am + +install-info-am: + +install-man: + +install-pdf: install-pdf-am + +install-pdf-am: + +install-ps: install-ps-am + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + -rm -rf ./$(DEPDIR) + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: uninstall-libLTLIBRARIES \ + uninstall-library_includeHEADERS + +.MAKE: install-am install-strip + +.PHONY: CTAGS GTAGS all all-am check check-am clean clean-generic \ + clean-libLTLIBRARIES clean-libtool ctags distclean \ + distclean-compile distclean-generic distclean-libtool \ + distclean-tags distdir dvi dvi-am html html-am info info-am \ + install install-am install-data install-data-am install-dvi \ + install-dvi-am install-exec install-exec-am install-html \ + install-html-am install-info install-info-am \ + install-libLTLIBRARIES install-library_includeHEADERS \ + install-man install-pdf install-pdf-am install-ps \ + install-ps-am install-strip installcheck installcheck-am \ + installdirs maintainer-clean maintainer-clean-generic \ + mostlyclean mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool pdf pdf-am ps ps-am tags uninstall \ + uninstall-am uninstall-libLTLIBRARIES \ + uninstall-library_includeHEADERS + + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/src/itzam.h b/src/itzam.h new file mode 100644 index 0000000..e171a1d --- /dev/null +++ b/src/itzam.h @@ -0,0 +1,709 @@ +/*
+ Itzam/C (version 6.0) is an embedded database engine written in Standard C.
+
+ Copyright 2011 Scott Robert Ladd. All rights reserved.
+
+ Older versions of Itzam/C are:
+ Copyright 2002, 2004, 2006, 2008 Scott Robert Ladd. All rights reserved.
+
+ Ancestral code, from Java and C++ books by the author, is:
+ Copyright 1992, 1994, 1996, 2001 Scott Robert Ladd. All rights reserved.
+
+ Itzam/C is user-supported open source software. It's continued development is dependent on
+ financial support from the community. You can provide funding by visiting the Itzam/C
+ website at:
+
+ http://www.coyotegulch.com
+
+ You may license Itzam/C in one of two fashions:
+
+ 1) Simplified BSD License (FreeBSD License)
+
+ 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 SCOTT ROBERT LADD ``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 SCOTT ROBERT LADD 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.
+
+ The views and conclusions contained in the software and documentation are those of the
+ authors and should not be interpreted as representing official policies, either expressed
+ or implied, of Scott Robert Ladd.
+
+ 2) Closed-Source Proprietary License
+
+ If your project is a closed-source or proprietary project, the Simplified BSD License may
+ not be appropriate or desirable. In such cases, contact the Itzam copyright holder to
+ arrange your purchase of an appropriate license.
+
+ The author can be contacted at:
+
+ scott.ladd@coyotegulch.com
+ scott.ladd@gmail.com
+ http:www.coyotegulch.com
+*/
+
+#if !defined(LIBITZAM_ITZAM_H)
+#define LIBITZAM_ITZAM_H
+
+#if defined(__cplusplus)
+extern "C" {
+#endif
+
+#include <string.h>
+#include <stdio.h>
+
+/*-----------------------------------------------------------------------------
+ Operating system identification and settings
+ */
+#if !defined(ITZAM32) && !defined(ITZAM64)
+ #if defined(__LP64__) || defined(_M_X64)
+ #undef ITZAM32
+ #define ITZAM64 1
+ #define ITZAM_MAX_FILE_SIZE 9223372036854775808
+ #define REF_BYTES 8
+ #else
+ #undef ITZAM64
+ #define ITZAM32 1
+ #define ITZAM_MAX_FILE_SIZE 2147483648
+ #define REF_BYTES 4
+ #endif
+#endif
+
+#if defined(_WIN32) || defined(_WIN64) || defined (_MSC_VER)
+ #define ITZAM_WINDOWS
+ #include <io.h>
+ #include <fcntl.h>
+ #include <share.h>
+ #include <windows.h>
+ #include <process.h>
+ #if _MSC_VER >= 0x0A00
+ #include <stdint.h>
+ #else
+ typedef unsigned __int64 uint64_t;
+ typedef __int64 int64_t;
+ typedef unsigned long uint32_t;
+ typedef long int32_t;
+ typedef unsigned short uint16_t;
+ typedef short int16_t;
+ typedef unsigned char uint8_t;
+ typedef signed char int8_t;
+ #endif
+ #define ITZAM_SHMEM_TYPE HANDLE
+ #define ITZAM_FILE_TYPE HANDLE
+ #define ITZAM_GOOD_FILE(file) (file != INVALID_HANDLE_VALUE)
+ #define ITZAM_SEEK_BEGIN FILE_BEGIN
+ #define ITZAM_SEEK_END FILE_END
+ #define ITZAM_SEEK_CURRENT FILE_CURRENT
+ #define DLL_EXPORT
+ #pragma warning (disable : 4786 4244 4267 4101 4996 4761 4127)
+#elif defined(__unix__) || defined(unix)
+ #if defined(__linux__) || defined(__linux)
+ #define ITZAM_LINUX
+ #endif
+ #define ITZAM_UNIX
+ #include <unistd.h>
+ #include <pthread.h>
+ #include <stdbool.h>
+ #include <stdint.h>
+ #include <fcntl.h>
+ #define ITZAM_SHMEM_TYPE int
+ #define ITZAM_FILE_TYPE int
+ #define ITZAM_SEEK_BEGIN SEEK_SET
+ #define ITZAM_SEEK_END SEEK_END
+ #define ITZAM_SEEK_CURRENT SEEK_CUR
+ #define ITZAM_GOOD_FILE(file) (file != -1)
+#else
+ #error "Itzam is designed for 32- and 64-bit Windows and POSIX"
+#endif
+
+#if defined(ITZAM_UNIX) || defined(ITZAM_LINUX)
+ #include <unistd.h>
+ #if _POSIX_VERSION < 200809L
+ #error "Itzam requires POSIX.1-2008 or later"
+ #endif
+#endif
+
+/*-----------------------------------------------------------------------------
+ * simple types and values
+ */
+
+#pragma pack(push)
+#pragma pack(8)
+
+/* create boolean type to ensure exact size on all platforms */
+typedef int16_t itzam_bool;
+static const int16_t itzam_true = -1;
+static const int16_t itzam_false = 0;
+
+typedef uint8_t itzam_byte;
+
+#if defined(ITZAM64)
+typedef int64_t itzam_ref;
+typedef int64_t itzam_int;
+#else
+typedef int32_t itzam_ref;
+typedef int32_t itzam_int;
+#endif
+
+static const itzam_ref ITZAM_NULL_REF = -1;
+static const itzam_ref ITZAM_NULL_KEY = -1;
+
+typedef enum
+{
+ ITZAM_ERROR_SIGNATURE, // 00
+ ITZAM_ERROR_VERSION,
+ ITZAM_ERROR_64BIT_DB,
+ ITZAM_ERROR_WRITE_FAILED,
+ ITZAM_ERROR_OPEN_FAILED,
+ ITZAM_ERROR_READ_FAILED,
+ ITZAM_ERROR_CLOSE_FAILED,
+ ITZAM_ERROR_SEEK_FAILED,
+ ITZAM_ERROR_TELL_FAILED,
+ ITZAM_ERROR_DUPE_REMOVE,
+ ITZAM_ERROR_FLUSH_FAILED, // 10
+ ITZAM_ERROR_TOO_SMALL,
+ ITZAM_ERROR_PAGE_NOT_FOUND,
+ ITZAM_ERROR_LOST_KEY,
+ ITZAM_ERROR_KEY_NOT_WRITTEN,
+ ITZAM_ERROR_KEY_SEEK_FAILED,
+ ITZAM_ERROR_KEY_REMOVE_FAILED,
+ ITZAM_ERROR_REC_SEEK_FAILED,
+ ITZAM_ERROR_REC_REMOVE_FAILED,
+ ITZAM_ERROR_DELLIST_NOT_READ,
+ ITZAM_ERROR_DELLIST_NOT_WRITTEN, // 20
+ ITZAM_ERROR_ITERATOR_COUNT,
+ ITZAM_ERROR_REWRITE_DELETED,
+ ITZAM_ERROR_INVALID_COL,
+ ITZAM_ERROR_INVALID_ROW,
+ ITZAM_ERROR_INVALID_HASH,
+ ITZAM_ERROR_MALLOC,
+ ITZAM_ERROR_READ_DELETED,
+ ITZAM_ERROR_INVALID_RECORD,
+ ITZAM_ERROR_INVALID_FILE_LOCK_MODE,
+ ITZAM_ERROR_FILE_LOCK_FAILED, // 30
+ ITZAM_ERROR_UNLOCK_FAILED,
+ ITZAM_ERROR_REC_SIZE,
+ ITZAM_ERROR_TRANSACTION_OVERLAP,
+ ITZAM_ERROR_NO_TRANSACTION,
+ ITZAM_ERROR_CURSOR_COUNT,
+ ITZAM_ERROR_INVALID_DATAFILE_OBJECT,
+ ITZAM_ERROR_SIZE_T,
+ ITZAM_ERROR_FILE_CREATE,
+ ITZAM_ERROR_SHMEM_PRIVILEGE,
+ ITZAM_ERROR_SHMEM, // 40
+ ITZAM_ERROR_ALREADY_CREATED,
+ ITZAM_ERROR_READ_ONLY,
+ ITZAM_ERROR_TOO_LONG
+} itzam_error;
+
+typedef enum
+{
+ ITZAM_OKAY,
+ ITZAM_FAILED,
+ ITZAM_VERSION_ERROR,
+ ITZAM_AT_END,
+ ITZAM_AT_BEGIN,
+ ITZAM_NOT_FOUND,
+ ITZAM_DUPLICATE,
+ ITZAM_32BIT_OVERFLOW,
+ ITZAM_DATA_WRITE_FAILED,
+ ITZAM_REF_SIZE_MISMATCH,
+ ITZAM_READ_ONLY,
+ ITZAM_OVERWRITE_TOO_LONG
+} itzam_state;
+
+/*-----------------------------------------------------------------------------
+ * shared memory
+ */
+
+ITZAM_SHMEM_TYPE itzam_shmem_obtain(const char * name, size_t len, itzam_bool * creator);
+
+void itzam_shmem_close(ITZAM_SHMEM_TYPE shmem, const char * name);
+
+void * itzam_shmem_getptr(ITZAM_SHMEM_TYPE shmem, size_t len);
+
+itzam_bool itzam_shmem_commit(void * shmem_ptr);
+
+itzam_bool itzam_shmem_freeptr(void * shmem_ptr, size_t len);
+
+/*-----------------------------------------------------------------------------
+ * generalized file operations
+ */
+
+ITZAM_FILE_TYPE itzam_file_create(const char * filename);
+
+ITZAM_FILE_TYPE itzam_file_open(const char * filename);
+
+itzam_bool itzam_file_close(ITZAM_FILE_TYPE datafile);
+
+itzam_bool itzam_file_read(ITZAM_FILE_TYPE datafile, void * data, size_t len);
+
+itzam_bool itzam_file_write(ITZAM_FILE_TYPE datafile, const void * data, size_t len);
+
+itzam_ref itzam_file_seek(ITZAM_FILE_TYPE datafile, itzam_ref pos, int mode);
+
+itzam_ref itzam_file_tell(ITZAM_FILE_TYPE datafile);
+
+itzam_bool itzam_file_commit(ITZAM_FILE_TYPE datafile);
+
+itzam_bool itzam_file_remove(const char * filename);
+
+itzam_bool itzam_file_lock(ITZAM_FILE_TYPE datafile);
+
+itzam_bool itzam_file_unlock(ITZAM_FILE_TYPE datafile);
+
+/*-----------------------------------------------------------------------------
+ * general function types
+ */
+
+typedef void itzam_error_handler(const char * function_name, itzam_error error);
+
+extern itzam_error_handler * default_error_handler;
+
+void itzam_set_default_error_handler(itzam_error_handler * handler);
+
+/*-----------------------------------------------------------------------------
+ * utility function for normalizing system objects' names (mutex, shm, ...)
+ */
+
+void itzam_build_normalized_name(char * buffer, const char * format, const char * basename);
+
+/* functions of this type must return:
+ * < 0 key1 is before key2
+ * 0 keys are equal
+ * > 0 key1 is after key2
+ */
+typedef int itzam_key_comparator(const void * key1, const void * key2);
+
+/* function to select keys to be included in a subset
+ * itzam_true include key
+ * itzam_false don't include this key
+ */
+typedef itzam_bool itzam_key_selector(const void * key);
+
+/* built-in key comparisons
+ */
+int itzam_comparator_int32(const void * key1, const void * key2);
+int itzam_comparator_uint32(const void * key1, const void * key2);
+int itzam_comparator_string(const void * key1, const void * key2);
+
+/* a callback function used to retrieve whatever data is associated with a reference
+ */
+typedef itzam_bool itzam_export_callback(itzam_ref ref, void ** record, itzam_int * rec_len);
+
+/*-----------------------------------------------------------------------------
+ * datafile structures
+ */
+
+/* data file header, prefix for entire data file
+ */
+static const uint32_t ITZAM_DATAFILE_SIGNATURE = 0x4D5A5449; /* ITZM */
+static const uint32_t ITZAM_RECORD_SIGNATURE = 0x525A5449; /* ITZR */
+
+#if defined(ITZAM64)
+static const uint32_t ITZAM_DATAFILE_VERSION = 0x40050100; /* 64.MM.MM.MM */
+#else
+static const uint32_t ITZAM_DATAFILE_VERSION = 0x20050100; /* 32.MM.MM.MM */
+#endif
+
+static const itzam_int ITZAM_DELLIST_BLOCK_SIZE = 256;
+
+/* flags and masks for record identification
+ */
+static const int32_t ITZAM_RECORD_FLAGS_GENERAL = 0x000000ff;
+static const int32_t ITZAM_RECORD_IN_USE = 0x00000001;
+static const int32_t ITZAM_RECORD_DELLIST = 0x00000002;
+static const int32_t ITZAM_RECORD_SCHEMA = 0x00000004;
+static const int32_t ITZAM_RECORD_TRAN_HEADER = 0x00000010;
+static const int32_t ITZAM_RECORD_TRAN_RECORD = 0x00000020;
+
+static const int32_t ITZAM_RECORD_FLAGS_BTREE = 0x00000f00;
+static const int32_t ITZAM_RECORD_BTREE_HEADER = 0x00000100;
+static const int32_t ITZAM_RECORD_BTREE_PAGE = 0x00000200;
+static const int32_t ITZAM_RECORD_BTREE_KEY = 0x00000400;
+
+static const int32_t ITZAM_RECORD_FLAGS_MATRIX = 0x0000f000;
+static const int32_t ITZAM_RECORD_MATRIX_HEADER = 0x00001000;
+static const int32_t ITZAM_RECORD_MATRIX_TABLE = 0x00002000;
+
+static const int32_t ITZAM_RECORD_FLAGS_HASH = 0x000f0000;
+static const int32_t ITZAM_RECORD_HASH_HEADER = 0x00010000;
+static const int32_t ITZAM_RECORD_HASH_TABLE = 0x00020000;
+static const int32_t ITZAM_RECORD_HASH_KEY = 0x00040000;
+static const int32_t ITZAM_RECORD_HASH_LIST_ENTRY = 0x00080000;
+
+/* record header, prefix for every record in a datafile
+ */
+typedef struct t_itzam_record_header
+{
+ uint32_t m_signature; /* four bytes that identify this as an itzam record */
+ uint32_t m_flags; /* a set of ITZAM_RECORD_* bit settings */
+ itzam_int m_length; /* record length */
+ itzam_int m_rec_len; /* number of bytes in use by actual data */
+}
+itzam_record_header;
+
+/* structures for list of deleted records
+ */
+typedef struct t_itzam_dellist_header
+{
+ itzam_int m_table_size; /* number of entries in the table */
+}
+itzam_dellist_header;
+
+typedef struct t_itzam_dellist_entry
+{
+ itzam_ref m_where; /* reference for this deleted record */
+ itzam_int m_length; /* length of the deleted record */
+}
+itzam_dellist_entry;
+
+/* transaction definitions
+ */
+typedef enum
+{
+ ITZAM_TRAN_OP_WRITE,
+ ITZAM_TRAN_OP_REMOVE,
+ ITZAM_TRAN_OP_OVERWRITE
+}
+itzam_op_type;
+
+/* data file header
+ */
+typedef struct t_itzam_datafile_header
+{
+ uint32_t m_signature; /* file type signature */
+ uint32_t m_version; /* version of this file type */
+ itzam_ref m_dellist_ref; /* position of deleted list in file */
+ itzam_ref m_schema_ref; /* position of XML schema that describes this file */
+ itzam_ref m_index_list_ref; /* position of index reference list */
+ itzam_ref m_transaction_tail; /* last item in the current transaction */
+}
+itzam_datafile_header;
+
+/* transaction operation header
+ */
+typedef struct t_itzam_op_header
+{
+ itzam_op_type m_type;
+ itzam_ref m_where;
+ itzam_ref m_prev_tran;
+ itzam_record_header m_record_header;
+ itzam_ref m_record_where;
+}
+itzam_op_header;
+
+/* definition of shared memory used by all isnatnces of a datafile
+ */
+typedef struct t_itzam_datafile_shared
+{
+ int m_count; /* header information */
+ itzam_datafile_header m_header; /* header information */
+#if defined(ITZAM_UNIX)
+ pthread_mutex_t m_mutex; /* shared mutex */
+#endif
+}
+itzam_datafile_shared;
+
+/* working storage for a loaded datafile
+ */
+typedef struct t_itzam_datafile
+{
+ /* OS file information */
+ ITZAM_FILE_TYPE m_file; /* file associated with this datafile */
+ char * m_filename; /* filename for this datafile */
+
+ /* list of deleted records */
+ itzam_dellist_header m_dellist_header; /* header for current deleted record list */
+ itzam_dellist_entry * m_dellist; /* pointer to list of deleted records */
+
+ /* transaction tracking file information */
+ char * m_tran_file_name; /* transaction filename */
+ struct t_itzam_datafile * m_tran_file; /* transaction file */
+
+#if defined(ITZAM_WINDOWS)
+ /* shared (named) mutex */
+ HANDLE m_mutex; /* mutex information */
+#endif
+
+ /* shared memory, used to communicate between threads and processes */
+ ITZAM_SHMEM_TYPE m_shmem; /* system link to shared memory */
+ char * m_shmem_name; /* name of shared memory block */
+ itzam_datafile_shared * m_shared; /* items shared among all instances */
+
+ /* error handling */
+ itzam_error_handler * m_error_handler; /* function to handle errors that occur */
+
+ /* flags */
+ itzam_bool m_is_open; /* is the file currently open? */
+ itzam_bool m_read_only; /* is the file open read-only? */
+ itzam_bool m_file_locked; /* is the file currently locked? */
+ itzam_bool m_in_transaction; /* are we journalizing a transaction? */
+ itzam_bool m_tran_replacing; /* set when a write replaces a record during a write */
+
+ /* file locking */
+#if defined(ITZAM_UNIX)
+ struct flock m_file_lock; /* fcntl lock */
+#endif
+}
+itzam_datafile;
+
+/*-----------------------------------------------------------------------------
+ * prototypes for variable-length reference data file
+ */
+
+itzam_bool itzam_datafile_exists(const char * filename);
+
+itzam_state itzam_datafile_create(itzam_datafile * datafile,
+ const char * filename);
+
+itzam_state itzam_datafile_open(itzam_datafile * datafile,
+ const char * filename,
+ itzam_bool recover,
+ itzam_bool read_only);
+
+itzam_state itzam_datafile_close(itzam_datafile * datafile);
+
+void itzam_datafile_mutex_lock(itzam_datafile * datafile);
+
+void itzam_datafile_mutex_unlock(itzam_datafile * datafile);
+
+itzam_bool itzam_datafile_file_lock(itzam_datafile * datafile);
+
+itzam_bool itzam_datafile_file_unlock(itzam_datafile * datafile);
+
+itzam_bool itzam_datafile_is_open(itzam_datafile * datafile);
+
+float itzam_datafile_get_version(itzam_datafile * datafile);
+
+void itzam_datafile_set_error_handler(itzam_datafile * datafile,
+ itzam_error_handler * error_handler);
+
+itzam_ref itzam_datafile_tell(itzam_datafile * datafile);
+
+itzam_state itzam_datafile_seek(itzam_datafile * datafile,
+ itzam_ref pos);
+
+itzam_state itzam_datafile_rewind(itzam_datafile * datafile);
+
+/* INTERNAL FUNCTION -- DO NOT USE EXPLICITLY */
+itzam_ref itzam_datafile_get_next_open(itzam_datafile * datafile,
+ itzam_int length);
+
+itzam_ref itzam_datafile_write_flags(itzam_datafile * datafile,
+ const void * data,
+ itzam_int length,
+ itzam_ref where,
+ int32_t flags);
+
+itzam_ref itzam_datafile_write(itzam_datafile * datafile,
+ const void * data,
+ itzam_int length,
+ itzam_ref where);
+
+itzam_state itzam_datafile_overwrite(itzam_datafile * datafile,
+ const void * data,
+ itzam_int length,
+ itzam_ref where,
+ itzam_int offset);
+
+itzam_state itzam_datafile_read(itzam_datafile * datafile,
+ void * data,
+ itzam_int max_length);
+
+itzam_state itzam_datafile_read_alloc(itzam_datafile * datafile,
+ void ** data,
+ itzam_int * length);
+
+itzam_state itzam_datafile_remove(itzam_datafile * datafile);
+
+itzam_state itzam_datafile_transaction_start(itzam_datafile * datafile);
+
+itzam_state itzam_datafile_transaction_commit(itzam_datafile * datafile);
+
+itzam_state itzam_datafile_transaction_rollback(itzam_datafile * datafile);
+
+/*-----------------------------------------------------------------------------
+ * B-tree types data structures
+ */
+
+/* page header, prefix for pages
+ */
+typedef struct t_itzam_btree_page_header
+{
+ itzam_ref m_where; /* location in page file */
+ itzam_ref m_parent; /* parent in page file */
+ uint16_t m_key_count; /* actual # of keys */
+}
+itzam_btree_page_header;
+
+/* a page in the B-tree
+ */
+typedef struct t_itzam_btree_page
+{
+ /* the actual data for this reference
+ */
+ itzam_byte * m_data;
+
+ /* header information
+ */
+ itzam_btree_page_header * m_header;
+
+ /* these elements are pointers into m_data
+ */
+ itzam_byte * m_keys; /* array of key/data objects */
+ itzam_ref * m_links; /* links to other pages */
+}
+itzam_btree_page;
+
+/* B-tree constants
+ */
+static const uint32_t ITZAM_BTREE_VERSION = 0x00040000;
+static const uint16_t ITZAM_BTREE_ORDER_MINIMUM = 4;
+static const uint16_t ITZAM_BTREE_ORDER_DEFAULT = 25;
+
+/* B-tree header
+ */
+typedef struct t_itzam_btree_header
+{
+ uint32_t m_version; /* version of this file structure */
+ uint32_t m_sizeof_page; /* sizeof(itzam_btree_page) used in creating this btreefile */
+ uint32_t m_sizeof_key; /* size of data being stored in pages */
+ uint16_t m_order; /* number of keys per page */
+ uint64_t m_count; /* counts number of active records */
+ uint64_t m_ticker; /* counts the total number of new records added over the life of this btree datafile*/
+ itzam_ref m_where; /* pointer to location of this header */
+ itzam_ref m_root_where; /* pointer to location of root reference in file */
+ itzam_ref m_schema_ref; /* links to a copy of the XML schema for this table (future use) */
+}
+itzam_btree_header;
+
+/* working storage for a loaded B-tree
+ */
+typedef struct t_itzam_btree
+{
+ itzam_datafile * m_datafile; /* file associated with this btree file */
+ ITZAM_SHMEM_TYPE m_shmem_header; /* memory map for the header */
+ char * m_shmem_header_name; /* name associated with memory map */
+ itzam_btree_header * m_header; /* header information */
+ ITZAM_SHMEM_TYPE m_shmem_root; /* memory map for the header */
+ char * m_shmem_root_name; /* name associated with memory map */
+ itzam_byte * m_root_data; /* actual root data */
+ itzam_btree_page m_root; /* root structure */
+ itzam_bool m_free_datafile; /* free the datafile object when closed */
+ uint16_t m_links_size; /* number of links per page; order + 1; calculated at creation time */
+ uint16_t m_min_keys; /* minimum # of keys; order / 2; calculated at creation time */
+ uint16_t m_cursor_count; /* Number of active cursors */
+ itzam_key_comparator * m_key_comparator; /* function to compare keys */
+ itzam_ref m_saved_header; /* temporary header saved during transaction, for use in a rollback */
+}
+itzam_btree;
+
+/*-----------------------------------------------------------------------------
+ * prototypes for B-tree file
+ */
+
+itzam_state itzam_btree_create(itzam_btree * btree,
+ const char * filename,
+ uint16_t order,
+ itzam_int key_size,
+ itzam_key_comparator * key_comparator,
+ itzam_error_handler * error_handler);
+
+itzam_state itzam_btree_open(itzam_btree * btree,
+ const char * filename,
+ itzam_key_comparator * key_comparator,
+ itzam_error_handler * error_handler,
+ itzam_bool recover,
+ itzam_bool read_only);
+
+itzam_state itzam_btree_close(itzam_btree * btree);
+
+uint64_t itzam_btree_count(itzam_btree * btree);
+
+uint64_t itzam_btree_ticker(itzam_btree * btree);
+
+void itzam_btree_mutex_lock(itzam_btree * btree);
+
+void itzam_btree_mutex_unlock(itzam_btree * btree);
+
+itzam_bool itzam_btree_file_lock(itzam_btree * btree);
+
+itzam_bool itzam_btree_file_unlock(itzam_btree * btree);
+
+itzam_bool itzam_btree_is_open(itzam_btree * btree);
+
+void itzam_btree_set_error_handler(itzam_btree * btree,
+ itzam_error_handler * error_handler);
+
+itzam_state itzam_btree_insert(itzam_btree * btree, const void * key);
+
+itzam_bool itzam_btree_find(itzam_btree * btree, const void * search_key, void * result);
+
+itzam_state itzam_btree_remove(itzam_btree * btree, const void * key);
+
+uint16_t itzam_btree_cursor_count(itzam_btree * btree);
+
+itzam_state itzam_btree_transaction_start(itzam_btree * btree);
+
+itzam_state itzam_btree_transaction_commit(itzam_btree * btree);
+
+itzam_state itzam_btree_transaction_rollback(itzam_btree * btree);
+
+/*-----------------------------------------------------------------------------
+ * B-tree cursor structures
+ */
+
+typedef struct t_itzam_btree_cursor_memory
+{
+ struct t_itzam_btree_cursor_memory * m_prev;
+ itzam_bool m_done;
+ size_t m_index;
+}
+itzam_btree_cursor_memory;
+
+typedef struct t_itzam_btree_cursor
+{
+ itzam_btree * m_btree;
+ itzam_btree_page * m_page;
+ size_t m_index;
+ itzam_btree_cursor_memory * m_parent_memory;
+}
+itzam_btree_cursor;
+
+/* B-tree cursor functions
+ */
+
+itzam_state itzam_btree_cursor_create(itzam_btree_cursor * cursor, itzam_btree * btree);
+
+itzam_bool itzam_btree_cursor_valid(itzam_btree_cursor * cursor);
+
+itzam_state itzam_btree_cursor_free(itzam_btree_cursor * cursor);
+
+itzam_bool itzam_btree_cursor_next(itzam_btree_cursor * cursor);
+
+itzam_bool itzam_btree_cursor_reset(itzam_btree_cursor * cursor);
+
+itzam_state itzam_btree_cursor_read(itzam_btree_cursor * cursor, void * returned_key);
+
+#pragma pack(pop)
+
+#if defined(__cplusplus)
+}
+#endif
+
+#endif
diff --git a/src/itzam_btree.c b/src/itzam_btree.c new file mode 100644 index 0000000..6b21ee6 --- /dev/null +++ b/src/itzam_btree.c @@ -0,0 +1,1993 @@ +/*
+ Itzam/C (version 6.0) is an embedded database engine written in Standard C.
+
+ Copyright 2011 Scott Robert Ladd. All rights reserved.
+
+ Older versions of Itzam/C are:
+ Copyright 2002, 2004, 2006, 2008 Scott Robert Ladd. All rights reserved.
+
+ Ancestral code, from Java and C++ books by the author, is:
+ Copyright 1992, 1994, 1996, 2001 Scott Robert Ladd. All rights reserved.
+
+ Itzam/C is user-supported open source software. It's continued development is dependent on
+ financial support from the community. You can provide funding by visiting the Itzam/C
+ website at:
+
+ http://www.coyotegulch.com
+
+ You may license Itzam/C in one of two fashions:
+
+ 1) Simplified BSD License (FreeBSD License)
+
+ 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 SCOTT ROBERT LADD ``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 SCOTT ROBERT LADD 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.
+
+ The views and conclusions contained in the software and documentation are those of the
+ authors and should not be interpreted as representing official policies, either expressed
+ or implied, of Scott Robert Ladd.
+
+ 2) Closed-Source Proprietary License
+
+ If your project is a closed-source or proprietary project, the Simplified BSD License may
+ not be appropriate or desirable. In such cases, contact the Itzam copyright holder to
+ arrange your purchase of an appropriate license.
+
+ The author can be contacted at:
+
+ scott.ladd@coyotegulch.com
+ scott.ladd@gmail.com
+ http:www.coyotegulch.com
+*/
+
+#include "itzam.h"
+
+#include <stdlib.h>
+#include <ctype.h>
+
+static pthread_mutex_t global_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+static itzam_state update_header(itzam_btree * btree)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ /* rewrite file header
+ */
+ itzam_ref where = itzam_datafile_write_flags(btree->m_datafile,
+ btree->m_header,
+ sizeof(itzam_btree_header),
+ btree->m_header->m_where,
+ ITZAM_RECORD_BTREE_HEADER);
+
+ if (where == btree->m_header->m_where)
+ result = ITZAM_OKAY;
+
+ return result;
+}
+
+static itzam_btree_page * dupe_page(const itzam_btree * btree, const itzam_btree_page * source_page)
+{
+ itzam_btree_page * page = NULL;
+
+ /* allocate page
+ */
+ page = (itzam_btree_page *)malloc(sizeof(itzam_btree_page));
+
+ if (page != NULL)
+ {
+ /* allocate data space
+ */
+ page->m_data = (itzam_byte *)malloc(btree->m_header->m_sizeof_page);
+
+ if (page->m_data != NULL)
+ {
+ page->m_header = (itzam_btree_page_header *)page->m_data;
+ page->m_keys = (itzam_byte *)(page->m_data + sizeof(itzam_btree_page_header));
+ page->m_links = (itzam_ref *)(page->m_data + sizeof(itzam_btree_page_header) + btree->m_header->m_sizeof_key * btree->m_header->m_order);
+ memcpy(page->m_data, source_page->m_data, btree->m_header->m_sizeof_page);
+ }
+ else
+ {
+ free(page);
+ page = NULL;
+ }
+ }
+
+ return page;
+}
+
+static void set_page_pointers(const itzam_btree * btree, itzam_btree_page * page)
+{
+ page->m_header = (itzam_btree_page_header *)page->m_data;
+ page->m_keys = (itzam_byte *)(page->m_data + sizeof(itzam_btree_page_header));
+ page->m_links = (itzam_ref *)(page->m_data + sizeof(itzam_btree_page_header) + btree->m_header->m_sizeof_key * btree->m_header->m_order);
+}
+
+static void init_page(const itzam_btree * btree, itzam_btree_page * page)
+{
+ int n;
+
+ page->m_header->m_where = ITZAM_NULL_REF;
+ page->m_header->m_parent = ITZAM_NULL_REF;
+ page->m_header->m_key_count = 0;
+
+ memset(page->m_keys, 0, btree->m_header->m_sizeof_key * btree->m_header->m_order);
+
+ for (n = 0; n < btree->m_header->m_order + 1; ++n)
+ page->m_links[n] = ITZAM_NULL_REF;
+}
+
+static void set_page(const itzam_btree * btree, itzam_btree_page * page, itzam_byte * memory)
+{
+ if ((page != NULL) && (memory != NULL))
+ {
+ page->m_data = memory;
+ set_page_pointers(btree,page);
+ }
+}
+
+static itzam_btree_page * alloc_page(const itzam_btree * btree)
+{
+ itzam_btree_page * page = NULL;
+
+ /* allocate page
+ */
+ page = (itzam_btree_page *)malloc(sizeof(itzam_btree_page));
+
+ if (page != NULL)
+ {
+ /* allocate data space
+ */
+ page->m_data = (itzam_byte *)malloc(btree->m_header->m_sizeof_page);
+
+ if (page->m_data != NULL)
+ {
+ set_page_pointers(btree,page);
+ init_page(btree,page);
+ }
+ else
+ {
+ /* error; clean up and return NULL
+ */
+ free(page);
+ page = NULL;
+ }
+ }
+
+ return page;
+}
+
+static void free_page(itzam_btree_page * page)
+{
+ if ((page != NULL) && (page->m_header->m_parent != ITZAM_NULL_REF))
+ {
+ if (page->m_data != NULL)
+ free(page->m_data);
+
+ free(page);
+ }
+}
+
+static void set_root(itzam_btree * btree, itzam_btree_page * new_root)
+{
+ memcpy(btree->m_root_data, new_root->m_data, btree->m_header->m_sizeof_page);
+ btree->m_header->m_root_where = new_root->m_header->m_where;
+ update_header(btree);
+ new_root->m_data = NULL;
+}
+
+/* can't be static because it's useful for debug/analysis routines
+ */
+itzam_btree_page * read_page(itzam_btree * btree, itzam_ref where)
+{
+ itzam_btree_page * page = NULL;
+
+ /* position datafile
+ */
+ if (ITZAM_OKAY == itzam_datafile_seek(btree->m_datafile,where))
+ {
+ /* allocate a buffer
+ */
+ page = alloc_page(btree);
+
+ if (page != NULL)
+ {
+ /* read the ref
+ */
+ if (ITZAM_OKAY != itzam_datafile_read(btree->m_datafile,page->m_data,btree->m_header->m_sizeof_page))
+ {
+ free_page(page);
+ page = NULL;
+ }
+ }
+ }
+
+ return page;
+}
+
+static itzam_ref write_page(itzam_btree * btree, itzam_btree_page * page)
+{
+ itzam_ref where;
+
+ /* does this page have a location, i.e., is it new?
+ */
+ if (page->m_header->m_where == ITZAM_NULL_REF)
+ page->m_header->m_where = itzam_datafile_get_next_open(btree->m_datafile, btree->m_header->m_sizeof_page);
+
+ where = itzam_datafile_write_flags(btree->m_datafile,
+ page->m_data,
+ btree->m_header->m_sizeof_page,
+ page->m_header->m_where,
+ ITZAM_RECORD_BTREE_PAGE);
+
+ /* make sure things got put where we thought they did
+ */
+ if (where != page->m_header->m_where)
+ where = ITZAM_NULL_REF;
+
+ return where;
+}
+
+int itzam_comparator_int32(const void * key1, const void * key2)
+{
+ int result = 0;
+
+ int32_t * k1 = (int32_t *)key1;
+ int32_t * k2 = (int32_t *)key2;
+
+ if (*k1 < *k2)
+ result = -1;
+ else if (*k1 > *k2)
+ result = 1;
+
+ return result;
+}
+
+int itzam_comparator_uint32(const void * key1, const void * key2)
+{
+ int result = 0;
+
+ uint32_t * k1 = (uint32_t *)key1;
+ uint32_t * k2 = (uint32_t *)key2;
+
+ if (*k1 < *k2)
+ result = -1;
+ else if (*k1 > *k2)
+ result = 1;
+
+ return result;
+}
+
+int itzam_comparator_string(const void * key1, const void * key2)
+{
+ return strcmp((const char *)key1,(const char *)key2);
+}
+
+static char * get_shared_name(const char * fmt, const char * filename)
+{
+ char * result = (char *)malloc(strlen(fmt) + strlen(filename) + 1);
+
+ char * norm = strdup(filename);
+ char * c = norm;
+
+ while (*c)
+ {
+ if (!isalnum(*c))
+ *c = '_';
+ else
+ if (isalpha(*c))
+ *c = tolower(*c);
+
+ ++c;
+ }
+
+ sprintf(result, fmt, norm);
+
+ free(norm);
+
+ return result;
+}
+
+#if defined(ITZAM_UNIX)
+static const char * HDR_NAME_MASK = "/%s-ItzamBTreeHeader";
+static const char * ROOT_NAME_MASK = "/%s-ItzamBTreeRoot";
+#else
+static const char * HDR_NAME_MASK = "Global\\%s-ItzamBTreeHeader";
+static const char * ROOT_NAME_MASK = "Global\\%s-ItzamBTreeRoot";
+#endif
+
+#define MAKE_ITZAM_BHNAME(basename) get_shared_name(HDR_NAME_MASK,basename)
+#define MAKE_ITZAM_ROOT_NAME(basename) get_shared_name(ROOT_NAME_MASK,basename)
+
+itzam_state itzam_btree_create(itzam_btree * btree,
+ const char * filename,
+ uint16_t order,
+ itzam_int key_size,
+ itzam_key_comparator * key_comparator,
+ itzam_error_handler * error_handler)
+{
+ itzam_state result = ITZAM_FAILED;
+ itzam_bool creator;
+
+ pthread_mutex_lock(&global_mutex);
+
+ /* make sure the arguments make sense
+ */
+ if ((btree != NULL) && (filename != NULL) && (key_size > 0) && (key_comparator != NULL))
+ {
+ /* allocate datafile
+ */
+ btree->m_datafile = (itzam_datafile *)malloc(sizeof(itzam_datafile));
+
+ if (btree->m_datafile != NULL)
+ {
+ /* create data file
+ */
+ result = itzam_datafile_create(btree->m_datafile,filename);
+
+ if (ITZAM_OKAY == result)
+ {
+ /* If an error handler was provided, assign it to the datafile
+ */
+ if (error_handler != NULL)
+ itzam_datafile_set_error_handler(btree->m_datafile,error_handler);
+
+ /* allocate memory for shared header
+ */
+ btree->m_shmem_header_name = MAKE_ITZAM_BHNAME(filename);
+
+ btree->m_shmem_header = itzam_shmem_obtain(btree->m_shmem_header_name, sizeof(itzam_btree_header),&creator);
+ btree->m_header = (itzam_btree_header *)itzam_shmem_getptr(btree->m_shmem_header, sizeof(itzam_btree_header));
+
+ /* fill in structure
+ */
+ if (order < ITZAM_BTREE_ORDER_MINIMUM)
+ order = ITZAM_BTREE_ORDER_MINIMUM;
+
+ btree->m_header->m_version = ITZAM_BTREE_VERSION;
+ btree->m_header->m_order = order;
+ btree->m_header->m_count = 0;
+ btree->m_header->m_ticker = 0;
+ btree->m_header->m_schema_ref = ITZAM_NULL_REF;
+
+ btree->m_free_datafile = itzam_true;
+ btree->m_links_size = btree->m_header->m_order + 1;
+ btree->m_min_keys = btree->m_header->m_order / 2;
+ btree->m_key_comparator = key_comparator;
+ btree->m_cursor_count = 0;
+
+ btree->m_header->m_where = itzam_datafile_get_next_open(btree->m_datafile,sizeof(itzam_btree_header));
+ btree->m_header->m_root_where = 0;
+ btree->m_header->m_sizeof_key = key_size;
+ btree->m_header->m_sizeof_page = sizeof(itzam_btree_page_header)
+ + btree->m_header->m_sizeof_key * btree->m_header->m_order
+ + sizeof(itzam_ref) * btree->m_links_size;
+
+ /* write header for first time (lacks root pointer info, but needs to occupy space in the file)
+ */
+ if (btree->m_header->m_where == itzam_datafile_write_flags(btree->m_datafile, btree->m_header, sizeof(itzam_btree_header), btree->m_header->m_where, ITZAM_RECORD_BTREE_HEADER))
+ {
+ /* allocate memory for shared header
+ */
+ btree->m_shmem_root_name = MAKE_ITZAM_ROOT_NAME(filename);
+ btree->m_shmem_root = itzam_shmem_obtain(btree->m_shmem_root_name, btree->m_header->m_sizeof_page, &creator);
+ btree->m_root_data = (itzam_byte *)itzam_shmem_getptr(btree->m_shmem_root, btree->m_header->m_sizeof_page);
+ set_page(btree, &btree->m_root, btree->m_root_data);
+ init_page(btree, &btree->m_root);
+
+ /* assign root a file position
+ */
+ btree->m_root.m_header->m_where = itzam_datafile_get_next_open(btree->m_datafile, btree->m_header->m_sizeof_page);
+
+ if (btree->m_root.m_header->m_where != ITZAM_NULL_REF)
+ {
+ /* write root page
+ */
+ btree->m_header->m_root_where = itzam_datafile_write_flags(btree->m_datafile,
+ btree->m_root.m_data,
+ btree->m_header->m_sizeof_page,
+ btree->m_root.m_header->m_where,
+ ITZAM_RECORD_BTREE_PAGE);
+
+
+ /* make certain that the root was written where we expect it to be
+ */
+ if ((btree->m_header->m_root_where == btree->m_root.m_header->m_where) && (btree->m_header->m_root_where != ITZAM_NULL_REF))
+ result = update_header(btree);
+
+ /* make certain root was written
+ */
+ itzam_file_commit(btree->m_datafile->m_file);
+ }
+ }
+
+ /* remember to deallocate this datafile at closing
+ */
+ btree->m_free_datafile = itzam_true;
+
+ result = ITZAM_OKAY;
+ }
+ }
+ }
+ else
+ default_error_handler("itzam_btree_create",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ pthread_mutex_unlock(&global_mutex);
+
+ return result;
+}
+
+itzam_state itzam_btree_open(itzam_btree * btree,
+ const char * filename,
+ itzam_key_comparator * key_comparator,
+ itzam_error_handler * error_handler,
+ itzam_bool recover,
+ itzam_bool read_only)
+{
+ /* what we return
+ */
+ itzam_state result = ITZAM_FAILED;
+ itzam_bool creator;
+
+ pthread_mutex_lock(&global_mutex);
+
+ /* make sure the arguments make sense
+ */
+ if ((btree != NULL) && (filename != NULL) && (key_comparator != NULL))
+ {
+ /* allocate datafile
+ */
+ btree->m_datafile = (itzam_datafile *)malloc(sizeof(itzam_datafile));
+
+ if (btree->m_datafile != NULL)
+ {
+ /* create data file
+ */
+ result = itzam_datafile_open(btree->m_datafile,filename,recover,read_only);
+
+ if (ITZAM_OKAY == result)
+ {
+ /* If an error handler was provided, assign it to the datafile
+ */
+ if (error_handler != NULL)
+ itzam_datafile_set_error_handler(btree->m_datafile,error_handler);
+
+ /* do the actual create
+ */
+ btree->m_free_datafile = itzam_true;
+ btree->m_key_comparator = key_comparator;
+ btree->m_cursor_count = 0;
+
+ /* allocate memory for embedded header
+ */
+ btree->m_shmem_header_name = MAKE_ITZAM_BHNAME(filename);
+ btree->m_shmem_header = itzam_shmem_obtain(btree->m_shmem_header_name, sizeof(itzam_btree_header),&creator);
+ btree->m_header = (itzam_btree_header *)itzam_shmem_getptr(btree->m_shmem_header, sizeof(itzam_btree_header));
+
+ /* assumes first record is header
+ */
+ if (ITZAM_OKAY == itzam_datafile_rewind(btree->m_datafile))
+ {
+ if (creator)
+ result = itzam_datafile_read(btree->m_datafile,btree->m_header,sizeof(itzam_btree_header));
+
+ if (ITZAM_OKAY == result)
+ {
+ /* verify version
+ */
+ if (btree->m_header->m_version == ITZAM_BTREE_VERSION)
+ {
+ /* finish intializing btree
+ */
+ btree->m_links_size = btree->m_header->m_order + 1;
+ btree->m_min_keys = btree->m_header->m_order / 2;
+
+ /* allocate memory for shared header
+ */
+ btree->m_shmem_root_name = MAKE_ITZAM_ROOT_NAME(filename);
+ btree->m_shmem_root = itzam_shmem_obtain(btree->m_shmem_root_name, btree->m_header->m_sizeof_page,&creator);
+ btree->m_root_data = (itzam_byte *)itzam_shmem_getptr(btree->m_shmem_root, btree->m_header->m_sizeof_page);
+ set_page(btree, &btree->m_root, btree->m_root_data);
+
+ /* read root
+ */
+ if (creator)
+ {
+ itzam_datafile_seek(btree->m_datafile, btree->m_header->m_root_where);
+ itzam_datafile_read(btree->m_datafile, btree->m_root_data, btree->m_header->m_sizeof_page);
+ }
+
+ result = ITZAM_OKAY;
+ }
+ else
+ result = ITZAM_VERSION_ERROR;
+ }
+ }
+
+ result = ITZAM_OKAY;
+ }
+ }
+ }
+ else
+ default_error_handler("itzam_btree_open",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ pthread_mutex_unlock(&global_mutex);
+
+ return result;
+}
+
+/* return number of active records in database
+ */
+uint64_t itzam_btree_count(itzam_btree * btree)
+{
+ uint64_t result = 0;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+
+ if (ITZAM_OKAY == result)
+ result = btree->m_header->m_count;
+
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ return result;
+}
+
+/* return ticker, which is a count of every record ever added to the database
+ */
+uint64_t itzam_btree_ticker(itzam_btree * btree)
+{
+ uint64_t result = 0;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+
+ if (ITZAM_OKAY == result)
+ result = btree->m_header->m_ticker;
+
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_btree_ticker",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+
+ return result;
+}
+
+/* close file
+ */
+itzam_state itzam_btree_close(itzam_btree * btree)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ pthread_mutex_lock(&global_mutex);
+
+ /* make sure the arguments make sense
+ */
+ if ((btree != NULL) && (btree->m_cursor_count == 0))
+ {
+ if (!btree->m_datafile->m_read_only)
+ {
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ update_header(btree);
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ if (result == ITZAM_OKAY)
+ {
+ free(btree->m_datafile);
+ btree->m_datafile = NULL;
+ }
+
+ itzam_shmem_freeptr(btree->m_root_data, btree->m_header->m_sizeof_page);
+ itzam_shmem_close(btree->m_shmem_root, btree->m_shmem_root_name);
+ free(btree->m_shmem_root_name);
+
+ itzam_shmem_freeptr(btree->m_header, sizeof(itzam_btree_header));
+ itzam_shmem_close(btree->m_shmem_header,btree->m_shmem_header_name);
+ free(btree->m_shmem_header_name);
+
+ result = ITZAM_OKAY;
+ }
+ else
+ default_error_handler("itzam_btree_close",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ pthread_mutex_unlock(&global_mutex);
+
+ return result;
+}
+
+void itzam_btree_mutex_lock(itzam_btree * btree)
+{
+ if (btree != NULL)
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ else
+ default_error_handler("itzam_btree_lock",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+}
+
+void itzam_btree_mutex_unlock(itzam_btree * btree)
+{
+ if (btree != NULL)
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ else
+ default_error_handler("itzam_btree_unlock",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+}
+
+/* lock btree file
+ */
+itzam_bool itzam_btree_file_lock(itzam_btree * btree)
+{
+ itzam_bool result = itzam_false;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ result = itzam_datafile_file_lock(btree->m_datafile);
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+ else
+ default_error_handler("itzam_btree_lock",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+/* unlock btree file
+ */
+itzam_bool itzam_btree_file_unlock(itzam_btree * btree)
+{
+ itzam_bool result = itzam_false;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ result = itzam_datafile_file_unlock(btree->m_datafile);
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+ else
+ default_error_handler("itzam_btree_unlock",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_bool itzam_btree_is_open(itzam_btree * btree)
+{
+ itzam_bool result = itzam_false;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ result = itzam_datafile_is_open(btree->m_datafile);
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_btree_is_open",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+
+ return result;
+}
+
+void itzam_btree_set_error_handler(itzam_btree * btree,
+ itzam_error_handler * error_handler)
+{
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ itzam_datafile_set_error_handler(btree->m_datafile,error_handler);
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_btree_set_error_handler",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+}
+
+/* structure used to return search information
+ */
+typedef struct
+{
+ itzam_btree_page * m_page;
+ int m_index;
+ itzam_bool m_found;
+} search_result;
+
+static void search(itzam_btree * btree, const void * key, search_result * result)
+{
+ int index;
+
+ /* duplicate root
+ */
+ itzam_btree_page * page = &btree->m_root;
+
+ while (itzam_true)
+ {
+ index = 0;
+
+ /* if page is empty, we didn't find the key
+ */
+ if ((page == NULL) || (page->m_header->m_key_count == 0))
+ {
+ result->m_page = page;
+ result->m_index = index;
+ result->m_found = itzam_false;
+ return;
+ }
+ else
+ {
+ /* loop through keys
+ */
+ while (index < page->m_header->m_key_count)
+ {
+ int comp = btree->m_key_comparator(key,(const void *)(page->m_keys + index * btree->m_header->m_sizeof_key));
+
+ /* do we move on, or have we found it?
+ */
+ if (comp > 0)
+ ++index;
+ else
+ {
+ if (comp == 0)
+ {
+ result->m_page = page;
+ result->m_index = index;
+ result->m_found = itzam_true;
+ return;
+ }
+
+ break;
+ }
+ }
+
+ /* if we're in a leaf, the key hasn't been found
+ */
+ if (page->m_links[index] == ITZAM_NULL_REF)
+ {
+ result->m_page = page;
+ result->m_index = index;
+ result->m_found = itzam_false;
+ return;
+ }
+ else
+ {
+ /* read and search next page
+ */
+ itzam_btree_page * next_page = read_page(btree,page->m_links[index]);
+
+ if (page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(page);
+
+ page = next_page;
+ }
+ }
+ }
+}
+
+itzam_bool itzam_btree_find(itzam_btree * btree, const void * key, void * returned_key)
+{
+ search_result s;
+
+ s.m_found = itzam_false;
+ s.m_index = 0;
+ s.m_page = NULL;
+
+ if ((btree != NULL) && (key != NULL))
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+
+ search(btree,key,&s);
+
+ if ((s.m_found) && (returned_key != NULL))
+ memcpy(returned_key,s.m_page->m_keys + s.m_index * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ if (s.m_page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(s.m_page);
+
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_btree_find",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+
+ return s.m_found;
+}
+
+/* promote key by creating new root
+ */
+static void promote_root(itzam_btree * btree,
+ itzam_byte * key,
+ itzam_btree_page * page_after)
+{
+ /* create a new root page
+ */
+ itzam_btree_page * new_root = alloc_page(btree);
+ itzam_btree_page * new_before = dupe_page(btree, &btree->m_root);
+
+ /* add key and links to root
+ */
+ memcpy(new_root->m_keys,key,btree->m_header->m_sizeof_key);
+ new_root->m_links[0] = new_before->m_header->m_where;
+ new_root->m_links[1] = page_after->m_header->m_where;
+ new_root->m_header->m_key_count = 1;
+
+ /* write new root to tree, and make it actual root internally
+ */
+ write_page(btree,new_root);
+ set_root(btree,new_root);
+
+ /* update children
+ */
+ new_before->m_header->m_parent = new_root->m_header->m_where;
+ page_after->m_header->m_parent = new_root->m_header->m_where;
+
+ write_page(btree,new_before);
+ write_page(btree,page_after);
+
+ free_page(new_before);
+ free_page(new_root);
+}
+
+/* promote key into parent
+ */
+static void promote_internal(itzam_btree * btree,
+ itzam_btree_page * page_insert,
+ itzam_byte * key,
+ itzam_ref link)
+{
+ if (page_insert->m_header->m_key_count == btree->m_header->m_order)
+ {
+ int nt = 0;
+ int ni = 0;
+ int insert_index = 0;
+
+ itzam_btree_page * page_sibling;
+ itzam_btree_page * child;
+
+ /* temporary array
+ */
+ itzam_byte * temp_keys = (itzam_byte *)malloc(btree->m_header->m_sizeof_key * (btree->m_header->m_order + 1));
+ itzam_ref * temp_links = (itzam_ref *)malloc(sizeof(itzam_ref) * (btree->m_header->m_order + 2));
+
+ if ((temp_keys == NULL) || (temp_links == NULL))
+ btree->m_datafile->m_error_handler("promote_internal", ITZAM_ERROR_MALLOC);
+
+ temp_links[0] = page_insert->m_links[0];
+
+ /* find insertion point
+ */
+ while ((insert_index < page_insert->m_header->m_key_count) && (btree->m_key_comparator(key,(const void *)(page_insert->m_keys + insert_index * btree->m_header->m_sizeof_key)) >= 0))
+ ++insert_index;
+
+ /* store new info
+ */
+ memcpy(temp_keys + insert_index * btree->m_header->m_sizeof_key, key, btree->m_header->m_sizeof_key);
+ temp_links[insert_index + 1] = link;
+
+ /* copy existing keys
+ */
+ while (ni < btree->m_header->m_order)
+ {
+ if (ni == insert_index)
+ ++nt;
+
+ memcpy(temp_keys + nt * btree->m_header->m_sizeof_key, page_insert->m_keys + ni * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ temp_links[nt + 1] = page_insert->m_links[ni + 1];
+
+ ++ni;
+ ++nt;
+ }
+
+ /* generate a new leaf node
+ */
+ page_sibling = alloc_page(btree);
+ page_sibling->m_header->m_parent = page_insert->m_header->m_parent;
+
+ /* clear key counts
+ */
+ page_insert->m_header->m_key_count = 0;
+ page_sibling->m_header->m_key_count = 0;
+ page_insert->m_links[0] = temp_links[0];
+
+ /* copy keys from temp to pages
+ */
+ for (ni = 0; ni < btree->m_min_keys; ++ni)
+ {
+ memcpy(page_insert->m_keys + ni * btree->m_header->m_sizeof_key, temp_keys + ni * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_insert->m_links[ni + 1] = temp_links[ni + 1];
+ ++page_insert->m_header->m_key_count;
+ }
+
+ page_sibling->m_links[0] = temp_links[btree->m_min_keys + 1];
+
+ for (ni = btree->m_min_keys + 1; ni <= btree->m_header->m_order; ++ni)
+ {
+ memcpy(page_sibling->m_keys + (ni - 1 - btree->m_min_keys) * btree->m_header->m_sizeof_key, temp_keys + ni * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_sibling->m_links[ni - btree->m_min_keys] = temp_links[ni + 1];
+ ++page_sibling->m_header->m_key_count;
+ }
+
+ /* replace unused entries with null
+ */
+ for (ni = btree->m_min_keys; ni < btree->m_header->m_order; ++ni)
+ {
+ memset(page_insert->m_keys + ni * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+ page_insert->m_links[ni + 1] = ITZAM_NULL_REF;
+ }
+
+ /* write pages
+ */
+ write_page(btree,page_insert);
+ write_page(btree,page_sibling);
+
+ if (page_insert->m_header->m_parent == ITZAM_NULL_REF)
+ set_root(btree,page_insert);
+
+ /* update parent links in child nodes
+ */
+ for (ni = 0; ni <= page_sibling->m_header->m_key_count; ++ni)
+ {
+ child = read_page(btree,page_sibling->m_links[ni]);
+
+ if (child != NULL)
+ {
+ child->m_header->m_parent = page_sibling->m_header->m_where;
+ write_page(btree,child);
+ }
+ else
+ btree->m_datafile->m_error_handler("promote_internal",ITZAM_ERROR_PAGE_NOT_FOUND);
+
+ free_page(child);
+ }
+
+ /* promote key and pointer
+ */
+ if (page_insert->m_header->m_parent == ITZAM_NULL_REF)
+ {
+ /* create a new root
+ */
+ promote_root(btree,
+ temp_keys + btree->m_min_keys * btree->m_header->m_sizeof_key,
+ page_sibling);
+ }
+ else
+ {
+ /* read parent and promote key
+ */
+ itzam_btree_page * parent_page = read_page(btree,page_insert->m_header->m_parent);
+
+ promote_internal(btree,
+ parent_page,
+ temp_keys + btree->m_min_keys * btree->m_header->m_sizeof_key,
+ page_sibling->m_header->m_where);
+
+ free_page(parent_page);
+ }
+
+ /* release resources
+ */
+ free_page(page_sibling);
+ free(temp_keys);
+ free(temp_links);
+ }
+ else
+ {
+ int n, insert_index = 0;
+
+ /* find insertion point
+ */
+ while ((insert_index < page_insert->m_header->m_key_count)
+ && (btree->m_key_comparator(key,(void *)(page_insert->m_keys + insert_index * btree->m_header->m_sizeof_key)) >= 0))
+ {
+ ++insert_index;
+ }
+
+ /* shift keys right
+ */
+ for (n = page_insert->m_header->m_key_count; n > insert_index; --n)
+ {
+ memcpy(page_insert->m_keys + n * btree->m_header->m_sizeof_key, page_insert->m_keys + (n - 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_insert->m_links[n + 1] = page_insert->m_links[n];
+ }
+
+ memcpy(page_insert->m_keys + insert_index * btree->m_header->m_sizeof_key, key, btree->m_header->m_sizeof_key);
+ page_insert->m_links[insert_index + 1] = link;
+
+ ++page_insert->m_header->m_key_count;
+
+ /* write updated page
+ */
+ write_page(btree,page_insert);
+
+ if (page_insert->m_header->m_parent == ITZAM_NULL_REF)
+ set_root(btree, page_insert);
+ }
+}
+
+static void write_key(itzam_btree * btree,
+ search_result * insert_info,
+ const itzam_byte * key)
+{
+ itzam_btree_page * page_sibling;
+ itzam_btree_page * page_parent;
+
+ /* check to see if page is full
+ */
+ if (insert_info->m_page->m_header->m_key_count == btree->m_header->m_order)
+ {
+ int nt, ni;
+
+ /* temporary array to store new items
+ */
+ itzam_byte * temp_keys = (itzam_byte *)malloc(btree->m_header->m_sizeof_key * (btree->m_header->m_order + 1));
+ memcpy(temp_keys + insert_info->m_index * btree->m_header->m_sizeof_key, key, btree->m_header->m_sizeof_key);
+
+ /* copy entries from insertion page to temps
+ */
+ nt = 0;
+ ni = 0;
+
+ while (ni < btree->m_header->m_order)
+ {
+ /* skip over inserted data
+ */
+ if (ni == insert_info->m_index)
+ ++nt;
+
+ /* copy data
+ */
+ memcpy(temp_keys + nt * btree->m_header->m_sizeof_key, insert_info->m_page->m_keys + ni * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* next one
+ */
+ ++ni;
+ ++nt;
+ }
+
+ /* create a new leaf
+ */
+ page_sibling = alloc_page(btree);
+ page_sibling->m_header->m_parent = insert_info->m_page->m_header->m_parent;
+
+ /* clear key counts
+ */
+ insert_info->m_page->m_header->m_key_count = 0;
+ page_sibling->m_header->m_key_count = 0;
+
+ /* copy keys from temp to pages
+ */
+ for (ni = 0; ni < btree->m_min_keys; ++ni)
+ {
+ memcpy(insert_info->m_page->m_keys + ni * btree->m_header->m_sizeof_key, temp_keys + ni * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ ++insert_info->m_page->m_header->m_key_count;
+ }
+
+ for (ni = btree->m_min_keys + 1; ni <= btree->m_header->m_order; ++ni)
+ {
+ memcpy(page_sibling->m_keys + (ni - 1 - btree->m_min_keys) * btree->m_header->m_sizeof_key, temp_keys + ni * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ ++page_sibling->m_header->m_key_count;
+ }
+
+ /* replace remaining entries with null
+ */
+ for (ni = btree->m_min_keys; ni < btree->m_header->m_order; ++ni)
+ memset(insert_info->m_page->m_keys + ni * btree->m_header->m_sizeof_key,0,btree->m_header->m_sizeof_key);
+
+ /* write pages
+ */
+ write_page(btree,insert_info->m_page);
+ write_page(btree,page_sibling);
+
+ /* promote key and its pointer
+ */
+ if (insert_info->m_page->m_header->m_parent == ITZAM_NULL_REF)
+ {
+ /* creating a new root page
+ */
+ promote_root(btree,
+ temp_keys + btree->m_min_keys * btree->m_header->m_sizeof_key,
+ page_sibling);
+ }
+ else
+ {
+ /* read parent
+ */
+ page_parent = read_page(btree,insert_info->m_page->m_header->m_parent);
+
+ /* promote key into parent page
+ */
+ promote_internal(btree,
+ page_parent,
+ temp_keys + btree->m_min_keys * btree->m_header->m_sizeof_key,
+ page_sibling->m_header->m_where);
+
+ free_page(page_parent);
+ }
+
+ /* release sibling page
+ */
+ if (page_sibling->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(page_sibling);
+
+ free(temp_keys);
+ }
+ else
+ {
+ int n;
+
+ /* move keys to make room for new one
+ */
+ for (n = insert_info->m_page->m_header->m_key_count; n > insert_info->m_index; --n)
+ memcpy(insert_info->m_page->m_keys + n * btree->m_header->m_sizeof_key, insert_info->m_page->m_keys + (n - 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ memcpy(insert_info->m_page->m_keys + insert_info->m_index * btree->m_header->m_sizeof_key, key, btree->m_header->m_sizeof_key);
+
+ ++insert_info->m_page->m_header->m_key_count;
+
+ /* write updated page
+ */
+ write_page(btree,insert_info->m_page);
+ }
+}
+
+itzam_state itzam_btree_insert(itzam_btree * btree,
+ const void * key)
+{
+ itzam_state result = ITZAM_FAILED;
+ search_result insert_info;
+
+ if ((btree != NULL) && (key != NULL) && (btree->m_cursor_count == 0))
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+
+ if (!btree->m_datafile->m_read_only)
+ {
+ search(btree,key,&insert_info);
+
+ if (!insert_info.m_found)
+ {
+ write_key(btree,&insert_info,(const itzam_byte *)key);
+ ++btree->m_header->m_count;
+ ++btree->m_header->m_ticker;
+
+ result = update_header(btree);
+ }
+ else
+ {
+ result = ITZAM_DUPLICATE;
+ }
+
+ if (insert_info.m_page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(insert_info.m_page);
+ }
+ else
+ result = ITZAM_READ_ONLY;
+
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ //return result;
+ return result;
+}
+
+static void redistribute(itzam_btree * btree,
+ int index,
+ itzam_btree_page * page_before,
+ itzam_btree_page * page_parent,
+ itzam_btree_page * page_after)
+{
+ if ((btree != NULL) && (page_before != NULL) && (page_parent != NULL) && (page_after != NULL))
+ {
+ /* check for leaf page
+ */
+ if (page_before->m_links[0] == ITZAM_NULL_REF)
+ {
+ if (page_before->m_header->m_key_count > page_after->m_header->m_key_count)
+ {
+ int n;
+
+ /* move a key from page_before to page_after
+ */
+ for (n = page_after->m_header->m_key_count; n > 0; --n)
+ memcpy(page_after->m_keys + n * btree->m_header->m_sizeof_key, page_after->m_keys + (n - 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* store parent separator in page_after
+ */
+ memcpy(page_after->m_keys, page_parent->m_keys + index * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* increment page_after key count
+ */
+ ++page_after->m_header->m_key_count;
+
+ /* decrement page_before key count
+ */
+ --page_before->m_header->m_key_count;
+
+ /* move last key in page_before to page_parent as separator
+ */
+ memcpy(page_parent->m_keys + index * btree->m_header->m_sizeof_key, page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* clear last key in page_before
+ */
+ memset(page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+ }
+ else
+ {
+ int n;
+
+ /* add parent key to lesser page
+ */
+ memcpy(page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, page_parent->m_keys + index * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* increment page_before key count
+ */
+ ++page_before->m_header->m_key_count;
+
+ /* move first key in page_after to page_parent as separator
+ */
+ memcpy(page_parent->m_keys + index * btree->m_header->m_sizeof_key, page_after->m_keys, btree->m_header->m_sizeof_key);
+
+ /* decrement page_after key count
+ */
+ --page_after->m_header->m_key_count;
+
+ /* move a key from page_after to page_before
+ */
+ for (n = 0; n < page_after->m_header->m_key_count; ++n)
+ memcpy(page_after->m_keys + n * btree->m_header->m_sizeof_key, page_after->m_keys + (n + 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* clear last key in page_after
+ */
+ memset(page_after->m_keys + n * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+ }
+ }
+ else
+ {
+ itzam_btree_page * page_child;
+
+ if (page_before->m_header->m_key_count > page_after->m_header->m_key_count)
+ {
+ int n;
+
+ /* move a key from page_before to page_after
+ */
+ for (n = page_after->m_header->m_key_count; n > 0; --n)
+ {
+ memcpy(page_after->m_keys + n * btree->m_header->m_sizeof_key, page_after->m_keys + (n - 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_after->m_links[n + 1] = page_after->m_links[n];
+ }
+
+ page_after->m_links[1] = page_after->m_links[0];
+
+ /* store page_parent separator key in page_after
+ */
+ memcpy(page_after->m_keys, page_parent->m_keys + index * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_after->m_links[0] = page_before->m_links[page_before->m_header->m_key_count];
+
+ /* update child link
+ */
+ page_child = read_page(btree,page_after->m_links[0]);
+
+ if (page_child != NULL)
+ {
+ page_child->m_header->m_parent = page_after->m_header->m_where;
+ write_page(btree,page_child);
+ free_page(page_child);
+ }
+ else
+ btree->m_datafile->m_error_handler("redistribute",ITZAM_ERROR_PAGE_NOT_FOUND);
+
+ /* increment page_after key count
+ */
+ ++page_after->m_header->m_key_count;
+
+ /* decrement page_before key count
+ */
+ --page_before->m_header->m_key_count;
+
+ /* move last key in page_before to page_parent as separator
+ */
+ memcpy(page_parent->m_keys + index * btree->m_header->m_sizeof_key, page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ /* clear last key in page_before
+ */
+ memset(page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+ page_before->m_links[page_before->m_header->m_key_count + 1] = ITZAM_NULL_REF;
+ }
+ else
+ {
+ int n;
+
+ /* store page_parent separator key in page_before
+ */
+ memcpy(page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, page_parent->m_keys + index * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_before->m_links[page_before->m_header->m_key_count + 1] = page_after->m_links[0];
+
+ /* update child link
+ */
+ page_child = read_page(btree,page_after->m_links[0]);
+
+ if (page_child != NULL)
+ {
+ page_child->m_header->m_parent = page_before->m_header->m_where;
+ write_page(btree,page_child);
+ free_page(page_child);
+ }
+ else
+ btree->m_datafile->m_error_handler("redistribute",ITZAM_ERROR_PAGE_NOT_FOUND);
+
+ /* increment page_before key count
+ */
+ ++page_before->m_header->m_key_count;
+
+ /* move last key in page_after to page_parent as separator
+ */
+ memcpy(page_parent->m_keys + index * btree->m_header->m_sizeof_key, page_after->m_keys, btree->m_header->m_sizeof_key);
+
+ /* decrement page_after key count
+ */
+ --page_after->m_header->m_key_count;
+
+ /* move a key from page_after to page_before
+ */
+ for (n = 0; n < page_after->m_header->m_key_count; ++n)
+ {
+ memcpy(page_after->m_keys + n * btree->m_header->m_sizeof_key, page_after->m_keys + (n + 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_after->m_links[n] = page_after->m_links[n + 1];
+ }
+
+ page_after->m_links[n] = page_after->m_links[n + 1];
+
+ /* clear last key in page_after
+ */
+ memset(page_after->m_keys + n * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+ page_after->m_links[n + 1] = ITZAM_NULL_REF;
+ }
+ }
+
+ /* write updated pages
+ */
+ write_page(btree,page_before);
+ write_page(btree,page_after);
+ write_page(btree,page_parent);
+
+ if(page_parent->m_header->m_parent == ITZAM_NULL_REF)
+ set_root(btree, page_parent);
+ }
+}
+
+static void adjust_tree(itzam_btree * btree, itzam_btree_page * page);
+
+static void concatenate(itzam_btree * btree, int index, itzam_btree_page * page_before, itzam_btree_page * page_parent, itzam_btree_page * page_after)
+{
+ int n, n2;
+
+ /* move separator key from page_parent into page_before
+ */
+ memcpy(page_before->m_keys + page_before->m_header->m_key_count * btree->m_header->m_sizeof_key, page_parent->m_keys + index * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_before->m_links[page_before->m_header->m_key_count + 1] = page_after->m_links[0];
+
+ /* increment page_before key count
+ */
+ ++page_before->m_header->m_key_count;
+
+ /* delete separator from page_parent
+ */
+ --page_parent->m_header->m_key_count;
+
+ for (n = index; n < page_parent->m_header->m_key_count; ++n)
+ {
+ memcpy(page_parent->m_keys + n * btree->m_header->m_sizeof_key, page_parent->m_keys + (n + 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_parent->m_links[n + 1] = page_parent->m_links[n + 2];
+ }
+
+ /* clear unused key from parent
+ */
+ memset(page_parent->m_keys + n * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+ page_parent->m_links[n + 1] = ITZAM_NULL_REF;
+
+ /* copy keys from page_after to page_before
+ */
+ n2 = 0;
+ n = page_before->m_header->m_key_count;
+
+ /* combine pages
+ */
+ while (n2 < page_after->m_header->m_key_count)
+ {
+ ++page_before->m_header->m_key_count;
+ memcpy(page_before->m_keys + n * btree->m_header->m_sizeof_key, page_after->m_keys + n2 * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+ page_before->m_links[n + 1] = page_after->m_links[n2 + 1];
+ ++n2;
+ ++n;
+ }
+
+ /* delete page_after
+ */
+ itzam_datafile_seek(btree->m_datafile,page_after->m_header->m_where);
+ itzam_datafile_remove(btree->m_datafile);
+
+ /* is this an inner page?
+ */
+ if (page_before->m_links[0] != ITZAM_NULL_REF)
+ {
+ /* adjust child pointers
+ */
+ itzam_btree_page * page_child;
+
+ for (n = 0; n <= page_before->m_header->m_key_count; ++n)
+ {
+ /* read child
+ */
+ page_child = read_page(btree,page_before->m_links[n]);
+
+ /* make sure the child was actually read
+ */
+ if (page_child != NULL)
+ {
+ page_child->m_header->m_parent = page_before->m_header->m_where;
+ write_page(btree,page_child);
+ free_page(page_child);
+ }
+ else
+ btree->m_datafile->m_error_handler("concatenate",ITZAM_ERROR_PAGE_NOT_FOUND);
+ }
+ }
+
+ /* write page_before and parent
+ */
+ if (page_parent->m_header->m_key_count == 0)
+ {
+ /* update before page with old parent's parent
+ */
+ page_before->m_header->m_parent = page_parent->m_header->m_parent;
+ write_page(btree,page_before);
+
+ if (page_before->m_header->m_parent == ITZAM_NULL_REF)
+ {
+ /* update the header if this is the new root
+ */
+ set_root(btree,page_before);
+ }
+ else
+ {
+ /* read parents's parent
+ */
+ itzam_btree_page * parents_parent = read_page(btree,page_parent->m_header->m_parent);
+
+ /* find parent reference and replace with before page
+ */
+ if (parents_parent != NULL)
+ {
+ for (n = 0; n < btree->m_links_size; ++n)
+ {
+ if (parents_parent->m_links[n] == page_parent->m_header->m_where)
+ {
+ parents_parent->m_links[n] = page_before->m_header->m_where;
+ write_page(btree,parents_parent);
+ }
+ }
+
+ free_page(parents_parent);
+ }
+ }
+
+ /* remove empty parent page
+ */
+ itzam_datafile_seek(btree->m_datafile,page_parent->m_header->m_where);
+ itzam_datafile_remove(btree->m_datafile);
+ }
+ else
+ {
+ /* write pages
+ */
+ write_page(btree,page_parent);
+ write_page(btree,page_before);
+
+ /* reset root page if needed
+ */
+ if (page_parent->m_header->m_parent == ITZAM_NULL_REF)
+ set_root(btree,page_parent);
+
+ /* if parent is too small, adjust
+ */
+ if (page_parent->m_header->m_key_count < btree->m_min_keys)
+ adjust_tree(btree,page_parent);
+ }
+}
+
+static void adjust_tree(itzam_btree * btree, itzam_btree_page * page)
+{
+ if ((btree != NULL) && (page != NULL) && (page->m_header->m_parent != ITZAM_NULL_REF))
+ {
+ /* get parent page
+ */
+ itzam_btree_page * page_parent = read_page(btree,page->m_header->m_parent);
+
+ if (page_parent != NULL)
+ {
+ itzam_btree_page * page_sibling_after = NULL;
+ itzam_btree_page * page_sibling_before = NULL;
+
+ /* find pointer to page
+ */
+ int n = 0;
+
+ while (page_parent->m_links[n] != page->m_header->m_where)
+ ++n;
+
+ /* read sibling pages
+ */
+ if (n < page_parent->m_header->m_key_count)
+ page_sibling_after = read_page(btree,page_parent->m_links[n+1]);
+
+ if (n > 0)
+ page_sibling_before = read_page(btree,page_parent->m_links[n-1]);
+
+ /* figure out what to do
+ */
+ if (page_sibling_before != NULL)
+ {
+ --n;
+
+ if (page_sibling_before->m_header->m_key_count > btree->m_min_keys)
+ redistribute(btree,n,page_sibling_before,page_parent,page);
+ else
+ concatenate(btree,n,page_sibling_before,page_parent,page);
+ }
+ else
+ {
+ if (page_sibling_after != NULL)
+ {
+ if (page_sibling_after->m_header->m_key_count > btree->m_min_keys)
+ redistribute(btree,n,page,page_parent,page_sibling_after);
+ else
+ concatenate(btree,n,page,page_parent,page_sibling_after);
+ }
+ }
+
+ if (page_sibling_before != NULL)
+ free_page(page_sibling_before);
+
+ if (page_sibling_after != NULL)
+ free_page(page_sibling_after);
+
+ if (page_parent->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(page_parent);
+ }
+ }
+}
+
+itzam_state itzam_btree_remove(itzam_btree * btree, const void * key)
+{
+ itzam_state result = ITZAM_FAILED;
+ search_result remove_info;
+
+ if ((btree != NULL) && (key != NULL) && (btree->m_cursor_count == 0))
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+
+ if (btree->m_datafile->m_read_only)
+ result = ITZAM_READ_ONLY;
+ else
+ {
+ search(btree,key,&remove_info);
+
+ if (remove_info.m_found)
+ {
+ /* is this a leaf node?
+ */
+ if (remove_info.m_page->m_links[0] == ITZAM_NULL_REF)
+ {
+ int n;
+
+ /* removing key from leaf
+ */
+ --remove_info.m_page->m_header->m_key_count;
+
+ /* slide keys left over removed one
+ */
+ for (n = remove_info.m_index; n < remove_info.m_page->m_header->m_key_count; ++n)
+ memcpy(remove_info.m_page->m_keys + n * btree->m_header->m_sizeof_key, remove_info.m_page->m_keys + (n + 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ memset( remove_info.m_page->m_keys + remove_info.m_page->m_header->m_key_count * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+
+ /* save page
+ */
+ write_page(btree,remove_info.m_page);
+
+ /* adjust the tree, if needed
+ */
+ if (remove_info.m_page->m_header->m_key_count < btree->m_min_keys)
+ adjust_tree(btree,remove_info.m_page);
+
+ result = ITZAM_OKAY;
+ }
+ else /* removing from an internal page */
+ {
+ /* get the successor page
+ */
+ itzam_btree_page * page_successor = read_page(btree,remove_info.m_page->m_links[remove_info.m_index + 1]);
+
+ if (page_successor != NULL)
+ {
+ int n;
+
+ while (page_successor->m_links[0] != ITZAM_NULL_REF)
+ {
+ itzam_btree_page * next_successor = read_page(btree,page_successor->m_links[0]);
+
+ /* check for null page in case of corrupted index
+ */
+ if (next_successor != NULL)
+ {
+ free_page(page_successor);
+ page_successor = next_successor;
+ }
+ else
+ btree->m_datafile->m_error_handler("itzam_btree_remove",ITZAM_ERROR_PAGE_NOT_FOUND);
+ }
+
+ /* first key is the "swappee"
+ */
+ memcpy(remove_info.m_page->m_keys + remove_info.m_index * btree->m_header->m_sizeof_key, page_successor->m_keys, btree->m_header->m_sizeof_key);
+
+ /* remove swapped key from successor page
+ */
+ --page_successor->m_header->m_key_count;
+
+ for (n = 0; n < page_successor->m_header->m_key_count; ++n)
+ memcpy(page_successor->m_keys + n * btree->m_header->m_sizeof_key, page_successor->m_keys + (n + 1) * btree->m_header->m_sizeof_key, btree->m_header->m_sizeof_key);
+
+ memset(page_successor->m_keys + page_successor->m_header->m_key_count * btree->m_header->m_sizeof_key, 0, btree->m_header->m_sizeof_key);
+
+ /* write modified pages
+ */
+ write_page(btree,remove_info.m_page);
+ write_page(btree,page_successor);
+
+ /* adjust tree for leaf node
+ */
+ if (page_successor->m_header->m_key_count < btree->m_min_keys)
+ adjust_tree(btree,page_successor);
+
+ result = ITZAM_OKAY;
+
+ free_page(page_successor);
+ }
+ }
+
+ /* decrement number of records in file
+ */
+ --btree->m_header->m_count;
+ update_header(btree);
+ }
+ else
+ {
+ result = ITZAM_NOT_FOUND;
+ }
+
+ if (remove_info.m_page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(remove_info.m_page);
+ }
+
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ return result;
+}
+
+uint16_t itzam_btree_cursor_count(itzam_btree * btree)
+{
+ uint16_t result = 0;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ result = btree->m_cursor_count;
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ return result;
+}
+
+itzam_state itzam_btree_transaction_start(itzam_btree * btree)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if (btree != NULL)
+ {
+ itzam_datafile_mutex_lock(btree->m_datafile);
+ result = itzam_datafile_transaction_start(btree->m_datafile);
+
+ if (result == ITZAM_OKAY)
+ btree->m_saved_header = itzam_datafile_write(btree->m_datafile->m_tran_file, btree->m_header, sizeof(itzam_btree_header), ITZAM_NULL_REF);
+ }
+
+ return result;
+}
+
+itzam_state itzam_btree_transaction_commit(itzam_btree * btree)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if (btree != NULL)
+ {
+ result = itzam_datafile_transaction_commit(btree->m_datafile);
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ return result;
+}
+
+itzam_state itzam_btree_transaction_rollback(itzam_btree * btree)
+{
+ itzam_state result = ITZAM_FAILED;
+ itzam_btree_page * old_root;
+
+ if (btree != NULL)
+ {
+ /* turn off transaction processing so we can restore
+ */
+ btree->m_datafile->m_in_transaction = itzam_false;
+ itzam_datafile_seek(btree->m_datafile->m_tran_file, btree->m_saved_header);
+ itzam_datafile_read(btree->m_datafile->m_tran_file, btree->m_header, sizeof(itzam_btree_header));
+ update_header(btree);
+
+ /* turn transaction processing on again
+ */
+ btree->m_datafile->m_in_transaction = itzam_true;
+ result = itzam_datafile_transaction_rollback(btree->m_datafile);
+
+ /* restore the root
+ */
+ old_root = read_page(btree,btree->m_header->m_root_where);
+ //free(btree->m_root.m_data);
+ memcpy(btree->m_root_data, old_root->m_data, btree->m_header->m_sizeof_page);
+
+ /* done here
+ */
+ itzam_datafile_mutex_unlock(btree->m_datafile);
+ }
+
+ return result;
+}
+
+/**
+ *------------------------------------------------------------
+ * B-tree cursor functions
+ */
+
+static itzam_bool reset_cursor(itzam_btree_cursor * cursor)
+{
+ itzam_bool result = itzam_false;
+ itzam_bool looking = itzam_true;
+
+ /* read root */
+ itzam_btree_page * next_page = NULL;
+ itzam_btree_cursor_memory * next_memory = NULL;
+ itzam_btree_page * page = &cursor->m_btree->m_root;
+
+ /* follow the tree to the first key in the sequence */
+ cursor->m_parent_memory = NULL;
+ cursor->m_page = NULL;
+ cursor->m_index = 0;
+
+ while (looking && (page != NULL))
+ {
+ if (page->m_header->m_key_count > 0)
+ {
+ if (page->m_links[0] == ITZAM_NULL_REF)
+ {
+ /* found the first key */
+ cursor->m_page = page;
+ cursor->m_index = 0;
+ result = itzam_true;
+ looking = itzam_false;
+ }
+ else
+ {
+ /* remember position in parent page */
+ next_memory = (itzam_btree_cursor_memory *)malloc(sizeof(itzam_btree_cursor_memory));
+
+ if (next_memory == NULL)
+ cursor->m_btree->m_datafile->m_error_handler("reset_sursor", ITZAM_ERROR_MALLOC);
+
+ next_memory->m_prev = cursor->m_parent_memory;
+ next_memory->m_index = 0;
+ cursor->m_parent_memory = next_memory;
+
+ /* move to next page */
+ next_page = read_page(cursor->m_btree,page->m_links[0]);
+
+ if (page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(page);
+
+ page = next_page;
+ }
+ }
+ else
+ {
+ free_page(page);
+ cursor->m_page = NULL;
+ cursor->m_index = 0;
+ cursor->m_parent_memory = NULL;
+ looking = itzam_false;
+ }
+ }
+
+ return result;
+}
+
+itzam_state itzam_btree_cursor_create(itzam_btree_cursor * cursor, itzam_btree * btree)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if ((cursor != NULL) && (btree != NULL))
+ {
+ /* keep reference to target tree */
+ cursor->m_btree = btree;
+
+ /* set cursor to first index key */
+ if (reset_cursor(cursor))
+ {
+ /* increment count of cursors in btree */
+ ++cursor->m_btree->m_cursor_count;
+ result = ITZAM_OKAY;
+ }
+ }
+
+ return result;
+}
+
+itzam_bool itzam_btree_cursor_valid(itzam_btree_cursor * cursor)
+{
+ return (cursor->m_page != NULL);
+}
+
+itzam_state itzam_btree_cursor_free(itzam_btree_cursor * cursor)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if ((cursor != NULL) && (cursor->m_page != NULL))
+ {
+ /* decrement btree cursor count */
+ if (cursor->m_btree->m_cursor_count > 0)
+ {
+ --cursor->m_btree->m_cursor_count;
+ result = ITZAM_OKAY;
+ }
+ else
+ cursor->m_btree->m_datafile->m_error_handler("itzam_btree_cursor_free",ITZAM_ERROR_CURSOR_COUNT);
+ }
+
+ return result;
+}
+
+itzam_bool itzam_btree_cursor_next(itzam_btree_cursor * cursor)
+{
+ itzam_bool result = itzam_false;
+ itzam_bool looking = itzam_true;
+ itzam_btree_page * next_page = NULL;
+ itzam_btree_cursor_memory * temp_memory = NULL;
+
+ if ((cursor != NULL) && (cursor->m_page != NULL))
+ {
+ ++cursor->m_index;
+
+ /* is this a leaf page? */
+ if (cursor->m_page->m_links[cursor->m_index] == ITZAM_NULL_REF)
+ {
+ while (looking)
+ {
+ /* are we at the end of the leaf page? */
+ if (cursor->m_index == cursor->m_page->m_header->m_key_count)
+ {
+ /* do we have a oarent to go back to? */
+ if (cursor->m_page->m_header->m_parent == ITZAM_NULL_REF)
+ {
+ /* at end of keys */
+ result = itzam_false;
+ looking = itzam_false;
+ }
+ else
+ {
+ /* return to parent */
+ next_page = read_page(cursor->m_btree,cursor->m_page->m_header->m_parent);
+
+ /* make new page our current page */
+ if (cursor->m_page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(cursor->m_page);
+
+ cursor->m_page = next_page;
+
+ /* restore parent page position, remove old parent memory */
+ temp_memory = cursor->m_parent_memory;
+ cursor->m_index = cursor->m_parent_memory->m_index;
+ cursor->m_parent_memory = cursor->m_parent_memory->m_prev;
+ free(temp_memory);
+
+ result = itzam_true;
+ looking = itzam_true;
+ }
+ }
+ else
+ {
+ /* we're on the next key */
+ result = itzam_true;
+ looking = itzam_false;
+ }
+ }
+ }
+ else /* inner page */
+ {
+ while (itzam_true)
+ {
+ /* read next page */
+ next_page = read_page(cursor->m_btree,cursor->m_page->m_links[cursor->m_index]);
+
+ /* remember position in parent page */
+ temp_memory = (itzam_btree_cursor_memory *)malloc(sizeof(itzam_btree_cursor_memory));
+ temp_memory->m_prev = cursor->m_parent_memory;
+ temp_memory->m_index = cursor->m_index;
+ cursor->m_parent_memory = temp_memory;
+
+ /* start at beginning of new page */
+ cursor->m_index = 0;
+
+ /* make new page our current page */
+ if (cursor->m_page->m_header->m_parent != ITZAM_NULL_REF)
+ free_page(cursor->m_page);
+
+ cursor->m_page = next_page;
+
+ /* do we need to push and move up again? */
+ if ((cursor->m_index == 0) && (cursor->m_page->m_header->m_parent != ITZAM_NULL_REF) && (cursor->m_page->m_links[0] != ITZAM_NULL_REF))
+ continue;
+ else
+ break;
+ }
+
+ result = itzam_true;
+ }
+ }
+
+ return result;
+}
+
+itzam_bool itzam_btree_cursor_reset(itzam_btree_cursor * cursor)
+{
+ return reset_cursor(cursor);
+}
+
+itzam_state itzam_btree_cursor_read(itzam_btree_cursor * cursor, void * returned_key)
+{
+ itzam_state result = ITZAM_NOT_FOUND;
+
+ if ((cursor != NULL) && (returned_key != NULL) && (cursor->m_page != NULL))
+ {
+ memcpy(returned_key, cursor->m_page->m_keys + cursor->m_index * cursor->m_btree->m_header->m_sizeof_key, cursor->m_btree->m_header->m_sizeof_key);
+ result = ITZAM_OKAY;
+ }
+
+ return result;
+}
diff --git a/src/itzam_data.c b/src/itzam_data.c new file mode 100644 index 0000000..b4b31d8 --- /dev/null +++ b/src/itzam_data.c @@ -0,0 +1,1573 @@ +/*
+ Itzam/C (version 6.0) is an embedded database engine written in Standard C.
+
+ Copyright 2011 Scott Robert Ladd. All rights reserved.
+
+ Older versions of Itzam/C are:
+ Copyright 2002, 2004, 2006, 2008 Scott Robert Ladd. All rights reserved.
+
+ Ancestral code, from Java and C++ books by the author, is:
+ Copyright 1992, 1994, 1996, 2001 Scott Robert Ladd. All rights reserved.
+
+ Itzam/C is user-supported open source software. It's continued development is dependent on
+ financial support from the community. You can provide funding by visiting the Itzam/C
+ website at:
+
+ http://www.coyotegulch.com
+
+ You may license Itzam/C in one of two fashions:
+
+ 1) Simplified BSD License (FreeBSD License)
+
+ 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 SCOTT ROBERT LADD ``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 SCOTT ROBERT LADD 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.
+
+ The views and conclusions contained in the software and documentation are those of the
+ authors and should not be interpreted as representing official policies, either expressed
+ or implied, of Scott Robert Ladd.
+
+ 2) Closed-Source Proprietary License
+
+ If your project is a closed-source or proprietary project, the Simplified BSD License may
+ not be appropriate or desirable. In such cases, contact the Itzam copyright holder to
+ arrange your purchase of an appropriate license.
+
+ The author can be contacted at:
+
+ scott.ladd@coyotegulch.com
+ scott.ladd@gmail.com
+ http:www.coyotegulch.com
+*/
+
+#include "itzam.h"
+
+#include <stdlib.h>
+#include <errno.h>
+#include <ctype.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+static pthread_mutex_t global_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+/*-----------------------------------------------------------------------------
+ * deleted record list management
+ */
+static itzam_state read_dellist(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if (datafile->m_shared->m_header.m_dellist_ref != ITZAM_NULL_REF)
+ {
+ if (-1 != itzam_file_seek(datafile->m_file,datafile->m_shared->m_header.m_dellist_ref + sizeof(itzam_record_header),ITZAM_SEEK_BEGIN))
+ {
+ /* read the header
+ */
+ if (itzam_file_read(datafile->m_file,&datafile->m_dellist_header,sizeof(itzam_dellist_header)))
+ {
+ itzam_int size = sizeof(itzam_dellist_entry) * datafile->m_dellist_header.m_table_size;
+
+ if (datafile->m_dellist != NULL)
+ free(datafile->m_dellist);
+
+ datafile->m_dellist = (itzam_dellist_entry *)malloc(size);
+
+ if (datafile->m_dellist != NULL)
+ {
+ if (itzam_file_read(datafile->m_file,datafile->m_dellist,size))
+ result = ITZAM_OKAY;
+ }
+ else
+ datafile->m_error_handler("read_dellist",ITZAM_ERROR_MALLOC);
+ }
+ }
+
+ if (result != ITZAM_OKAY)
+ datafile->m_error_handler("read_dellist",ITZAM_ERROR_DELLIST_NOT_READ);
+ }
+ else
+ datafile->m_dellist = NULL;
+
+ return result;
+}
+
+static itzam_state write_dellist(itzam_datafile * datafile, itzam_bool has_grown)
+{
+ itzam_int size = sizeof(itzam_dellist_entry) * datafile->m_dellist_header.m_table_size;
+ itzam_state result = ITZAM_FAILED;
+ itzam_record_header header;
+
+ if (has_grown)
+ {
+ /* remove old record if there was one
+ */
+ if (datafile->m_shared->m_header.m_dellist_ref != ITZAM_NULL_REF)
+ {
+ if (-1 != itzam_file_seek(datafile->m_file,datafile->m_shared->m_header.m_dellist_ref,ITZAM_SEEK_BEGIN))
+ {
+ /* read the header
+ */
+ if (itzam_file_read(datafile->m_file,&header,sizeof(header)))
+ {
+ /* change record header; make this record the head of the deleted list
+ */
+ header.m_flags &= ~ITZAM_RECORD_IN_USE;
+ header.m_flags &= ~ITZAM_RECORD_DELLIST;
+
+ /* move to beginning of record header again and rewrite it
+ */
+ itzam_file_seek(datafile->m_file,datafile->m_shared->m_header.m_dellist_ref,ITZAM_SEEK_BEGIN);
+
+ if (itzam_file_write(datafile->m_file,&header,sizeof(header)))
+ result = ITZAM_OKAY;
+ }
+ }
+ }
+
+ /* explicitly append; we can't use write because it might try to change the
+ * deleted list while we're saving it
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,0,ITZAM_SEEK_END))
+ {
+ datafile->m_shared->m_header.m_dellist_ref = itzam_file_tell(datafile->m_file);
+
+ if (datafile->m_shared->m_header.m_dellist_ref > 0)
+ {
+ /* write new record header
+ */
+ itzam_record_header rec_head;
+
+ rec_head.m_signature = ITZAM_RECORD_SIGNATURE;
+ rec_head.m_flags = ITZAM_RECORD_IN_USE | ITZAM_RECORD_DELLIST;
+ rec_head.m_length = sizeof(itzam_dellist_header) + size;
+ rec_head.m_rec_len = rec_head.m_length;
+
+ if (itzam_file_write(datafile->m_file,&rec_head,sizeof(itzam_record_header)))
+ {
+ /* write the list header
+ */
+ if (itzam_file_write(datafile->m_file,&datafile->m_dellist_header,sizeof(itzam_dellist_header)))
+ {
+ /* write the list
+ */
+ if (itzam_file_write(datafile->m_file,datafile->m_dellist,size))
+ {
+ /* update the header with the pointer to the new deleted record list
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,0,ITZAM_SEEK_BEGIN))
+ {
+ if (itzam_file_write(datafile->m_file,&datafile->m_shared->m_header,sizeof(itzam_datafile_header)))
+ result = ITZAM_OKAY;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ else
+ {
+ if (-1 != itzam_file_seek(datafile->m_file,datafile->m_shared->m_header.m_dellist_ref + sizeof(itzam_record_header),ITZAM_SEEK_BEGIN))
+ {
+ /* write the header
+ */
+ if (itzam_file_write(datafile->m_file,&datafile->m_dellist_header,sizeof(itzam_dellist_header)))
+ {
+ /* write the list
+ */
+ if (itzam_file_write(datafile->m_file,datafile->m_dellist,size))
+ result = ITZAM_OKAY;
+ }
+ }
+ }
+
+ if (result != ITZAM_OKAY)
+ datafile->m_error_handler("write_dellist",ITZAM_ERROR_DELLIST_NOT_WRITTEN);
+
+ return result;
+}
+
+/*-----------------------------------------------------------------------------
+ * utilities
+ */
+static char * get_tranfile_name(const char * filename)
+{
+ static const char * tran_name_mask = "%s.itzamtran";
+ char * result = (char *)malloc(strlen(tran_name_mask) + strlen(filename) + 1);
+ sprintf(result,tran_name_mask,filename);
+ return result;
+}
+
+itzam_bool itzam_datafile_exists(const char * filename)
+{
+ struct stat info;
+ return (0 == stat(filename, &info));
+}
+
+static char * get_shared_name(const char * mask, const char * filename)
+{
+ char * result = (char *)malloc(strlen(mask) + strlen(filename) + 1);
+
+ char * norm = strdup(filename);
+ char * c = norm;
+
+ while (*c)
+ {
+ if (!isalnum(*c))
+ *c = '_';
+ else
+ if (isalpha(*c))
+ *c = tolower(*c);
+
+ ++c;
+ }
+
+ sprintf(result, mask, norm);
+
+ free(norm);
+
+ return result;
+}
+
+#if defined(ITZAM_UNIX)
+static const char * shared_mask = "/%s_ItzamSharedDatafile";
+#else
+static const char * shared_mask = "Global\\%s_ItzamSharedDatafile";
+static const char * mutex_mask = "Global\\%s_ItzamMutex";
+#endif
+
+/*-----------------------------------------------------------------------------
+ * datafile functions
+ */
+itzam_state itzam_datafile_create(itzam_datafile * datafile, const char * filename)
+{
+ itzam_datafile_header header;
+#if defined(ITZAM_UNIX)
+ pthread_mutexattr_t attr;
+#else
+ char * mutex_name;
+#endif
+ itzam_state result = ITZAM_FAILED;
+ itzam_bool creator;
+
+ pthread_mutex_lock(&global_mutex);
+
+ /* verify arguments before proceeding
+ */
+ if (datafile != NULL)
+ {
+ /* fill header
+ */
+ header.m_signature = ITZAM_DATAFILE_SIGNATURE;
+ header.m_version = ITZAM_DATAFILE_VERSION;
+ header.m_dellist_ref = ITZAM_NULL_REF;
+ header.m_schema_ref = ITZAM_NULL_REF;
+ header.m_index_list_ref = ITZAM_NULL_REF;
+ header.m_transaction_tail = ITZAM_NULL_REF;
+
+ /* fill remaining datafile members
+ */
+#if defined(ITZAM_UNIX)
+ datafile->m_file = -1;
+ datafile->m_shmem = -1;
+#else
+ datafile->m_file = NULL;
+ datafile->m_shmem = NULL;
+#endif
+ datafile->m_filename = strdup(filename);
+ datafile->m_dellist = NULL;
+ datafile->m_tran_file = NULL;
+ datafile->m_tran_replacing = itzam_false;
+ datafile->m_shared = NULL;
+ datafile->m_is_open = itzam_false;
+ datafile->m_file_locked = itzam_false;
+ datafile->m_in_transaction = itzam_false;
+ datafile->m_error_handler = default_error_handler;
+
+#if defined(ITZAM_UNIX)
+ memset(&datafile->m_file_lock,0,sizeof(struct flock));
+#endif
+
+ /* generate transaction file name
+ */
+ datafile->m_tran_file_name = get_tranfile_name(filename);;
+
+ /* generate shared memory for header
+ */
+ datafile->m_shmem_name = get_shared_name(shared_mask, filename);
+
+ /* create OS-level file
+ */
+ datafile->m_file = itzam_file_create(filename);
+
+ if (ITZAM_GOOD_FILE(datafile->m_file))
+ {
+ /* write header
+ */
+ if (itzam_file_write(datafile->m_file,&header,sizeof(itzam_datafile_header)))
+ {
+ itzam_file_commit(datafile->m_file);
+
+ /* generate shared memory and fill it
+ */
+ datafile->m_shmem = itzam_shmem_obtain(datafile->m_shmem_name, sizeof(itzam_datafile_shared), &creator);
+ datafile->m_shared = (itzam_datafile_shared *)itzam_shmem_getptr(datafile->m_shmem, sizeof(itzam_datafile_shared));
+ datafile->m_shared->m_count = 1;
+
+ /* obtain mutex
+ */
+#if defined(ITZAM_UNIX)
+ pthread_mutexattr_init(&attr);
+ pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
+ pthread_mutex_init(&datafile->m_shared->m_mutex, &attr);
+#else
+ mutex_name = get_shared_name(mutex_mask,filename);
+
+ datafile->m_mutex = OpenMutex(MUTEX_ALL_ACCESS, FALSE, (LPCSTR)name);
+
+ if (datafile->m_mutex == NULL)
+ datafile->m_mutex = CreateMutex(NULL, FALSE, (LPCSTR)name);
+
+ free(mutex_name);
+#endif
+ datafile->m_read_only = itzam_false; /* can't be read only durign creation */
+ memcpy(&datafile->m_shared->m_header, &header, sizeof(itzam_datafile_header));
+
+ result = ITZAM_OKAY;
+ }
+ else
+ default_error_handler("itzam_datafile_create",ITZAM_ERROR_WRITE_FAILED);
+ }
+ else
+ default_error_handler("itzam_datafile_create",ITZAM_ERROR_FILE_CREATE);
+
+ datafile->m_is_open = (result == ITZAM_OKAY);
+ }
+ else
+ default_error_handler("itzam_datafile_create",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ pthread_mutex_unlock(&global_mutex);
+
+ return result;
+}
+
+itzam_state itzam_datafile_open(itzam_datafile * datafile,
+ const char * filename,
+ itzam_bool recover,
+ itzam_bool read_only)
+{
+ itzam_bool have_header = itzam_false;
+ itzam_bool creator = itzam_false;
+#if defined(ITZAM_UNIX)
+ pthread_mutexattr_t attr;
+#else
+ char * mutex_name;
+#endif
+ itzam_state result = ITZAM_FAILED;
+
+ pthread_mutex_lock(&global_mutex);
+
+ /* verify arguments before proceeding
+ */
+ if (datafile != NULL)
+ {
+ /* set default error handler
+ */
+ datafile->m_error_handler = default_error_handler;
+ datafile->m_tran_file = NULL;
+ datafile->m_tran_replacing = itzam_false;
+ datafile->m_file_locked = itzam_false;
+ datafile->m_is_open = itzam_false;
+ datafile->m_dellist = NULL;
+ datafile->m_in_transaction = itzam_false;
+
+#if defined(ITZAM_UNIX)
+ memset(&datafile->m_file_lock,0,sizeof(struct flock));
+#endif
+
+ /* assumes that datafile is a clean structure (i.e., it isn't open already)
+ */
+ datafile->m_file = itzam_file_open(filename);
+
+ if (ITZAM_GOOD_FILE(datafile->m_file))
+ {
+ datafile->m_is_open = itzam_true;
+
+ //itzam_datafile_file_lock(datafile);
+
+ /* get tranfile name
+ */
+ datafile->m_tran_file_name = get_tranfile_name(filename);;
+
+ /* get shared memory
+ */
+ datafile->m_shmem_name = get_shared_name(shared_mask, filename);
+ datafile->m_shmem = itzam_shmem_obtain(datafile->m_shmem_name, sizeof(itzam_datafile_shared), &creator);
+ datafile->m_shared = (itzam_datafile_shared *)itzam_shmem_getptr(datafile->m_shmem, sizeof(itzam_datafile_shared));
+
+#if defined(ITZAM_UNIX)
+ if (creator)
+ {
+ pthread_mutexattr_init(&attr);
+ pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
+ pthread_mutex_init(&datafile->m_shared->m_mutex, &attr);
+ }
+#else
+ mutex_name = get_shared_name(mutex_mask,filename);
+
+ datafile->m_mutex = OpenMutex(MUTEX_ALL_ACCESS, FALSE, (LPCSTR)name);
+
+ if (datafile->m_mutex == NULL)
+ datafile->m_mutex = CreateMutex(NULL, FALSE, (LPCSTR)name);
+
+ free(mutex_name);
+#endif
+
+ datafile->m_read_only = read_only;
+
+ if (creator)
+ datafile->m_shared->m_count = 1;
+ else
+ datafile->m_shared->m_count += 1;
+
+ /* read the header
+ */
+ if (creator) // (datafile->m_shared->m_header.m_signature != ITZAM_DATAFILE_SIGNATURE) && (creator))
+ have_header = itzam_file_read(datafile->m_file, &datafile->m_shared->m_header, sizeof(itzam_datafile_header));
+ else
+ have_header = itzam_true;
+
+ if (have_header)
+ {
+ /* verify signature and version
+ */
+ if (datafile->m_shared->m_header.m_signature == ITZAM_DATAFILE_SIGNATURE)
+ {
+ if (datafile->m_shared->m_header.m_version == ITZAM_DATAFILE_VERSION)
+ {
+ /* read deleted list, if any
+ */
+ if (datafile->m_shared->m_header.m_dellist_ref != ITZAM_NULL_REF)
+ result = read_dellist(datafile);
+ else
+ result = ITZAM_OKAY;
+
+ /* if we have a dangling transaction, roll it back
+ */
+ if (recover && (datafile->m_shared->m_header.m_transaction_tail != ITZAM_NULL_REF))
+ itzam_datafile_transaction_rollback(datafile);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_open",ITZAM_ERROR_VERSION);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_open",ITZAM_ERROR_SIGNATURE);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_open",ITZAM_ERROR_OPEN_FAILED);
+ }
+
+ /* can size_t hold the types of references used by this file?
+ */
+ if (result == ITZAM_OKAY)
+ {
+ size_t refbytes = (int)((datafile->m_shared->m_header.m_version & 0xFF000000) >> 24) / 8;
+
+ if (REF_BYTES != refbytes)
+ result = ITZAM_REF_SIZE_MISMATCH;
+ }
+
+ //itzam_datafile_file_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_open",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ pthread_mutex_unlock(&global_mutex);
+
+ return result;
+}
+
+itzam_state itzam_datafile_close(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+ itzam_bool last_owner = itzam_false;
+
+ pthread_mutex_lock(&global_mutex);
+
+ if (datafile != NULL)
+ {
+ itzam_datafile_mutex_lock(datafile);
+ datafile->m_shared->m_count -= 1;
+ itzam_datafile_mutex_unlock(datafile);
+
+ last_owner = (datafile->m_shared->m_count <= 0) ? itzam_true : itzam_false;
+
+ if (last_owner)
+ #if defined(ITZAM_UNIX)
+ pthread_mutex_destroy(&datafile->m_shared->m_mutex);
+ #else
+ CloseHandle(datafile->m_mutex);
+ #endif
+
+ if (datafile->m_dellist != NULL)
+ {
+ free(datafile->m_dellist);
+ datafile->m_dellist = NULL;
+ }
+
+ free(datafile->m_tran_file_name);
+
+ itzam_shmem_freeptr(datafile->m_shared, sizeof(itzam_datafile_shared));
+
+ if (last_owner)
+ itzam_shmem_close(datafile->m_shmem, datafile->m_shmem_name);
+
+ free(datafile->m_shmem_name);
+
+ if (itzam_file_close(datafile->m_file))
+ {
+ datafile->m_is_open = itzam_false;
+ result = ITZAM_OKAY;
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_close",ITZAM_ERROR_CLOSE_FAILED);
+ }
+ else
+ default_error_handler("itzam_datafile_close",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ pthread_mutex_unlock(&global_mutex);
+
+ return result;
+}
+
+void itzam_datafile_mutex_lock(itzam_datafile * datafile)
+{
+#if defined(ITZAM_UNIX)
+ pthread_mutex_lock(&datafile->m_shared->m_mutex);
+#else
+ WaitForSingleObject(datafile->m_mutex, INFINITE);
+#endif
+}
+
+void itzam_datafile_mutex_unlock(itzam_datafile * datafile)
+{
+#if defined(ITZAM_UNIX)
+ pthread_mutex_unlock(&datafile->m_shared->m_mutex);
+#else
+ ReleaseMutex(datafile->m_mutex);
+#endif
+}
+
+itzam_bool itzam_datafile_file_lock(itzam_datafile * datafile)
+{
+ itzam_bool result = itzam_false;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ if (datafile->m_file_locked)
+ result = itzam_true;
+ else
+ {
+#if defined(ITZAM_UNIX)
+ memset(&datafile->m_file_lock,0,sizeof(struct flock));
+ datafile->m_file_lock.l_type = F_WRLCK;
+ result = (itzam_bool)fcntl(datafile->m_file,F_SETLKW,&datafile->m_file_lock);
+#else
+ result = (itzam_bool)LockFile(datafile->m_file, 0, 0, 0xFFFFFFFF, 0xFFFFFFFF);
+#endif
+ }
+
+ datafile->m_file_locked = result;
+ }
+ else
+ {
+ default_error_handler("itzam_datafile_file_lock",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+
+ return result;
+}
+
+itzam_bool itzam_datafile_file_unlock(itzam_datafile * datafile)
+{
+ itzam_bool result = itzam_false;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ if (datafile->m_file_locked)
+ {
+#if defined(ITZAM_UNIX)
+ fsync(datafile->m_file);
+ datafile->m_file_lock.l_type = F_UNLCK;
+ result = (itzam_bool)fcntl(datafile->m_file,F_SETLKW,&datafile->m_file_lock);
+#else
+ result = (itzam_bool)UnlockFile(datafile->m_file, 0, 0, 0xFFFFFFFF, 0xFFFFFFFF);
+#endif
+ }
+ else
+ result = itzam_true; /* file wasn't locked, so it *is* unlocked... */
+
+ if (result == itzam_true)
+ datafile->m_file_locked = itzam_false;
+ }
+ else
+ default_error_handler("itzam_datafile_file_unlock",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_bool itzam_datafile_is_open(itzam_datafile * datafile)
+{
+ itzam_bool result = itzam_false;
+
+ if (datafile != NULL)
+ {
+ itzam_datafile_mutex_lock(datafile);
+ result = datafile->m_is_open;
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_datafile_is_open",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+
+ return result;
+}
+
+float itzam_datafile_get_version(itzam_datafile * datafile)
+{
+ float result = 0.0F;
+
+ if (datafile != NULL)
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ result = (double)((datafile->m_shared->m_header.m_version & 0x00FF0000) >> 16)
+ + ((datafile->m_shared->m_header.m_version & 0x0000FF00) >> 8) / 100.0
+ + ((datafile->m_shared->m_header.m_version & 0x000000FF)) / 10000.0;
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_datafile_get_version",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+
+ return result;
+}
+
+void itzam_datafile_set_error_handler(itzam_datafile * datafile,
+ itzam_error_handler * error_handler)
+{
+ if (datafile != NULL)
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ if (error_handler == NULL)
+ datafile->m_error_handler = default_error_handler;
+ else
+ datafile->m_error_handler = error_handler;
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ {
+ default_error_handler("itzam_datafile_set_error_handler",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+}
+
+itzam_ref itzam_datafile_tell(itzam_datafile * datafile)
+{
+ itzam_ref where = -1;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ where = (itzam_ref)itzam_file_tell(datafile->m_file);
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_tell",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return where;
+}
+
+itzam_state itzam_datafile_seek(itzam_datafile * datafile, itzam_ref pos)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ /* seek to requested position
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,(long)pos,ITZAM_SEEK_BEGIN))
+ result = ITZAM_OKAY;
+ else
+ datafile->m_error_handler("itzam_datafile_seek",ITZAM_ERROR_SEEK_FAILED);
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_seek",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_state itzam_datafile_rewind(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ /* seek to byte after first deleted marker
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,(long)sizeof(itzam_datafile_header),ITZAM_SEEK_BEGIN))
+ result = ITZAM_OKAY;
+ else
+ datafile->m_error_handler("itzam_datafile_rewind",ITZAM_ERROR_SEEK_FAILED);
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_rewind",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+/* This function should NEVER be called by user code; it is an internal function used by indexes.
+ * It assumes that a returned deleted record will be used by the calling function.
+ */
+itzam_ref itzam_datafile_get_next_open(itzam_datafile * datafile, itzam_int length)
+{
+ itzam_int n;
+ itzam_ref where = ITZAM_NULL_REF;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ if (ITZAM_OKAY == read_dellist(datafile))
+ {
+ for (n = 0; n < datafile->m_dellist_header.m_table_size; ++n)
+ {
+ if (datafile->m_dellist[n].m_where != ITZAM_NULL_REF)
+ {
+ if (datafile->m_dellist[n].m_length == length)
+ {
+ /* save the location of the deleted record we're replacing
+ */
+ where = datafile->m_dellist[n].m_where;
+
+ /* remove this entry from the table
+ */
+ datafile->m_dellist[n].m_where = ITZAM_NULL_REF;
+ datafile->m_dellist[n].m_length = 0;
+ write_dellist(datafile,itzam_false);
+ break;
+ }
+ }
+ }
+ }
+
+ if (where == ITZAM_NULL_REF)
+ {
+ /* no deleted records, so append
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,0,ITZAM_SEEK_END))
+ {
+ where = itzam_file_tell(datafile->m_file);
+
+ if (where < 0)
+ where = ITZAM_NULL_REF;
+ }
+ else
+ where = ITZAM_NULL_REF;
+ }
+ }
+ else
+ default_error_handler("itzam_datafile_get_next_open",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return where;
+}
+
+/* internal function to add an operation to the transaction list
+ */
+static itzam_bool add_tran_op(itzam_datafile * datafile, itzam_int where, itzam_record_header * header, const void * data, itzam_op_type op_type)
+{
+ itzam_bool result = itzam_false;
+ itzam_op_header op_header;
+ itzam_int op_where;
+
+ if (datafile->m_in_transaction)
+ {
+ /* initialize operation header and copy data in
+ */
+ op_header.m_type = op_type;
+ op_header.m_where = where;
+ op_header.m_prev_tran = datafile->m_shared->m_header.m_transaction_tail;
+ memcpy(&op_header.m_record_header,header,sizeof(itzam_record_header));
+ op_header.m_record_header.m_flags |= ITZAM_RECORD_TRAN_RECORD;
+ op_header.m_record_where = ITZAM_NULL_REF;
+
+ /* turn off transactions for a moment
+ */
+ datafile->m_in_transaction = itzam_false;
+
+ /* write op data to the file
+ */
+ if (op_type != ITZAM_TRAN_OP_WRITE)
+ {
+ op_header.m_record_where = itzam_datafile_get_next_open(datafile->m_tran_file,op_header.m_record_header.m_length);
+ itzam_datafile_write_flags(datafile->m_tran_file,data,op_header.m_record_header.m_length,op_header.m_record_where,ITZAM_RECORD_TRAN_RECORD);
+ }
+
+ /* write op header
+ */
+ op_where = itzam_datafile_get_next_open(datafile->m_tran_file,sizeof(itzam_op_header));
+ itzam_datafile_write_flags(datafile->m_tran_file,&op_header,sizeof(op_header),op_where,ITZAM_RECORD_TRAN_HEADER);
+
+ /* turn transactions on again
+ */
+ datafile->m_in_transaction = itzam_true;
+
+ /* rewrite datafile header
+ */
+ datafile->m_shared->m_header.m_transaction_tail = op_where;
+
+ if (-1 != itzam_file_seek(datafile->m_file,0,ITZAM_SEEK_BEGIN))
+ {
+ if (itzam_file_write(datafile->m_file,&datafile->m_shared->m_header,sizeof(itzam_datafile_header)))
+ result = itzam_true;
+ }
+ }
+
+ return result;
+}
+
+itzam_ref itzam_datafile_write_flags(itzam_datafile * datafile, const void * data, itzam_int length, itzam_ref where, int32_t flags)
+{
+ itzam_record_header rec_header;
+
+ /* make sure the arguments make sense
+ */
+ if ((datafile != NULL) && (data != NULL) && (length > 0) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ if (datafile->m_read_only)
+ return ITZAM_NULL_REF;
+ else
+ {
+ /* if we aren't told where to put the record, find a place
+ */
+ if (where == ITZAM_NULL_REF)
+ where = itzam_datafile_get_next_open(datafile,length);
+ else
+ {
+ /* are we in a transaction?
+ */
+ if (datafile->m_in_transaction)
+ {
+ /* read the old record rec_header
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,where,ITZAM_SEEK_BEGIN))
+ {
+ if (itzam_file_read(datafile->m_file,&rec_header,sizeof(itzam_record_header)))
+ {
+ /* if the record is active, then we need to save it
+ */
+ if (rec_header.m_flags & ITZAM_RECORD_IN_USE)
+ {
+ /* create a temporary buffer
+ */
+ void * op_data = malloc(rec_header.m_rec_len);
+
+ /* read data
+ */
+ if (op_data != NULL)
+ {
+ /* now save record information
+ */
+ if (itzam_file_read(datafile->m_file,op_data,rec_header.m_length))
+ {
+ add_tran_op(datafile,where,&rec_header,op_data,ITZAM_TRAN_OP_REMOVE);
+ free(op_data);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_write_flags (1)",ITZAM_ERROR_READ_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_write_flags (2)",ITZAM_ERROR_MALLOC);
+ }
+ }
+ }
+ }
+ }
+
+ rec_header.m_signature = ITZAM_RECORD_SIGNATURE;
+ rec_header.m_flags = ITZAM_RECORD_IN_USE | flags;
+ rec_header.m_length = 0;
+ rec_header.m_rec_len = 0;
+
+ /* do we have a good place to write?
+ */
+ if (where != ITZAM_NULL_REF)
+ {
+ /* modify record rec_header
+ */
+ rec_header.m_rec_len = length;
+ rec_header.m_length = length;
+
+ /* ITZAM_SEEK to beginning of new record
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,where,ITZAM_SEEK_BEGIN))
+ {
+ /* write the record rec_header
+ */
+ if (itzam_file_write(datafile->m_file,&rec_header,sizeof(rec_header)))
+ {
+ /* write the record
+ */
+ if (!itzam_file_write(datafile->m_file,data,length))
+ {
+ datafile->m_error_handler("itzam_datafile_write_flags (4)",ITZAM_ERROR_WRITE_FAILED);
+ where = ITZAM_NULL_REF;
+ }
+ }
+ else
+ {
+ datafile->m_error_handler("itzam_datafile_write_flags (5)", ITZAM_ERROR_WRITE_FAILED);
+ where = ITZAM_NULL_REF;
+ }
+ }
+ else
+ {
+ datafile->m_error_handler("itzam_datafile_write_flags (6)",ITZAM_ERROR_SEEK_FAILED);
+ where = ITZAM_NULL_REF;
+ }
+
+ if ((where != ITZAM_NULL_REF) && (datafile->m_in_transaction))
+ add_tran_op(datafile,where,&rec_header,data,ITZAM_TRAN_OP_WRITE);
+ }
+ }
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_write_flags (7)",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return where;
+}
+
+itzam_ref itzam_datafile_write(itzam_datafile * datafile, const void * data, itzam_int length, itzam_ref where)
+{
+ return itzam_datafile_write_flags(datafile, data, length, where, 0);
+}
+
+// dangerous! this function could overwrite critical file data structures
+itzam_state itzam_datafile_overwrite(itzam_datafile * datafile, const void * data, itzam_int length, itzam_ref where, itzam_int offset)
+{
+ itzam_state result = ITZAM_FAILED;
+ itzam_record_header rec_header;
+
+ if ((datafile != NULL) && (data != NULL) && (length > 0) && (datafile->m_is_open) && (where != ITZAM_NULL_REF))
+ {
+ if (datafile->m_read_only)
+ {
+ datafile->m_error_handler("itzam_datafile_write_flags", ITZAM_ERROR_READ_ONLY);
+ return ITZAM_FAILED;
+ }
+
+ itzam_datafile_mutex_lock(datafile);
+
+ /* read header file
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,where,ITZAM_SEEK_BEGIN))
+ {
+ if (!itzam_file_read(datafile->m_file,&rec_header,sizeof(itzam_record_header)))
+ datafile->m_error_handler("itzam_datafile_explicit_write (1)",ITZAM_ERROR_READ_FAILED);
+
+ if ((0 == (rec_header.m_flags & ITZAM_RECORD_IN_USE)) || (rec_header.m_signature != ITZAM_RECORD_SIGNATURE))
+ datafile->m_error_handler("itzam_datafile_explicit_write (2)",ITZAM_ERROR_INVALID_RECORD);
+ }
+
+ /* make sure we fit inside the record
+ */
+ if (rec_header.m_length < (length + offset))
+ return ITZAM_OVERWRITE_TOO_LONG;
+
+ /* are we in a transaction? if so, save the rec we're changing
+ */
+ if (datafile->m_in_transaction)
+ {
+ /* create a temporary buffer
+ */
+ void * op_data = malloc(rec_header.m_rec_len);
+
+ /* read data
+ */
+ if (op_data != NULL)
+ {
+ /* now save record information
+ */
+ if (itzam_file_read(datafile->m_file,op_data,rec_header.m_length))
+ {
+ add_tran_op(datafile, where, &rec_header, op_data, ITZAM_TRAN_OP_OVERWRITE);
+ free(op_data);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_explicit_write (2)",ITZAM_ERROR_READ_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_explicit_write (3)",ITZAM_ERROR_MALLOC);
+ }
+
+ /* modify record at given offset
+ */
+ if (-1 != itzam_file_seek(datafile->m_file, where + sizeof(itzam_record_header) + offset, ITZAM_SEEK_BEGIN))
+ {
+ if (!itzam_file_write(datafile->m_file,data,length))
+ {
+ datafile->m_error_handler("itzam_datafile_explicit_write (4)",ITZAM_ERROR_WRITE_FAILED);
+ where = ITZAM_NULL_REF;
+ }
+ }
+ else
+ {
+ datafile->m_error_handler("itzam_datafile_explicit_write (5)",ITZAM_ERROR_SEEK_FAILED);
+ where = ITZAM_NULL_REF;
+ }
+
+ itzam_datafile_mutex_unlock(datafile);
+
+ result = ITZAM_OKAY;
+ }
+ else
+ default_error_handler("itzam_datafile_write_flags (5)",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_state itzam_datafile_read(itzam_datafile * datafile, void * record, itzam_int max_length)
+{
+ itzam_state result = ITZAM_FAILED;
+ itzam_record_header header = { 0, 0, 0, 0 };
+ itzam_bool error = itzam_false;
+
+ if ((datafile != NULL) && (record != NULL) && (max_length > 0) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ while (!error)
+ {
+ /* read the record header
+ */
+ if (itzam_file_read(datafile->m_file,&header,sizeof(itzam_record_header)))
+ {
+ /* if the record is active, we can read it
+ */
+ if ((header.m_flags & ITZAM_RECORD_IN_USE) && !(header.m_flags & ITZAM_RECORD_DELLIST))
+ break;
+
+ /* if the record signature is invalid, we have an error
+ */
+ if (header.m_signature != ITZAM_RECORD_SIGNATURE)
+ {
+ datafile->m_error_handler("itzam_datafile_read",ITZAM_ERROR_INVALID_RECORD);
+ error = itzam_true;
+ }
+
+ /* move to the next record
+ */
+ if (-1 == itzam_file_seek(datafile->m_file,header.m_length,ITZAM_SEEK_CURRENT))
+ {
+ datafile->m_error_handler("itzam_datafile_read",ITZAM_ERROR_SEEK_FAILED);
+ error = itzam_true;
+ }
+ }
+ else
+ {
+ datafile->m_error_handler("itzam_datafile_read",ITZAM_ERROR_READ_FAILED);
+ error = itzam_true;
+ }
+ }
+
+ /* only read actual data if no errors
+ */
+ if (!error)
+ {
+ itzam_int read_len = (max_length < header.m_rec_len) ? max_length : header.m_rec_len;
+
+ if (itzam_file_read(datafile->m_file, record, read_len))
+ {
+ /* skip any "padding" between record size and record buffer length
+ */
+ if (read_len < header.m_length)
+ {
+ if (-1 == itzam_file_seek(datafile->m_file,header.m_length - read_len,ITZAM_SEEK_CURRENT))
+ {
+ datafile->m_error_handler("itzam_datafile_read",ITZAM_ERROR_SEEK_FAILED);
+ error = itzam_true;
+ }
+ }
+
+ result = ITZAM_OKAY;
+ }
+ else
+ {
+ datafile->m_error_handler("itzam_datafile_read",ITZAM_ERROR_READ_FAILED);
+ error = itzam_true;
+ }
+ }
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_read",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_state itzam_datafile_read_alloc(itzam_datafile * datafile, void ** data, itzam_int * length)
+{
+ itzam_state result = ITZAM_FAILED;
+ itzam_record_header header;
+
+ if ((datafile != NULL) && (data != NULL) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ if (itzam_file_read(datafile->m_file,&header,sizeof(header)))
+ {
+ /* if the record is active, we can read it
+ */
+ if (header.m_flags & ITZAM_RECORD_IN_USE)
+ {
+ /* create a temporary buffer
+ */
+ if (length != NULL)
+ *length = header.m_rec_len;
+
+ *data = malloc(header.m_rec_len);
+
+ /* read data
+ */
+ if (*data != NULL)
+ {
+ if (itzam_file_read(datafile->m_file,*data,header.m_length))
+ {
+ /* skip any "padding" between record size and record buffer length
+ */
+ if (header.m_rec_len < header.m_length)
+ itzam_file_seek(datafile->m_file,header.m_length - header.m_rec_len,ITZAM_SEEK_CURRENT);
+
+ result = ITZAM_OKAY;
+ }
+ else
+ datafile->m_error_handler("1) itzam_datafile_read_alloc",ITZAM_ERROR_READ_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_read_alloc",ITZAM_ERROR_MALLOC);
+ }
+ else
+ datafile->m_error_handler("2) itzam_datafile_read_alloc",ITZAM_ERROR_READ_FAILED);
+ }
+ else
+ datafile->m_error_handler("3) itzam_datafile_read_alloc",ITZAM_ERROR_READ_FAILED);
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_read_alloc",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_state itzam_datafile_remove(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+ int n;
+ itzam_ref where;
+
+ if ((datafile != NULL) && (datafile->m_is_open))
+ {
+ itzam_datafile_mutex_lock(datafile);
+
+ if (datafile->m_read_only)
+ result = ITZAM_READ_ONLY;
+ else
+ {
+ /* get our position
+ */
+ where = itzam_file_tell(datafile->m_file);
+
+ /* make sure we're not in the file header
+ */
+ if (where >= sizeof(itzam_ref))
+ {
+ itzam_record_header header;
+
+ /* read the header
+ */
+ if (itzam_file_read(datafile->m_file,&header,sizeof(header)))
+ {
+ /* only delete if it isn't already deleted
+ */
+ if (header.m_flags & ITZAM_RECORD_IN_USE)
+ {
+ /* save this record if we're in a transaction
+ */
+ if (datafile->m_in_transaction)
+ {
+ /**
+ * create a temporary buffer
+ */
+ void * op_data = malloc(header.m_rec_len);
+
+ /* read data
+ */
+ if (op_data != NULL)
+ {
+ /* now save record information
+ */
+ if (itzam_file_read(datafile->m_file,op_data,header.m_length))
+ {
+ add_tran_op(datafile,where,&header,op_data,ITZAM_TRAN_OP_REMOVE);
+ free(op_data);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_READ_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_MALLOC);
+ }
+
+ /* change record header; make this record the head of the deleted list
+ */
+ header.m_flags &= ~ITZAM_RECORD_IN_USE;
+
+ /* move to beginning of record header
+ */
+ if (-1 != itzam_file_seek(datafile->m_file,where,ITZAM_SEEK_BEGIN))
+ {
+ /* write revised record header
+ */
+ if (itzam_file_write(datafile->m_file,&header,sizeof(header)))
+ {
+ /* update deleted list
+ */
+ if (ITZAM_FAILED == read_dellist(datafile))
+ {
+ datafile->m_dellist_header.m_table_size = ITZAM_DELLIST_BLOCK_SIZE;
+ datafile->m_dellist = (itzam_dellist_entry *)malloc(sizeof(itzam_dellist_entry) * datafile->m_dellist_header.m_table_size);
+
+ if (datafile->m_dellist != NULL)
+ {
+ datafile->m_dellist[0].m_where = where;
+ datafile->m_dellist[0].m_length = header.m_length;
+
+ for (n = 1; n < datafile->m_dellist_header.m_table_size; ++n)
+ {
+ datafile->m_dellist[n].m_where = ITZAM_NULL_REF;
+ datafile->m_dellist[n].m_length = 0;
+ }
+
+ result = write_dellist(datafile,itzam_true);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_MALLOC);
+ }
+ else
+ {
+ for (n = 0; n < datafile->m_dellist_header.m_table_size; ++n)
+ {
+ if (datafile->m_dellist[n].m_where == ITZAM_NULL_REF)
+ {
+ datafile->m_dellist[n].m_where = where;
+ datafile->m_dellist[n].m_length = header.m_length;
+ result = write_dellist(datafile,itzam_false);
+ break;
+ }
+ }
+
+ /* if the entry didn't fit, we have to expand it
+ */
+ if (n == datafile->m_dellist_header.m_table_size)
+ {
+ /* create new table
+ */
+ itzam_int newsize = datafile->m_dellist_header.m_table_size + ITZAM_DELLIST_BLOCK_SIZE;
+ itzam_dellist_entry * newlist = (itzam_dellist_entry *)malloc(sizeof(itzam_dellist_entry) * newsize);
+
+ if (newlist != NULL)
+ {
+ /* copy old entries; could (?should) use memcpy here I suppose
+ */
+ for (n = 0; n < datafile->m_dellist_header.m_table_size; ++n)
+ {
+ newlist[n].m_where = datafile->m_dellist[n].m_where;
+ newlist[n].m_length = datafile->m_dellist[n].m_length;
+ }
+
+ /* add the newly-deleted record
+ */
+ newlist[n].m_where = where;
+ newlist[n].m_length = header.m_length;
+
+ /* add the old deleted list record
+ */
+ newlist[n+1].m_where = datafile->m_shared->m_header.m_dellist_ref;
+ newlist[n+1].m_length = datafile->m_dellist_header.m_table_size;
+
+ /* initialize remaining unused new entries
+ */
+ for (n += 2 ; n < newsize; ++n)
+ {
+ newlist[n].m_where = ITZAM_NULL_REF;
+ newlist[n].m_length = 0;
+ }
+
+ /* free space used by old list
+ */
+ free(datafile->m_dellist);
+
+ /* exchange new list for old
+ */
+ datafile->m_dellist = newlist;
+ datafile->m_dellist_header.m_table_size = newsize;
+
+ /* write it
+ */
+ result = write_dellist(datafile,itzam_true);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_read_alloc",ITZAM_ERROR_MALLOC);
+ }
+ }
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_WRITE_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_SEEK_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_DUPE_REMOVE);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_READ_FAILED);
+ }
+ else
+ datafile->m_error_handler("itzam_datafile_remove",ITZAM_ERROR_TELL_FAILED);
+ }
+
+ itzam_datafile_mutex_unlock(datafile);
+ }
+ else
+ default_error_handler("itzam_datafile_remove",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_state itzam_datafile_transaction_start(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ /* only start a transaction is one isn't already in progress
+ */
+ if ((datafile != NULL) && (datafile->m_is_open) && (!datafile->m_in_transaction))
+ {
+ if (datafile->m_read_only)
+ {
+ datafile->m_error_handler("itzam_datafile_transactions_start", ITZAM_ERROR_READ_ONLY);
+ return ITZAM_READ_ONLY;
+ }
+
+ itzam_datafile_mutex_lock(datafile);
+
+ datafile->m_tran_file = (itzam_datafile *)malloc(sizeof(itzam_datafile));
+
+ if (datafile->m_tran_file != NULL)
+ {
+ /* create a datafile to contain the transaction operations
+ */
+ result = itzam_datafile_create(datafile->m_tran_file,datafile->m_tran_file_name);
+
+ if (ITZAM_OKAY == result)
+ datafile->m_in_transaction = itzam_true;
+ else
+ default_error_handler("itzam_datafile_transaction_start",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+ }
+ }
+ else
+ default_error_handler("itzam_datafile_transaction_start",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+static void transaction_cleanup(itzam_datafile * datafile, itzam_bool rollback)
+{
+ itzam_op_header * op_header;
+ itzam_int dont_care;
+ void * op_record;
+ itzam_int data_len;
+ itzam_int n;
+ itzam_bool dummy;
+
+ if (rollback)
+ {
+ /* start at the beginning
+ */
+ itzam_ref op_where = datafile->m_shared->m_header.m_transaction_tail;
+
+ /* while we have something to process
+ */
+ while (op_where != ITZAM_NULL_REF)
+ {
+ /* read the operation header
+ */
+ itzam_datafile_seek(datafile->m_tran_file,op_where);
+
+ /* read the rolled-back record
+ */
+ itzam_datafile_read_alloc(datafile->m_tran_file,(void **)(void*)&op_header,&dont_care);
+
+ /* act upon the op_record....
+ */
+ switch (op_header->m_type)
+ {
+ /* remove a record that was written
+ */
+ case ITZAM_TRAN_OP_WRITE:
+ itzam_datafile_seek(datafile,op_header->m_where);
+ itzam_datafile_remove(datafile);
+ break;
+
+ /* replace a record that was removed
+ */
+ case ITZAM_TRAN_OP_REMOVE:
+ itzam_datafile_seek(datafile->m_tran_file,op_header->m_record_where);
+ itzam_datafile_read_alloc(datafile->m_tran_file,(void **)&op_record,&data_len);
+ itzam_datafile_write(datafile,op_record,op_header->m_record_header.m_length,op_header->m_where);
+ free(op_record);
+
+ if (ITZAM_OKAY == read_dellist(datafile))
+ {
+ for (n = 0; n < datafile->m_dellist_header.m_table_size; ++n)
+ {
+ if (datafile->m_dellist[n].m_where == op_header->m_where)
+ {
+ /* remove this entry from the table
+ */
+ datafile->m_dellist[n].m_where = ITZAM_NULL_REF;
+ datafile->m_dellist[n].m_length = 0;
+ break;
+ }
+ }
+ }
+
+ write_dellist(datafile,itzam_false);
+
+ break;
+
+ /* restore a record that was over-written
+ */
+ case ITZAM_TRAN_OP_OVERWRITE:
+ itzam_datafile_seek(datafile->m_tran_file,op_header->m_record_where);
+ itzam_datafile_read_alloc(datafile->m_tran_file,(void **)&op_record,&data_len);
+ itzam_datafile_write(datafile, op_record, op_header->m_record_header.m_length, op_header->m_where);
+ free(op_record);
+
+ break;
+ }
+
+ /* save next operation
+ */
+ op_where = op_header->m_prev_tran;
+
+ /* release memory
+ */
+ free(op_header);
+ }
+ }
+
+ /* update the header
+ */
+ datafile->m_shared->m_header.m_transaction_tail = ITZAM_NULL_REF;
+ itzam_file_seek(datafile->m_file,0,ITZAM_SEEK_BEGIN);
+ dummy = itzam_file_write(datafile->m_file,&datafile->m_shared->m_header,sizeof(itzam_datafile_header));
+
+ /* close and remove transaction file
+ */
+ itzam_datafile_close(datafile->m_tran_file);
+ itzam_file_remove(datafile->m_tran_file_name);
+ free(datafile->m_tran_file);
+ datafile->m_tran_file = NULL;
+
+ itzam_datafile_mutex_unlock(datafile);
+}
+
+itzam_state itzam_datafile_transaction_commit(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ /* only commit if a transaction is active
+ */
+ if ((datafile != NULL) && (datafile->m_is_open) && (datafile->m_in_transaction))
+ {
+ /* we're no longer in a transaction
+ */
+ datafile->m_in_transaction = itzam_false;
+
+ /* clean up transactioon data; it's no longer needed
+ */
+ transaction_cleanup(datafile,itzam_false);
+ result = ITZAM_OKAY;
+ }
+ else
+ default_error_handler("itzam_datafile_transaction_commit",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
+
+itzam_state itzam_datafile_transaction_rollback(itzam_datafile * datafile)
+{
+ itzam_state result = ITZAM_FAILED;
+
+ /* only rollback if a transaction is active
+ */
+ if ((datafile != NULL) && (datafile->m_is_open) && (datafile->m_in_transaction))
+ {
+ /* we're no longer in a transaction
+ */
+ datafile->m_in_transaction = itzam_false;
+
+ /* clean up transaction data; it's no longer needed
+ */
+ transaction_cleanup(datafile,itzam_true);
+ result = ITZAM_OKAY;
+ }
+ else
+ default_error_handler("itzam_datafile_transaction_rollback",ITZAM_ERROR_INVALID_DATAFILE_OBJECT);
+
+ return result;
+}
diff --git a/src/itzam_util.c b/src/itzam_util.c new file mode 100644 index 0000000..cdfbc66 --- /dev/null +++ b/src/itzam_util.c @@ -0,0 +1,308 @@ +/*
+ Itzam/C (version 6.0) is an embedded database engine written in Standard C.
+
+ Copyright 2011 Scott Robert Ladd. All rights reserved.
+
+ Older versions of Itzam/C are:
+ Copyright 2002, 2004, 2006, 2008 Scott Robert Ladd. All rights reserved.
+
+ Ancestral code, from Java and C++ books by the author, is:
+ Copyright 1992, 1994, 1996, 2001 Scott Robert Ladd. All rights reserved.
+
+ Itzam/C is user-supported open source software. It's continued development is dependent on
+ financial support from the community. You can provide funding by visiting the Itzam/C
+ website at:
+
+ http://www.coyotegulch.com
+
+ You may license Itzam/C in one of two fashions:
+
+ 1) Simplified BSD License (FreeBSD License)
+
+ 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 SCOTT ROBERT LADD ``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 SCOTT ROBERT LADD 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.
+
+ The views and conclusions contained in the software and documentation are those of the
+ authors and should not be interpreted as representing official policies, either expressed
+ or implied, of Scott Robert Ladd.
+
+ 2) Closed-Source Proprietary License
+
+ If your project is a closed-source or proprietary project, the Simplified BSD License may
+ not be appropriate or desirable. In such cases, contact the Itzam copyright holder to
+ arrange your purchase of an appropriate license.
+
+ The author can be contacted at:
+
+ scott.ladd@coyotegulch.com
+ scott.ladd@gmail.com
+ http:www.coyotegulch.com
+*/
+
+#include "itzam.h"
+
+#include <stdlib.h>
+#include <errno.h>
+#include <ctype.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#if defined(ITZAM_UNIX)
+#include <sys/mman.h>
+#endif
+
+/*-----------------------------------------------------------------------------
+ * default error handler, for errors outside the scope of valid datafile objects
+ */
+void default_default_error_handler(const char * function_name, itzam_error error)
+{
+ /* default error handler displays a simple message and exits program
+ */
+ fprintf(stderr,"Itzam internal error in %s: %d\n",function_name,error);
+ exit(1);
+}
+
+itzam_error_handler * default_error_handler = default_default_error_handler;
+
+void itzam_set_default_error_handler(itzam_error_handler * handler)
+{
+ if (handler != NULL)
+ default_error_handler = handler;
+}
+
+/*-----------------------------------------------------------------------------
+ * shared memory
+ */
+
+ITZAM_SHMEM_TYPE itzam_shmem_obtain(const char * name, size_t len, itzam_bool * creator)
+{
+#if defined(ITZAM_UNIX)
+ int result;
+
+ result = shm_open(name, O_CREAT | O_EXCL | O_RDWR, S_IRUSR | S_IWUSR);
+
+ if (result < 0)
+ {
+ if (errno == EEXIST)
+ {
+ *creator = itzam_false;
+
+ result = shm_open(name, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR);
+
+ if (result < 0)
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM);
+ }
+ }
+ else
+ {
+ *creator = itzam_true;
+
+ if (ftruncate(result, len))
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM);
+ }
+
+ return result;
+#else
+ HANDLE result;
+
+ result = OpenFileMapping(FILE_MAP_ALL_ACCESS, FALSE, (LPCSTR)name);
+
+ if ((result == NULL) && (len > 0))
+ {
+ *created = itzam_true;
+ result = CreateFileMapping(INVALID_HANDLE_VALUE, NULL, PAGE_READWRITE, 0, (DWORD)len, (LPCTSTR)name);
+ }
+ else
+ *created = itzam_false;
+
+ if (result == NULL)
+ {
+ if (ERROR_ACCESS_DENIED == GetLastError())
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM_PRIVILEGE);
+ else
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM);
+ }
+
+ return result;
+#endif
+}
+
+void itzam_shmem_close(ITZAM_SHMEM_TYPE shmem, const char * name)
+{
+#if defined(ITZAM_UNIX)
+ close(shmem);
+ shm_unlink(name);
+#else
+ if (shmem != NULL)
+ CloseHandle(shmem);
+#endif
+}
+
+void * itzam_shmem_getptr(ITZAM_SHMEM_TYPE shmem, size_t len)
+{
+#if defined(ITZAM_UNIX)
+ void * result = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_SHARED, shmem, 0);
+
+ if (result == MAP_FAILED)
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM);
+
+ return result;
+#else
+ void * result = NULL;
+
+ result = (void *)MapViewOfFile(shmem, FILE_MAP_ALL_ACCESS, 0, 0, len);
+
+ if (result == NULL)
+ {
+ if (ERROR_ACCESS_DENIED == GetLastError())
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM_PRIVILEGE);
+ else
+ default_error_handler("itzam_shmem_obtain",ITZAM_ERROR_SHMEM);
+ }
+
+ return result;
+#endif
+}
+
+itzam_bool itzam_shmem_freeptr(void * shmem_ptr, size_t len)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_bool)(0 == munmap(shmem_ptr,len));
+#else
+ return (itzam_bool)UnmapViewOfFile(shmem_ptr);
+#endif
+}
+
+/*-----------------------------------------------------------------------------
+ * file I/O functions
+ */
+
+ITZAM_FILE_TYPE itzam_file_create(const char * filename)
+{
+#if defined(ITZAM_UNIX)
+ return open(filename, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH );
+#else
+ HANDLE result = NULL;
+
+ do
+ {
+ result = CreateFile((LPCSTR)filename,
+ GENERIC_READ | GENERIC_WRITE,
+ FILE_SHARE_READ | FILE_SHARE_WRITE,
+ NULL,
+ CREATE_ALWAYS,
+ FILE_FLAG_RANDOM_ACCESS, // | FILE_FLAG_WRITE_THROUGH,
+ NULL);
+
+ if ((result != NULL) && (result != INVALID_HANDLE_VALUE))
+ break;
+
+ if ((result == INVALID_HANDLE_VALUE) && (GetLastError() == ERROR_ACCESS_DENIED))
+ Sleep(250);
+ else
+ break;
+ }
+ while (1);
+
+ return result;
+
+#endif
+}
+
+ITZAM_FILE_TYPE itzam_file_open(const char * filename)
+{
+#if defined(ITZAM_UNIX)
+ return open(filename, O_RDWR);
+#else
+ return CreateFile((LPCSTR)filename,
+ GENERIC_READ | GENERIC_WRITE,
+ FILE_SHARE_READ | FILE_SHARE_WRITE,
+ NULL,
+ OPEN_EXISTING,
+ FILE_FLAG_RANDOM_ACCESS, // | FILE_FLAG_WRITE_THROUGH,
+ NULL);
+
+#endif
+}
+
+itzam_bool itzam_file_close(ITZAM_FILE_TYPE file)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_bool)(0 == close(file));
+#else
+ return (itzam_bool)CloseHandle(file);
+#endif
+}
+
+itzam_bool itzam_file_read(ITZAM_FILE_TYPE file, void * data, size_t len)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_bool)(len == read(file,data,len));
+#else
+ DWORD count;
+ return (itzam_bool)ReadFile(file, (LPVOID)data, (DWORD)len, &count, NULL);
+#endif
+}
+
+itzam_bool itzam_file_write(ITZAM_FILE_TYPE file, const void * data, size_t len)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_bool)(len == write(file,data,len));
+#else
+ DWORD count;
+ return (itzam_bool)WriteFile(file,(LPVOID)data, (DWORD)len, &count, NULL);
+#endif
+}
+
+itzam_ref itzam_file_seek(ITZAM_FILE_TYPE file, itzam_ref pos, int mode)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_ref)lseek(file,pos,mode);
+#else
+ return (itzam_ref)SetFilePointer(file, (LONG)pos, NULL, mode);
+#endif
+}
+
+itzam_ref itzam_file_tell(ITZAM_FILE_TYPE file)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_ref)lseek(file,0,SEEK_CUR);
+#else
+ return (itzam_ref)SetFilePointer(file, 0, NULL, FILE_CURRENT);
+#endif
+}
+
+itzam_bool itzam_file_commit(ITZAM_FILE_TYPE file)
+{
+#if defined(ITZAM_UNIX)
+ return true; // (itzam_bool)commit(file);
+#else
+ return (itzam_bool)FlushFileBuffers(file);
+#endif
+}
+
+itzam_bool itzam_file_remove(const char * filename)
+{
+#if defined(ITZAM_UNIX)
+ return (itzam_bool)remove(filename);
+#else
+ return (itzam_bool)DeleteFile((LPCSTR)filename);
+#endif
+}
|