diff options
Diffstat (limited to 'src/plugins/fts-squat')
| -rw-r--r-- | src/plugins/fts-squat/Makefile.am | 47 | ||||
| -rw-r--r-- | src/plugins/fts-squat/Makefile.in | 883 | ||||
| -rw-r--r-- | src/plugins/fts-squat/fts-backend-squat.c | 497 | ||||
| -rw-r--r-- | src/plugins/fts-squat/fts-squat-plugin.c | 18 | ||||
| -rw-r--r-- | src/plugins/fts-squat/fts-squat-plugin.h | 14 | ||||
| -rw-r--r-- | src/plugins/fts-squat/squat-test.c | 197 | ||||
| -rw-r--r-- | src/plugins/fts-squat/squat-trie-private.h | 192 | ||||
| -rw-r--r-- | src/plugins/fts-squat/squat-trie.c | 2096 | ||||
| -rw-r--r-- | src/plugins/fts-squat/squat-trie.h | 54 | ||||
| -rw-r--r-- | src/plugins/fts-squat/squat-uidlist.c | 1624 | ||||
| -rw-r--r-- | src/plugins/fts-squat/squat-uidlist.h | 71 |
11 files changed, 5693 insertions, 0 deletions
diff --git a/src/plugins/fts-squat/Makefile.am b/src/plugins/fts-squat/Makefile.am new file mode 100644 index 0000000..6c8181c --- /dev/null +++ b/src/plugins/fts-squat/Makefile.am @@ -0,0 +1,47 @@ +AM_CPPFLAGS = \ + -I$(top_srcdir)/src/lib \ + -I$(top_srcdir)/src/lib-mail \ + -I$(top_srcdir)/src/lib-index \ + -I$(top_srcdir)/src/lib-storage \ + -I$(top_srcdir)/src/plugins/fts + +NOPLUGIN_LDFLAGS = +lib21_fts_squat_plugin_la_LDFLAGS = -module -avoid-version + +module_LTLIBRARIES = \ + lib21_fts_squat_plugin.la + +if DOVECOT_PLUGIN_DEPS +lib21_fts_squat_plugin_la_LIBADD = \ + ../fts/lib20_fts_plugin.la +endif + +lib21_fts_squat_plugin_la_SOURCES = \ + fts-squat-plugin.c \ + fts-backend-squat.c \ + squat-trie.c \ + squat-uidlist.c + +noinst_HEADERS = \ + fts-squat-plugin.h \ + squat-trie.h \ + squat-trie-private.h \ + squat-uidlist.h + +noinst_PROGRAMS = squat-test + +squat_test_SOURCES = \ + squat-test.c + +common_objects = \ + squat-trie.lo \ + squat-uidlist.lo + +squat_test_LDADD = \ + $(common_objects) \ + $(LIBDOVECOT_STORAGE) \ + $(LIBDOVECOT) +squat_test_DEPENDENCIES = \ + $(common_objects) \ + $(LIBDOVECOT_STORAGE_DEPS) \ + $(LIBDOVECOT_DEPS) diff --git a/src/plugins/fts-squat/Makefile.in b/src/plugins/fts-squat/Makefile.in new file mode 100644 index 0000000..443a7d0 --- /dev/null +++ b/src/plugins/fts-squat/Makefile.in @@ -0,0 +1,883 @@ +# Makefile.in generated by automake 1.16.1 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994-2018 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@ +am__is_gnu_make = { \ + if test -z '$(MAKELEVEL)'; then \ + false; \ + elif test -n '$(MAKE_HOST)'; then \ + true; \ + elif test -n '$(MAKE_VERSION)' && test -n '$(CURDIR)'; then \ + true; \ + else \ + false; \ + fi; \ +} +am__make_running_with_option = \ + case $${target_option-} in \ + ?) ;; \ + *) echo "am__make_running_with_option: internal error: invalid" \ + "target option '$${target_option-}' specified" >&2; \ + exit 1;; \ + esac; \ + has_opt=no; \ + sane_makeflags=$$MAKEFLAGS; \ + if $(am__is_gnu_make); then \ + sane_makeflags=$$MFLAGS; \ + else \ + case $$MAKEFLAGS in \ + *\\[\ \ ]*) \ + bs=\\; \ + sane_makeflags=`printf '%s\n' "$$MAKEFLAGS" \ + | sed "s/$$bs$$bs[$$bs $$bs ]*//g"`;; \ + esac; \ + fi; \ + skip_next=no; \ + strip_trailopt () \ + { \ + flg=`printf '%s\n' "$$flg" | sed "s/$$1.*$$//"`; \ + }; \ + for flg in $$sane_makeflags; do \ + test $$skip_next = yes && { skip_next=no; continue; }; \ + case $$flg in \ + *=*|--*) continue;; \ + -*I) strip_trailopt 'I'; skip_next=yes;; \ + -*I?*) strip_trailopt 'I';; \ + -*O) strip_trailopt 'O'; skip_next=yes;; \ + -*O?*) strip_trailopt 'O';; \ + -*l) strip_trailopt 'l'; skip_next=yes;; \ + -*l?*) strip_trailopt 'l';; \ + -[dEDm]) skip_next=yes;; \ + -[JT]) skip_next=yes;; \ + esac; \ + case $$flg in \ + *$$target_option*) has_opt=yes; break;; \ + esac; \ + done; \ + test $$has_opt = yes +am__make_dryrun = (target_option=n; $(am__make_running_with_option)) +am__make_keepgoing = (target_option=k; $(am__make_running_with_option)) +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@ +noinst_PROGRAMS = squat-test$(EXEEXT) +subdir = src/plugins/fts-squat +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/m4/ac_checktype2.m4 \ + $(top_srcdir)/m4/ac_typeof.m4 $(top_srcdir)/m4/arc4random.m4 \ + $(top_srcdir)/m4/blockdev.m4 $(top_srcdir)/m4/c99_vsnprintf.m4 \ + $(top_srcdir)/m4/clock_gettime.m4 $(top_srcdir)/m4/crypt.m4 \ + $(top_srcdir)/m4/crypt_xpg6.m4 $(top_srcdir)/m4/dbqlk.m4 \ + $(top_srcdir)/m4/dirent_dtype.m4 $(top_srcdir)/m4/dovecot.m4 \ + $(top_srcdir)/m4/fd_passing.m4 $(top_srcdir)/m4/fdatasync.m4 \ + $(top_srcdir)/m4/flexible_array_member.m4 \ + $(top_srcdir)/m4/glibc.m4 $(top_srcdir)/m4/gmtime_max.m4 \ + $(top_srcdir)/m4/gmtime_tm_gmtoff.m4 \ + $(top_srcdir)/m4/ioloop.m4 $(top_srcdir)/m4/iovec.m4 \ + $(top_srcdir)/m4/ipv6.m4 $(top_srcdir)/m4/libcap.m4 \ + $(top_srcdir)/m4/libtool.m4 $(top_srcdir)/m4/libwrap.m4 \ + $(top_srcdir)/m4/linux_mremap.m4 $(top_srcdir)/m4/ltoptions.m4 \ + $(top_srcdir)/m4/ltsugar.m4 $(top_srcdir)/m4/ltversion.m4 \ + $(top_srcdir)/m4/lt~obsolete.m4 $(top_srcdir)/m4/mmap_write.m4 \ + $(top_srcdir)/m4/mntctl.m4 $(top_srcdir)/m4/modules.m4 \ + $(top_srcdir)/m4/notify.m4 $(top_srcdir)/m4/nsl.m4 \ + $(top_srcdir)/m4/off_t_max.m4 $(top_srcdir)/m4/pkg.m4 \ + $(top_srcdir)/m4/pr_set_dumpable.m4 \ + $(top_srcdir)/m4/q_quotactl.m4 $(top_srcdir)/m4/quota.m4 \ + $(top_srcdir)/m4/random.m4 $(top_srcdir)/m4/rlimit.m4 \ + $(top_srcdir)/m4/sendfile.m4 $(top_srcdir)/m4/size_t_signed.m4 \ + $(top_srcdir)/m4/sockpeercred.m4 $(top_srcdir)/m4/sql.m4 \ + $(top_srcdir)/m4/ssl.m4 $(top_srcdir)/m4/st_tim.m4 \ + $(top_srcdir)/m4/static_array.m4 $(top_srcdir)/m4/test_with.m4 \ + $(top_srcdir)/m4/time_t.m4 $(top_srcdir)/m4/typeof.m4 \ + $(top_srcdir)/m4/typeof_dev_t.m4 \ + $(top_srcdir)/m4/uoff_t_max.m4 $(top_srcdir)/m4/vararg.m4 \ + $(top_srcdir)/m4/want_apparmor.m4 \ + $(top_srcdir)/m4/want_bsdauth.m4 \ + $(top_srcdir)/m4/want_bzlib.m4 \ + $(top_srcdir)/m4/want_cassandra.m4 \ + $(top_srcdir)/m4/want_cdb.m4 \ + $(top_srcdir)/m4/want_checkpassword.m4 \ + $(top_srcdir)/m4/want_clucene.m4 $(top_srcdir)/m4/want_db.m4 \ + $(top_srcdir)/m4/want_gssapi.m4 $(top_srcdir)/m4/want_icu.m4 \ + $(top_srcdir)/m4/want_ldap.m4 $(top_srcdir)/m4/want_lua.m4 \ + $(top_srcdir)/m4/want_lz4.m4 $(top_srcdir)/m4/want_lzma.m4 \ + $(top_srcdir)/m4/want_mysql.m4 $(top_srcdir)/m4/want_pam.m4 \ + $(top_srcdir)/m4/want_passwd.m4 $(top_srcdir)/m4/want_pgsql.m4 \ + $(top_srcdir)/m4/want_prefetch.m4 \ + $(top_srcdir)/m4/want_shadow.m4 \ + $(top_srcdir)/m4/want_sodium.m4 $(top_srcdir)/m4/want_solr.m4 \ + $(top_srcdir)/m4/want_sqlite.m4 \ + $(top_srcdir)/m4/want_stemmer.m4 \ + $(top_srcdir)/m4/want_systemd.m4 \ + $(top_srcdir)/m4/want_textcat.m4 \ + $(top_srcdir)/m4/want_unwind.m4 $(top_srcdir)/m4/want_zlib.m4 \ + $(top_srcdir)/m4/want_zstd.m4 $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +DIST_COMMON = $(srcdir)/Makefile.am $(noinst_HEADERS) \ + $(am__DIST_COMMON) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +PROGRAMS = $(noinst_PROGRAMS) +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__uninstall_files_from_dir = { \ + test -z "$$files" \ + || { test ! -d "$$dir" && test ! -f "$$dir" && test ! -r "$$dir"; } \ + || { echo " ( cd '$$dir' && rm -f" $$files ")"; \ + $(am__cd) "$$dir" && rm -f $$files; }; \ + } +am__installdirs = "$(DESTDIR)$(moduledir)" +LTLIBRARIES = $(module_LTLIBRARIES) +@DOVECOT_PLUGIN_DEPS_TRUE@lib21_fts_squat_plugin_la_DEPENDENCIES = \ +@DOVECOT_PLUGIN_DEPS_TRUE@ ../fts/lib20_fts_plugin.la +am_lib21_fts_squat_plugin_la_OBJECTS = fts-squat-plugin.lo \ + fts-backend-squat.lo squat-trie.lo squat-uidlist.lo +lib21_fts_squat_plugin_la_OBJECTS = \ + $(am_lib21_fts_squat_plugin_la_OBJECTS) +AM_V_lt = $(am__v_lt_@AM_V@) +am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@) +am__v_lt_0 = --silent +am__v_lt_1 = +lib21_fts_squat_plugin_la_LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC \ + $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=link $(CCLD) \ + $(AM_CFLAGS) $(CFLAGS) $(lib21_fts_squat_plugin_la_LDFLAGS) \ + $(LDFLAGS) -o $@ +am_squat_test_OBJECTS = squat-test.$(OBJEXT) +squat_test_OBJECTS = $(am_squat_test_OBJECTS) +am__DEPENDENCIES_1 = +AM_V_P = $(am__v_P_@AM_V@) +am__v_P_ = $(am__v_P_@AM_DEFAULT_V@) +am__v_P_0 = false +am__v_P_1 = : +AM_V_GEN = $(am__v_GEN_@AM_V@) +am__v_GEN_ = $(am__v_GEN_@AM_DEFAULT_V@) +am__v_GEN_0 = @echo " GEN " $@; +am__v_GEN_1 = +AM_V_at = $(am__v_at_@AM_V@) +am__v_at_ = $(am__v_at_@AM_DEFAULT_V@) +am__v_at_0 = @ +am__v_at_1 = +DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top_builddir) +depcomp = $(SHELL) $(top_srcdir)/depcomp +am__maybe_remake_depfiles = depfiles +am__depfiles_remade = ./$(DEPDIR)/fts-backend-squat.Plo \ + ./$(DEPDIR)/fts-squat-plugin.Plo ./$(DEPDIR)/squat-test.Po \ + ./$(DEPDIR)/squat-trie.Plo ./$(DEPDIR)/squat-uidlist.Plo +am__mv = mv -f +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +LTCOMPILE = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=compile $(CC) $(DEFS) \ + $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) \ + $(AM_CFLAGS) $(CFLAGS) +AM_V_CC = $(am__v_CC_@AM_V@) +am__v_CC_ = $(am__v_CC_@AM_DEFAULT_V@) +am__v_CC_0 = @echo " CC " $@; +am__v_CC_1 = +CCLD = $(CC) +LINK = $(LIBTOOL) $(AM_V_lt) --tag=CC $(AM_LIBTOOLFLAGS) \ + $(LIBTOOLFLAGS) --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) \ + $(AM_LDFLAGS) $(LDFLAGS) -o $@ +AM_V_CCLD = $(am__v_CCLD_@AM_V@) +am__v_CCLD_ = $(am__v_CCLD_@AM_DEFAULT_V@) +am__v_CCLD_0 = @echo " CCLD " $@; +am__v_CCLD_1 = +SOURCES = $(lib21_fts_squat_plugin_la_SOURCES) $(squat_test_SOURCES) +DIST_SOURCES = $(lib21_fts_squat_plugin_la_SOURCES) \ + $(squat_test_SOURCES) +am__can_run_installinfo = \ + case $$AM_UPDATE_INFO_DIR in \ + n|no|NO) false;; \ + *) (install-info --version) >/dev/null 2>&1;; \ + esac +HEADERS = $(noinst_HEADERS) +am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP) +# Read a list of newline-separated strings from the standard input, +# and print each of them once, without duplicates. Input order is +# *not* preserved. +am__uniquify_input = $(AWK) '\ + BEGIN { nonempty = 0; } \ + { items[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in items) print i; }; } \ +' +# Make sure the list of sources is unique. This is necessary because, +# e.g., the same source file might be shared among _SOURCES variables +# for different programs/libraries. +am__define_uniq_tagged_files = \ + list='$(am__tagged_files)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | $(am__uniquify_input)` +ETAGS = etags +CTAGS = ctags +am__DIST_COMMON = $(srcdir)/Makefile.in $(top_srcdir)/depcomp +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +ACLOCAL = @ACLOCAL@ +ACLOCAL_AMFLAGS = @ACLOCAL_AMFLAGS@ +AMTAR = @AMTAR@ +AM_DEFAULT_VERBOSITY = @AM_DEFAULT_VERBOSITY@ +APPARMOR_LIBS = @APPARMOR_LIBS@ +AR = @AR@ +AUTH_CFLAGS = @AUTH_CFLAGS@ +AUTH_LIBS = @AUTH_LIBS@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +BINARY_CFLAGS = @BINARY_CFLAGS@ +BINARY_LDFLAGS = @BINARY_LDFLAGS@ +BISON = @BISON@ +CASSANDRA_CFLAGS = @CASSANDRA_CFLAGS@ +CASSANDRA_LIBS = @CASSANDRA_LIBS@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CDB_LIBS = @CDB_LIBS@ +CFLAGS = @CFLAGS@ +CLUCENE_CFLAGS = @CLUCENE_CFLAGS@ +CLUCENE_LIBS = @CLUCENE_LIBS@ +COMPRESS_LIBS = @COMPRESS_LIBS@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CRYPT_LIBS = @CRYPT_LIBS@ +CXX = @CXX@ +CXXCPP = @CXXCPP@ +CXXDEPMODE = @CXXDEPMODE@ +CXXFLAGS = @CXXFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +DICT_LIBS = @DICT_LIBS@ +DLLIB = @DLLIB@ +DLLTOOL = @DLLTOOL@ +DSYMUTIL = @DSYMUTIL@ +DUMPBIN = @DUMPBIN@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +FGREP = @FGREP@ +FLEX = @FLEX@ +FUZZER_CPPFLAGS = @FUZZER_CPPFLAGS@ +FUZZER_LDFLAGS = @FUZZER_LDFLAGS@ +GREP = @GREP@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +KRB5CONFIG = @KRB5CONFIG@ +KRB5_CFLAGS = @KRB5_CFLAGS@ +KRB5_LIBS = @KRB5_LIBS@ +LD = @LD@ +LDAP_LIBS = @LDAP_LIBS@ +LDFLAGS = @LDFLAGS@ +LD_NO_WHOLE_ARCHIVE = @LD_NO_WHOLE_ARCHIVE@ +LD_WHOLE_ARCHIVE = @LD_WHOLE_ARCHIVE@ +LIBCAP = @LIBCAP@ +LIBDOVECOT = @LIBDOVECOT@ +LIBDOVECOT_COMPRESS = @LIBDOVECOT_COMPRESS@ +LIBDOVECOT_DEPS = @LIBDOVECOT_DEPS@ +LIBDOVECOT_DSYNC = @LIBDOVECOT_DSYNC@ +LIBDOVECOT_LA_LIBS = @LIBDOVECOT_LA_LIBS@ +LIBDOVECOT_LDA = @LIBDOVECOT_LDA@ +LIBDOVECOT_LDAP = @LIBDOVECOT_LDAP@ +LIBDOVECOT_LIBFTS = @LIBDOVECOT_LIBFTS@ +LIBDOVECOT_LIBFTS_DEPS = @LIBDOVECOT_LIBFTS_DEPS@ +LIBDOVECOT_LOGIN = @LIBDOVECOT_LOGIN@ +LIBDOVECOT_LUA = @LIBDOVECOT_LUA@ +LIBDOVECOT_LUA_DEPS = @LIBDOVECOT_LUA_DEPS@ +LIBDOVECOT_SQL = @LIBDOVECOT_SQL@ +LIBDOVECOT_STORAGE = @LIBDOVECOT_STORAGE@ +LIBDOVECOT_STORAGE_DEPS = @LIBDOVECOT_STORAGE_DEPS@ +LIBEXTTEXTCAT_CFLAGS = @LIBEXTTEXTCAT_CFLAGS@ +LIBEXTTEXTCAT_LIBS = @LIBEXTTEXTCAT_LIBS@ +LIBICONV = @LIBICONV@ +LIBICU_CFLAGS = @LIBICU_CFLAGS@ +LIBICU_LIBS = @LIBICU_LIBS@ +LIBOBJS = @LIBOBJS@ +LIBS = @LIBS@ +LIBSODIUM_CFLAGS = @LIBSODIUM_CFLAGS@ +LIBSODIUM_LIBS = @LIBSODIUM_LIBS@ +LIBTIRPC_CFLAGS = @LIBTIRPC_CFLAGS@ +LIBTIRPC_LIBS = @LIBTIRPC_LIBS@ +LIBTOOL = @LIBTOOL@ +LIBUNWIND_CFLAGS = @LIBUNWIND_CFLAGS@ +LIBUNWIND_LIBS = @LIBUNWIND_LIBS@ +LIBWRAP_LIBS = @LIBWRAP_LIBS@ +LINKED_STORAGE_LDADD = @LINKED_STORAGE_LDADD@ +LIPO = @LIPO@ +LN_S = @LN_S@ +LTLIBICONV = @LTLIBICONV@ +LTLIBOBJS = @LTLIBOBJS@ +LT_SYS_LIBRARY_PATH = @LT_SYS_LIBRARY_PATH@ +LUA_CFLAGS = @LUA_CFLAGS@ +LUA_LIBS = @LUA_LIBS@ +MAINT = @MAINT@ +MAKEINFO = @MAKEINFO@ +MANIFEST_TOOL = @MANIFEST_TOOL@ +MKDIR_P = @MKDIR_P@ +MODULE_LIBS = @MODULE_LIBS@ +MODULE_SUFFIX = @MODULE_SUFFIX@ +MYSQL_CFLAGS = @MYSQL_CFLAGS@ +MYSQL_CONFIG = @MYSQL_CONFIG@ +MYSQL_LIBS = @MYSQL_LIBS@ +NM = @NM@ +NMEDIT = @NMEDIT@ +NOPLUGIN_LDFLAGS = +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@ +PANDOC = @PANDOC@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +PGSQL_CFLAGS = @PGSQL_CFLAGS@ +PGSQL_LIBS = @PGSQL_LIBS@ +PG_CONFIG = @PG_CONFIG@ +PIE_CFLAGS = @PIE_CFLAGS@ +PIE_LDFLAGS = @PIE_LDFLAGS@ +PKG_CONFIG = @PKG_CONFIG@ +PKG_CONFIG_LIBDIR = @PKG_CONFIG_LIBDIR@ +PKG_CONFIG_PATH = @PKG_CONFIG_PATH@ +QUOTA_LIBS = @QUOTA_LIBS@ +RANLIB = @RANLIB@ +RELRO_LDFLAGS = @RELRO_LDFLAGS@ +RPCGEN = @RPCGEN@ +RUN_TEST = @RUN_TEST@ +SED = @SED@ +SETTING_FILES = @SETTING_FILES@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +SQLITE_CFLAGS = @SQLITE_CFLAGS@ +SQLITE_LIBS = @SQLITE_LIBS@ +SQL_CFLAGS = @SQL_CFLAGS@ +SQL_LIBS = @SQL_LIBS@ +SSL_CFLAGS = @SSL_CFLAGS@ +SSL_LIBS = @SSL_LIBS@ +STRIP = @STRIP@ +SYSTEMD_CFLAGS = @SYSTEMD_CFLAGS@ +SYSTEMD_LIBS = @SYSTEMD_LIBS@ +VALGRIND = @VALGRIND@ +VERSION = @VERSION@ +ZSTD_CFLAGS = @ZSTD_CFLAGS@ +ZSTD_LIBS = @ZSTD_LIBS@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_AR = @ac_ct_AR@ +ac_ct_CC = @ac_ct_CC@ +ac_ct_CXX = @ac_ct_CXX@ +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@ +dict_drivers = @dict_drivers@ +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@ +mandir = @mandir@ +mkdir_p = @mkdir_p@ +moduledir = @moduledir@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +rundir = @rundir@ +runstatedir = @runstatedir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +sql_drivers = @sql_drivers@ +srcdir = @srcdir@ +ssldir = @ssldir@ +statedir = @statedir@ +sysconfdir = @sysconfdir@ +systemdservicetype = @systemdservicetype@ +systemdsystemunitdir = @systemdsystemunitdir@ +target_alias = @target_alias@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +AM_CPPFLAGS = \ + -I$(top_srcdir)/src/lib \ + -I$(top_srcdir)/src/lib-mail \ + -I$(top_srcdir)/src/lib-index \ + -I$(top_srcdir)/src/lib-storage \ + -I$(top_srcdir)/src/plugins/fts + +lib21_fts_squat_plugin_la_LDFLAGS = -module -avoid-version +module_LTLIBRARIES = \ + lib21_fts_squat_plugin.la + +@DOVECOT_PLUGIN_DEPS_TRUE@lib21_fts_squat_plugin_la_LIBADD = \ +@DOVECOT_PLUGIN_DEPS_TRUE@ ../fts/lib20_fts_plugin.la + +lib21_fts_squat_plugin_la_SOURCES = \ + fts-squat-plugin.c \ + fts-backend-squat.c \ + squat-trie.c \ + squat-uidlist.c + +noinst_HEADERS = \ + fts-squat-plugin.h \ + squat-trie.h \ + squat-trie-private.h \ + squat-uidlist.h + +squat_test_SOURCES = \ + squat-test.c + +common_objects = \ + squat-trie.lo \ + squat-uidlist.lo + +squat_test_LDADD = \ + $(common_objects) \ + $(LIBDOVECOT_STORAGE) \ + $(LIBDOVECOT) + +squat_test_DEPENDENCIES = \ + $(common_objects) \ + $(LIBDOVECOT_STORAGE_DEPS) \ + $(LIBDOVECOT_DEPS) + +all: all-am + +.SUFFIXES: +.SUFFIXES: .c .lo .o .obj +$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ $(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/plugins/fts-squat/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --foreign src/plugins/fts-squat/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__maybe_remake_depfiles)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__maybe_remake_depfiles);; \ + esac; + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: @MAINTAINER_MODE_TRUE@ $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): @MAINTAINER_MODE_TRUE@ $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): + +clean-noinstPROGRAMS: + @list='$(noinst_PROGRAMS)'; test -n "$$list" || exit 0; \ + echo " rm -f" $$list; \ + rm -f $$list || exit $$?; \ + test -n "$(EXEEXT)" || exit 0; \ + list=`for p in $$list; do echo "$$p"; done | sed 's/$(EXEEXT)$$//'`; \ + echo " rm -f" $$list; \ + rm -f $$list + +install-moduleLTLIBRARIES: $(module_LTLIBRARIES) + @$(NORMAL_INSTALL) + @list='$(module_LTLIBRARIES)'; test -n "$(moduledir)" || list=; \ + list2=; for p in $$list; do \ + if test -f $$p; then \ + list2="$$list2 $$p"; \ + else :; fi; \ + done; \ + test -z "$$list2" || { \ + echo " $(MKDIR_P) '$(DESTDIR)$(moduledir)'"; \ + $(MKDIR_P) "$(DESTDIR)$(moduledir)" || exit 1; \ + echo " $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $$list2 '$(DESTDIR)$(moduledir)'"; \ + $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=install $(INSTALL) $(INSTALL_STRIP_FLAG) $$list2 "$(DESTDIR)$(moduledir)"; \ + } + +uninstall-moduleLTLIBRARIES: + @$(NORMAL_UNINSTALL) + @list='$(module_LTLIBRARIES)'; test -n "$(moduledir)" || list=; \ + for p in $$list; do \ + $(am__strip_dir) \ + echo " $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=uninstall rm -f '$(DESTDIR)$(moduledir)/$$f'"; \ + $(LIBTOOL) $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=uninstall rm -f "$(DESTDIR)$(moduledir)/$$f"; \ + done + +clean-moduleLTLIBRARIES: + -test -z "$(module_LTLIBRARIES)" || rm -f $(module_LTLIBRARIES) + @list='$(module_LTLIBRARIES)'; \ + locs=`for p in $$list; do echo $$p; done | \ + sed 's|^[^/]*$$|.|; s|/[^/]*$$||; s|$$|/so_locations|' | \ + sort -u`; \ + test -z "$$locs" || { \ + echo rm -f $${locs}; \ + rm -f $${locs}; \ + } + +lib21_fts_squat_plugin.la: $(lib21_fts_squat_plugin_la_OBJECTS) $(lib21_fts_squat_plugin_la_DEPENDENCIES) $(EXTRA_lib21_fts_squat_plugin_la_DEPENDENCIES) + $(AM_V_CCLD)$(lib21_fts_squat_plugin_la_LINK) -rpath $(moduledir) $(lib21_fts_squat_plugin_la_OBJECTS) $(lib21_fts_squat_plugin_la_LIBADD) $(LIBS) + +squat-test$(EXEEXT): $(squat_test_OBJECTS) $(squat_test_DEPENDENCIES) $(EXTRA_squat_test_DEPENDENCIES) + @rm -f squat-test$(EXEEXT) + $(AM_V_CCLD)$(LINK) $(squat_test_OBJECTS) $(squat_test_LDADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fts-backend-squat.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fts-squat-plugin.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/squat-test.Po@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/squat-trie.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/squat-uidlist.Plo@am__quote@ # am--include-marker + +$(am__depfiles_remade): + @$(MKDIR_P) $(@D) + @echo '# dummy' >$@-t && $(am__mv) $@-t $@ + +am--depfiles: $(am__depfiles_remade) + +.c.o: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(COMPILE) -c -o $@ $< + +.c.obj: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ `$(CYGPATH_W) '$<'` +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(COMPILE) -c -o $@ `$(CYGPATH_W) '$<'` + +.c.lo: +@am__fastdepCC_TRUE@ $(AM_V_CC)$(LTCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(AM_V_at)$(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Plo +@AMDEP_TRUE@@am__fastdepCC_FALSE@ $(AM_V_CC)source='$<' object='$@' libtool=yes @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(AM_V_CC@am__nodep@)$(LTCOMPILE) -c -o $@ $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs + +ID: $(am__tagged_files) + $(am__define_uniq_tagged_files); mkid -fID $$unique +tags: tags-am +TAGS: tags + +tags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files) + set x; \ + here=`pwd`; \ + $(am__define_uniq_tagged_files); \ + 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-am + +CTAGS: ctags +ctags-am: $(TAGS_DEPENDENCIES) $(am__tagged_files) + $(am__define_uniq_tagged_files); \ + 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" +cscopelist: cscopelist-am + +cscopelist-am: $(am__tagged_files) + list='$(am__tagged_files)'; \ + case "$(srcdir)" in \ + [\\/]* | ?:[\\/]*) sdir="$(srcdir)" ;; \ + *) sdir=$(subdir)/$(srcdir) ;; \ + esac; \ + for i in $$list; do \ + if test -f "$$i"; then \ + echo "$(subdir)/$$i"; \ + else \ + echo "$$sdir/$$i"; \ + fi; \ + done >> $(top_builddir)/cscope.files + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +distdir: $(BUILT_SOURCES) + $(MAKE) $(AM_MAKEFLAGS) distdir-am + +distdir-am: $(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 $(PROGRAMS) $(LTLIBRARIES) $(HEADERS) +installdirs: + for dir in "$(DESTDIR)$(moduledir)"; 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: + if test -z '$(STRIP)'; then \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + install; \ + else \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \ + fi +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-libtool clean-moduleLTLIBRARIES \ + clean-noinstPROGRAMS mostlyclean-am + +distclean: distclean-am + -rm -f ./$(DEPDIR)/fts-backend-squat.Plo + -rm -f ./$(DEPDIR)/fts-squat-plugin.Plo + -rm -f ./$(DEPDIR)/squat-test.Po + -rm -f ./$(DEPDIR)/squat-trie.Plo + -rm -f ./$(DEPDIR)/squat-uidlist.Plo + -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-moduleLTLIBRARIES + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: + +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 -f ./$(DEPDIR)/fts-backend-squat.Plo + -rm -f ./$(DEPDIR)/fts-squat-plugin.Plo + -rm -f ./$(DEPDIR)/squat-test.Po + -rm -f ./$(DEPDIR)/squat-trie.Plo + -rm -f ./$(DEPDIR)/squat-uidlist.Plo + -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-moduleLTLIBRARIES + +.MAKE: install-am install-strip + +.PHONY: CTAGS GTAGS TAGS all all-am am--depfiles check check-am clean \ + clean-generic clean-libtool clean-moduleLTLIBRARIES \ + clean-noinstPROGRAMS cscopelist-am ctags ctags-am 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-man \ + install-moduleLTLIBRARIES 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 tags-am uninstall uninstall-am \ + uninstall-moduleLTLIBRARIES + +.PRECIOUS: Makefile + + +# 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/plugins/fts-squat/fts-backend-squat.c b/src/plugins/fts-squat/fts-backend-squat.c new file mode 100644 index 0000000..fbd7bbe --- /dev/null +++ b/src/plugins/fts-squat/fts-backend-squat.c @@ -0,0 +1,497 @@ +/* Copyright (c) 2006-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "str.h" +#include "unichar.h" +#include "mail-user.h" +#include "mail-namespace.h" +#include "mail-storage-private.h" +#include "mail-search-build.h" +#include "squat-trie.h" +#include "fts-squat-plugin.h" + + +#define SQUAT_FILE_PREFIX "dovecot.index.search" + +struct squat_fts_backend { + struct fts_backend backend; + + struct mailbox *box; + struct squat_trie *trie; + + unsigned int partial_len, full_len; + bool refresh; +}; + +struct squat_fts_backend_update_context { + struct fts_backend_update_context ctx; + struct squat_trie_build_context *build_ctx; + + enum squat_index_type squat_type; + uint32_t uid; + string_t *hdr; + + bool failed; +}; + +static struct fts_backend *fts_backend_squat_alloc(void) +{ + struct squat_fts_backend *backend; + + backend = i_new(struct squat_fts_backend, 1); + backend->backend = fts_backend_squat; + return &backend->backend; +} + +static int +fts_backend_squat_init(struct fts_backend *_backend, const char **error_r) +{ + struct squat_fts_backend *backend = + (struct squat_fts_backend *)_backend; + const char *const *tmp, *env; + unsigned int len; + + env = mail_user_plugin_getenv(_backend->ns->user, "fts_squat"); + if (env == NULL) + return 0; + + for (tmp = t_strsplit_spaces(env, " "); *tmp != NULL; tmp++) { + if (str_begins(*tmp, "partial=")) { + if (str_to_uint(*tmp + 8, &len) < 0 || len == 0) { + *error_r = t_strdup_printf( + "Invalid partial length: %s", *tmp + 8); + return -1; + } + backend->partial_len = len; + } else if (str_begins(*tmp, "full=")) { + if (str_to_uint(*tmp + 5, &len) < 0 || len == 0) { + *error_r = t_strdup_printf( + "Invalid full length: %s", *tmp + 5); + return -1; + } + backend->full_len = len; + } else { + *error_r = t_strdup_printf("Invalid setting: %s", *tmp); + return -1; + } + } + return 0; +} + +static void +fts_backend_squat_unset_box(struct squat_fts_backend *backend) +{ + if (backend->trie != NULL) + squat_trie_deinit(&backend->trie); + backend->box = NULL; +} + +static void fts_backend_squat_deinit(struct fts_backend *_backend) +{ + struct squat_fts_backend *backend = + (struct squat_fts_backend *)_backend; + + fts_backend_squat_unset_box(backend); + i_free(backend); +} + +static int +fts_backend_squat_set_box(struct squat_fts_backend *backend, + struct mailbox *box) +{ + const struct mailbox_permissions *perm; + struct mail_storage *storage; + struct mailbox_status status; + const char *path; + enum squat_index_flags flags = 0; + int ret; + + if (backend->box == box) + { + if (backend->refresh) { + ret = squat_trie_refresh(backend->trie); + if (ret < 0) + return ret; + backend->refresh = FALSE; + } + return 0; + } + fts_backend_squat_unset_box(backend); + backend->refresh = FALSE; + if (box == NULL) + return 0; + + perm = mailbox_get_permissions(box); + storage = mailbox_get_storage(box); + if (mailbox_get_path_to(box, MAILBOX_LIST_PATH_TYPE_INDEX, &path) <= 0) + i_unreached(); /* fts already checked this */ + + mailbox_get_open_status(box, STATUS_UIDVALIDITY, &status); + if (storage->set->mmap_disable) + flags |= SQUAT_INDEX_FLAG_MMAP_DISABLE; + if (storage->set->mail_nfs_index) + flags |= SQUAT_INDEX_FLAG_NFS_FLUSH; + if (storage->set->dotlock_use_excl) + flags |= SQUAT_INDEX_FLAG_DOTLOCK_USE_EXCL; + + backend->trie = + squat_trie_init(t_strconcat(path, "/"SQUAT_FILE_PREFIX, NULL), + status.uidvalidity, + storage->set->parsed_lock_method, + flags, perm->file_create_mode, + perm->file_create_gid); + + if (backend->partial_len != 0) + squat_trie_set_partial_len(backend->trie, backend->partial_len); + if (backend->full_len != 0) + squat_trie_set_full_len(backend->trie, backend->full_len); + backend->box = box; + return squat_trie_open(backend->trie); +} + +static int +fts_backend_squat_get_last_uid(struct fts_backend *_backend, + struct mailbox *box, uint32_t *last_uid_r) +{ + struct squat_fts_backend *backend = + (struct squat_fts_backend *)_backend; + + int ret = fts_backend_squat_set_box(backend, box); + if (ret < 0) + return -1; + return squat_trie_get_last_uid(backend->trie, last_uid_r); +} + +static struct fts_backend_update_context * +fts_backend_squat_update_init(struct fts_backend *_backend) +{ + struct squat_fts_backend_update_context *ctx; + + ctx = i_new(struct squat_fts_backend_update_context, 1); + ctx->ctx.backend = _backend; + ctx->hdr = str_new(default_pool, 1024*32); + return &ctx->ctx; +} + +static int get_all_msg_uids(struct mailbox *box, ARRAY_TYPE(seq_range) *uids) +{ + struct mailbox_transaction_context *t; + struct mail_search_context *search_ctx; + struct mail_search_args *search_args; + struct mail *mail; + int ret; + + t = mailbox_transaction_begin(box, 0, __func__); + + search_args = mail_search_build_init(); + mail_search_build_add_all(search_args); + search_ctx = mailbox_search_init(t, search_args, NULL, 0, NULL); + mail_search_args_unref(&search_args); + + while (mailbox_search_next(search_ctx, &mail)) { + /* *2 because even/odd is for body/header */ + seq_range_array_add_range(uids, mail->uid * 2, + mail->uid * 2 + 1); + } + ret = mailbox_search_deinit(&search_ctx); + (void)mailbox_transaction_commit(&t); + return ret; +} + +static int +fts_backend_squat_update_uid_changed(struct squat_fts_backend_update_context *ctx) +{ + int ret = 0; + + if (ctx->uid == 0) + return 0; + + if (squat_trie_build_more(ctx->build_ctx, ctx->uid, + SQUAT_INDEX_TYPE_HEADER, + str_data(ctx->hdr), str_len(ctx->hdr)) < 0) + ret = -1; + str_truncate(ctx->hdr, 0); + return ret; +} + +static int +fts_backend_squat_build_deinit(struct squat_fts_backend_update_context *ctx) +{ + struct squat_fts_backend *backend = + (struct squat_fts_backend *)ctx->ctx.backend; + ARRAY_TYPE(seq_range) uids; + int ret = 0; + + if (ctx->build_ctx == NULL) + return 0; + + if (fts_backend_squat_update_uid_changed(ctx) < 0) + ret = -1; + + i_array_init(&uids, 1024); + if (get_all_msg_uids(backend->box, &uids) < 0) { + (void)squat_trie_build_deinit(&ctx->build_ctx, NULL); + ret = -1; + } else { + seq_range_array_invert(&uids, 2, (uint32_t)-2); + if (squat_trie_build_deinit(&ctx->build_ctx, &uids) < 0) + ret = -1; + } + array_free(&uids); + return ret; +} + +static int +fts_backend_squat_update_deinit(struct fts_backend_update_context *_ctx) +{ + struct squat_fts_backend_update_context *ctx = + (struct squat_fts_backend_update_context *)_ctx; + int ret = ctx->failed ? -1 : 0; + + if (fts_backend_squat_build_deinit(ctx) < 0) + ret = -1; + str_free(&ctx->hdr); + i_free(ctx); + return ret; +} + +static void +fts_backend_squat_update_set_mailbox(struct fts_backend_update_context *_ctx, + struct mailbox *box) +{ + struct squat_fts_backend_update_context *ctx = + (struct squat_fts_backend_update_context *)_ctx; + struct squat_fts_backend *backend = + (struct squat_fts_backend *)ctx->ctx.backend; + + if (fts_backend_squat_build_deinit(ctx) < 0) + ctx->failed = TRUE; + if (fts_backend_squat_set_box(backend, box) < 0) + ctx->failed = TRUE; + else if (box != NULL) { + if (squat_trie_build_init(backend->trie, &ctx->build_ctx) < 0) + ctx->failed = TRUE; + } +} + +static void +fts_backend_squat_update_expunge(struct fts_backend_update_context *_ctx ATTR_UNUSED, + uint32_t last_uid ATTR_UNUSED) +{ + /* FIXME */ +} + +static bool +fts_backend_squat_update_set_build_key(struct fts_backend_update_context *_ctx, + const struct fts_backend_build_key *key) +{ + struct squat_fts_backend_update_context *ctx = + (struct squat_fts_backend_update_context *)_ctx; + + if (ctx->failed) + return FALSE; + + if (key->uid != ctx->uid) { + if (fts_backend_squat_update_uid_changed(ctx) < 0) + ctx->failed = TRUE; + } + + switch (key->type) { + case FTS_BACKEND_BUILD_KEY_HDR: + case FTS_BACKEND_BUILD_KEY_MIME_HDR: + str_printfa(ctx->hdr, "%s: ", key->hdr_name); + ctx->squat_type = SQUAT_INDEX_TYPE_HEADER; + break; + case FTS_BACKEND_BUILD_KEY_BODY_PART: + ctx->squat_type = SQUAT_INDEX_TYPE_BODY; + break; + case FTS_BACKEND_BUILD_KEY_BODY_PART_BINARY: + i_unreached(); + } + ctx->uid = key->uid; + return TRUE; +} + +static void +fts_backend_squat_update_unset_build_key(struct fts_backend_update_context *_ctx) +{ + struct squat_fts_backend_update_context *ctx = + (struct squat_fts_backend_update_context *)_ctx; + + if (ctx->squat_type == SQUAT_INDEX_TYPE_HEADER) + str_append_c(ctx->hdr, '\n'); +} + +static int +fts_backend_squat_update_build_more(struct fts_backend_update_context *_ctx, + const unsigned char *data, size_t size) +{ + struct squat_fts_backend_update_context *ctx = + (struct squat_fts_backend_update_context *)_ctx; + + if (ctx->squat_type == SQUAT_INDEX_TYPE_HEADER) { + str_append_data(ctx->hdr, data, size); + return 0; + } + return squat_trie_build_more(ctx->build_ctx, ctx->uid, ctx->squat_type, + data, size); +} + +static int fts_backend_squat_refresh(struct fts_backend *_backend) +{ + struct squat_fts_backend *backend = + (struct squat_fts_backend *)_backend; + + backend->refresh = TRUE; + return 0; +} + +static int fts_backend_squat_optimize(struct fts_backend *_backend ATTR_UNUSED) +{ + /* FIXME: drop expunged messages */ + return 0; +} + +static int squat_lookup_arg(struct squat_fts_backend *backend, + const struct mail_search_arg *arg, bool and_args, + ARRAY_TYPE(seq_range) *definite_uids, + ARRAY_TYPE(seq_range) *maybe_uids) +{ + enum squat_index_type squat_type; + ARRAY_TYPE(seq_range) tmp_definite_uids, tmp_maybe_uids; + string_t *dtc; + uint32_t last_uid; + int ret; + + switch (arg->type) { + case SEARCH_TEXT: + squat_type = SQUAT_INDEX_TYPE_HEADER | + SQUAT_INDEX_TYPE_BODY; + break; + case SEARCH_BODY: + squat_type = SQUAT_INDEX_TYPE_BODY; + break; + case SEARCH_HEADER: + case SEARCH_HEADER_ADDRESS: + case SEARCH_HEADER_COMPRESS_LWSP: + squat_type = SQUAT_INDEX_TYPE_HEADER; + break; + default: + return 0; + } + + i_array_init(&tmp_definite_uids, 128); + i_array_init(&tmp_maybe_uids, 128); + + dtc = t_str_new(128); + if (backend->backend.ns->user-> + default_normalizer(arg->value.str, strlen(arg->value.str), dtc) < 0) + i_panic("squat: search key not utf8"); + + ret = squat_trie_lookup(backend->trie, str_c(dtc), squat_type, + &tmp_definite_uids, &tmp_maybe_uids); + if (arg->match_not) { + /* definite -> non-match + maybe -> maybe + non-match -> maybe */ + array_clear(&tmp_maybe_uids); + + if (squat_trie_get_last_uid(backend->trie, &last_uid) < 0) + i_unreached(); + seq_range_array_add_range(&tmp_maybe_uids, 1, last_uid); + seq_range_array_remove_seq_range(&tmp_maybe_uids, + &tmp_definite_uids); + array_clear(&tmp_definite_uids); + } + + if (and_args) { + /* AND: + definite && definite -> definite + definite && maybe -> maybe + maybe && maybe -> maybe */ + + /* put definites among maybies, so they can be intersected */ + seq_range_array_merge(maybe_uids, definite_uids); + seq_range_array_merge(&tmp_maybe_uids, &tmp_definite_uids); + + seq_range_array_intersect(maybe_uids, &tmp_maybe_uids); + seq_range_array_intersect(definite_uids, &tmp_definite_uids); + /* remove duplicate maybies that are also definites */ + seq_range_array_remove_seq_range(maybe_uids, definite_uids); + } else { + /* OR: + definite || definite -> definite + definite || maybe -> definite + maybe || maybe -> maybe */ + + /* remove maybies that are now definites */ + seq_range_array_remove_seq_range(&tmp_maybe_uids, + definite_uids); + seq_range_array_remove_seq_range(maybe_uids, + &tmp_definite_uids); + + seq_range_array_merge(definite_uids, &tmp_definite_uids); + seq_range_array_merge(maybe_uids, &tmp_maybe_uids); + } + + array_free(&tmp_definite_uids); + array_free(&tmp_maybe_uids); + return ret < 0 ? -1 : 1; +} + +static int +fts_backend_squat_lookup(struct fts_backend *_backend, struct mailbox *box, + struct mail_search_arg *args, + enum fts_lookup_flags flags, + struct fts_result *result) +{ + struct squat_fts_backend *backend = + (struct squat_fts_backend *)_backend; + bool and_args = (flags & FTS_LOOKUP_FLAG_AND_ARGS) != 0; + bool first = TRUE; + int ret; + + ret = fts_backend_squat_set_box(backend, box); + if (ret < 0) + return -1; + + for (; args != NULL; args = args->next) { + ret = squat_lookup_arg(backend, args, first ? FALSE : and_args, + &result->definite_uids, + &result->maybe_uids); + if (ret < 0) + return -1; + if (ret > 0) { + args->match_always = TRUE; + first = FALSE; + } + } + return 0; +} + +struct fts_backend fts_backend_squat = { + .name = "squat", + .flags = FTS_BACKEND_FLAG_NORMALIZE_INPUT, + + { + fts_backend_squat_alloc, + fts_backend_squat_init, + fts_backend_squat_deinit, + fts_backend_squat_get_last_uid, + fts_backend_squat_update_init, + fts_backend_squat_update_deinit, + fts_backend_squat_update_set_mailbox, + fts_backend_squat_update_expunge, + fts_backend_squat_update_set_build_key, + fts_backend_squat_update_unset_build_key, + fts_backend_squat_update_build_more, + fts_backend_squat_refresh, + NULL, + fts_backend_squat_optimize, + fts_backend_default_can_lookup, + fts_backend_squat_lookup, + NULL, + NULL + } +}; diff --git a/src/plugins/fts-squat/fts-squat-plugin.c b/src/plugins/fts-squat/fts-squat-plugin.c new file mode 100644 index 0000000..59d9383 --- /dev/null +++ b/src/plugins/fts-squat/fts-squat-plugin.c @@ -0,0 +1,18 @@ +/* Copyright (c) 2006-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "fts-squat-plugin.h" + +const char *fts_squat_plugin_version = DOVECOT_ABI_VERSION; + +void fts_squat_plugin_init(struct module *module ATTR_UNUSED) +{ + fts_backend_register(&fts_backend_squat); +} + +void fts_squat_plugin_deinit(void) +{ + fts_backend_unregister(fts_backend_squat.name); +} + +const char *fts_squat_plugin_dependencies[] = { "fts", NULL }; diff --git a/src/plugins/fts-squat/fts-squat-plugin.h b/src/plugins/fts-squat/fts-squat-plugin.h new file mode 100644 index 0000000..0d6bfcb --- /dev/null +++ b/src/plugins/fts-squat/fts-squat-plugin.h @@ -0,0 +1,14 @@ +#ifndef FTS_SQUAT_PLUGIN_H +#define FTS_SQUAT_PLUGIN_H + +#include "fts-api-private.h" + +struct module; + +extern const char *fts_squat_plugin_dependencies[]; +extern struct fts_backend fts_backend_squat; + +void fts_squat_plugin_init(struct module *module); +void fts_squat_plugin_deinit(void); + +#endif diff --git a/src/plugins/fts-squat/squat-test.c b/src/plugins/fts-squat/squat-test.c new file mode 100644 index 0000000..b55646c --- /dev/null +++ b/src/plugins/fts-squat/squat-test.c @@ -0,0 +1,197 @@ +/* Copyright (c) 2006-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "file-lock.h" +#include "istream.h" +#include "time-util.h" +#include "unichar.h" +#include "squat-trie.h" +#include "squat-uidlist.h" + +#include <stdio.h> +#include <unistd.h> +#include <fcntl.h> +#include <time.h> +#include <sys/time.h> + +static void result_print(ARRAY_TYPE(seq_range) *result) +{ + const struct seq_range *range; + unsigned int i, count; + + range = array_get(result, &count); + for (i = 0; i < count; i++) { + if (i != 0) + printf(","); + printf("%u", range[i].seq1); + if (range[i].seq1 != range[i].seq2) + printf("-%u", range[i].seq2); + } + printf("\n"); +} + +int main(int argc ATTR_UNUSED, char *argv[]) +{ + const char *trie_path = "/tmp/squat-test-index.search"; + const char *uidlist_path = "/tmp/squat-test-index.search.uids"; + struct squat_trie *trie; + struct squat_trie_build_context *build_ctx; + struct istream *input; + struct stat trie_st, uidlist_st; + ARRAY_TYPE(seq_range) definite_uids, maybe_uids; + char *line, *str, buf[4096]; + buffer_t *valid; + int ret, fd; + unsigned int last = 0, seq = 1, node_count, uidlist_count; + size_t len; + enum squat_index_type index_type; + bool data_header = TRUE, first = TRUE, skip_body = FALSE; + bool mime_header = TRUE; + size_t trie_mem, uidlist_mem; + clock_t clock_start, clock_end; + struct timeval tv_start, tv_end; + double cputime; + + lib_init(); + i_unlink_if_exists(trie_path); + i_unlink_if_exists(uidlist_path); + trie = squat_trie_init(trie_path, time(NULL), + FILE_LOCK_METHOD_FCNTL, 0, 0600, (gid_t)-1); + + clock_start = clock(); + i_gettimeofday(&tv_start); + + fd = open(argv[1], O_RDONLY); + if (fd == -1) + return 1; + + if (squat_trie_build_init(trie, &build_ctx) < 0) + return 1; + + valid = buffer_create_dynamic(default_pool, 4096); + input = i_stream_create_fd(fd, SIZE_MAX); + ret = 0; + while (ret == 0 && (line = i_stream_read_next_line(input)) != NULL) { + if (last != input->v_offset/(1024*100)) { + fprintf(stderr, "\r%ukB", (unsigned)(input->v_offset/1024)); + fflush(stderr); + last = input->v_offset/(1024*100); + } + if (str_begins(line, "From ")) { + if (!first) + seq++; + data_header = TRUE; + skip_body = FALSE; + mime_header = TRUE; + continue; + } + first = FALSE; + + if (str_begins(line, "--")) { + skip_body = FALSE; + mime_header = TRUE; + } + + if (mime_header) { + if (*line == '\0') { + data_header = FALSE; + mime_header = FALSE; + continue; + } + + if (strncasecmp(line, "Content-Type:", 13) == 0 && + strncasecmp(line, "Content-Type: text/", 19) != 0 && + strncasecmp(line, "Content-Type: message/", 22) != 0) + skip_body = TRUE; + else if (strncasecmp(line, "Content-Transfer-Encoding: base64", 33) == 0) + skip_body = TRUE; + } else if (skip_body) + continue; + if (*line == '\0') + continue; + + /* we're actually indexing here headers as bodies and bodies + as headers. it doesn't really matter in this test, and + fixing it would require storing headers temporarily + elsewhere and index them only after the body */ + index_type = !data_header ? SQUAT_INDEX_TYPE_HEADER : + SQUAT_INDEX_TYPE_BODY; + + buffer_set_used_size(valid, 0); + len = strlen(line); + if (uni_utf8_get_valid_data((const unsigned char *)line, + len, valid)) { + ret = squat_trie_build_more(build_ctx, seq, index_type, + (const void *)line, len); + } else if (valid->used > 0) { + ret = squat_trie_build_more(build_ctx, seq, index_type, + valid->data, valid->used); + } + } + buffer_free(&valid); + if (squat_trie_build_deinit(&build_ctx, NULL) < 0) + ret = -1; + if (ret < 0) { + printf("build broken\n"); + return 1; + } + + clock_end = clock(); + i_gettimeofday(&tv_end); + + cputime = (double)(clock_end - clock_start) / CLOCKS_PER_SEC; + fprintf(stderr, "\n - Index time: %.2f CPU seconds, " + "%.2f real seconds (%.02fMB/CPUs)\n", cputime, + timeval_diff_msecs(&tv_end, &tv_start)/1000.0, + input->v_offset / cputime / (1024*1024)); + + if (stat(trie_path, &trie_st) < 0) + i_error("stat(%s) failed: %m", trie_path); + if (stat(uidlist_path, &uidlist_st) < 0) + i_error("stat(%s) failed: %m", uidlist_path); + + trie_mem = squat_trie_mem_used(trie, &node_count); + uidlist_mem = squat_uidlist_mem_used(squat_trie_get_uidlist(trie), + &uidlist_count); + fprintf(stderr, " - memory: %uk for trie, %uk for uidlist\n", + (unsigned)(trie_mem/1024), (unsigned)(uidlist_mem/1024)); + fprintf(stderr, " - %"PRIuUOFF_T" bytes in %u nodes (%.02f%%)\n", + trie_st.st_size, node_count, + trie_st.st_size / (float)input->v_offset * 100.0); + fprintf(stderr, " - %"PRIuUOFF_T" bytes in %u UID lists (%.02f%%)\n", + uidlist_st.st_size, uidlist_count, + uidlist_st.st_size / (float)input->v_offset * 100.0); + fprintf(stderr, " - %"PRIuUOFF_T" bytes total of %" + PRIuUOFF_T" (%.02f%%)\n", + (trie_st.st_size + uidlist_st.st_size), input->v_offset, + (trie_st.st_size + uidlist_st.st_size) / + (float)input->v_offset * 100.0); + + i_stream_unref(&input); + i_close_fd(&fd); + + i_array_init(&definite_uids, 128); + i_array_init(&maybe_uids, 128); + while ((str = fgets(buf, sizeof(buf), stdin)) != NULL) { + ret = strlen(str)-1; + str[ret] = 0; + + i_gettimeofday(&tv_start); + ret = squat_trie_lookup(trie, str, SQUAT_INDEX_TYPE_HEADER | + SQUAT_INDEX_TYPE_BODY, + &definite_uids, &maybe_uids); + if (ret < 0) + printf("error\n"); + else { + i_gettimeofday(&tv_end); + printf(" - Search took %.05f CPU seconds\n", + timeval_diff_usecs(&tv_end, &tv_start)/1000000.0); + printf(" - definite uids: "); + result_print(&definite_uids); + printf(" - maybe uids: "); + result_print(&maybe_uids); + } + } + return 0; +} diff --git a/src/plugins/fts-squat/squat-trie-private.h b/src/plugins/fts-squat/squat-trie-private.h new file mode 100644 index 0000000..b079554 --- /dev/null +++ b/src/plugins/fts-squat/squat-trie-private.h @@ -0,0 +1,192 @@ +#ifndef SQUAT_TRIE_PRIVATE_H +#define SQUAT_TRIE_PRIVATE_H + +#include "file-dotlock.h" +#include "squat-trie.h" + +#define SQUAT_TRIE_VERSION 2 +#define SQUAT_TRIE_LOCK_TIMEOUT 60 +#define SQUAT_TRIE_DOTLOCK_STALE_TIMEOUT (15*60) + +struct squat_file_header { + uint8_t version; + uint8_t unused[3]; + + uint32_t indexid; + uint32_t uidvalidity; + uint32_t used_file_size; + uint32_t deleted_space; + uint32_t node_count; + + uint32_t root_offset; + uint32_t root_unused_uids; + uint32_t root_next_uid; + uint32_t root_uidlist_idx; + + uint8_t partial_len; + uint8_t full_len; + uint8_t normalize_map[256]; +}; + +/* + node file: FIXME: no up-to-date + + struct squat_file_header; + + // children are written before their parents + node[] { + uint8_t child_count; + unsigned char chars[child_count]; + packed neg_diff_to_first_child_offset; // relative to node + packed diff_to_prev_offset[child_count-1]; + packed[child_count] { + // unused_uids_count == uid if have_uid_offset bit is zero + (unused_uids_count << 1) | (have_uid_offset); + [diff_to_prev_uid_offset;] // first one is relative to zero + } + } +*/ + +struct squat_node { + unsigned int child_count:8; + + /* children.leaf_string contains this many bytes */ + unsigned int leaf_string_length:16; + + /* TRUE = children.data contains our children. + FALSE = children.offset contains offset to our children in the + index file. */ + bool children_not_mapped:1; + /* When allocating our children, use a sequential array. */ + bool want_sequential:1; + /* This node's children are in a sequential array, meaning that the + first SEQUENTIAL_COUNT children have chars[n] = n. */ + bool have_sequential:1; + + /* Number of UIDs that exists in parent node but not in this one + (i.e. number of UIDs [0..next_uid-1] not in this node's uidlist). + This is mainly used when adding new UIDs to our children to set + the UID to be relative to this node's UID list. */ + uint32_t unused_uids; + + /* next_uid=0 means there are no UIDs in this node, otherwise + next_uid-1 is the last UID added to this node. */ + uint32_t next_uid; + uint32_t uid_list_idx; + + /* + struct { + unsigned char chars[child_count]; + struct squat_node[child_count]; + } *children; + */ + union { + /* children_not_mapped determines if data or offset should + be used. */ + void *data; + unsigned char *leaf_string; + unsigned char static_leaf_string[sizeof(void *)]; + uint32_t offset; + } children; +}; +/* Return pointer to node.children.chars[] */ +#define NODE_CHILDREN_CHARS(node) \ + ((unsigned char *)(node)->children.data) +/* Return pointer to node.children.node[] */ +#define NODE_CHILDREN_NODES(_node) \ + ((struct squat_node *)(NODE_CHILDREN_CHARS(_node) + \ + MEM_ALIGN((_node)->child_count))) +/* Return number of bytes allocated in node.children.data */ +#define NODE_CHILDREN_ALLOC_SIZE(child_count) \ + (MEM_ALIGN(child_count) + \ + ((child_count) / 8 + 1) * 8 * sizeof(struct squat_node)) +/* Return TRUE if children.leaf_string is set. */ +#define NODE_IS_DYNAMIC_LEAF(node) \ + ((node)->leaf_string_length > \ + sizeof((node)->children.static_leaf_string)) +/* Return node's leaf string. Assumes that it is set. */ +#define NODE_LEAF_STRING(node) \ + (NODE_IS_DYNAMIC_LEAF(node) ? \ + (node)->children.leaf_string : (node)->children.static_leaf_string) +struct squat_trie { + struct squat_node root; + struct squat_uidlist *uidlist; + + struct squat_file_header hdr; + size_t node_alloc_size; + unsigned int unmapped_child_count; + + enum squat_index_flags flags; + enum file_lock_method lock_method; + mode_t create_mode; + gid_t create_gid; + uint32_t uidvalidity; + + char *path; + int fd; + struct file_cache *file_cache; + struct dotlock_settings dotlock_set; + + uoff_t locked_file_size; + const void *data; + size_t data_size; + + void *mmap_base; + size_t mmap_size; + + unsigned char default_normalize_map[256]; + unsigned int default_partial_len; + unsigned int default_full_len; + + bool corrupted:1; +}; + +#define SQUAT_PACK_MAX_SIZE ((sizeof(uint32_t) * 8 + 7) / 7) + +static inline void squat_pack_num(uint8_t **p, uint32_t num) +{ + /* number continues as long as the highest bit is set */ + while (num >= 0x80) { + **p = (num & 0x7f) | 0x80; + *p += 1; + num >>= 7; + } + + **p = num; + *p += 1; +} + +static inline uint32_t squat_unpack_num(const uint8_t **p, const uint8_t *end) +{ + const uint8_t *c = *p; + uint32_t value = 0; + unsigned int bits = 0; + + for (;;) { + if (unlikely(c == end)) { + /* we should never see EOF */ + return 0; + } + + value |= (*c & 0x7f) << bits; + if (*c < 0x80) + break; + + bits += 7; + c++; + } + + if (unlikely(bits >= 32)) { + /* broken input */ + *p = end; + return 0; + } + + *p = c + 1; + return value; +} + +int squat_trie_create_fd(struct squat_trie *trie, const char *path, int flags); +void squat_trie_delete(struct squat_trie *trie); + +#endif diff --git a/src/plugins/fts-squat/squat-trie.c b/src/plugins/fts-squat/squat-trie.c new file mode 100644 index 0000000..d006817 --- /dev/null +++ b/src/plugins/fts-squat/squat-trie.c @@ -0,0 +1,2096 @@ +/* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "str.h" +#include "read-full.h" +#include "istream.h" +#include "ostream.h" +#include "unichar.h" +#include "nfs-workarounds.h" +#include "file-cache.h" +#include "seq-range-array.h" +#include "squat-uidlist.h" +#include "squat-trie-private.h" + +#include <stdio.h> +#include <unistd.h> +#include <sys/mman.h> + +#define DEFAULT_NORMALIZE_MAP_CHARS \ + "EOTIRSACDNLMVUGPHBFWYXKJQZ0123456789@.-+#$%_&" +#define DEFAULT_PARTIAL_LEN 4 +#define DEFAULT_FULL_LEN 4 + +#define MAX_FAST_LEVEL 3 +#define SEQUENTIAL_COUNT 46 + +#define TRIE_BYTES_LEFT(n) \ + ((n) * SQUAT_PACK_MAX_SIZE) +#define TRIE_READAHEAD_SIZE \ + I_MAX(4096, 1 + 256 + TRIE_BYTES_LEFT(256)) + +struct squat_trie_build_context { + struct squat_trie *trie; + struct ostream *output; + struct squat_uidlist_build_context *uidlist_build_ctx; + + struct file_lock *file_lock; + struct dotlock *dotlock; + + uint32_t first_uid; + bool compress_nodes:1; +}; + +struct squat_trie_iterate_node { + struct squat_node *node; + ARRAY_TYPE(seq_range) shifts; + unsigned int idx; +}; + +struct squat_trie_iterate_context { + struct squat_trie *trie; + struct squat_trie_iterate_node cur; + ARRAY(struct squat_trie_iterate_node) parents; + bool failed; +}; + +static int squat_trie_map(struct squat_trie *trie, bool building); + +void squat_trie_delete(struct squat_trie *trie) +{ + i_unlink_if_exists(trie->path); + squat_uidlist_delete(trie->uidlist); +} + +static void squat_trie_set_corrupted(struct squat_trie *trie) +{ + trie->corrupted = TRUE; + i_error("Corrupted file %s", trie->path); + squat_trie_delete(trie); +} + +static void squat_trie_normalize_map_build(struct squat_trie *trie) +{ + static unsigned char valid_chars[] = + DEFAULT_NORMALIZE_MAP_CHARS; + unsigned int i, j; + + memset(trie->default_normalize_map, 0, + sizeof(trie->default_normalize_map)); + +#if 1 + for (i = 0, j = 1; i < sizeof(valid_chars)-1; i++) { + unsigned char chr = valid_chars[i]; + + if (chr >= 'A' && chr <= 'Z') + trie->default_normalize_map[chr-'A'+'a'] = j; + trie->default_normalize_map[chr] = j++; + } + i_assert(j <= SEQUENTIAL_COUNT); + + for (i = 128; i < 256; i++) + trie->default_normalize_map[i] = j++; +#else + for (i = 0; i < sizeof(valid_chars)-1; i++) { + unsigned char chr = valid_chars[i]; + + if (chr >= 'A' && chr <= 'Z') + trie->default_normalize_map[chr-'A'+'a'] = chr; + trie->default_normalize_map[chr] = chr; + } + for (i = 128; i < 256; i++) + trie->default_normalize_map[i] = i_toupper(i); +#endif +} + +static void node_free(struct squat_trie *trie, struct squat_node *node) +{ + struct squat_node *children; + unsigned int i; + + if (node->leaf_string_length > 0) { + if (NODE_IS_DYNAMIC_LEAF(node)) + i_free(node->children.leaf_string); + } else if (!node->children_not_mapped) { + children = NODE_CHILDREN_NODES(node); + + trie->node_alloc_size -= + NODE_CHILDREN_ALLOC_SIZE(node->child_count); + for (i = 0; i < node->child_count; i++) + node_free(trie, &children[i]); + + i_free(node->children.data); + } +} + +struct squat_trie * +squat_trie_init(const char *path, uint32_t uidvalidity, + enum file_lock_method lock_method, enum squat_index_flags flags, + mode_t mode, gid_t gid) +{ + struct squat_trie *trie; + + trie = i_new(struct squat_trie, 1); + trie->path = i_strdup(path); + trie->uidlist = squat_uidlist_init(trie); + trie->fd = -1; + trie->lock_method = lock_method; + trie->uidvalidity = uidvalidity; + trie->flags = flags; + trie->create_mode = mode; + trie->create_gid = gid; + squat_trie_normalize_map_build(trie); + + trie->dotlock_set.use_excl_lock = + (flags & SQUAT_INDEX_FLAG_DOTLOCK_USE_EXCL) != 0; + trie->dotlock_set.nfs_flush = (flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0; + trie->dotlock_set.timeout = SQUAT_TRIE_LOCK_TIMEOUT; + trie->dotlock_set.stale_timeout = SQUAT_TRIE_DOTLOCK_STALE_TIMEOUT; + trie->default_partial_len = DEFAULT_PARTIAL_LEN; + trie->default_full_len = DEFAULT_FULL_LEN; + return trie; +} + +static void squat_trie_close_fd(struct squat_trie *trie) +{ + trie->data = NULL; + trie->data_size = 0; + + if (trie->mmap_size != 0) { + if (munmap(trie->mmap_base, trie->mmap_size) < 0) + i_error("munmap(%s) failed: %m", trie->path); + trie->mmap_base = NULL; + trie->mmap_size = 0; + } + i_close_fd_path(&trie->fd, trie->path); +} + +static void squat_trie_close(struct squat_trie *trie) +{ + trie->corrupted = FALSE; + node_free(trie, &trie->root); + i_zero(&trie->root); + i_zero(&trie->hdr); + + squat_trie_close_fd(trie); + if (trie->file_cache != NULL) + file_cache_free(&trie->file_cache); + trie->locked_file_size = 0; +} + +void squat_trie_deinit(struct squat_trie **_trie) +{ + struct squat_trie *trie = *_trie; + + *_trie = NULL; + squat_trie_close(trie); + squat_uidlist_deinit(trie->uidlist); + i_free(trie->path); + i_free(trie); +} + +void squat_trie_set_partial_len(struct squat_trie *trie, unsigned int len) +{ + trie->default_partial_len = len; +} + +void squat_trie_set_full_len(struct squat_trie *trie, unsigned int len) +{ + trie->default_full_len = len; +} + +static void squat_trie_header_init(struct squat_trie *trie) +{ + i_zero(&trie->hdr); + trie->hdr.version = SQUAT_TRIE_VERSION; + trie->hdr.indexid = time(NULL); + trie->hdr.uidvalidity = trie->uidvalidity; + trie->hdr.partial_len = trie->default_partial_len; + trie->hdr.full_len = trie->default_full_len; + + i_assert(sizeof(trie->hdr.normalize_map) == + sizeof(trie->default_normalize_map)); + memcpy(trie->hdr.normalize_map, trie->default_normalize_map, + sizeof(trie->hdr.normalize_map)); +} + +static int squat_trie_open_fd(struct squat_trie *trie) +{ + trie->fd = open(trie->path, O_RDWR); + if (trie->fd == -1) { + if (errno == ENOENT) { + squat_trie_header_init(trie); + return 0; + } + i_error("open(%s) failed: %m", trie->path); + return -1; + } + if (trie->file_cache != NULL) + file_cache_set_fd(trie->file_cache, trie->fd); + return 0; +} + +int squat_trie_open(struct squat_trie *trie) +{ + squat_trie_close(trie); + + if (squat_trie_open_fd(trie) < 0) + return -1; + return squat_trie_map(trie, FALSE); +} + +static int squat_trie_is_file_stale(struct squat_trie *trie) +{ + struct stat st, st2; + + if ((trie->flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0) + nfs_flush_file_handle_cache(trie->path); + if (nfs_safe_stat(trie->path, &st) < 0) { + if (errno == ENOENT) + return 1; + + i_error("stat(%s) failed: %m", trie->path); + return -1; + } + if (fstat(trie->fd, &st2) < 0) { + if (errno == ESTALE) + return 1; + i_error("fstat(%s) failed: %m", trie->path); + return -1; + } + trie->locked_file_size = st2.st_size; + + if (st.st_ino == st2.st_ino && CMP_DEV_T(st.st_dev, st2.st_dev)) { + i_assert(trie->locked_file_size >= trie->data_size); + return 0; + } + return 1; +} + +int squat_trie_refresh(struct squat_trie *trie) +{ + int ret; + + ret = squat_trie_is_file_stale(trie); + if (ret > 0) + ret = squat_trie_open(trie); + return ret; +} + +static int squat_trie_lock(struct squat_trie *trie, int lock_type, + struct file_lock **file_lock_r, + struct dotlock **dotlock_r) +{ + const char *error; + int ret; + + i_assert(trie->fd != -1); + + *file_lock_r = NULL; + *dotlock_r = NULL; + + for (;;) { + if (trie->lock_method != FILE_LOCK_METHOD_DOTLOCK) { + struct file_lock_settings lock_set = { + .lock_method = trie->lock_method, + }; + ret = file_wait_lock(trie->fd, trie->path, lock_type, + &lock_set, SQUAT_TRIE_LOCK_TIMEOUT, + file_lock_r, &error); + if (ret < 0) { + i_error("squat trie %s: %s", + trie->path, error); + } + } else { + ret = file_dotlock_create(&trie->dotlock_set, + trie->path, 0, dotlock_r); + } + if (ret == 0) { + i_error("squat trie %s: Locking timed out", trie->path); + return 0; + } + if (ret < 0) + return -1; + + /* if the trie has been compressed, we need to reopen the + file and try to lock again */ + ret = squat_trie_is_file_stale(trie); + if (ret == 0) + break; + + if (*file_lock_r != NULL) + file_unlock(file_lock_r); + else + file_dotlock_delete(dotlock_r); + if (ret < 0) + return -1; + + squat_trie_close(trie); + if (squat_trie_open_fd(trie) < 0) + return -1; + if (trie->fd == -1) + return 0; + } + + if ((trie->flags & SQUAT_INDEX_FLAG_NFS_FLUSH) != 0) + nfs_flush_read_cache_locked(trie->path, trie->fd); + return 1; +} + +static void +node_make_sequential(struct squat_trie *trie, struct squat_node *node, int level) +{ + const unsigned int alloc_size = + NODE_CHILDREN_ALLOC_SIZE(SEQUENTIAL_COUNT); + struct squat_node *children; + unsigned char *chars; + unsigned int i; + + i_assert(node->child_count == 0); + + trie->node_alloc_size += alloc_size; + + node->want_sequential = FALSE; + node->have_sequential = TRUE; + + node->child_count = SEQUENTIAL_COUNT; + node->children.data = i_malloc(alloc_size); + + chars = NODE_CHILDREN_CHARS(node); + for (i = 0; i < SEQUENTIAL_COUNT; i++) + chars[i] = i; + + if (level < MAX_FAST_LEVEL) { + children = NODE_CHILDREN_NODES(node); + for (i = 0; i < SEQUENTIAL_COUNT; i++) + children[i].want_sequential = TRUE; + } +} + +static unsigned int +node_add_child(struct squat_trie *trie, struct squat_node *node, + unsigned char chr, int level) +{ + unsigned int old_child_count = node->child_count; + struct squat_node *children, *old_children; + unsigned char *chars; + size_t old_size, new_size; + + i_assert(node->leaf_string_length == 0); + + if (node->want_sequential) { + node_make_sequential(trie, node, level); + + if (chr < SEQUENTIAL_COUNT) + return chr; + old_child_count = SEQUENTIAL_COUNT; + } + + node->child_count++; + new_size = NODE_CHILDREN_ALLOC_SIZE(node->child_count); + + if (old_child_count == 0) { + /* first child */ + node->children.data = i_malloc(new_size); + trie->node_alloc_size += new_size; + } else { + old_size = NODE_CHILDREN_ALLOC_SIZE(old_child_count); + if (old_size != new_size) { + trie->node_alloc_size += new_size - old_size; + node->children.data = i_realloc(node->children.data, + old_size, new_size); + } + + children = NODE_CHILDREN_NODES(node); + old_children = (void *)(NODE_CHILDREN_CHARS(node) + + MEM_ALIGN(old_child_count)); + if (children != old_children) { + memmove(children, old_children, + old_child_count * sizeof(struct squat_node)); + } + } + + chars = NODE_CHILDREN_CHARS(node); + i_assert(chars != NULL); + chars[node->child_count - 1] = chr; + return node->child_count - 1; +} + +static int +trie_file_cache_read(struct squat_trie *trie, size_t offset, size_t size) +{ + if (trie->file_cache == NULL) + return 0; + + if (file_cache_read(trie->file_cache, offset, size) < 0) { + i_error("read(%s) failed: %m", trie->path); + return -1; + } + trie->data = file_cache_get_map(trie->file_cache, &trie->data_size); + return 0; +} + +static int +node_read_children(struct squat_trie *trie, struct squat_node *node, int level) +{ + const uint8_t *data, *end; + const unsigned char *child_chars; + struct squat_node *child, *children = NULL; + uoff_t node_offset; + unsigned int i, child_idx, child_count; + uoff_t base_offset; + uint32_t num; + + i_assert(node->children_not_mapped); + i_assert(!node->have_sequential); + i_assert(trie->unmapped_child_count > 0); + i_assert(trie->data_size <= trie->locked_file_size); + + trie->unmapped_child_count--; + node_offset = node->children.offset; + node->children_not_mapped = FALSE; + node->children.data = NULL; + + if (trie_file_cache_read(trie, node_offset, TRIE_READAHEAD_SIZE) < 0) + return -1; + if (unlikely(node_offset >= trie->data_size)) { + squat_trie_set_corrupted(trie); + return -1; + } + + data = CONST_PTR_OFFSET(trie->data, node_offset); + end = CONST_PTR_OFFSET(trie->data, trie->data_size); + child_count = *data++; + if (unlikely(node_offset + child_count >= trie->data_size)) { + squat_trie_set_corrupted(trie); + return -1; + } + + if (child_count == 0) + return 0; + + child_chars = data; + data += child_count; + + /* get child offsets */ + base_offset = node_offset; + for (i = 0; i < child_count; i++) { + /* we always start with !have_sequential, so at i=0 this + check always goes to add the first child */ + if (node->have_sequential && child_chars[i] < SEQUENTIAL_COUNT) + child_idx = child_chars[i]; + else { + child_idx = node_add_child(trie, node, child_chars[i], + level); + children = NODE_CHILDREN_NODES(node); + } + + i_assert(children != NULL); + + child = &children[child_idx]; + + /* 1) child offset */ + num = squat_unpack_num(&data, end); + if (num == 0) { + /* no children */ + } else { + if ((num & 1) != 0) { + base_offset += num >> 1; + } else { + base_offset -= num >> 1; + } + if (base_offset >= trie->locked_file_size) { + squat_trie_set_corrupted(trie); + return -1; + } + trie->unmapped_child_count++; + child->children_not_mapped = TRUE; + child->children.offset = base_offset; + } + + /* 2) uidlist */ + child->uid_list_idx = squat_unpack_num(&data, end); + if (child->uid_list_idx == 0) { + /* we don't write nodes with empty uidlists */ + squat_trie_set_corrupted(trie); + return -1; + } + if (!UIDLIST_IS_SINGLETON(child->uid_list_idx)) { + /* 3) next uid */ + child->next_uid = squat_unpack_num(&data, end) + 1; + } else { + uint32_t idx = child->uid_list_idx; + + child->next_uid = 1 + + squat_uidlist_singleton_last_uid(idx); + } + + /* 4) unused uids + leaf string flag */ + num = squat_unpack_num(&data, end); + child->unused_uids = num >> 1; + if ((num & 1) != 0) { + /* leaf string */ + unsigned int len; + unsigned char *dest; + + /* 5) leaf string length */ + len = child->leaf_string_length = + squat_unpack_num(&data, end) + 1; + if (!NODE_IS_DYNAMIC_LEAF(child)) + dest = child->children.static_leaf_string; + else { + dest = child->children.leaf_string = + i_malloc(len); + } + + if (trie->file_cache != NULL) { + /* the string may be long - + recalculate the end pos */ + size_t offset, size; + + offset = (const char *)data - + (const char *)trie->data; + size = len + TRIE_BYTES_LEFT(child_count - i); + + if (trie_file_cache_read(trie, offset, + size) < 0) + return -1; + data = CONST_PTR_OFFSET(trie->data, offset); + end = CONST_PTR_OFFSET(trie->data, + trie->data_size); + child_chars = CONST_PTR_OFFSET(trie->data, + node_offset + 1); + } + + if ((size_t)(end - data) < len) { + squat_trie_set_corrupted(trie); + return -1; + } + memcpy(dest, data, len); + data += len; + } + } + if (unlikely(data == end)) { + /* we should never get this far */ + squat_trie_set_corrupted(trie); + return -1; + } + return 0; +} + +static void +node_write_children(struct squat_trie_build_context *ctx, + struct squat_node *node, const uoff_t *node_offsets) +{ + struct squat_node *children; + const unsigned char *chars; + uint8_t child_count, buf[SQUAT_PACK_MAX_SIZE * 5], *bufp; + uoff_t base_offset; + unsigned int i; + + chars = NODE_CHILDREN_CHARS(node); + children = NODE_CHILDREN_NODES(node); + + base_offset = ctx->output->offset; + child_count = node->child_count; + o_stream_nsend(ctx->output, &child_count, 1); + o_stream_nsend(ctx->output, chars, child_count); + + for (i = 0; i < child_count; i++) { + bufp = buf; + /* 1) child offset */ + if (node_offsets[i] == 0) + *bufp++ = 0; + else if (node_offsets[i] >= base_offset) { + squat_pack_num(&bufp, + ((node_offsets[i] - base_offset) << 1) | 1); + base_offset = node_offsets[i]; + } else { + squat_pack_num(&bufp, + (base_offset - node_offsets[i]) << 1); + base_offset = node_offsets[i]; + } + + /* 2) uidlist */ + squat_pack_num(&bufp, children[i].uid_list_idx); + if (!UIDLIST_IS_SINGLETON(children[i].uid_list_idx)) { + /* 3) next uid */ + squat_pack_num(&bufp, children[i].next_uid - 1); + } + + if (children[i].leaf_string_length == 0) { + /* 4a) unused uids */ + squat_pack_num(&bufp, children[i].unused_uids << 1); + o_stream_nsend(ctx->output, buf, bufp - buf); + } else { + i_assert(node_offsets[i] == 0); + /* 4b) unused uids + flag */ + squat_pack_num(&bufp, (children[i].unused_uids << 1) | 1); + /* 5) leaf string length */ + squat_pack_num(&bufp, children[i].leaf_string_length - 1); + o_stream_nsend(ctx->output, buf, bufp - buf); + o_stream_nsend(ctx->output, + NODE_LEAF_STRING(&children[i]), + children[i].leaf_string_length); + } + } +} + +static inline void +node_add_uid(struct squat_trie_build_context *ctx, uint32_t uid, + struct squat_node *node) +{ + if (uid < node->next_uid) { + /* duplicate */ + return; + } + node->unused_uids += uid - node->next_uid; + node->next_uid = uid + 1; + + node->uid_list_idx = + squat_uidlist_build_add_uid(ctx->uidlist_build_ctx, + node->uid_list_idx, uid); +} + +static void +node_split_string(struct squat_trie_build_context *ctx, struct squat_node *node) +{ + struct squat_node *child; + unsigned char *str; + unsigned int uid, idx, leafstr_len = node->leaf_string_length; + + i_assert(leafstr_len > 0); + + /* make a copy of the leaf string and convert to normal node by + removing it. */ + str = t_malloc_no0(leafstr_len); + if (!NODE_IS_DYNAMIC_LEAF(node)) + memcpy(str, node->children.static_leaf_string, leafstr_len); + else { + memcpy(str, node->children.leaf_string, leafstr_len); + i_free(node->children.leaf_string); + } + node->leaf_string_length = 0; + + /* create a new child node for the rest of the string */ + idx = node_add_child(ctx->trie, node, str[0], MAX_FAST_LEVEL); + child = NODE_CHILDREN_NODES(node) + idx; + + /* update uidlist to contain all of parent's UIDs */ + child->next_uid = node->next_uid - node->unused_uids; + for (uid = 0; uid < child->next_uid; uid++) { + child->uid_list_idx = + squat_uidlist_build_add_uid(ctx->uidlist_build_ctx, + child->uid_list_idx, uid); + } + + i_assert(!child->have_sequential && child->children.data == NULL); + if (leafstr_len > 1) { + /* make the child a leaf string */ + leafstr_len--; + child->leaf_string_length = leafstr_len; + if (!NODE_IS_DYNAMIC_LEAF(child)) { + memcpy(child->children.static_leaf_string, + str + 1, leafstr_len); + } else { + child->children.leaf_string = i_malloc(leafstr_len); + memcpy(child->children.leaf_string, + str + 1, leafstr_len); + } + } +} + +static bool +node_leaf_string_add_or_split(struct squat_trie_build_context *ctx, + struct squat_node *node, + const unsigned char *data, unsigned int data_len) +{ + const unsigned char *str = NODE_LEAF_STRING(node); + const unsigned int leafstr_len = node->leaf_string_length; + unsigned int i; + + if (data_len != leafstr_len) { + /* different lengths, can't match */ + T_BEGIN { + node_split_string(ctx, node); + } T_END; + return FALSE; + } + + for (i = 0; i < data_len; i++) { + if (data[i] != str[i]) { + /* non-match */ + T_BEGIN { + node_split_string(ctx, node); + } T_END; + return FALSE; + } + } + return TRUE; +} + +static int squat_build_add(struct squat_trie_build_context *ctx, uint32_t uid, + const unsigned char *data, unsigned int size) +{ + struct squat_trie *trie = ctx->trie; + struct squat_node *node = &trie->root; + const unsigned char *end = data + size; + unsigned char *chars; + unsigned int idx; + int level = 0; + + for (;;) { + if (node->children_not_mapped) { + if (unlikely(node_read_children(trie, node, level) < 0)) + return -1; + } + + if (node->leaf_string_length != 0) { + /* the whole string must match or we need to split + the node */ + if (node_leaf_string_add_or_split(ctx, node, data, + end - data)) { + node_add_uid(ctx, uid, node); + return 0; + } + } + + node_add_uid(ctx, uid, node); + + if (unlikely(uid < node->unused_uids)) { + squat_trie_set_corrupted(trie); + return -1; + } + /* child node's UIDs are relative to ours. so for example if + we're adding UID 4 and this node now has [2,4] UIDs, + unused_uids=3 and so the child node will be adding + UID 4-3 = 1. */ + uid -= node->unused_uids; + + if (data == end) + return 0; + level++; + + if (node->have_sequential) { + i_assert(node->child_count >= SEQUENTIAL_COUNT); + if (*data < SEQUENTIAL_COUNT) { + idx = *data; + goto found; + } + idx = SEQUENTIAL_COUNT; + } else { + idx = 0; + } + chars = NODE_CHILDREN_CHARS(node); + for (; idx < node->child_count; idx++) { + if (chars[idx] == *data) + goto found; + } + break; + found: + data++; + node = NODE_CHILDREN_NODES(node) + idx; + } + + /* create new children */ + i_assert(node->leaf_string_length == 0); + + for (;;) { + idx = node_add_child(trie, node, *data, + size - (end - data) + 1); + node = NODE_CHILDREN_NODES(node) + idx; + + node_add_uid(ctx, uid, node); + uid = 0; + + if (++data == end) + break; + + if (!node->have_sequential) { + /* convert the node into a leaf string */ + unsigned int len = end - data; + + i_assert(node->children.data == NULL); + node->leaf_string_length = len; + if (!NODE_IS_DYNAMIC_LEAF(node)) { + memcpy(node->children.static_leaf_string, + data, len); + } else { + node->children.leaf_string = i_malloc(len); + memcpy(node->children.leaf_string, data, len); + } + break; + } + } + return 0; +} + +static int +squat_build_word_bytes(struct squat_trie_build_context *ctx, uint32_t uid, + const unsigned char *data, unsigned int size) +{ + struct squat_trie *trie = ctx->trie; + unsigned int i; + + if (trie->hdr.full_len <= trie->hdr.partial_len) + i = 0; + else { + /* the first word is longer than others */ + if (squat_build_add(ctx, uid, data, + I_MIN(size, trie->hdr.full_len)) < 0) + return -1; + i = 1; + } + + for (; i < size; i++) { + if (squat_build_add(ctx, uid, data + i, + I_MIN(trie->hdr.partial_len, size-i)) < 0) + return -1; + } + return 0; +} + +static int +squat_build_word(struct squat_trie_build_context *ctx, uint32_t uid, + const unsigned char *data, const uint8_t *char_lengths, + unsigned int size) +{ + struct squat_trie *trie = ctx->trie; + unsigned int i, j, bytelen; + + if (char_lengths == NULL) { + /* optimization path: all characters are bytes */ + return squat_build_word_bytes(ctx, uid, data, size); + } + + if (trie->hdr.full_len <= trie->hdr.partial_len) + i = 0; + else { + /* the first word is longer than others */ + bytelen = 0; + for (j = 0; j < trie->hdr.full_len && bytelen < size; j++) + bytelen += char_lengths[bytelen]; + i_assert(bytelen <= size); + + if (squat_build_add(ctx, uid, data, bytelen) < 0) + return -1; + i = char_lengths[0]; + } + + for (; i < size; i += char_lengths[i]) { + bytelen = 0; + for (j = 0; j < trie->hdr.partial_len && i+bytelen < size; j++) + bytelen += char_lengths[i + bytelen]; + i_assert(i + bytelen <= size); + + if (squat_build_add(ctx, uid, data + i, bytelen) < 0) + return -1; + } + return 0; +} + +static unsigned char * +squat_data_normalize(struct squat_trie *trie, const unsigned char *data, + unsigned int size) +{ + static const unsigned char replacement_utf8[] = { 0xef, 0xbf, 0xbd }; + unsigned char *dest; + unsigned int i; + + dest = t_malloc_no0(size); + for (i = 0; i < size; i++) { + if (data[i] == replacement_utf8[0] && i + 2 < size && + data[i+1] == replacement_utf8[1] && + data[i+2] == replacement_utf8[2]) { + /* Don't index replacement character */ + dest[i++] = 0; + dest[i++] = 0; + dest[i] = 0; + } else { + dest[i] = trie->hdr.normalize_map[data[i]]; + } + } + return dest; +} + +static int +squat_trie_build_more_real(struct squat_trie_build_context *ctx, + uint32_t uid, enum squat_index_type type, + const unsigned char *input, unsigned int size) +{ + struct squat_trie *trie = ctx->trie; + const unsigned char *data; + uint8_t *char_lengths; + unsigned int i, start = 0; + bool multibyte_chars = FALSE; + int ret = 0; + + uid = uid * 2 + (type == SQUAT_INDEX_TYPE_HEADER ? 1 : 0); + + char_lengths = t_malloc_no0(size); + data = squat_data_normalize(trie, input, size); + for (i = 0; i < size; i++) { + char_lengths[i] = uni_utf8_char_bytes(input[i]); + if (char_lengths[i] != 1) + multibyte_chars = TRUE; + if (data[i] != '\0') + continue; + + while (start < i && data[start] == '\0') + start++; + if (i != start) { + if (squat_build_word(ctx, uid, data + start, + !multibyte_chars ? NULL : + char_lengths + start, + i - start) < 0) { + ret = -1; + start = i; + break; + } + } + start = i + 1; + } + while (start < i && data[start] == '\0') + start++; + if (i != start) { + if (squat_build_word(ctx, uid, data + start, + !multibyte_chars ? NULL : + char_lengths + start, i - start) < 0) + ret = -1; + } + return ret; +} + +int squat_trie_build_more(struct squat_trie_build_context *ctx, + uint32_t uid, enum squat_index_type type, + const unsigned char *input, unsigned int size) +{ + int ret = 0; + + if (size != 0) T_BEGIN { + ret = squat_trie_build_more_real(ctx, uid, type, input, size); + } T_END; + return ret; +} + +static void +node_drop_unused_children(struct squat_trie *trie, struct squat_node *node) +{ + unsigned char *chars; + struct squat_node *children_src, *children_dest; + unsigned int i, j, orig_child_count = node->child_count; + + chars = NODE_CHILDREN_CHARS(node); + children_src = NODE_CHILDREN_NODES(node); + + /* move chars */ + for (i = j = 0; i < orig_child_count; i++) { + if (children_src[i].next_uid != 0) + chars[j++] = chars[i]; + } + node->child_count = j; + + /* move children. note that children_dest may point to different + location than children_src, although they both point to the + same node. */ + children_dest = NODE_CHILDREN_NODES(node); + for (i = j = 0; i < orig_child_count; i++) { + if (children_src[i].next_uid != 0) + children_dest[j++] = children_src[i]; + else + node_free(trie, &children_src[i]); + } +} + +static int +squat_write_node(struct squat_trie_build_context *ctx, struct squat_node *node, + uoff_t *node_offset_r, int level) +{ + struct squat_trie *trie = ctx->trie; + struct squat_node *children; + unsigned int i; + uoff_t *node_offsets; + uint8_t child_count; + int ret; + + i_assert(node->next_uid != 0); + + if (node->children_not_mapped && ctx->compress_nodes) { + if (node_read_children(trie, node, MAX_FAST_LEVEL) < 0) + return -1; + } + + node->have_sequential = FALSE; + node_drop_unused_children(trie, node); + + child_count = node->child_count; + if (child_count == 0) { + i_assert(!node->children_not_mapped || + node->leaf_string_length == 0); + *node_offset_r = !node->children_not_mapped ? 0 : + node->children.offset; + return 0; + } + i_assert(!node->children_not_mapped); + + trie->hdr.node_count++; + + children = NODE_CHILDREN_NODES(node); + node_offsets = t_new(uoff_t, child_count); + for (i = 0; i < child_count; i++) { + T_BEGIN { + ret = squat_write_node(ctx, &children[i], + &node_offsets[i], level + 1); + } T_END; + if (ret < 0) + return -1; + } + + *node_offset_r = ctx->output->offset; + node_write_children(ctx, node, node_offsets); + return 0; +} + +static int squat_write_nodes(struct squat_trie_build_context *ctx) +{ + struct squat_trie *trie = ctx->trie; + uoff_t node_offset; + int ret; + + if (ctx->trie->root.next_uid == 0) + return 0; + + T_BEGIN { + ret = squat_write_node(ctx, &ctx->trie->root, &node_offset, 0); + } T_END; + if (ret < 0) + return -1; + + trie->hdr.root_offset = node_offset; + trie->hdr.root_unused_uids = trie->root.unused_uids; + trie->hdr.root_next_uid = trie->root.next_uid; + trie->hdr.root_uidlist_idx = trie->root.uid_list_idx; + return 0; +} + +static struct squat_trie_iterate_context * +squat_trie_iterate_init(struct squat_trie *trie) +{ + struct squat_trie_iterate_context *ctx; + + ctx = i_new(struct squat_trie_iterate_context, 1); + ctx->trie = trie; + ctx->cur.node = &trie->root; + i_array_init(&ctx->parents, trie->hdr.partial_len*2); + return ctx; +} + +static int +squat_trie_iterate_deinit(struct squat_trie_iterate_context *ctx) +{ + struct squat_trie_iterate_node *node; + int ret = ctx->failed ? -1 : 0; + + if (array_is_created(&ctx->cur.shifts)) { + array_foreach_modifiable(&ctx->parents, node) + array_free(&node->shifts); + array_free(&ctx->cur.shifts); + } + array_free(&ctx->parents); + i_free(ctx); + return ret; +} + +static struct squat_node * +squat_trie_iterate_first(struct squat_trie_iterate_context *ctx) +{ + if (ctx->cur.node->children_not_mapped) { + if (node_read_children(ctx->trie, ctx->cur.node, 1) < 0) { + ctx->failed = TRUE; + return NULL; + } + } + return ctx->cur.node; +} + +static struct squat_node * +squat_trie_iterate_next(struct squat_trie_iterate_context *ctx, + ARRAY_TYPE(seq_range) *shifts_r) +{ + struct squat_trie_iterate_node *iter_nodes; + struct squat_node *children; + unsigned int count, shift_count = 0; + + while (ctx->cur.idx == ctx->cur.node->child_count || + ctx->cur.node->uid_list_idx == 0) + { + iter_nodes = array_get_modifiable(&ctx->parents, &count); + if (count == 0) + return NULL; + + if (array_is_created(&ctx->cur.shifts)) + array_free(&ctx->cur.shifts); + ctx->cur = iter_nodes[count-1]; + array_delete(&ctx->parents, count-1, 1); + } + + *shifts_r = ctx->cur.shifts; + if (array_is_created(&ctx->cur.shifts)) + shift_count = array_count(&ctx->cur.shifts); + + children = NODE_CHILDREN_NODES(ctx->cur.node); + while (children[ctx->cur.idx++].uid_list_idx == 0) { + if (ctx->cur.idx == ctx->cur.node->child_count) { + /* no more non-empty children in this node */ + return squat_trie_iterate_next(ctx, shifts_r); + } + } + array_push_back(&ctx->parents, &ctx->cur); + ctx->cur.node = &children[ctx->cur.idx-1]; + ctx->cur.idx = 0; + if (shift_count != 0) + i_array_init(&ctx->cur.shifts, shift_count); + else + i_zero(&ctx->cur.shifts); + return squat_trie_iterate_first(ctx); +} + +static void +squat_uidlist_update_expunged_uids(const ARRAY_TYPE(seq_range) *shifts_arr, + ARRAY_TYPE(seq_range) *child_shifts, + ARRAY_TYPE(seq_range) *uids_arr, + struct squat_trie *trie, + struct squat_node *node, bool do_shifts) +{ + const struct seq_range *shifts; + struct seq_range *uids, shift; + unsigned int i, uid_idx, uid_count, shift_count; + uint32_t child_shift_seq1, child_shift_count, seq_high; + unsigned int shift_sum = 0, child_sum = 0; + + if (!array_is_created(shifts_arr)) { + i_assert(node->uid_list_idx != 0 || node->child_count == 0); + return; + } + + /* we'll recalculate this */ + node->unused_uids = 0; + + uids = array_get_modifiable(uids_arr, &uid_count); + shifts = array_get(shifts_arr, &shift_count); + for (i = 0, uid_idx = 0, seq_high = 0;; ) { + /* skip UID ranges until we skip/overlap shifts */ + while (uid_idx < uid_count && + (i == shift_count || + I_MAX(shifts[i].seq1, seq_high) > uids[uid_idx].seq2)) + { + i_assert(uids[uid_idx].seq1 >= shift_sum); + uids[uid_idx].seq1 -= shift_sum; + uids[uid_idx].seq2 -= shift_sum; + child_sum += uids[uid_idx].seq2 - + uids[uid_idx].seq1 + 1; + + if (uid_idx > 0 && + uids[uid_idx-1].seq2 >= uids[uid_idx].seq1 - 1) { + /* we can merge this and the previous range */ + i_assert(uids[uid_idx-1].seq2 == + uids[uid_idx].seq1 - 1); + uids[uid_idx-1].seq2 = uids[uid_idx].seq2; + array_delete(uids_arr, uid_idx, 1); + uids = array_get_modifiable(uids_arr, + &uid_count); + } else { + if (uid_idx == 0) + node->unused_uids += uids[0].seq1; + else { + node->unused_uids += + uids[uid_idx].seq1 - + uids[uid_idx-1].seq2 - 1; + } + uid_idx++; + } + } + if (uid_idx == uid_count) + break; + + shift.seq1 = I_MAX(shifts[i].seq1, seq_high); + shift.seq2 = shifts[i].seq2; + if (shift.seq2 < uids[uid_idx].seq1) { + /* shift is entirely before UID range */ + shift_sum += shift.seq2 - shift.seq1 + 1; + i++; + } else { + /* handle shifts before UID range */ + if (shift.seq1 < uids[uid_idx].seq1) { + shift_sum += uids[uid_idx].seq1 - shift.seq1; + shift.seq1 = uids[uid_idx].seq1; + } + /* update child shifts */ + child_shift_seq1 = child_sum + + shift.seq1 - uids[uid_idx].seq1; + child_shift_count = + I_MIN(shift.seq2, uids[uid_idx].seq2) - + shift.seq1 + 1; + seq_range_array_add_range(child_shifts, + child_shift_seq1, + child_shift_seq1 + + child_shift_count - 1); + child_sum += child_shift_count; + + /* if the shifts continue after the UID range, + treat it in the next loop iteration */ + if (shift.seq2 <= uids[uid_idx].seq2) + i++; + else + seq_high = uids[uid_idx].seq2 + 1; + + /* update UIDs - no matter where within the UID range + the shifts happened, the result is the same: + shift number of UIDs are removed, and the rest + are decreased by shift_sum. + + 123 uids child_shifts + a) s -> 12 1 + b) s -> 12 2 + c) s -> 12 3 + */ + if (uids[uid_idx].seq1 + + child_shift_count > uids[uid_idx].seq2) { + /* removed completely */ + array_delete(uids_arr, uid_idx, 1); + uids = array_get_modifiable(uids_arr, + &uid_count); + } else if (do_shifts) { + /* the next loop iteration fixes the UIDs */ + uids[uid_idx].seq1 += child_shift_count; + } else { + seq_range_array_remove_range(uids_arr, + shift.seq1, + I_MIN(shift.seq2, uids[uid_idx].seq2)); + uids = array_get_modifiable(uids_arr, + &uid_count); + } + shift_sum += child_shift_count; + } + if (!do_shifts) { + /* root node - UIDs are only removed, not shifted */ + shift_sum = 0; + } + } + + if (uid_count == 0) { + /* no UIDs left, delete the node's children and mark it + unused */ + if (!NODE_IS_DYNAMIC_LEAF(node)) + node_free(trie, node); + + node->child_count = 0; + node->have_sequential = FALSE; + node->next_uid = 0; + } else { + if (do_shifts) + node->next_uid = uids[uid_count-1].seq2 + 1; + else { + node->unused_uids += (node->next_uid - 1) - + uids[uid_count-1].seq2; + } + } +} + +static int +squat_trie_expunge_uidlists(struct squat_trie_build_context *ctx, + struct squat_uidlist_rebuild_context *rebuild_ctx, + struct squat_trie_iterate_context *iter, + const ARRAY_TYPE(seq_range) *expunged_uids) +{ + struct squat_node *node; + ARRAY_TYPE(seq_range) uid_range, root_shifts, shifts; + bool shift = FALSE; + int ret = 0; + + node = squat_trie_iterate_first(iter); + if (node->uid_list_idx == 0) + return 0; + + i_array_init(&uid_range, 1024); + i_array_init(&root_shifts, array_count(expunged_uids)); + array_append_array(&root_shifts, expunged_uids); + + if (array_count(expunged_uids) > 0) + i_array_init(&iter->cur.shifts, array_count(expunged_uids)); + + shifts = root_shifts; + do { + i_assert(node->uid_list_idx != 0); + array_clear(&uid_range); + if (squat_uidlist_get_seqrange(ctx->trie->uidlist, + node->uid_list_idx, + &uid_range) < 0) { + ret = -1; + break; + } + squat_uidlist_update_expunged_uids(&shifts, &iter->cur.shifts, + &uid_range, ctx->trie, node, + shift); + node->uid_list_idx = + squat_uidlist_rebuild_nextu(rebuild_ctx, &uid_range); + i_assert(node->uid_list_idx != 0 || node->next_uid == 0); + + node = squat_trie_iterate_next(iter, &shifts); + shift = TRUE; + } while (node != NULL); + array_free(&uid_range); + array_free(&root_shifts); + return ret; +} + +static int +squat_trie_renumber_uidlists2(struct squat_trie_build_context *ctx, + struct squat_uidlist_rebuild_context *rebuild_ctx, + struct squat_trie_iterate_context *iter) +{ + struct squat_node *node; + ARRAY_TYPE(seq_range) shifts; + ARRAY_TYPE(uint32_t) uids; + int ret = 0; + + node = squat_trie_iterate_first(iter); + if (node->uid_list_idx == 0) + return 0; + + i_array_init(&uids, 1024); + while (node != NULL) { + i_assert(node->uid_list_idx != 0); + if (!UIDLIST_IS_SINGLETON(node->uid_list_idx)) { + /* rebuild the uidlist */ + array_clear(&uids); + if (squat_uidlist_get(ctx->trie->uidlist, + node->uid_list_idx, &uids) < 0) { + ret = -1; + break; + } + node->uid_list_idx = + squat_uidlist_rebuild_next(rebuild_ctx, &uids); + } + node = squat_trie_iterate_next(iter, &shifts); + } + array_free(&uids); + return ret; +} + +static int +squat_trie_renumber_uidlists(struct squat_trie_build_context *ctx, + const ARRAY_TYPE(seq_range) *expunged_uids, + bool compress) +{ + struct squat_trie_iterate_context *iter; + struct squat_uidlist_rebuild_context *rebuild_ctx; + time_t now; + int ret = 0; + + if ((ret = squat_uidlist_rebuild_init(ctx->uidlist_build_ctx, + compress, &rebuild_ctx)) <= 0) + return ret; + + now = time(NULL); + ctx->trie->hdr.indexid = + I_MAX((unsigned int)now, ctx->trie->hdr.indexid + 1); + + iter = squat_trie_iterate_init(ctx->trie); + if (expunged_uids != NULL) { + ret = squat_trie_expunge_uidlists(ctx, rebuild_ctx, iter, + expunged_uids); + } else { + ret = squat_trie_renumber_uidlists2(ctx, rebuild_ctx, iter); + } + if (squat_trie_iterate_deinit(iter) < 0) + ret = -1; + + /* lock the trie before we rename uidlist */ + i_assert(ctx->file_lock == NULL && ctx->dotlock == NULL); + if (squat_trie_lock(ctx->trie, F_WRLCK, + &ctx->file_lock, &ctx->dotlock) <= 0) + ret = -1; + return squat_uidlist_rebuild_finish(rebuild_ctx, ret < 0); +} + +static bool squat_trie_check_header(struct squat_trie *trie) +{ + if (trie->hdr.version != SQUAT_TRIE_VERSION || + trie->hdr.uidvalidity != trie->uidvalidity) + return FALSE; + + if (trie->hdr.partial_len > trie->hdr.full_len) { + i_error("Corrupted %s: partial len > full len", trie->path); + return FALSE; + } + if (trie->hdr.full_len == 0) { + i_error("Corrupted %s: full len=0", trie->path); + return FALSE; + } + return TRUE; +} + +static int squat_trie_map_header(struct squat_trie *trie) +{ + int ret; + + if (trie->locked_file_size == 0) { + /* newly created file */ + squat_trie_header_init(trie); + return 1; + } + i_assert(trie->fd != -1); + + if ((trie->flags & SQUAT_INDEX_FLAG_MMAP_DISABLE) != 0) { + ret = pread_full(trie->fd, &trie->hdr, sizeof(trie->hdr), 0); + if (ret <= 0) { + if (ret < 0) { + i_error("pread(%s) failed: %m", trie->path); + return -1; + } + i_error("Corrupted %s: File too small", trie->path); + return 0; + } + trie->data = NULL; + trie->data_size = 0; + } else { + if (trie->locked_file_size < sizeof(trie->hdr)) { + i_error("Corrupted %s: File too small", trie->path); + return 0; + } + if (trie->mmap_size != 0) { + if (munmap(trie->mmap_base, trie->mmap_size) < 0) + i_error("munmap(%s) failed: %m", trie->path); + } + + trie->mmap_size = trie->locked_file_size; + trie->mmap_base = mmap(NULL, trie->mmap_size, + PROT_READ | PROT_WRITE, + MAP_SHARED, trie->fd, 0); + if (trie->mmap_base == MAP_FAILED) { + trie->data = trie->mmap_base = NULL; + trie->data_size = trie->mmap_size = 0; + i_error("mmap(%s) failed: %m", trie->path); + return -1; + } + memcpy(&trie->hdr, trie->mmap_base, sizeof(trie->hdr)); + trie->data = trie->mmap_base; + trie->data_size = trie->mmap_size; + } + + return squat_trie_check_header(trie) ? 1 : 0; +} + +static int squat_trie_map(struct squat_trie *trie, bool building) +{ + struct file_lock *file_lock = NULL; + struct dotlock *dotlock = NULL; + bool changed; + int ret; + + if (trie->fd != -1) { + if (squat_trie_lock(trie, F_RDLCK, &file_lock, &dotlock) <= 0) + return -1; + if ((trie->flags & SQUAT_INDEX_FLAG_MMAP_DISABLE) != 0 && + trie->file_cache == NULL) + trie->file_cache = file_cache_new_path(trie->fd, trie->path); + } + + ret = squat_trie_map_header(trie); + if (ret == 0) { + if (file_lock != NULL) + file_unlock(&file_lock); + else + file_dotlock_delete(&dotlock); + squat_trie_delete(trie); + squat_trie_close(trie); + squat_trie_header_init(trie); + } + changed = trie->root.children.offset != trie->hdr.root_offset; + + if (changed || trie->hdr.root_offset == 0) { + node_free(trie, &trie->root); + i_zero(&trie->root); + trie->root.want_sequential = TRUE; + trie->root.unused_uids = trie->hdr.root_unused_uids; + trie->root.next_uid = trie->hdr.root_next_uid; + trie->root.uid_list_idx = trie->hdr.root_uidlist_idx; + trie->root.children.offset = trie->hdr.root_offset; + + if (trie->hdr.root_offset == 0) { + trie->unmapped_child_count = 0; + trie->root.children_not_mapped = FALSE; + } else { + trie->unmapped_child_count = 1; + trie->root.children_not_mapped = TRUE; + } + } + + if (ret >= 0 && !building) { + /* do this while we're still locked */ + ret = squat_uidlist_refresh(trie->uidlist); + } + + if (file_lock != NULL) + file_unlock(&file_lock); + if (dotlock != NULL) + file_dotlock_delete(&dotlock); + if (ret < 0) + return -1; + + return trie->hdr.root_offset == 0 || !changed ? 0 : + node_read_children(trie, &trie->root, 1); +} + +int squat_trie_create_fd(struct squat_trie *trie, const char *path, int flags) +{ + mode_t old_mask; + int fd; + + old_mask = umask(0); + fd = open(path, O_RDWR | O_CREAT | flags, trie->create_mode); + umask(old_mask); + if (fd == -1) { + i_error("creat(%s) failed: %m", path); + return -1; + } + if (trie->create_gid != (gid_t)-1) { + if (fchown(fd, (uid_t)-1, trie->create_gid) < 0) { + i_error("fchown(%s, -1, %ld) failed: %m", + path, (long)trie->create_gid); + i_close_fd(&fd); + return -1; + } + } + return fd; +} + +int squat_trie_build_init(struct squat_trie *trie, + struct squat_trie_build_context **ctx_r) +{ + struct squat_trie_build_context *ctx; + struct squat_uidlist_build_context *uidlist_build_ctx; + + if (trie->fd == -1) { + trie->fd = squat_trie_create_fd(trie, trie->path, 0); + if (trie->fd == -1) + return -1; + + if (trie->file_cache != NULL) + file_cache_set_fd(trie->file_cache, trie->fd); + i_assert(trie->locked_file_size == 0); + } + + /* uidlist locks building */ + if (squat_uidlist_build_init(trie->uidlist, &uidlist_build_ctx) < 0) + return -1; + + if (squat_trie_map(trie, TRUE) < 0) { + squat_uidlist_build_deinit(&uidlist_build_ctx); + return -1; + } + + ctx = i_new(struct squat_trie_build_context, 1); + ctx->trie = trie; + ctx->uidlist_build_ctx = uidlist_build_ctx; + ctx->first_uid = trie->root.next_uid; + + *ctx_r = ctx; + return 0; +} + +static int squat_trie_write_lock(struct squat_trie_build_context *ctx) +{ + if (ctx->file_lock != NULL || ctx->dotlock != NULL) + return 0; + + if (squat_trie_lock(ctx->trie, F_WRLCK, + &ctx->file_lock, &ctx->dotlock) <= 0) + return -1; + return 0; +} + +static int squat_trie_write(struct squat_trie_build_context *ctx) +{ + struct squat_trie *trie = ctx->trie; + struct file_lock *file_lock = NULL; + struct ostream *output; + const char *path, *error; + int fd = -1, ret = 0; + + if ((trie->hdr.used_file_size > sizeof(trie->hdr) && + trie->unmapped_child_count < trie->hdr.node_count/4) || 1) { + /* we might as well recreate the file */ + ctx->compress_nodes = TRUE; + + path = t_strconcat(trie->path, ".tmp", NULL); + fd = squat_trie_create_fd(trie, path, O_TRUNC); + if (fd == -1) + return -1; + + if (trie->lock_method != FILE_LOCK_METHOD_DOTLOCK) { + struct file_lock_settings lock_set = { + .lock_method = trie->lock_method, + }; + ret = file_wait_lock(fd, path, F_WRLCK, &lock_set, + SQUAT_TRIE_LOCK_TIMEOUT, + &file_lock, &error); + if (ret <= 0) { + i_error("file_wait_lock(%s) failed: %s", + path, error); + i_close_fd(&fd); + return -1; + } + } + + output = o_stream_create_fd(fd, 0); + o_stream_cork(output); + o_stream_nsend(output, &trie->hdr, sizeof(trie->hdr)); + } else { + /* we need to lock only while header is being written */ + path = trie->path; + ctx->compress_nodes = + trie->hdr.used_file_size == sizeof(trie->hdr); + + if (trie->hdr.used_file_size == 0) { + /* lock before opening the file, in case we reopen it */ + if (squat_trie_write_lock(ctx) < 0) + return -1; + } + output = o_stream_create_fd(trie->fd, 0); + o_stream_cork(output); + + if (trie->hdr.used_file_size != 0) + (void)o_stream_seek(output, trie->hdr.used_file_size); + else + o_stream_nsend(output, &trie->hdr, sizeof(trie->hdr)); + } + + ctx->output = output; + ret = squat_write_nodes(ctx); + ctx->output = NULL; + + /* write 1 byte guard at the end of file, so that we can verify broken + squat_unpack_num() input by checking if data==end */ + o_stream_nsend(output, "", 1); + + if (trie->corrupted) + ret = -1; + if (ret == 0) + ret = squat_trie_write_lock(ctx); + if (ret == 0) { + trie->hdr.used_file_size = output->offset; + (void)o_stream_seek(output, 0); + o_stream_nsend(output, &trie->hdr, sizeof(trie->hdr)); + } + if (o_stream_finish(output) < 0) { + i_error("write(%s) failed: %s", path, + o_stream_get_error(output)); + ret = -1; + } + o_stream_destroy(&output); + + if (fd == -1) { + /* appended to the existing file */ + i_assert(file_lock == NULL); + return ret; + } + + /* recreating the trie file */ + if (ret < 0) { + if (close(fd) < 0) + i_error("close(%s) failed: %m", path); + fd = -1; + } else if (rename(path, trie->path) < 0) { + i_error("rename(%s, %s) failed: %m", path, trie->path); + ret = -1; + } + + if (ret < 0) { + i_unlink_if_exists(path); + file_lock_free(&file_lock); + } else { + squat_trie_close_fd(trie); + trie->fd = fd; + trie->locked_file_size = trie->hdr.used_file_size; + if (trie->file_cache != NULL) + file_cache_set_fd(trie->file_cache, trie->fd); + + file_lock_free(&ctx->file_lock); + ctx->file_lock = file_lock; + } + return ret; +} + +int squat_trie_build_deinit(struct squat_trie_build_context **_ctx, + const ARRAY_TYPE(seq_range) *expunged_uids) +{ + struct squat_trie_build_context *ctx = *_ctx; + bool compress, unlock = TRUE; + int ret; + + *_ctx = NULL; + + compress = (ctx->trie->root.next_uid - ctx->first_uid) > 10; + + /* keep trie locked while header is being written and when files are + being renamed, so that while trie is read locked, uidlist can't + change under. */ + squat_uidlist_build_flush(ctx->uidlist_build_ctx); + ret = squat_trie_renumber_uidlists(ctx, expunged_uids, compress); + if (ret == 0) { + ret = squat_trie_write(ctx); + if (ret < 0) + unlock = FALSE; + } + + if (ret == 0) + ret = squat_uidlist_build_finish(ctx->uidlist_build_ctx); + if (ctx->file_lock != NULL) { + if (unlock) + file_unlock(&ctx->file_lock); + else + file_lock_free(&ctx->file_lock); + } + if (ctx->dotlock != NULL) + file_dotlock_delete(&ctx->dotlock); + squat_uidlist_build_deinit(&ctx->uidlist_build_ctx); + + i_free(ctx); + return ret; +} + +int squat_trie_get_last_uid(struct squat_trie *trie, uint32_t *last_uid_r) +{ + if (trie->fd == -1) { + if (squat_trie_open(trie) < 0) + return -1; + } + + *last_uid_r = I_MAX((trie->root.next_uid+1)/2, 1) - 1; + return 0; +} + +static int +squat_trie_lookup_data(struct squat_trie *trie, const unsigned char *data, + unsigned int size, ARRAY_TYPE(seq_range) *uids) +{ + struct squat_node *node = &trie->root; + unsigned char *chars; + unsigned int idx; + int level = 0; + + array_clear(uids); + + for (;;) { + if (node->children_not_mapped) { + if (node_read_children(trie, node, level) < 0) + return -1; + } + if (node->leaf_string_length != 0) { + unsigned int len = node->leaf_string_length; + const unsigned char *str; + + if (len > sizeof(node->children.static_leaf_string)) + str = node->children.leaf_string; + else + str = node->children.static_leaf_string; + + if (size > len || memcmp(data, str, size) != 0) + return 0; + + /* match */ + break; + } + + if (size == 0) + break; + level++; + + if (node->have_sequential) { + if (*data < SEQUENTIAL_COUNT) { + idx = *data; + goto found; + } + idx = SEQUENTIAL_COUNT; + } else { + idx = 0; + } + chars = NODE_CHILDREN_CHARS(node); + for (; idx < node->child_count; idx++) { + if (chars[idx] == *data) + goto found; + } + return 0; + found: + /* follow to children */ + if (level == 1) { + /* root level, add all UIDs */ + if (squat_uidlist_get_seqrange(trie->uidlist, + node->uid_list_idx, + uids) < 0) + return -1; + } else { + if (squat_uidlist_filter(trie->uidlist, + node->uid_list_idx, uids) < 0) + return -1; + } + data++; + size--; + node = NODE_CHILDREN_NODES(node) + idx; + } + + if (squat_uidlist_filter(trie->uidlist, node->uid_list_idx, uids) < 0) + return -1; + return 1; +} + +static void +squat_trie_filter_type(enum squat_index_type type, + const ARRAY_TYPE(seq_range) *src, + ARRAY_TYPE(seq_range) *dest) +{ + const struct seq_range *src_range; + struct seq_range new_range; + unsigned int i, count, mask; + uint32_t next_seq, uid; + + array_clear(dest); + src_range = array_get(src, &count); + if (count == 0) + return; + + if ((type & SQUAT_INDEX_TYPE_HEADER) != 0 && + (type & SQUAT_INDEX_TYPE_BODY) != 0) { + /* everything is fine, just fix the UIDs */ + new_range.seq1 = src_range[0].seq1 / 2; + new_range.seq2 = src_range[0].seq2 / 2; + for (i = 1; i < count; i++) { + next_seq = src_range[i].seq1 / 2; + if (next_seq == new_range.seq2 + 1) { + /* we can continue the previous range */ + } else { + array_push_back(dest, &new_range); + new_range.seq1 = src_range[i].seq1 / 2; + } + new_range.seq2 = src_range[i].seq2 / 2; + } + array_push_back(dest, &new_range); + return; + } + + /* we'll have to drop either header or body UIDs */ + mask = (type & SQUAT_INDEX_TYPE_HEADER) != 0 ? 1 : 0; + for (i = 0; i < count; i++) { + for (uid = src_range[i].seq1; uid <= src_range[i].seq2; uid++) { + if ((uid & 1) == mask) + seq_range_array_add(dest, uid/2); + } + } +} + +struct squat_trie_lookup_context { + struct squat_trie *trie; + enum squat_index_type type; + + ARRAY_TYPE(seq_range) *definite_uids, *maybe_uids; + ARRAY_TYPE(seq_range) tmp_uids, tmp_uids2; + bool first; +}; + +static int +squat_trie_lookup_partial(struct squat_trie_lookup_context *ctx, + const unsigned char *data, uint8_t *char_lengths, + unsigned int size) +{ + const unsigned int partial_len = ctx->trie->hdr.partial_len; + unsigned int char_idx, max_chars, i, j, bytelen; + int ret; + + for (i = 0, max_chars = 0; i < size; max_chars++) + i += char_lengths[i]; + i_assert(max_chars > 0); + + i = 0; char_idx = 0; + do { + bytelen = 0; + for (j = 0; j < partial_len && i+bytelen < size; j++) + bytelen += char_lengths[i + bytelen]; + + ret = squat_trie_lookup_data(ctx->trie, data + i, bytelen, + &ctx->tmp_uids); + if (ret <= 0) { + array_clear(ctx->maybe_uids); + return ret; + } + + if (ctx->first) { + squat_trie_filter_type(ctx->type, &ctx->tmp_uids, + ctx->maybe_uids); + ctx->first = FALSE; + } else { + squat_trie_filter_type(ctx->type, &ctx->tmp_uids, + &ctx->tmp_uids2); + seq_range_array_intersect(ctx->maybe_uids, + &ctx->tmp_uids2); + } + i += char_lengths[i]; + char_idx++; + } while (max_chars - char_idx >= partial_len); + return 1; +} + +static void squat_trie_add_unknown(struct squat_trie *trie, + ARRAY_TYPE(seq_range) *maybe_uids) +{ + struct seq_range *range, new_range; + unsigned int count; + uint32_t last_uid; + + last_uid = I_MAX((trie->root.next_uid+1)/2, 1) - 1; + + range = array_get_modifiable(maybe_uids, &count); + if (count > 0 && range[count-1].seq2 == last_uid) { + /* increase the range */ + range[count-1].seq2 = (uint32_t)-1; + } else { + new_range.seq1 = last_uid + 1; + new_range.seq2 = (uint32_t)-1; + array_push_back(maybe_uids, &new_range); + } +} + +static int +squat_trie_lookup_real(struct squat_trie *trie, const char *str, + enum squat_index_type type, + ARRAY_TYPE(seq_range) *definite_uids, + ARRAY_TYPE(seq_range) *maybe_uids) +{ + struct squat_trie_lookup_context ctx; + unsigned char *data; + uint8_t *char_lengths; + unsigned int i, start, bytes, str_bytelen, str_charlen; + bool searched = FALSE; + int ret = 0; + + array_clear(definite_uids); + array_clear(maybe_uids); + + i_zero(&ctx); + ctx.trie = trie; + ctx.type = type; + ctx.definite_uids = definite_uids; + ctx.maybe_uids = maybe_uids; + i_array_init(&ctx.tmp_uids, 128); + i_array_init(&ctx.tmp_uids2, 128); + ctx.first = TRUE; + + str_bytelen = strlen(str); + char_lengths = str_bytelen == 0 ? NULL : t_malloc0(str_bytelen); + for (i = 0, str_charlen = 0; i < str_bytelen; str_charlen++) { + bytes = uni_utf8_char_bytes(str[i]); + char_lengths[i] = bytes; + i += bytes; + } + data = squat_data_normalize(trie, (const unsigned char *)str, + str_bytelen); + + for (i = start = 0; i < str_bytelen && ret >= 0; i += char_lengths[i]) { + if (data[i] != '\0') + continue; + + /* string has nonindexed characters. + search it in parts. */ + if (i != start) { + ret = squat_trie_lookup_partial(&ctx, data + start, + char_lengths + start, + i - start); + searched = TRUE; + } + start = i + char_lengths[i]; + } + + if (start == 0) { + if (str_charlen <= trie->hdr.partial_len || + trie->hdr.full_len > trie->hdr.partial_len) { + ret = squat_trie_lookup_data(trie, data, str_bytelen, + &ctx.tmp_uids); + if (ret > 0) { + squat_trie_filter_type(type, &ctx.tmp_uids, + definite_uids); + } + } else { + array_clear(definite_uids); + } + + if (str_charlen <= trie->hdr.partial_len || + trie->hdr.partial_len == 0) { + /* we have the result */ + array_clear(maybe_uids); + } else { + ret = squat_trie_lookup_partial(&ctx, data + start, + char_lengths + start, + i - start); + } + } else if (str_bytelen > 0) { + /* string has nonindexed characters. finish the search. */ + array_clear(definite_uids); + if (i != start && ret >= 0) { + ret = squat_trie_lookup_partial(&ctx, data + start, + char_lengths + start, + i - start); + } else if (!searched) { + /* string has only nonindexed chars, + list all root UIDs as maybes */ + ret = squat_uidlist_get_seqrange(trie->uidlist, + trie->root.uid_list_idx, + &ctx.tmp_uids); + squat_trie_filter_type(type, &ctx.tmp_uids, + maybe_uids); + } + } else { + /* zero string length - list all root UIDs as definite + answers */ +#if 0 /* FIXME: this code is never actually reached now. */ + ret = squat_uidlist_get_seqrange(trie->uidlist, + trie->root.uid_list_idx, + &ctx.tmp_uids); + squat_trie_filter_type(type, &ctx.tmp_uids, + definite_uids); +#else + i_unreached(); +#endif + } + seq_range_array_remove_seq_range(maybe_uids, definite_uids); + squat_trie_add_unknown(trie, maybe_uids); + array_free(&ctx.tmp_uids); + array_free(&ctx.tmp_uids2); + return ret < 0 ? -1 : 0; +} + +int squat_trie_lookup(struct squat_trie *trie, const char *str, + enum squat_index_type type, + ARRAY_TYPE(seq_range) *definite_uids, + ARRAY_TYPE(seq_range) *maybe_uids) +{ + int ret; + + T_BEGIN { + ret = squat_trie_lookup_real(trie, str, type, + definite_uids, maybe_uids); + } T_END; + return ret; +} + +struct squat_uidlist *squat_trie_get_uidlist(struct squat_trie *trie) +{ + return trie->uidlist; +} + +size_t squat_trie_mem_used(struct squat_trie *trie, unsigned int *count_r) +{ + *count_r = trie->hdr.node_count; + return trie->node_alloc_size; +} diff --git a/src/plugins/fts-squat/squat-trie.h b/src/plugins/fts-squat/squat-trie.h new file mode 100644 index 0000000..91530b8 --- /dev/null +++ b/src/plugins/fts-squat/squat-trie.h @@ -0,0 +1,54 @@ +#ifndef SQUAT_TRIE_H +#define SQUAT_TRIE_H + +#include "file-lock.h" +#include "seq-range-array.h" + +enum squat_index_flags { + SQUAT_INDEX_FLAG_MMAP_DISABLE = 0x01, + SQUAT_INDEX_FLAG_NFS_FLUSH = 0x02, + SQUAT_INDEX_FLAG_DOTLOCK_USE_EXCL = 0x04 +}; + +enum squat_index_type { + SQUAT_INDEX_TYPE_HEADER = 0x01, + SQUAT_INDEX_TYPE_BODY = 0x02 +}; + +struct squat_trie_build_context; + +struct squat_trie * +squat_trie_init(const char *path, uint32_t uidvalidity, + enum file_lock_method lock_method, + enum squat_index_flags flags, mode_t mode, gid_t gid); +void squat_trie_deinit(struct squat_trie **trie); + +void squat_trie_set_partial_len(struct squat_trie *trie, unsigned int len); +void squat_trie_set_full_len(struct squat_trie *trie, unsigned int len); + +int squat_trie_open(struct squat_trie *trie); +int squat_trie_refresh(struct squat_trie *trie); + +int squat_trie_build_init(struct squat_trie *trie, + struct squat_trie_build_context **ctx_r); +/* bodies must be added before headers */ +int squat_trie_build_more(struct squat_trie_build_context *ctx, + uint32_t uid, enum squat_index_type type, + const unsigned char *data, unsigned int size); +/* if expunged_uids is non-NULL, they may be removed from the index if they + still exist. */ +int squat_trie_build_deinit(struct squat_trie_build_context **ctx, + const ARRAY_TYPE(seq_range) *expunged_uids) + ATTR_NULL(2); + +int squat_trie_get_last_uid(struct squat_trie *trie, uint32_t *last_uid_r); +/* type specifies if we're looking at header, body or both */ +int squat_trie_lookup(struct squat_trie *trie, const char *str, + enum squat_index_type type, + ARRAY_TYPE(seq_range) *definite_uids, + ARRAY_TYPE(seq_range) *maybe_uids); + +struct squat_uidlist *squat_trie_get_uidlist(struct squat_trie *trie); +size_t squat_trie_mem_used(struct squat_trie *trie, unsigned int *count_r); + +#endif diff --git a/src/plugins/fts-squat/squat-uidlist.c b/src/plugins/fts-squat/squat-uidlist.c new file mode 100644 index 0000000..facb8d0 --- /dev/null +++ b/src/plugins/fts-squat/squat-uidlist.c @@ -0,0 +1,1624 @@ +/* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */ + +#include "lib.h" +#include "array.h" +#include "sort.h" +#include "bsearch-insert-pos.h" +#include "file-cache.h" +#include "file-lock.h" +#include "read-full.h" +#include "write-full.h" +#include "ostream.h" +#include "mmap-util.h" +#include "squat-trie-private.h" +#include "squat-uidlist.h" + +#include <stdio.h> +#include <sys/stat.h> + +#define UIDLIST_LIST_SIZE 31 +#define UIDLIST_BLOCK_LIST_COUNT 100 +#define UID_LIST_MASK_RANGE 0x80000000U + +/* set = points to uidlist index number, unset = points to uidlist offset */ +#define UID_LIST_POINTER_MASK_LIST_IDX 0x80000000U + +#define UIDLIST_PACKED_FLAG_BITMASK 1 +#define UIDLIST_PACKED_FLAG_BEGINS_WITH_POINTER 2 + +struct uidlist_list { + unsigned int uid_count:31; + bool uid_begins_with_pointer:1; + uint32_t uid_list[UIDLIST_LIST_SIZE]; +}; + +struct squat_uidlist { + struct squat_trie *trie; + + char *path; + int fd; + struct file_cache *file_cache; + + struct file_lock *file_lock; + struct dotlock *dotlock; + uoff_t locked_file_size; + + void *mmap_base; + size_t mmap_size; + struct squat_uidlist_file_header hdr; + + const void *data; + size_t data_size; + + unsigned int cur_block_count; + const uint32_t *cur_block_offsets; + const uint32_t *cur_block_end_indexes; + + size_t max_size; + bool corrupted:1; + bool building:1; +}; + +struct squat_uidlist_build_context { + struct squat_uidlist *uidlist; + struct ostream *output; + + ARRAY_TYPE(uint32_t) block_offsets; + ARRAY_TYPE(uint32_t) block_end_indexes; + + ARRAY(struct uidlist_list) lists; + uint32_t list_start_idx; + + struct squat_uidlist_file_header build_hdr; + bool need_reopen:1; +}; + +struct squat_uidlist_rebuild_context { + struct squat_uidlist *uidlist; + struct squat_uidlist_build_context *build_ctx; + + int fd; + struct ostream *output; + + ARRAY_TYPE(uint32_t) new_block_offsets, new_block_end_indexes; + uoff_t cur_block_start_offset; + + uint32_t list_sizes[UIDLIST_BLOCK_LIST_COUNT]; + uint32_t next_uid_list_idx; + unsigned int list_idx; + unsigned int new_count; +}; + +static void squat_uidlist_close(struct squat_uidlist *uidlist); + +void squat_uidlist_delete(struct squat_uidlist *uidlist) +{ + i_unlink_if_exists(uidlist->path); +} + +static void squat_uidlist_set_corrupted(struct squat_uidlist *uidlist, + const char *reason) +{ + if (uidlist->corrupted) + return; + uidlist->corrupted = TRUE; + + i_error("Corrupted squat uidlist file %s: %s", uidlist->path, reason); + squat_trie_delete(uidlist->trie); +} + +static int +uidlist_write_array(struct ostream *output, const uint32_t *uid_list, + unsigned int uid_count, uint32_t packed_flags, + uint32_t offset, bool write_size, uint32_t *size_r) +{ + uint8_t *uidbuf, *bufp, sizebuf[SQUAT_PACK_MAX_SIZE], *sizebufp; + uint8_t listbuf[SQUAT_PACK_MAX_SIZE], *listbufp = listbuf; + uint32_t uid, uid2, prev, base_uid, size_value; + unsigned int i, bitmask_len, uid_list_len; + unsigned int idx, max_idx, mask; + bool datastack; + int num; + + if ((packed_flags & UIDLIST_PACKED_FLAG_BEGINS_WITH_POINTER) != 0) + squat_pack_num(&listbufp, offset); + + /* @UNSAFE */ + base_uid = uid_list[0] & ~UID_LIST_MASK_RANGE; + datastack = uid_count < 1024*8/SQUAT_PACK_MAX_SIZE; + if (datastack) + uidbuf = t_malloc_no0(SQUAT_PACK_MAX_SIZE * uid_count); + else + uidbuf = i_malloc(SQUAT_PACK_MAX_SIZE * uid_count); + bufp = uidbuf; + squat_pack_num(&bufp, base_uid); + + bitmask_len = (uid_list[uid_count-1] - base_uid + 7) / 8 + + (bufp - uidbuf); + if (bitmask_len < uid_count) { + bitmask_build: + i_assert(bitmask_len < SQUAT_PACK_MAX_SIZE*uid_count); + + memset(bufp, 0, bitmask_len - (bufp - uidbuf)); + if ((uid_list[0] & UID_LIST_MASK_RANGE) == 0) { + i = 1; + uid = i == uid_count ? 0 : uid_list[i]; + } else { + i = 0; + uid = uid_list[0] + 1; + } + base_uid++; + + for (; i < uid_count; i++) { + i_assert((uid & ~UID_LIST_MASK_RANGE) >= base_uid); + if ((uid & UID_LIST_MASK_RANGE) == 0) { + uid -= base_uid; + uid2 = uid; + } else { + uid &= ~UID_LIST_MASK_RANGE; + uid -= base_uid; + uid2 = uid_list[i+1] - base_uid; + i++; + } + + if (uid2 - uid < 3*8) { + for (; uid <= uid2; uid++) + bufp[uid / 8] |= 1 << (uid % 8); + } else { + /* first byte */ + idx = uid / 8; + num = uid % 8; + if (num != 0) { + uid += 8 - num; + for (mask = 0; num < 8; num++) + mask |= 1 << num; + bufp[idx++] |= mask; + } + + /* middle bytes */ + num = uid2 % 8; + max_idx = idx + (uid2 - num - uid)/8; + for (; idx < max_idx; idx++, uid += 8) + bufp[idx] = 0xff; + + /* last byte */ + for (mask = 0; num >= 0; num--) + mask |= 1 << num; + bufp[idx] |= mask; + } + uid = i+1 == uid_count ? 0 : uid_list[i+1]; + } + uid_list_len = bitmask_len; + packed_flags |= UIDLIST_PACKED_FLAG_BITMASK; + } else { + bufp = uidbuf; + prev = 0; + for (i = 0; i < uid_count; i++) { + uid = uid_list[i]; + if (unlikely((uid & ~UID_LIST_MASK_RANGE) < prev)) { + if (!datastack) + i_free(uidbuf); + return -1; + } + if ((uid & UID_LIST_MASK_RANGE) == 0) { + squat_pack_num(&bufp, (uid - prev) << 1); + prev = uid + 1; + } else { + uid &= ~UID_LIST_MASK_RANGE; + squat_pack_num(&bufp, 1 | (uid - prev) << 1); + squat_pack_num(&bufp, uid_list[i+1] - uid - 1); + prev = uid_list[i+1] + 1; + i++; + } + } + uid_list_len = bufp - uidbuf; + if (uid_list_len > bitmask_len) { + bufp = uidbuf; + squat_pack_num(&bufp, base_uid); + goto bitmask_build; + } + } + + size_value = ((uid_list_len + + (listbufp - listbuf)) << 2) | packed_flags; + if (write_size) { + sizebufp = sizebuf; + squat_pack_num(&sizebufp, size_value); + o_stream_nsend(output, sizebuf, sizebufp - sizebuf); + } + o_stream_nsend(output, listbuf, listbufp - listbuf); + o_stream_nsend(output, uidbuf, uid_list_len); + if (!datastack) + i_free(uidbuf); + + *size_r = size_value; + return 0; +} + +static int +uidlist_write(struct ostream *output, const struct uidlist_list *list, + bool write_size, uint32_t *size_r) +{ + const uint32_t *uid_list = list->uid_list; + uint8_t buf[SQUAT_PACK_MAX_SIZE], *bufp; + uint32_t uid_count = list->uid_count; + uint32_t packed_flags = 0; + uint32_t offset = 0; + int ret; + + if (list->uid_begins_with_pointer) { + /* continued UID list */ + packed_flags |= UIDLIST_PACKED_FLAG_BEGINS_WITH_POINTER; + if ((uid_list[0] & UID_LIST_POINTER_MASK_LIST_IDX) != 0) { + offset = ((uid_list[0] & ~UID_LIST_POINTER_MASK_LIST_IDX) << 1) | 1; + if (list->uid_count == 1) { + bufp = buf; + squat_pack_num(&bufp, offset); + o_stream_nsend(output, buf, bufp - buf); + *size_r = (bufp - buf) << 2 | packed_flags; + return 0; + } + } else if (unlikely(output->offset <= uid_list[0])) { + i_assert(output->closed); + return -1; + } else { + i_assert(list->uid_count > 1); + offset = (output->offset - uid_list[0]) << 1; + } + uid_list++; + uid_count--; + } + + T_BEGIN { + ret = uidlist_write_array(output, uid_list, uid_count, + packed_flags, offset, + write_size, size_r); + } T_END; + return ret; +} + +static void squat_uidlist_map_blocks_set_pointers(struct squat_uidlist *uidlist) +{ + const void *base; + size_t end_index_size, end_size; + + base = CONST_PTR_OFFSET(uidlist->data, uidlist->hdr.block_list_offset + + sizeof(uint32_t)); + + end_index_size = uidlist->cur_block_count * sizeof(uint32_t); + end_size = end_index_size + uidlist->cur_block_count * sizeof(uint32_t); + if (end_size <= uidlist->data_size) { + uidlist->cur_block_end_indexes = base; + uidlist->cur_block_offsets = + CONST_PTR_OFFSET(base, end_index_size); + } else { + uidlist->cur_block_end_indexes = NULL; + uidlist->cur_block_offsets = NULL; + } +} + +static int uidlist_file_cache_read(struct squat_uidlist *uidlist, + size_t offset, size_t size) +{ + if (uidlist->file_cache == NULL) + return 0; + + if (file_cache_read(uidlist->file_cache, offset, size) < 0) { + i_error("read(%s) failed: %m", uidlist->path); + return -1; + } + uidlist->data = file_cache_get_map(uidlist->file_cache, + &uidlist->data_size); + squat_uidlist_map_blocks_set_pointers(uidlist); + return 0; +} + +static int squat_uidlist_map_blocks(struct squat_uidlist *uidlist) +{ + const struct squat_uidlist_file_header *hdr = &uidlist->hdr; + const void *base; + uint32_t block_count, blocks_offset, blocks_size, i, verify_count; + + if (hdr->block_list_offset == 0) { + /* empty file */ + uidlist->cur_block_count = 0; + return 1; + } + + /* get number of blocks */ + if (uidlist_file_cache_read(uidlist, hdr->block_list_offset, + sizeof(block_count)) < 0) + return -1; + blocks_offset = hdr->block_list_offset + sizeof(block_count); + if (blocks_offset > uidlist->data_size) { + squat_uidlist_set_corrupted(uidlist, "block list outside file"); + return 0; + } + + i_assert(uidlist->data != NULL); + base = CONST_PTR_OFFSET(uidlist->data, hdr->block_list_offset); + memcpy(&block_count, base, sizeof(block_count)); + + /* map the blocks */ + blocks_size = block_count * sizeof(uint32_t)*2; + if (uidlist_file_cache_read(uidlist, blocks_offset, blocks_size) < 0) + return -1; + if (blocks_offset + blocks_size > uidlist->data_size) { + squat_uidlist_set_corrupted(uidlist, "block list outside file"); + return 0; + } + + uidlist->cur_block_count = block_count; + squat_uidlist_map_blocks_set_pointers(uidlist); + + i_assert(uidlist->cur_block_end_indexes != NULL); + + /* verify just a couple of the end indexes to make sure they + look correct */ + verify_count = I_MIN(block_count, 8); + for (i = 1; i < verify_count; i++) { + if (unlikely(uidlist->cur_block_end_indexes[i-1] >= + uidlist->cur_block_end_indexes[i])) { + squat_uidlist_set_corrupted(uidlist, + "block list corrupted"); + return 0; + } + } + return 1; +} + +static int squat_uidlist_map_header(struct squat_uidlist *uidlist) +{ + if (uidlist->hdr.indexid == 0) { + /* still being built */ + return 1; + } + if (uidlist->hdr.indexid != uidlist->trie->hdr.indexid) { + /* see if trie was recreated */ + (void)squat_trie_open(uidlist->trie); + } + if (uidlist->hdr.indexid != uidlist->trie->hdr.indexid) { + squat_uidlist_set_corrupted(uidlist, "wrong indexid"); + return 0; + } + if (uidlist->hdr.used_file_size < sizeof(uidlist->hdr) || + (uidlist->hdr.used_file_size > uidlist->mmap_size && + uidlist->mmap_base != NULL)) { + squat_uidlist_set_corrupted(uidlist, "broken used_file_size"); + return 0; + } + return squat_uidlist_map_blocks(uidlist); +} + +static void squat_uidlist_unmap(struct squat_uidlist *uidlist) +{ + if (uidlist->mmap_size != 0) { + if (munmap(uidlist->mmap_base, uidlist->mmap_size) < 0) + i_error("munmap(%s) failed: %m", uidlist->path); + uidlist->mmap_base = NULL; + uidlist->mmap_size = 0; + } + uidlist->cur_block_count = 0; + uidlist->cur_block_end_indexes = NULL; + uidlist->cur_block_offsets = NULL; +} + +static int squat_uidlist_mmap(struct squat_uidlist *uidlist) +{ + struct stat st; + + if (fstat(uidlist->fd, &st) < 0) { + i_error("fstat(%s) failed: %m", uidlist->path); + return -1; + } + if (st.st_size < (off_t)sizeof(uidlist->hdr)) { + squat_uidlist_set_corrupted(uidlist, "File too small"); + return -1; + } + + squat_uidlist_unmap(uidlist); + uidlist->mmap_size = st.st_size; + uidlist->mmap_base = mmap(NULL, uidlist->mmap_size, + PROT_READ | PROT_WRITE, + MAP_SHARED, uidlist->fd, 0); + if (uidlist->mmap_base == MAP_FAILED) { + uidlist->data = uidlist->mmap_base = NULL; + uidlist->data_size = uidlist->mmap_size = 0; + i_error("mmap(%s) failed: %m", uidlist->path); + return -1; + } + uidlist->data = uidlist->mmap_base; + uidlist->data_size = uidlist->mmap_size; + return 0; +} + +static int squat_uidlist_map(struct squat_uidlist *uidlist) +{ + const struct squat_uidlist_file_header *mmap_hdr = uidlist->mmap_base; + int ret; + + if (mmap_hdr != NULL && !uidlist->building && + uidlist->hdr.block_list_offset == mmap_hdr->block_list_offset) { + /* file hasn't changed */ + return 1; + } + + if ((uidlist->trie->flags & SQUAT_INDEX_FLAG_MMAP_DISABLE) == 0) { + if (mmap_hdr == NULL || uidlist->building || + uidlist->mmap_size < mmap_hdr->used_file_size) { + if (squat_uidlist_mmap(uidlist) < 0) + return -1; + } + + if (!uidlist->building) { + memcpy(&uidlist->hdr, uidlist->mmap_base, + sizeof(uidlist->hdr)); + } + } else if (uidlist->building) { + /* we want to update blocks mapping, but using the header + in memory */ + } else { + ret = pread_full(uidlist->fd, &uidlist->hdr, + sizeof(uidlist->hdr), 0); + if (ret <= 0) { + if (ret < 0) { + i_error("pread(%s) failed: %m", uidlist->path); + return -1; + } + i_error("Corrupted %s: File too small", uidlist->path); + return 0; + } + uidlist->data = NULL; + uidlist->data_size = 0; + } + if (uidlist->file_cache == NULL && + (uidlist->trie->flags & SQUAT_INDEX_FLAG_MMAP_DISABLE) != 0) + uidlist->file_cache = file_cache_new_path(uidlist->fd, uidlist->path); + return squat_uidlist_map_header(uidlist); +} + +static int squat_uidlist_read_to_memory(struct squat_uidlist *uidlist) +{ + size_t i, page_size = mmap_get_page_size(); + + if (uidlist->file_cache != NULL) { + return uidlist_file_cache_read(uidlist, 0, + uidlist->hdr.used_file_size); + } + /* Tell the kernel we're going to use the uidlist data, so it loads + it into memory and keeps it there. */ + (void)madvise(uidlist->mmap_base, uidlist->mmap_size, MADV_WILLNEED); + /* It also speeds up a bit for us to sequentially load everything + into memory, although at least Linux catches up quite fast even + without this code. Compiler can quite easily optimize away this + entire for loop, but volatile seems to help with gcc 4.2. */ + for (i = 0; i < uidlist->mmap_size; i += page_size) + ((const volatile char *)uidlist->data)[i]; + return 0; +} + +static void squat_uidlist_free_from_memory(struct squat_uidlist *uidlist) +{ + size_t page_size = mmap_get_page_size(); + + if (uidlist->file_cache != NULL) { + file_cache_invalidate(uidlist->file_cache, + page_size, UOFF_T_MAX); + } else { + (void)madvise(uidlist->mmap_base, uidlist->mmap_size, + MADV_DONTNEED); + } +} + +struct squat_uidlist *squat_uidlist_init(struct squat_trie *trie) +{ + struct squat_uidlist *uidlist; + + uidlist = i_new(struct squat_uidlist, 1); + uidlist->trie = trie; + uidlist->path = i_strconcat(trie->path, ".uids", NULL); + uidlist->fd = -1; + + return uidlist; +} + +void squat_uidlist_deinit(struct squat_uidlist *uidlist) +{ + squat_uidlist_close(uidlist); + + i_free(uidlist->path); + i_free(uidlist); +} + +static int squat_uidlist_open(struct squat_uidlist *uidlist) +{ + squat_uidlist_close(uidlist); + + uidlist->fd = open(uidlist->path, O_RDWR); + if (uidlist->fd == -1) { + if (errno == ENOENT) { + i_zero(&uidlist->hdr); + return 0; + } + i_error("open(%s) failed: %m", uidlist->path); + return -1; + } + return squat_uidlist_map(uidlist) <= 0 ? -1 : 0; +} + +static void squat_uidlist_close(struct squat_uidlist *uidlist) +{ + i_assert(!uidlist->building); + + squat_uidlist_unmap(uidlist); + if (uidlist->file_cache != NULL) + file_cache_free(&uidlist->file_cache); + file_lock_free(&uidlist->file_lock); + if (uidlist->dotlock != NULL) + file_dotlock_delete(&uidlist->dotlock); + i_close_fd_path(&uidlist->fd, uidlist->path); + uidlist->corrupted = FALSE; +} + +int squat_uidlist_refresh(struct squat_uidlist *uidlist) +{ + /* we assume here that trie is locked, so that we don't need to worry + about it when reading the header */ + if (uidlist->fd == -1 || + uidlist->hdr.indexid != uidlist->trie->hdr.indexid) { + if (squat_uidlist_open(uidlist) < 0) + return -1; + } else { + if (squat_uidlist_map(uidlist) <= 0) + return -1; + } + return 0; +} + +static int squat_uidlist_is_file_stale(struct squat_uidlist *uidlist) +{ + struct stat st, st2; + + i_assert(uidlist->fd != -1); + + if (stat(uidlist->path, &st) < 0) { + if (errno == ENOENT) + return 1; + + i_error("stat(%s) failed: %m", uidlist->path); + return -1; + } + if (fstat(uidlist->fd, &st2) < 0) { + i_error("fstat(%s) failed: %m", uidlist->path); + return -1; + } + uidlist->locked_file_size = st2.st_size; + + return st.st_ino == st2.st_ino && + CMP_DEV_T(st.st_dev, st2.st_dev) ? 0 : 1; +} + +static int squat_uidlist_lock(struct squat_uidlist *uidlist) +{ + const char *error; + int ret; + + for (;;) { + i_assert(uidlist->fd != -1); + i_assert(uidlist->file_lock == NULL); + i_assert(uidlist->dotlock == NULL); + + if (uidlist->trie->lock_method != FILE_LOCK_METHOD_DOTLOCK) { + struct file_lock_settings lock_set = { + .lock_method = uidlist->trie->lock_method, + }; + ret = file_wait_lock(uidlist->fd, uidlist->path, + F_WRLCK, &lock_set, + SQUAT_TRIE_LOCK_TIMEOUT, + &uidlist->file_lock, &error); + if (ret < 0) { + i_error("squat uidlist %s: %s", + uidlist->path, error); + } + } else { + ret = file_dotlock_create(&uidlist->trie->dotlock_set, + uidlist->path, 0, + &uidlist->dotlock); + } + if (ret == 0) { + i_error("squat uidlist %s: Locking timed out", + uidlist->path); + return 0; + } + if (ret < 0) + return -1; + + ret = squat_uidlist_is_file_stale(uidlist); + if (ret == 0) + break; + + if (uidlist->file_lock != NULL) + file_unlock(&uidlist->file_lock); + else + file_dotlock_delete(&uidlist->dotlock); + if (ret < 0) + return -1; + + squat_uidlist_close(uidlist); + uidlist->fd = squat_trie_create_fd(uidlist->trie, + uidlist->path, 0); + if (uidlist->fd == -1) + return -1; + } + return 1; +} + +static int squat_uidlist_open_or_create(struct squat_uidlist *uidlist) +{ + int ret; + + if (uidlist->fd == -1) { + uidlist->fd = squat_trie_create_fd(uidlist->trie, + uidlist->path, 0); + if (uidlist->fd == -1) + return -1; + } + if (squat_uidlist_lock(uidlist) <= 0) + return -1; + + if (uidlist->locked_file_size != 0) { + if ((ret = squat_uidlist_map(uidlist)) < 0) + return -1; + if (ret == 0) { + /* broken file, truncate */ + if (ftruncate(uidlist->fd, 0) < 0) { + i_error("ftruncate(%s) failed: %m", + uidlist->path); + return -1; + } + uidlist->locked_file_size = 0; + } + } + if (uidlist->locked_file_size == 0) { + /* write using 0 until we're finished */ + i_zero(&uidlist->hdr); + if (write_full(uidlist->fd, &uidlist->hdr, + sizeof(uidlist->hdr)) < 0) { + i_error("write(%s) failed: %m", uidlist->path); + return -1; + } + } + return 0; +} + +int squat_uidlist_build_init(struct squat_uidlist *uidlist, + struct squat_uidlist_build_context **ctx_r) +{ + struct squat_uidlist_build_context *ctx; + int ret; + + i_assert(!uidlist->building); + + ret = squat_uidlist_open_or_create(uidlist); + if (ret == 0 && + lseek(uidlist->fd, uidlist->hdr.used_file_size, SEEK_SET) < 0) { + i_error("lseek(%s) failed: %m", uidlist->path); + ret = -1; + } + + if (ret < 0) { + if (uidlist->file_lock != NULL) + file_unlock(&uidlist->file_lock); + if (uidlist->dotlock != NULL) + file_dotlock_delete(&uidlist->dotlock); + return -1; + } + + ctx = i_new(struct squat_uidlist_build_context, 1); + ctx->uidlist = uidlist; + ctx->output = o_stream_create_fd(uidlist->fd, 0); + if (ctx->output->offset == 0) { + struct squat_uidlist_file_header hdr; + + i_zero(&hdr); + o_stream_nsend(ctx->output, &hdr, sizeof(hdr)); + } + o_stream_cork(ctx->output); + i_array_init(&ctx->lists, 10240); + i_array_init(&ctx->block_offsets, 128); + i_array_init(&ctx->block_end_indexes, 128); + ctx->list_start_idx = uidlist->hdr.count; + ctx->build_hdr = uidlist->hdr; + + uidlist->building = TRUE; + *ctx_r = ctx; + return 0; +} + +static void +uidlist_write_block_list_and_header(struct squat_uidlist_build_context *ctx, + struct ostream *output, + ARRAY_TYPE(uint32_t) *block_offsets, + ARRAY_TYPE(uint32_t) *block_end_indexes, + bool write_old_blocks) +{ + struct squat_uidlist *uidlist = ctx->uidlist; + unsigned int align, old_block_count, new_block_count; + uint32_t block_offset_count; + uoff_t block_list_offset; + + i_assert(uidlist->trie->hdr.indexid != 0); + ctx->build_hdr.indexid = uidlist->trie->hdr.indexid; + + if (array_count(block_end_indexes) == 0) { + ctx->build_hdr.used_file_size = output->offset; + ctx->build_hdr.block_list_offset = 0; + uidlist->hdr = ctx->build_hdr; + return; + } + + align = output->offset % sizeof(uint32_t); + if (align != 0) { + static char null[sizeof(uint32_t)-1] = { 0, }; + + o_stream_nsend(output, null, sizeof(uint32_t) - align); + } + block_list_offset = output->offset; + + new_block_count = array_count(block_offsets); + old_block_count = write_old_blocks ? uidlist->cur_block_count : 0; + + block_offset_count = new_block_count + old_block_count; + o_stream_nsend(output, &block_offset_count, sizeof(block_offset_count)); + /* write end indexes */ + o_stream_nsend(output, uidlist->cur_block_end_indexes, + old_block_count * sizeof(uint32_t)); + o_stream_nsend(output, array_front(block_end_indexes), + new_block_count * sizeof(uint32_t)); + /* write offsets */ + o_stream_nsend(output, uidlist->cur_block_offsets, + old_block_count * sizeof(uint32_t)); + o_stream_nsend(output, array_front(block_offsets), + new_block_count * sizeof(uint32_t)); + (void)o_stream_flush(output); + + /* update header - it's written later when trie is locked */ + ctx->build_hdr.block_list_offset = block_list_offset; + ctx->build_hdr.used_file_size = output->offset; + uidlist->hdr = ctx->build_hdr; +} + +void squat_uidlist_build_flush(struct squat_uidlist_build_context *ctx) +{ + struct uidlist_list *lists; + uint8_t buf[SQUAT_PACK_MAX_SIZE], *bufp; + unsigned int i, j, count, max; + uint32_t block_offset, block_end_idx, start_offset; + uint32_t list_sizes[UIDLIST_BLOCK_LIST_COUNT]; + size_t mem_size; + + if (ctx->uidlist->corrupted) + return; + + lists = array_get_modifiable(&ctx->lists, &count); + if (count == 0) + return; + + /* write the lists and save the written sizes to uid_list[0] */ + for (i = 0; i < count; i += UIDLIST_BLOCK_LIST_COUNT) { + start_offset = ctx->output->offset; + max = I_MIN(count - i, UIDLIST_BLOCK_LIST_COUNT); + for (j = 0; j < max; j++) { + if (uidlist_write(ctx->output, &lists[i+j], + FALSE, &list_sizes[j]) < 0) { + squat_uidlist_set_corrupted(ctx->uidlist, + "Broken uidlists"); + return; + } + } + + block_offset = ctx->output->offset; + block_end_idx = ctx->list_start_idx + i + max; + array_push_back(&ctx->block_offsets, &block_offset); + array_push_back(&ctx->block_end_indexes, &block_end_idx); + + /* write the full size of the uidlists */ + bufp = buf; + squat_pack_num(&bufp, block_offset - start_offset); + o_stream_nsend(ctx->output, buf, bufp - buf); + + /* write the sizes/flags */ + for (j = 0; j < max; j++) { + bufp = buf; + squat_pack_num(&bufp, list_sizes[j]); + o_stream_nsend(ctx->output, buf, bufp - buf); + } + } + + mem_size = ctx->lists.arr.buffer->used + + ctx->block_offsets.arr.buffer->used + + ctx->block_end_indexes.arr.buffer->used; + if (ctx->uidlist->max_size < mem_size) + ctx->uidlist->max_size = mem_size; + + ctx->list_start_idx += count; + array_clear(&ctx->lists); + + uidlist_write_block_list_and_header(ctx, ctx->output, + &ctx->block_offsets, + &ctx->block_end_indexes, TRUE); + + (void)squat_uidlist_map(ctx->uidlist); + + array_clear(&ctx->block_offsets); + array_clear(&ctx->block_end_indexes); +} + +int squat_uidlist_build_finish(struct squat_uidlist_build_context *ctx) +{ + if (ctx->uidlist->corrupted) + return -1; + + if (!ctx->output->closed) { + (void)o_stream_seek(ctx->output, 0); + o_stream_nsend(ctx->output, + &ctx->build_hdr, sizeof(ctx->build_hdr)); + (void)o_stream_seek(ctx->output, ctx->build_hdr.used_file_size); + } + + if (o_stream_finish(ctx->output) < 0) { + i_error("write() to %s failed: %s", ctx->uidlist->path, + o_stream_get_error(ctx->output)); + return -1; + } + return 0; +} + +void squat_uidlist_build_deinit(struct squat_uidlist_build_context **_ctx) +{ + struct squat_uidlist_build_context *ctx = *_ctx; + + *_ctx = NULL; + + i_assert(array_count(&ctx->lists) == 0 || ctx->uidlist->corrupted); + i_assert(ctx->uidlist->building); + ctx->uidlist->building = FALSE; + + if (ctx->uidlist->file_lock != NULL) + file_unlock(&ctx->uidlist->file_lock); + else + file_dotlock_delete(&ctx->uidlist->dotlock); + + if (ctx->need_reopen) + (void)squat_uidlist_open(ctx->uidlist); + + array_free(&ctx->block_offsets); + array_free(&ctx->block_end_indexes); + array_free(&ctx->lists); + o_stream_ignore_last_errors(ctx->output); + o_stream_unref(&ctx->output); + i_free(ctx); +} + +int squat_uidlist_rebuild_init(struct squat_uidlist_build_context *build_ctx, + bool compress, + struct squat_uidlist_rebuild_context **ctx_r) +{ + struct squat_uidlist_rebuild_context *ctx; + struct squat_uidlist_file_header hdr; + const char *temp_path; + int fd; + + if (build_ctx->build_hdr.link_count == 0) + return 0; + + if (!compress) { + if (build_ctx->build_hdr.link_count < + build_ctx->build_hdr.count*2/3) + return 0; + } + + /* make sure the entire uidlist is in memory before beginning, + otherwise the pages are faulted to memory in random order which + takes forever. */ + if (squat_uidlist_read_to_memory(build_ctx->uidlist) < 0) + return -1; + + temp_path = t_strconcat(build_ctx->uidlist->path, ".tmp", NULL); + fd = squat_trie_create_fd(build_ctx->uidlist->trie, temp_path, O_TRUNC); + if (fd == -1) + return -1; + + ctx = i_new(struct squat_uidlist_rebuild_context, 1); + ctx->uidlist = build_ctx->uidlist; + ctx->build_ctx = build_ctx; + ctx->fd = fd; + ctx->output = o_stream_create_fd(ctx->fd, 0); + ctx->next_uid_list_idx = 0x100; + o_stream_cork(ctx->output); + + i_zero(&hdr); + o_stream_nsend(ctx->output, &hdr, sizeof(hdr)); + + ctx->cur_block_start_offset = ctx->output->offset; + i_array_init(&ctx->new_block_offsets, + build_ctx->build_hdr.count / UIDLIST_BLOCK_LIST_COUNT); + i_array_init(&ctx->new_block_end_indexes, + build_ctx->build_hdr.count / UIDLIST_BLOCK_LIST_COUNT); + *ctx_r = ctx; + return 1; +} + +static void +uidlist_rebuild_flush_block(struct squat_uidlist_rebuild_context *ctx) +{ + uint8_t buf[SQUAT_PACK_MAX_SIZE], *bufp; + uint32_t block_offset, block_end_idx; + unsigned int i; + + ctx->new_count += ctx->list_idx; + + block_offset = ctx->output->offset; + block_end_idx = ctx->new_count; + array_push_back(&ctx->new_block_offsets, &block_offset); + array_push_back(&ctx->new_block_end_indexes, &block_end_idx); + + /* this block's contents started from cur_block_start_offset and + ended to current offset. write the size of this area. */ + bufp = buf; + squat_pack_num(&bufp, block_offset - ctx->cur_block_start_offset); + o_stream_nsend(ctx->output, buf, bufp - buf); + + /* write the sizes/flags */ + for (i = 0; i < ctx->list_idx; i++) { + bufp = buf; + squat_pack_num(&bufp, ctx->list_sizes[i]); + o_stream_nsend(ctx->output, buf, bufp - buf); + } + ctx->cur_block_start_offset = ctx->output->offset; +} + +uint32_t squat_uidlist_rebuild_next(struct squat_uidlist_rebuild_context *ctx, + const ARRAY_TYPE(uint32_t) *uids) +{ + int ret; + + T_BEGIN { + ret = uidlist_write_array(ctx->output, array_front(uids), + array_count(uids), 0, 0, FALSE, + &ctx->list_sizes[ctx->list_idx]); + } T_END; + if (ret < 0) + squat_uidlist_set_corrupted(ctx->uidlist, "Broken uidlists"); + + if (++ctx->list_idx == UIDLIST_BLOCK_LIST_COUNT) { + uidlist_rebuild_flush_block(ctx); + ctx->list_idx = 0; + } + return ctx->next_uid_list_idx++ << 1; +} + +uint32_t squat_uidlist_rebuild_nextu(struct squat_uidlist_rebuild_context *ctx, + const ARRAY_TYPE(seq_range) *uids) +{ + const struct seq_range *range; + ARRAY_TYPE(uint32_t) tmp_uids; + uint32_t seq, uid1, ret; + unsigned int i, count; + + range = array_get(uids, &count); + if (count == 0) + return 0; + + if (range[count-1].seq2 < 8) { + /* we can use a singleton bitmask */ + ret = 0; + for (i = 0; i < count; i++) { + for (seq = range[i].seq1; seq <= range[i].seq2; seq++) + ret |= 1 << (seq+1); + } + return ret; + } + if (count == 1 && range[0].seq1 == range[0].seq2) { + /* single UID */ + return (range[0].seq1 << 1) | 1; + } + + /* convert seq range to our internal representation and use the + normal _rebuild_next() to write it */ + i_array_init(&tmp_uids, 128); + for (i = 0; i < count; i++) { + if (range[i].seq1 == range[i].seq2) + array_push_back(&tmp_uids, &range[i].seq1); + else { + uid1 = range[i].seq1 | UID_LIST_MASK_RANGE; + array_push_back(&tmp_uids, &uid1); + array_push_back(&tmp_uids, &range[i].seq2); + } + } + ret = squat_uidlist_rebuild_next(ctx, &tmp_uids); + array_free(&tmp_uids); + return ret; +} + +int squat_uidlist_rebuild_finish(struct squat_uidlist_rebuild_context *ctx, + bool cancel) +{ + const char *temp_path; + int ret = 1; + + if (ctx->list_idx != 0) + uidlist_rebuild_flush_block(ctx); + if (cancel || ctx->uidlist->corrupted) + ret = 0; + + temp_path = t_strconcat(ctx->uidlist->path, ".tmp", NULL); + if (ret > 0) { + ctx->build_ctx->build_hdr.indexid = + ctx->uidlist->trie->hdr.indexid; + ctx->build_ctx->build_hdr.count = ctx->new_count; + ctx->build_ctx->build_hdr.link_count = 0; + uidlist_write_block_list_and_header(ctx->build_ctx, ctx->output, + &ctx->new_block_offsets, + &ctx->new_block_end_indexes, + FALSE); + (void)o_stream_seek(ctx->output, 0); + o_stream_nsend(ctx->output, &ctx->build_ctx->build_hdr, + sizeof(ctx->build_ctx->build_hdr)); + (void)o_stream_seek(ctx->output, + ctx->build_ctx->build_hdr.used_file_size); + + if (ctx->uidlist->corrupted) + ret = -1; + else if (o_stream_finish(ctx->output) < 0) { + i_error("write(%s) failed: %s", temp_path, + o_stream_get_error(ctx->output)); + ret = -1; + } else if (rename(temp_path, ctx->uidlist->path) < 0) { + i_error("rename(%s, %s) failed: %m", + temp_path, ctx->uidlist->path); + ret = -1; + } + ctx->build_ctx->need_reopen = TRUE; + } else { + o_stream_abort(ctx->output); + } + + /* we no longer require the entire uidlist to be in memory, + let it be used for something more useful. */ + squat_uidlist_free_from_memory(ctx->uidlist); + + o_stream_unref(&ctx->output); + if (close(ctx->fd) < 0) + i_error("close(%s) failed: %m", temp_path); + + if (ret <= 0) + i_unlink(temp_path); + array_free(&ctx->new_block_offsets); + array_free(&ctx->new_block_end_indexes); + i_free(ctx); + return ret < 0 ? -1 : 0; +} + +static void +uidlist_flush(struct squat_uidlist_build_context *ctx, + struct uidlist_list *list, uint32_t uid) +{ + uint32_t size, offset = ctx->output->offset; + + ctx->build_hdr.link_count++; + if (uidlist_write(ctx->output, list, TRUE, &size) < 0) + squat_uidlist_set_corrupted(ctx->uidlist, "Broken uidlists"); + + list->uid_count = 2; + list->uid_begins_with_pointer = TRUE; + + list->uid_list[0] = offset; + list->uid_list[1] = uid; +} + +static struct uidlist_list * +uidlist_add_new(struct squat_uidlist_build_context *ctx, unsigned int count, + uint32_t *uid_list_idx_r) +{ + struct uidlist_list *list; + + i_assert(array_count(&ctx->lists) + + ctx->list_start_idx == ctx->build_hdr.count); + *uid_list_idx_r = (ctx->build_hdr.count + 0x100) << 1; + list = array_append_space(&ctx->lists); + ctx->build_hdr.count++; + + list->uid_count = count; + return list; +} + +uint32_t squat_uidlist_build_add_uid(struct squat_uidlist_build_context *ctx, + uint32_t uid_list_idx, uint32_t uid) +{ + struct uidlist_list *list; + unsigned int idx, mask; + uint32_t *p; + + if ((uid_list_idx & 1) != 0) { + /* adding second UID */ + uint32_t prev_uid = uid_list_idx >> 1; + + i_assert(prev_uid != uid); + list = uidlist_add_new(ctx, 2, &uid_list_idx); + list->uid_list[0] = prev_uid; + if (prev_uid + 1 == uid) + list->uid_list[0] |= UID_LIST_MASK_RANGE; + list->uid_list[1] = uid; + return uid_list_idx; + } else if (uid_list_idx < (0x100 << 1)) { + uint32_t old_list_idx; + + if (uid < 8) { + /* UID lists containing only UIDs 0-7 are saved as + uidlist values 2..511. think of it as a bitmask. */ + uid_list_idx |= 1 << (uid + 1); + i_assert((uid_list_idx & 1) == 0); + return uid_list_idx; + } + + if (uid_list_idx == 0) { + /* first UID */ + return (uid << 1) | 1; + } + + /* create a new list */ + old_list_idx = uid_list_idx >> 1; + list = uidlist_add_new(ctx, 1, &uid_list_idx); + /* add the first UID ourself */ + idx = 0; + i_assert((old_list_idx & 0xff) != 0); + for (mask = 1; mask <= 128; mask <<= 1, idx++) { + if ((old_list_idx & mask) != 0) { + list->uid_list[0] = idx; + idx++; mask <<= 1; + break; + } + } + for (; mask <= 128; mask <<= 1, idx++) { + if ((old_list_idx & mask) != 0) { + (void)squat_uidlist_build_add_uid(ctx, + uid_list_idx, idx); + } + } + } + + /* add to existing list */ + idx = (uid_list_idx >> 1) - 0x100; + if (idx < ctx->list_start_idx) { + list = uidlist_add_new(ctx, 2, &uid_list_idx); + list->uid_list[0] = UID_LIST_POINTER_MASK_LIST_IDX | idx; + list->uid_list[1] = uid; + list->uid_begins_with_pointer = TRUE; + ctx->build_hdr.link_count++; + return uid_list_idx; + } + + idx -= ctx->list_start_idx; + if (idx >= array_count(&ctx->lists)) { + squat_uidlist_set_corrupted(ctx->uidlist, + "missing/broken uidlist"); + return 0; + } + list = array_idx_modifiable(&ctx->lists, idx); + i_assert(list->uid_count > 0); + + p = &list->uid_list[list->uid_count-1]; + i_assert(uid != *p || ctx->uidlist->corrupted || + (list->uid_count == 1 && list->uid_begins_with_pointer)); + if (uid == *p + 1 && + (list->uid_count > 1 || !list->uid_begins_with_pointer)) { + /* use a range */ + if (list->uid_count > 1 && (p[-1] & UID_LIST_MASK_RANGE) != 0 && + (list->uid_count > 2 || !list->uid_begins_with_pointer)) { + /* increase the existing range */ + *p += 1; + return uid_list_idx; + } + + if (list->uid_count == UIDLIST_LIST_SIZE) { + uidlist_flush(ctx, list, uid); + return uid_list_idx; + } + /* create a new range */ + *p |= UID_LIST_MASK_RANGE; + } else { + if (list->uid_count == UIDLIST_LIST_SIZE) { + uidlist_flush(ctx, list, uid); + return uid_list_idx; + } + } + + p++; + list->uid_count++; + + *p = uid; + return uid_list_idx; +} + +static void uidlist_array_append(ARRAY_TYPE(uint32_t) *uids, uint32_t uid) +{ + uint32_t *uidlist; + unsigned int count; + + uidlist = array_get_modifiable(uids, &count); + if (count == 0) { + array_push_back(uids, &uid); + return; + } + if (uidlist[count-1] + 1 == uid) { + if (count > 1 && (uidlist[count-2] & + UID_LIST_MASK_RANGE) != 0) { + uidlist[count-1]++; + return; + } + uidlist[count-1] |= UID_LIST_MASK_RANGE; + } + array_push_back(uids, &uid); +} + +static void uidlist_array_append_range(ARRAY_TYPE(uint32_t) *uids, + uint32_t uid1, uint32_t uid2) +{ + uint32_t *uidlist; + unsigned int count; + + i_assert(uid1 < uid2); + + uidlist = array_get_modifiable(uids, &count); + if (count == 0) { + uid1 |= UID_LIST_MASK_RANGE; + array_push_back(uids, &uid1); + array_push_back(uids, &uid2); + return; + } + if (uidlist[count-1] + 1 == uid1) { + if (count > 1 && (uidlist[count-2] & + UID_LIST_MASK_RANGE) != 0) { + uidlist[count-1] = uid2; + return; + } + uidlist[count-1] |= UID_LIST_MASK_RANGE; + } else { + uid1 |= UID_LIST_MASK_RANGE; + array_push_back(uids, &uid1); + } + array_push_back(uids, &uid2); +} + +static int +squat_uidlist_get_at_offset(struct squat_uidlist *uidlist, uoff_t offset, + uint32_t num, ARRAY_TYPE(uint32_t) *uids) +{ + const uint32_t *uid_list; + const uint8_t *p, *end; + uint32_t size, base_uid, next_uid, flags, prev; + uoff_t uidlist_data_offset; + unsigned int i, j, count; + + if (num != 0) + uidlist_data_offset = offset; + else { + /* not given, read it */ + if (uidlist_file_cache_read(uidlist, offset, + SQUAT_PACK_MAX_SIZE) < 0) + return -1; + + p = CONST_PTR_OFFSET(uidlist->data, offset); + end = CONST_PTR_OFFSET(uidlist->data, uidlist->data_size); + num = squat_unpack_num(&p, end); + uidlist_data_offset = p - (const uint8_t *)uidlist->data; + } + size = num >> 2; + + if (uidlist_file_cache_read(uidlist, uidlist_data_offset, size) < 0) + return -1; + if (uidlist_data_offset + size > uidlist->data_size) { + squat_uidlist_set_corrupted(uidlist, + "size points outside file"); + return -1; + } + + p = CONST_PTR_OFFSET(uidlist->data, uidlist_data_offset); + end = p + size; + + flags = num; + if ((flags & UIDLIST_PACKED_FLAG_BEGINS_WITH_POINTER) != 0) { + /* link to the file */ + prev = squat_unpack_num(&p, end); + + if ((prev & 1) != 0) { + /* pointer to uidlist */ + prev = ((prev >> 1) + 0x100) << 1; + if (squat_uidlist_get(uidlist, prev, uids) < 0) + return -1; + } else { + prev = offset - (prev >> 1); + if (squat_uidlist_get_at_offset(uidlist, prev, + 0, uids) < 0) + return -1; + } + uid_list = array_get(uids, &count); + next_uid = count == 0 ? 0 : uid_list[count-1] + 1; + } else { + next_uid = 0; + } + + num = base_uid = squat_unpack_num(&p, end); + if ((flags & UIDLIST_PACKED_FLAG_BITMASK) == 0) + base_uid >>= 1; + if (base_uid < next_uid) { + squat_uidlist_set_corrupted(uidlist, + "broken continued uidlist"); + return -1; + } + + if ((flags & UIDLIST_PACKED_FLAG_BITMASK) != 0) { + /* bitmask */ + size = end - p; + + uidlist_array_append(uids, base_uid++); + for (i = 0; i < size; i++) { + for (j = 0; j < 8; j++, base_uid++) { + if ((p[i] & (1 << j)) != 0) + uidlist_array_append(uids, base_uid); + } + } + } else { + /* range */ + for (;;) { + if ((num & 1) == 0) { + uidlist_array_append(uids, base_uid); + } else { + /* range */ + uint32_t seq1 = base_uid; + base_uid += squat_unpack_num(&p, end) + 1; + uidlist_array_append_range(uids, seq1, + base_uid); + } + if (p == end) + break; + + num = squat_unpack_num(&p, end); + base_uid += (num >> 1) + 1; + } + } + return 0; +} + +static int +squat_uidlist_get_offset(struct squat_uidlist *uidlist, uint32_t uid_list_idx, + uint32_t *offset_r, uint32_t *num_r) +{ + const uint8_t *p, *end; + unsigned int idx; + uint32_t num, skip_bytes, uidlists_offset; + size_t max_map_size; + + if (uidlist->fd == -1) { + squat_uidlist_set_corrupted(uidlist, "no uidlists"); + return -1; + } + + if (bsearch_insert_pos(&uid_list_idx, uidlist->cur_block_end_indexes, + uidlist->cur_block_count, + sizeof(uint32_t), uint32_cmp, &idx)) + idx++; + if (unlikely(idx == uidlist->cur_block_count)) { + squat_uidlist_set_corrupted(uidlist, "uidlist not found"); + return -1; + } + i_assert(uidlist->cur_block_end_indexes != NULL); + if (unlikely(idx > 0 && + uidlist->cur_block_end_indexes[idx-1] > uid_list_idx)) { + squat_uidlist_set_corrupted(uidlist, "broken block list"); + return -1; + } + + /* make sure everything is mapped */ + uid_list_idx -= idx == 0 ? 0 : uidlist->cur_block_end_indexes[idx-1]; + max_map_size = SQUAT_PACK_MAX_SIZE * (1+uid_list_idx); + if (uidlist_file_cache_read(uidlist, uidlist->cur_block_offsets[idx], + max_map_size) < 0) + return -1; + + /* find the uidlist inside the block */ + i_assert(uidlist->cur_block_offsets != NULL); + p = CONST_PTR_OFFSET(uidlist->data, uidlist->cur_block_offsets[idx]); + end = CONST_PTR_OFFSET(uidlist->data, uidlist->data_size); + + uidlists_offset = uidlist->cur_block_offsets[idx] - + squat_unpack_num(&p, end); + for (skip_bytes = 0; uid_list_idx > 0; uid_list_idx--) { + num = squat_unpack_num(&p, end); + skip_bytes += num >> 2; + } + *offset_r = uidlists_offset + skip_bytes; + *num_r = squat_unpack_num(&p, end); + + if (unlikely(p == end)) { + squat_uidlist_set_corrupted(uidlist, "broken file"); + return -1; + } + if (unlikely(*offset_r > uidlist->mmap_size && + uidlist->mmap_base != NULL)) { + squat_uidlist_set_corrupted(uidlist, "broken offset"); + return -1; + } + return 0; +} + +int squat_uidlist_get(struct squat_uidlist *uidlist, uint32_t uid_list_idx, + ARRAY_TYPE(uint32_t) *uids) +{ + unsigned int mask; + uint32_t uid, offset, num; + + if ((uid_list_idx & 1) != 0) { + /* single UID */ + uid = uid_list_idx >> 1; + uidlist_array_append(uids, uid); + return 0; + } else if (uid_list_idx < (0x100 << 1)) { + /* bitmask */ + for (uid = 0, mask = 2; mask <= 256; mask <<= 1, uid++) { + if ((uid_list_idx & mask) != 0) + uidlist_array_append(uids, uid); + } + return 0; + } + + uid_list_idx = (uid_list_idx >> 1) - 0x100; + if (squat_uidlist_get_offset(uidlist, uid_list_idx, &offset, &num) < 0) + return -1; + return squat_uidlist_get_at_offset(uidlist, offset, num, uids); +} + +uint32_t squat_uidlist_singleton_last_uid(uint32_t uid_list_idx) +{ + unsigned int idx, mask; + + if ((uid_list_idx & 1) != 0) { + /* single UID */ + return uid_list_idx >> 1; + } else if (uid_list_idx < (0x100 << 1)) { + /* bitmask */ + if (uid_list_idx == 2) { + /* just a quick optimization */ + return 0; + } + for (idx = 7, mask = 256; mask > 2; mask >>= 1, idx--) { + if ((uid_list_idx & mask) != 0) + return idx; + } + } + + i_unreached(); + return 0; +} + +int squat_uidlist_get_seqrange(struct squat_uidlist *uidlist, + uint32_t uid_list_idx, + ARRAY_TYPE(seq_range) *seq_range_arr) +{ + ARRAY_TYPE(uint32_t) tmp_uid_arr; + struct seq_range range; + const uint32_t *tmp_uids; + unsigned int i, count; + int ret; + + i_array_init(&tmp_uid_arr, 128); + ret = squat_uidlist_get(uidlist, uid_list_idx, &tmp_uid_arr); + if (ret == 0) { + tmp_uids = array_get(&tmp_uid_arr, &count); + for (i = 0; i < count; i++) { + if ((tmp_uids[i] & UID_LIST_MASK_RANGE) == 0) + range.seq1 = range.seq2 = tmp_uids[i]; + else { + range.seq1 = tmp_uids[i] & ~UID_LIST_MASK_RANGE; + range.seq2 = tmp_uids[++i]; + } + array_push_back(seq_range_arr, &range); + } + } + array_free(&tmp_uid_arr); + return ret; +} + +int squat_uidlist_filter(struct squat_uidlist *uidlist, uint32_t uid_list_idx, + ARRAY_TYPE(seq_range) *uids) +{ + const struct seq_range *parent_range; + ARRAY_TYPE(seq_range) dest_uids; + ARRAY_TYPE(uint32_t) relative_uids; + const uint32_t *rel_range; + unsigned int i, rel_count, parent_idx, parent_count, diff, parent_uid; + uint32_t prev_seq, seq1, seq2; + int ret = 0; + + parent_range = array_get(uids, &parent_count); + if (parent_count == 0) + return 0; + + i_array_init(&relative_uids, 128); + i_array_init(&dest_uids, 128); + if (squat_uidlist_get(uidlist, uid_list_idx, &relative_uids) < 0) + ret = -1; + + parent_idx = 0; + rel_range = array_get(&relative_uids, &rel_count); + prev_seq = 0; parent_uid = parent_range[0].seq1; + for (i = 0; i < rel_count; i++) { + if (unlikely(parent_uid == (uint32_t)-1)) { + i_error("broken UID ranges"); + ret = -1; + break; + } + if ((rel_range[i] & UID_LIST_MASK_RANGE) == 0) + seq1 = seq2 = rel_range[i]; + else { + seq1 = (rel_range[i] & ~UID_LIST_MASK_RANGE); + seq2 = rel_range[++i]; + } + i_assert(seq1 >= prev_seq); + diff = seq1 - prev_seq; + while (diff > 0) { + if (unlikely(parent_uid == (uint32_t)-1)) { + i_error("broken UID ranges"); + ret = -1; + break; + } + + for (; parent_idx < parent_count; parent_idx++) { + if (parent_range[parent_idx].seq2 <= parent_uid) + continue; + if (parent_uid < parent_range[parent_idx].seq1) + parent_uid = parent_range[parent_idx].seq1; + else + parent_uid++; + break; + } + diff--; + } + diff = seq2 - seq1 + 1; + while (diff > 0) { + if (unlikely(parent_uid == (uint32_t)-1)) { + i_error("broken UID ranges"); + ret = -1; + break; + } + seq_range_array_add(&dest_uids, parent_uid); + for (; parent_idx < parent_count; parent_idx++) { + if (parent_range[parent_idx].seq2 <= parent_uid) + continue; + if (parent_uid < parent_range[parent_idx].seq1) + parent_uid = parent_range[parent_idx].seq1; + else + parent_uid++; + break; + } + diff--; + } + + prev_seq = seq2 + 1; + } + + buffer_set_used_size(uids->arr.buffer, 0); + array_append_array(uids, &dest_uids); + + array_free(&relative_uids); + array_free(&dest_uids); + return ret; +} + +size_t squat_uidlist_mem_used(struct squat_uidlist *uidlist, + unsigned int *count_r) +{ + *count_r = uidlist->hdr.count; + return uidlist->max_size; +} diff --git a/src/plugins/fts-squat/squat-uidlist.h b/src/plugins/fts-squat/squat-uidlist.h new file mode 100644 index 0000000..79ed791 --- /dev/null +++ b/src/plugins/fts-squat/squat-uidlist.h @@ -0,0 +1,71 @@ +#ifndef SQUAT_UIDLIST_H +#define SQUAT_UIDLIST_H + +struct squat_trie; +struct squat_uidlist_build_context; +struct squat_uidlist_rebuild_context; + +struct squat_uidlist_file_header { + uint32_t indexid; + uint32_t used_file_size; + uint32_t block_list_offset; + uint32_t count, link_count; +}; + +/* + uidlist file: + + struct uidlist_header; + + // size includes both prev_offset and uidlist + packed (size << 2) | packed_flags; // UIDLIST_PACKED_FLAG_* + [packed prev_offset;] // If UIDLIST_PACKED_FLAG_BEGINS_WITH_OFFSET is set + if (UIDLIST_PACKED_FLAG_BITMASK) { + packed base_uid; // first UID in uidlist + uint8_t bitmask[]; // first bit is base_uid+1 + } else { + // FIXME: packed range + } +*/ + +#define UIDLIST_IS_SINGLETON(idx) \ + (((idx) & 1) != 0 || (idx) < (0x100 << 1)) + +struct squat_uidlist *squat_uidlist_init(struct squat_trie *trie); +void squat_uidlist_deinit(struct squat_uidlist *uidlist); + +int squat_uidlist_refresh(struct squat_uidlist *uidlist); + +int squat_uidlist_build_init(struct squat_uidlist *uidlist, + struct squat_uidlist_build_context **ctx_r); +uint32_t squat_uidlist_build_add_uid(struct squat_uidlist_build_context *ctx, + uint32_t uid_list_idx, uint32_t uid); +void squat_uidlist_build_flush(struct squat_uidlist_build_context *ctx); +int squat_uidlist_build_finish(struct squat_uidlist_build_context *ctx); +void squat_uidlist_build_deinit(struct squat_uidlist_build_context **ctx); + +int squat_uidlist_rebuild_init(struct squat_uidlist_build_context *build_ctx, + bool compress, + struct squat_uidlist_rebuild_context **ctx_r); +uint32_t squat_uidlist_rebuild_next(struct squat_uidlist_rebuild_context *ctx, + const ARRAY_TYPE(uint32_t) *uids); +uint32_t squat_uidlist_rebuild_nextu(struct squat_uidlist_rebuild_context *ctx, + const ARRAY_TYPE(seq_range) *uids); +int squat_uidlist_rebuild_finish(struct squat_uidlist_rebuild_context *ctx, + bool cancel); + +int squat_uidlist_get(struct squat_uidlist *uidlist, uint32_t uid_list_idx, + ARRAY_TYPE(uint32_t) *uids); +uint32_t squat_uidlist_singleton_last_uid(uint32_t uid_list_idx); + +int squat_uidlist_get_seqrange(struct squat_uidlist *uidlist, + uint32_t uid_list_idx, + ARRAY_TYPE(seq_range) *seq_range_arr); +int squat_uidlist_filter(struct squat_uidlist *uidlist, uint32_t uid_list_idx, + ARRAY_TYPE(seq_range) *uids); + +void squat_uidlist_delete(struct squat_uidlist *uidlist); +size_t squat_uidlist_mem_used(struct squat_uidlist *uidlist, + unsigned int *count_r); + +#endif |