diff options
Diffstat (limited to 'util')
| -rw-r--r-- | util/Makefile.am | 24 | ||||
| -rw-r--r-- | util/Makefile.in | 709 | ||||
| -rw-r--r-- | util/cache.c | 128 | ||||
| -rw-r--r-- | util/cache.h | 68 | ||||
| -rw-r--r-- | util/gtrie.c | 511 | ||||
| -rw-r--r-- | util/gtrie.h | 42 | ||||
| -rw-r--r-- | util/list.c | 118 | ||||
| -rw-r--r-- | util/list.h | 59 | ||||
| -rw-r--r-- | util/md5-utils.c | 355 | ||||
| -rw-r--r-- | util/md5-utils.h | 54 | ||||
| -rw-r--r-- | util/url-scanner.c | 583 | ||||
| -rw-r--r-- | util/url-scanner.h | 65 |
12 files changed, 2716 insertions, 0 deletions
diff --git a/util/Makefile.am b/util/Makefile.am new file mode 100644 index 0000000..ff7b7fb --- /dev/null +++ b/util/Makefile.am @@ -0,0 +1,24 @@ +## Process this file with automake to produce Makefile.in + +SUBDIRS = . + +noinst_LTLIBRARIES = libgmime-util.la + +INCLUDES = -I$(top_srcdir) \ + $(VERSION_FLAGS) \ + -DG_LOG_DOMAIN=\"util\" \ + $(GMIME_CFLAGS) \ + $(GLIB_CFLAGS) + +libgmime-util_la_SOURCES = \ + cache.c \ + cache.h \ + gtrie.c \ + gtrie.h \ + list.c \ + list.h \ + md5-utils.c \ + md5-utils.h \ + url-scanner.c \ + url-scanner.h + diff --git a/util/Makefile.in b/util/Makefile.in new file mode 100644 index 0000000..cd03dc1 --- /dev/null +++ b/util/Makefile.in @@ -0,0 +1,709 @@ +# Makefile.in generated by automake 1.11.3 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, 2002, +# 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 Free Software +# Foundation, Inc. +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +VPATH = @srcdir@ +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_triplet = @build@ +host_triplet = @host@ +target_triplet = @target@ +subdir = util +DIST_COMMON = $(srcdir)/Makefile.am $(srcdir)/Makefile.in +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/acinclude.m4 \ + $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +LTLIBRARIES = $(noinst_LTLIBRARIES) +libgmime-util_la_LIBADD = +am_libgmime-util_la_OBJECTS = cache.lo gtrie.lo list.lo md5-utils.lo \ + url-scanner.lo +libgmime-util_la_OBJECTS = $(am_libgmime-util_la_OBJECTS) +DEFAULT_INCLUDES = -I.@am__isrc@ -I$(top_builddir) +depcomp = $(SHELL) $(top_srcdir)/depcomp +am__depfiles_maybe = depfiles +am__mv = mv -f +COMPILE = $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) \ + $(CPPFLAGS) $(AM_CFLAGS) $(CFLAGS) +CCLD = $(CC) +LINK = $(LIBTOOL) --tag=CC $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) \ + --mode=link $(CCLD) $(AM_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \ + $(LDFLAGS) -o $@ +SOURCES = $(libgmime-util_la_SOURCES) +DIST_SOURCES = $(libgmime-util_la_SOURCES) +RECURSIVE_TARGETS = all-recursive check-recursive dvi-recursive \ + html-recursive info-recursive install-data-recursive \ + install-dvi-recursive install-exec-recursive \ + install-html-recursive install-info-recursive \ + install-pdf-recursive install-ps-recursive install-recursive \ + installcheck-recursive installdirs-recursive pdf-recursive \ + ps-recursive uninstall-recursive +RECURSIVE_CLEAN_TARGETS = mostlyclean-recursive clean-recursive \ + distclean-recursive maintainer-clean-recursive +AM_RECURSIVE_TARGETS = $(RECURSIVE_TARGETS:-recursive=) \ + $(RECURSIVE_CLEAN_TARGETS:-recursive=) tags TAGS ctags CTAGS \ + distdir +ETAGS = etags +CTAGS = ctags +DIST_SUBDIRS = $(SUBDIRS) +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +am__relativize = \ + dir0=`pwd`; \ + sed_first='s,^\([^/]*\)/.*$$,\1,'; \ + sed_rest='s,^[^/]*/*,,'; \ + sed_last='s,^.*/\([^/]*\)$$,\1,'; \ + sed_butlast='s,/*[^/]*$$,,'; \ + while test -n "$$dir1"; do \ + first=`echo "$$dir1" | sed -e "$$sed_first"`; \ + if test "$$first" != "."; then \ + if test "$$first" = ".."; then \ + dir2=`echo "$$dir0" | sed -e "$$sed_last"`/"$$dir2"; \ + dir0=`echo "$$dir0" | sed -e "$$sed_butlast"`; \ + else \ + first2=`echo "$$dir2" | sed -e "$$sed_first"`; \ + if test "$$first2" = "$$first"; then \ + dir2=`echo "$$dir2" | sed -e "$$sed_rest"`; \ + else \ + dir2="../$$dir2"; \ + fi; \ + dir0="$$dir0"/"$$first"; \ + fi; \ + fi; \ + dir1=`echo "$$dir1" | sed -e "$$sed_rest"`; \ + done; \ + reldir="$$dir2" +ACLOCAL = @ACLOCAL@ +ACLOCAL_AMFLAGS = @ACLOCAL_AMFLAGS@ +AMTAR = @AMTAR@ +API_VERSION = @API_VERSION@ +AR = @AR@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CFLAGS = @CFLAGS@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CSC = @CSC@ +CYGPATH_W = @CYGPATH_W@ +DB2HTML = @DB2HTML@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +DLLTOOL = @DLLTOOL@ +DOLT_BASH = @DOLT_BASH@ +DSYMUTIL = @DSYMUTIL@ +DUMPBIN = @DUMPBIN@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +FGREP = @FGREP@ +GACUTIL = @GACUTIL@ +GAPI_CODEGEN = @GAPI_CODEGEN@ +GAPI_FIXUP = @GAPI_FIXUP@ +GAPI_PARSER = @GAPI_PARSER@ +GAPI_TOOLS_CFLAGS = @GAPI_TOOLS_CFLAGS@ +GAPI_TOOLS_LIBS = @GAPI_TOOLS_LIBS@ +GLIB_CFLAGS = @GLIB_CFLAGS@ +GLIB_COMPILE_RESOURCES = @GLIB_COMPILE_RESOURCES@ +GLIB_GENMARSHAL = @GLIB_GENMARSHAL@ +GLIB_LIBS = @GLIB_LIBS@ +GLIB_MKENUMS = @GLIB_MKENUMS@ +GLIB_SHARP_CFLAGS = @GLIB_SHARP_CFLAGS@ +GLIB_SHARP_LIBS = @GLIB_SHARP_LIBS@ +GMIME_API_VERSION = @GMIME_API_VERSION@ +GMIME_BINARY_AGE = @GMIME_BINARY_AGE@ +GMIME_CFLAGS = @GMIME_CFLAGS@ +GMIME_INCLUDEDIR = @GMIME_INCLUDEDIR@ +GMIME_INTERFACE_AGE = @GMIME_INTERFACE_AGE@ +GMIME_LIBDIR = @GMIME_LIBDIR@ +GMIME_LIBS = @GMIME_LIBS@ +GMIME_LIBS_PRIVATE = @GMIME_LIBS_PRIVATE@ +GMIME_MAJOR_VERSION = @GMIME_MAJOR_VERSION@ +GMIME_MICRO_VERSION = @GMIME_MICRO_VERSION@ +GMIME_MINOR_VERSION = @GMIME_MINOR_VERSION@ +GMIME_VERSION = @GMIME_VERSION@ +GOBJECT_QUERY = @GOBJECT_QUERY@ +GPGME_CONFIG = @GPGME_CONFIG@ +GPGME_PTHREAD_CFLAGS = @GPGME_PTHREAD_CFLAGS@ +GPGME_PTHREAD_LIBS = @GPGME_PTHREAD_LIBS@ +GREP = @GREP@ +GTKDOC_CHECK = @GTKDOC_CHECK@ +GTKDOC_DEPS_CFLAGS = @GTKDOC_DEPS_CFLAGS@ +GTKDOC_DEPS_LIBS = @GTKDOC_DEPS_LIBS@ +GTKDOC_MKPDF = @GTKDOC_MKPDF@ +GTKDOC_REBASE = @GTKDOC_REBASE@ +HTML_DIR = @HTML_DIR@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +LD = @LD@ +LDFLAGS = @LDFLAGS@ +LIBICONV = @LIBICONV@ +LIBOBJS = @LIBOBJS@ +LIBS = @LIBS@ +LIBTOOL = @LIBTOOL@ +LIB_EXE_MACHINE_FLAG = @LIB_EXE_MACHINE_FLAG@ +LIPO = @LIPO@ +LN_S = @LN_S@ +LTCOMPILE = @LTCOMPILE@ +LTCXXCOMPILE = @LTCXXCOMPILE@ +LTLIBICONV = @LTLIBICONV@ +LTLIBOBJS = @LTLIBOBJS@ +LT_AGE = @LT_AGE@ +LT_CURRENT = @LT_CURRENT@ +LT_CURRENT_MINUS_AGE = @LT_CURRENT_MINUS_AGE@ +LT_RELEASE = @LT_RELEASE@ +LT_REVISION = @LT_REVISION@ +MAINT = @MAINT@ +MAKEINFO = @MAKEINFO@ +MANIFEST_TOOL = @MANIFEST_TOOL@ +MKDIR_P = @MKDIR_P@ +MV = @MV@ +NM = @NM@ +NMEDIT = @NMEDIT@ +OBJDUMP = @OBJDUMP@ +OBJEXT = @OBJEXT@ +OTOOL = @OTOOL@ +OTOOL64 = @OTOOL64@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +PKG_CONFIG = @PKG_CONFIG@ +PKG_CONFIG_LIBDIR = @PKG_CONFIG_LIBDIR@ +PKG_CONFIG_PATH = @PKG_CONFIG_PATH@ +RANLIB = @RANLIB@ +RM = @RM@ +SED = @SED@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +STRIP = @STRIP@ +TAR = @TAR@ +VERSION = @VERSION@ +WINDRES = @WINDRES@ +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_DUMPBIN = @ac_ct_DUMPBIN@ +am__include = @am__include@ +am__leading_dot = @am__leading_dot@ +am__quote = @am__quote@ +am__tar = @am__tar@ +am__untar = @am__untar@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_vendor = @build_vendor@ +builddir = @builddir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +gacdir = @gacdir@ +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@ +ms_librarian = @ms_librarian@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +sysconfdir = @sysconfdir@ +target = @target@ +target_alias = @target_alias@ +target_cpu = @target_cpu@ +target_os = @target_os@ +target_vendor = @target_vendor@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +SUBDIRS = . +noinst_LTLIBRARIES = libgmime-util.la +INCLUDES = -I$(top_srcdir) \ + $(VERSION_FLAGS) \ + -DG_LOG_DOMAIN=\"util\" \ + $(GMIME_CFLAGS) \ + $(GLIB_CFLAGS) + +libgmime-util_la_SOURCES = \ + cache.c \ + cache.h \ + gtrie.c \ + gtrie.h \ + list.c \ + list.h \ + md5-utils.c \ + md5-utils.h \ + url-scanner.c \ + url-scanner.h + +all: all-recursive + +.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 util/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --foreign util/Makefile +.PRECIOUS: Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ + esac; + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: @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-noinstLTLIBRARIES: + -test -z "$(noinst_LTLIBRARIES)" || rm -f $(noinst_LTLIBRARIES) + @list='$(noinst_LTLIBRARIES)'; for p in $$list; do \ + dir="`echo $$p | sed -e 's|/[^/]*$$||'`"; \ + test "$$dir" != "$$p" || dir=.; \ + echo "rm -f \"$${dir}/so_locations\""; \ + rm -f "$${dir}/so_locations"; \ + done +libgmime-util.la: $(libgmime-util_la_OBJECTS) $(libgmime-util_la_DEPENDENCIES) $(EXTRA_libgmime-util_la_DEPENDENCIES) + $(LINK) $(libgmime-util_la_OBJECTS) $(libgmime-util_la_LIBADD) $(LIBS) + +mostlyclean-compile: + -rm -f *.$(OBJEXT) + +distclean-compile: + -rm -f *.tab.c + +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cache.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gtrie.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/list.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/md5-utils.Plo@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/url-scanner.Plo@am__quote@ + +.c.o: +@am__fastdepCC_TRUE@ $(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(COMPILE) -c $< + +.c.obj: +@am__fastdepCC_TRUE@ $(COMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ `$(CYGPATH_W) '$<'` +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(COMPILE) -c `$(CYGPATH_W) '$<'` + +.c.lo: +@am__fastdepCC_TRUE@ $(LTCOMPILE) -MT $@ -MD -MP -MF $(DEPDIR)/$*.Tpo -c -o $@ $< +@am__fastdepCC_TRUE@ $(am__mv) $(DEPDIR)/$*.Tpo $(DEPDIR)/$*.Plo +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='$<' object='$@' libtool=yes @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(LTCOMPILE) -c -o $@ $< + +mostlyclean-libtool: + -rm -f *.lo + +clean-libtool: + -rm -rf .libs _libs + +# This directory's subdirectories are mostly independent; you can cd +# into them and run `make' without going through this Makefile. +# To change the values of `make' variables: instead of editing Makefiles, +# (1) if the variable is set in `config.status', edit `config.status' +# (which will cause the Makefiles to be regenerated when you run `make'); +# (2) otherwise, pass the desired values on the `make' command line. +$(RECURSIVE_TARGETS): + @fail= failcom='exit 1'; \ + for f in x $$MAKEFLAGS; do \ + case $$f in \ + *=* | --[!k]*);; \ + *k*) failcom='fail=yes';; \ + esac; \ + done; \ + dot_seen=no; \ + target=`echo $@ | sed s/-recursive//`; \ + list='$(SUBDIRS)'; for subdir in $$list; do \ + echo "Making $$target in $$subdir"; \ + if test "$$subdir" = "."; then \ + dot_seen=yes; \ + local_target="$$target-am"; \ + else \ + local_target="$$target"; \ + fi; \ + ($(am__cd) $$subdir && $(MAKE) $(AM_MAKEFLAGS) $$local_target) \ + || eval $$failcom; \ + done; \ + if test "$$dot_seen" = "no"; then \ + $(MAKE) $(AM_MAKEFLAGS) "$$target-am" || exit 1; \ + fi; test -z "$$fail" + +$(RECURSIVE_CLEAN_TARGETS): + @fail= failcom='exit 1'; \ + for f in x $$MAKEFLAGS; do \ + case $$f in \ + *=* | --[!k]*);; \ + *k*) failcom='fail=yes';; \ + esac; \ + done; \ + dot_seen=no; \ + case "$@" in \ + distclean-* | maintainer-clean-*) list='$(DIST_SUBDIRS)' ;; \ + *) list='$(SUBDIRS)' ;; \ + esac; \ + rev=''; for subdir in $$list; do \ + if test "$$subdir" = "."; then :; else \ + rev="$$subdir $$rev"; \ + fi; \ + done; \ + rev="$$rev ."; \ + target=`echo $@ | sed s/-recursive//`; \ + for subdir in $$rev; do \ + echo "Making $$target in $$subdir"; \ + if test "$$subdir" = "."; then \ + local_target="$$target-am"; \ + else \ + local_target="$$target"; \ + fi; \ + ($(am__cd) $$subdir && $(MAKE) $(AM_MAKEFLAGS) $$local_target) \ + || eval $$failcom; \ + done && test -z "$$fail" +tags-recursive: + list='$(SUBDIRS)'; for subdir in $$list; do \ + test "$$subdir" = . || ($(am__cd) $$subdir && $(MAKE) $(AM_MAKEFLAGS) tags); \ + done +ctags-recursive: + list='$(SUBDIRS)'; for subdir in $$list; do \ + test "$$subdir" = . || ($(am__cd) $$subdir && $(MAKE) $(AM_MAKEFLAGS) ctags); \ + done + +ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + mkid -fID $$unique +tags: TAGS + +TAGS: tags-recursive $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + set x; \ + here=`pwd`; \ + if ($(ETAGS) --etags-include --version) >/dev/null 2>&1; then \ + include_option=--etags-include; \ + empty_fix=.; \ + else \ + include_option=--include; \ + empty_fix=; \ + fi; \ + list='$(SUBDIRS)'; for subdir in $$list; do \ + if test "$$subdir" = .; then :; else \ + test ! -f $$subdir/TAGS || \ + set "$$@" "$$include_option=$$here/$$subdir/TAGS"; \ + fi; \ + done; \ + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + shift; \ + if test -z "$(ETAGS_ARGS)$$*$$unique"; then :; else \ + test -n "$$unique" || unique=$$empty_fix; \ + if test $$# -gt 0; then \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + "$$@" $$unique; \ + else \ + $(ETAGS) $(ETAGSFLAGS) $(AM_ETAGSFLAGS) $(ETAGS_ARGS) \ + $$unique; \ + fi; \ + fi +ctags: CTAGS +CTAGS: ctags-recursive $(HEADERS) $(SOURCES) $(TAGS_DEPENDENCIES) \ + $(TAGS_FILES) $(LISP) + list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ + unique=`for i in $$list; do \ + if test -f "$$i"; then echo $$i; else echo $(srcdir)/$$i; fi; \ + done | \ + $(AWK) '{ files[$$0] = 1; nonempty = 1; } \ + END { if (nonempty) { for (i in files) print i; }; }'`; \ + test -z "$(CTAGS_ARGS)$$unique" \ + || $(CTAGS) $(CTAGSFLAGS) $(AM_CTAGSFLAGS) $(CTAGS_ARGS) \ + $$unique + +GTAGS: + here=`$(am__cd) $(top_builddir) && pwd` \ + && $(am__cd) $(top_srcdir) \ + && gtags -i $(GTAGS_ARGS) "$$here" + +distclean-tags: + -rm -f TAGS ID GTAGS GRTAGS GSYMS GPATH tags + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done + @list='$(DIST_SUBDIRS)'; for subdir in $$list; do \ + if test "$$subdir" = .; then :; else \ + test -d "$(distdir)/$$subdir" \ + || $(MKDIR_P) "$(distdir)/$$subdir" \ + || exit 1; \ + fi; \ + done + @list='$(DIST_SUBDIRS)'; for subdir in $$list; do \ + if test "$$subdir" = .; then :; else \ + dir1=$$subdir; dir2="$(distdir)/$$subdir"; \ + $(am__relativize); \ + new_distdir=$$reldir; \ + dir1=$$subdir; dir2="$(top_distdir)"; \ + $(am__relativize); \ + new_top_distdir=$$reldir; \ + echo " (cd $$subdir && $(MAKE) $(AM_MAKEFLAGS) top_distdir="$$new_top_distdir" distdir="$$new_distdir" \\"; \ + echo " am__remove_distdir=: am__skip_length_check=: am__skip_mode_fix=: distdir)"; \ + ($(am__cd) $$subdir && \ + $(MAKE) $(AM_MAKEFLAGS) \ + top_distdir="$$new_top_distdir" \ + distdir="$$new_distdir" \ + am__remove_distdir=: \ + am__skip_length_check=: \ + am__skip_mode_fix=: \ + distdir) \ + || exit 1; \ + fi; \ + done +check-am: all-am +check: check-recursive +all-am: Makefile $(LTLIBRARIES) +installdirs: installdirs-recursive +installdirs-am: +install: install-recursive +install-exec: install-exec-recursive +install-data: install-data-recursive +uninstall: uninstall-recursive + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-recursive +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-recursive + +clean-am: clean-generic clean-libtool clean-noinstLTLIBRARIES \ + mostlyclean-am + +distclean: distclean-recursive + -rm -rf ./$(DEPDIR) + -rm -f Makefile +distclean-am: clean-am distclean-compile distclean-generic \ + distclean-tags + +dvi: dvi-recursive + +dvi-am: + +html: html-recursive + +html-am: + +info: info-recursive + +info-am: + +install-data-am: + +install-dvi: install-dvi-recursive + +install-dvi-am: + +install-exec-am: + +install-html: install-html-recursive + +install-html-am: + +install-info: install-info-recursive + +install-info-am: + +install-man: + +install-pdf: install-pdf-recursive + +install-pdf-am: + +install-ps: install-ps-recursive + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-recursive + -rm -rf ./$(DEPDIR) + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-recursive + +mostlyclean-am: mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool + +pdf: pdf-recursive + +pdf-am: + +ps: ps-recursive + +ps-am: + +uninstall-am: + +.MAKE: $(RECURSIVE_CLEAN_TARGETS) $(RECURSIVE_TARGETS) ctags-recursive \ + install-am install-strip tags-recursive + +.PHONY: $(RECURSIVE_CLEAN_TARGETS) $(RECURSIVE_TARGETS) CTAGS GTAGS \ + all all-am check check-am clean clean-generic clean-libtool \ + clean-noinstLTLIBRARIES ctags ctags-recursive 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-pdf install-pdf-am install-ps install-ps-am \ + install-strip installcheck installcheck-am installdirs \ + installdirs-am maintainer-clean maintainer-clean-generic \ + mostlyclean mostlyclean-compile mostlyclean-generic \ + mostlyclean-libtool pdf pdf-am ps ps-am tags tags-recursive \ + uninstall uninstall-am + + +# 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/util/cache.c b/util/cache.c new file mode 100644 index 0000000..1fc8a8d --- /dev/null +++ b/util/cache.c @@ -0,0 +1,128 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include "cache.h" + + +static void +cache_node_free (gpointer node_data) +{ + CacheNode *node = (CacheNode *) node_data; + Cache *cache = node->cache; + + cache->free_node (node); + g_free (node->key); + + g_slice_free1 (cache->node_size, node); +} + + +Cache * +cache_new (CacheNodeExpireFunc expire, CacheNodeFreeFunc free_node, size_t node_size, size_t max_size) +{ + Cache *cache; + + cache = g_new (Cache, 1); + list_init (&cache->list); + cache->expire = expire; + cache->free_node = free_node; + cache->node_hash = g_hash_table_new_full (g_str_hash, g_str_equal, NULL, cache_node_free); + cache->node_size = node_size; + cache->max_size = max_size; + cache->size = 0; + + return cache; +} + + +void +cache_free (Cache *cache) +{ + g_hash_table_destroy (cache->node_hash); + g_free (cache); +} + + +void +cache_expire_unused (Cache *cache) +{ + ListNode *node, *prev; + + node = cache->list.tailpred; + while (node->prev && cache->size > cache->max_size) { + prev = node->prev; + if (cache->expire (cache, (CacheNode *) node)) { + list_unlink (node); + g_hash_table_remove (cache->node_hash, ((CacheNode *) node)->key); + cache->size--; + } + node = prev; + } +} + +CacheNode * +cache_node_insert (Cache *cache, const char *key) +{ + CacheNode *node; + + cache->size++; + + if (cache->size > cache->max_size) + cache_expire_unused (cache); + + node = g_slice_alloc (cache->node_size); + node->key = g_strdup (key); + node->cache = cache; + + g_hash_table_insert (cache->node_hash, node->key, node); + list_prepend (&cache->list, (ListNode *) node); + + return node; +} + +CacheNode * +cache_node_lookup (Cache *cache, const char *key, gboolean use) +{ + CacheNode *node; + + node = g_hash_table_lookup (cache->node_hash, key); + if (node && use) { + list_unlink ((ListNode *) node); + list_prepend (&cache->list, (ListNode *) node); + } + + return node; +} + +void +cache_node_expire (CacheNode *node) +{ + Cache *cache; + + cache = node->cache; + list_unlink ((ListNode *) node); + g_hash_table_remove (cache->node_hash, node->key); + cache->size--; +} diff --git a/util/cache.h b/util/cache.h new file mode 100644 index 0000000..9180911 --- /dev/null +++ b/util/cache.h @@ -0,0 +1,68 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifndef __CACHE_H__ +#define __CACHE_H__ + +#include <glib.h> + +#include <sys/types.h> + +#include <util/list.h> + +G_BEGIN_DECLS + +typedef struct _Cache Cache; + +typedef struct { + ListNode node; + Cache *cache; + char *key; +} CacheNode; + +typedef gboolean (*CacheNodeExpireFunc) (Cache *cache, CacheNode *node); +typedef void (*CacheNodeFreeFunc) (CacheNode *node); + +struct _Cache { + List list; + size_t size; + size_t max_size; + size_t node_size; + GHashTable *node_hash; + CacheNodeExpireFunc expire; + CacheNodeFreeFunc free_node; +}; + + +G_GNUC_INTERNAL Cache *cache_new (CacheNodeExpireFunc expire, CacheNodeFreeFunc free_node, + size_t bucket_size, size_t max_cache_size); + +G_GNUC_INTERNAL void cache_free (Cache *cache); + +G_GNUC_INTERNAL CacheNode *cache_node_insert (Cache *cache, const char *key); +G_GNUC_INTERNAL CacheNode *cache_node_lookup (Cache *cache, const char *key, gboolean use); + +G_GNUC_INTERNAL void cache_expire_unused (Cache *cache); +G_GNUC_INTERNAL void cache_node_expire (CacheNode *node); + +G_END_DECLS + +#endif /* __CACHE_H__ */ diff --git a/util/gtrie.c b/util/gtrie.c new file mode 100644 index 0000000..eec5721 --- /dev/null +++ b/util/gtrie.c @@ -0,0 +1,511 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include <stdio.h> +#include <string.h> + +#include "gtrie.h" + +#ifdef ENABLE_WARNINGS +#define w(x) x +#else +#define w(x) +#endif /* ENABLE_WARNINGS */ + +#define d(x) + +struct _trie_state { + struct _trie_state *next; + struct _trie_state *fail; + struct _trie_match *match; + unsigned int final; + int id; +}; + +struct _trie_match { + struct _trie_match *next; + struct _trie_state *state; + gunichar c; +}; + +struct _GTrie { + struct _trie_state root; + GPtrArray *fail_states; + gboolean icase; +}; + +static void trie_match_free (struct _trie_match *match); +static void trie_state_free (struct _trie_state *state); + +static struct _trie_match * +trie_match_new (void) +{ + return g_slice_new (struct _trie_match); +} + +static void +trie_match_free (struct _trie_match *match) +{ + struct _trie_match *next; + + while (match) { + next = match->next; + trie_state_free (match->state); + g_slice_free (struct _trie_match, match); + match = next; + } +} + +static struct _trie_state * +trie_state_new (void) +{ + return g_slice_new (struct _trie_state); +} + +static void +trie_state_free (struct _trie_state *state) +{ + trie_match_free (state->match); + g_slice_free (struct _trie_state, state); +} + + +static inline gunichar +trie_utf8_getc (const char **in, size_t inlen) +{ + register const unsigned char *inptr = (const unsigned char *) *in; + const unsigned char *inend = inptr + inlen; + register unsigned char c, r; + register gunichar m, u = 0; + + if (inlen == 0) + return 0; + + r = *inptr++; + if (r < 0x80) { + *in = (const char *) inptr; + u = r; + } else if (r < 0xfe) { /* valid start char? */ + u = r; + m = 0x7f80; /* used to mask out the length bits */ + do { + if (inptr >= inend) + return 0; + + c = *inptr++; + if ((c & 0xc0) != 0x80) + goto error; + + u = (u << 6) | (c & 0x3f); + r <<= 1; + m <<= 5; + } while (r & 0x40); + + *in = (const char *) inptr; + + u &= ~m; + } else { + error: + *in = (*in) + 1; + u = 0xfffe; + } + + return u; +} + + +GTrie * +g_trie_new (gboolean icase) +{ + GTrie *trie; + + trie = g_new (GTrie, 1); + trie->root.next = NULL; + trie->root.fail = NULL; + trie->root.match = NULL; + trie->root.final = 0; + + trie->fail_states = g_ptr_array_new (); + trie->icase = icase; + + return trie; +} + + +void +g_trie_free (GTrie *trie) +{ + g_ptr_array_free (trie->fail_states, TRUE); + trie_match_free (trie->root.match); + g_free (trie); +} + + + +static struct _trie_match * +g (struct _trie_state *s, gunichar c) +{ + struct _trie_match *m = s->match; + + while (m && m->c != c) + m = m->next; + + return m; +} + +static struct _trie_state * +trie_insert (GTrie *trie, guint depth, struct _trie_state *q, gunichar c) +{ + struct _trie_match *m; + + m = trie_match_new (); + m->next = q->match; + m->c = c; + + q->match = m; + q = m->state = trie_state_new (); + q->match = NULL; + q->fail = &trie->root; + q->final = 0; + q->id = 0; + + if (trie->fail_states->len < depth + 1) { + unsigned int size = trie->fail_states->len; + + size = MAX (size + 64, depth + 1); + g_ptr_array_set_size (trie->fail_states, size); + } + + q->next = trie->fail_states->pdata[depth]; + trie->fail_states->pdata[depth] = q; + + return q; +} + + +#if d(!)0 +static void +dump_trie (struct _trie_state *s, int depth) +{ + char *p = g_alloca ((depth * 2) + 1); + struct _trie_match *m; + + memset (p, ' ', depth * 2); + p[depth * 2] = '\0'; + + fprintf (stderr, "%s[state] %p: final=%d; pattern-id=%s; fail=%p\n", + p, s, s->final, s->id, s->fail); + m = s->match; + while (m) { + fprintf (stderr, " %s'%c' -> %p\n", p, m->c, m->state); + if (m->state) + dump_trie (m->state, depth + 1); + + m = m->next; + } +} +#endif + + +/* + * final = empty set + * FOR p = 1 TO #pat + * q = root + * FOR j = 1 TO m[p] + * IF g(q, pat[p][j]) == null + * insert(q, pat[p][j]) + * ENDIF + * q = g(q, pat[p][j]) + * ENDFOR + * final = union(final, q) + * ENDFOR +*/ + +void +g_trie_add (GTrie *trie, const char *pattern, int pattern_id) +{ + const char *inptr = pattern; + struct _trie_state *q, *q1, *r; + struct _trie_match *m, *n; + guint i, depth = 0; + gunichar c; + + /* Step 1: add the pattern to the trie */ + + q = &trie->root; + + while ((c = trie_utf8_getc (&inptr, -1))) { + if (c == 0xfffe) { + w(g_warning ("Invalid UTF-8 sequence in pattern '%s' at %s", + pattern, (inptr - 1))); + continue; + } + + if (trie->icase) + c = g_unichar_tolower (c); + + m = g (q, c); + if (m == NULL) { + q = trie_insert (trie, depth, q, c); + } else { + q = m->state; + } + + depth++; + } + + q->final = depth; + q->id = pattern_id; + + /* Step 2: compute failure graph */ + + for (i = 0; i < trie->fail_states->len; i++) { + q = trie->fail_states->pdata[i]; + while (q) { + m = q->match; + while (m) { + c = m->c; + q1 = m->state; + r = q->fail; + while (r && (n = g (r, c)) == NULL) + r = r->fail; + + if (r != NULL) { + q1->fail = n->state; + if (q1->fail->final > q1->final) + q1->final = q1->fail->final; + } else { + if ((n = g (&trie->root, c))) + q1->fail = n->state; + else + q1->fail = &trie->root; + } + + m = m->next; + } + + q = q->next; + } + } + + d(fprintf (stderr, "\nafter adding pattern '%s' to trie %p:\n", pattern, trie)); + d(dump_trie (&trie->root, 0)); +} + +/* + * Aho-Corasick + * + * q = root + * FOR i = 1 TO n + * WHILE q != fail AND g(q, text[i]) == fail + * q = h(q) + * ENDWHILE + * IF q == fail + * q = root + * ELSE + * q = g(q, text[i]) + * ENDIF + * IF isElement(q, final) + * RETURN TRUE + * ENDIF + * ENDFOR + * RETURN FALSE + */ + +const char * +g_trie_quick_search (GTrie *trie, const char *buffer, size_t buflen, int *matched_id) +{ + const char *inptr, *inend, *prev, *pat; + register size_t inlen = buflen; + struct _trie_match *m = NULL; + struct _trie_state *q; + gunichar c; + + inend = buffer + buflen; + inptr = buffer; + + q = &trie->root; + pat = prev = inptr; + while ((c = trie_utf8_getc (&inptr, inlen))) { + inlen = (inend - inptr); + + if (c == 0xfffe) { +#ifdef ENABLE_WARNINGS + prev = (inptr - 1); + pat = buffer + buflen; + g_warning ("Invalid UTF-8 in buffer '%.*s' at %.*s", + buflen, buffer, pat - prev, prev); +#endif + + pat = prev = inptr; + } + + if (trie->icase) + c = g_unichar_tolower (c); + + while (q != NULL && (m = g (q, c)) == NULL) + q = q->fail; + + if (q == &trie->root) + pat = prev; + + if (q == NULL) { + q = &trie->root; + pat = inptr; + } else if (m != NULL) { + q = m->state; + + if (q->final) { + if (matched_id) + *matched_id = q->id; + + return pat; + } + } + + prev = inptr; + } + + return NULL; +} + +const char * +g_trie_search (GTrie *trie, const char *buffer, size_t buflen, int *matched_id) +{ + const char *inptr, *inend, *prev, *pat; + register size_t inlen = buflen; + struct _trie_match *m = NULL; + struct _trie_state *q; + size_t matched = 0; + gunichar c; + + inend = buffer + buflen; + inptr = buffer; + + q = &trie->root; + pat = prev = inptr; + while ((c = trie_utf8_getc (&inptr, inlen))) { + inlen = (inend - inptr); + + if (c == 0xfffe) { + if (matched) + return pat; + +#ifdef ENABLE_WARNINGS + prev = (inptr - 1); + pat = buffer + buflen; + g_warning ("Invalid UTF-8 in buffer '%.*s' at %.*s", + buflen, buffer, pat - prev, prev); +#endif + + pat = prev = inptr; + } + + if (trie->icase) + c = g_unichar_tolower (c); + + while (q != NULL && (m = g (q, c)) == NULL && matched == 0) + q = q->fail; + + if (q == &trie->root) { + if (matched) + return pat; + + pat = prev; + } + + if (q == NULL) { + if (matched) + return pat; + + q = &trie->root; + pat = inptr; + } else if (m != NULL) { + q = m->state; + + if (q->final > matched) { + if (matched_id) + *matched_id = q->id; + + matched = q->final; + } + } + + prev = inptr; + } + + return matched ? pat : NULL; +} + + +#ifdef TEST + +static char *patterns[] = { + "news://", + "nntp://", + "telnet://", + "file://", + "ftp://", + "http://", + "https://", + "www.", + "ftp.", + "mailto:", + "@" +}; + +static char *haystacks[] = { + "try this url: http://www.ximian.com", + "or, feel free to email me at fejj@ximian.com", + "don't forget to check out www.ximian.com", + "I've attached a file (file:///cvs/gmime/gmime/gtrie.c)", +}; + +int main (int argc, char **argv) +{ + const char *match; + GTrie *trie; + guint i; + int id; + + trie = g_trie_new (TRUE); + for (i = 0; i < G_N_ELEMENTS (patterns); i++) + g_trie_add (trie, patterns[i], i); + + for (i = 0; i < G_N_ELEMENTS (haystacks); i++) { + if ((match = g_trie_search (trie, haystacks[i], -1, &id))) { + fprintf (stderr, "matched @ '%s' with pattern '%s'\n", match, patterns[id]); + } else { + fprintf (stderr, "no match\n"); + } + } + + fflush (stdout); + + g_trie_free (trie); + + return match == NULL ? 0 : 1; +} +#endif /* TEST */ diff --git a/util/gtrie.h b/util/gtrie.h new file mode 100644 index 0000000..4331d5f --- /dev/null +++ b/util/gtrie.h @@ -0,0 +1,42 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifndef __G_TRIE_H__ +#define __G_TRIE_H__ + +#include <glib.h> + +G_BEGIN_DECLS + +typedef struct _GTrie GTrie; + +GTrie *g_trie_new (gboolean icase); +void g_trie_free (GTrie *trie); + +void g_trie_add (GTrie *trie, const char *pattern, int pattern_id); + +const char *g_trie_quick_search (GTrie *trie, const char *buffer, size_t buflen, int *matched_id); + +const char *g_trie_search (GTrie *trie, const char *buffer, size_t buflen, int *matched_id); + +G_END_DECLS + +#endif /* __G_TRIE_H__ */ diff --git a/util/list.c b/util/list.c new file mode 100644 index 0000000..c27f695 --- /dev/null +++ b/util/list.c @@ -0,0 +1,118 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include "list.h" + +void +list_init (List *list) +{ + list->head = (ListNode *) &list->tail; + list->tail = NULL; + list->tailpred = (ListNode *) &list->head; +} + +int +list_is_empty (List *list) +{ + return list->head == (ListNode *) &list->tail; +} + +int +list_length (List *list) +{ + ListNode *node; + int n = 0; + + node = list->head; + while (node->next) { + node = node->next; + n++; + } + + return n; +} + +ListNode * +list_unlink_head (List *list) +{ + ListNode *n, *nn; + + n = list->head; + nn = n->next; + if (nn) { + nn->prev = n->prev; + list->head = nn; + return n; + } + + return NULL; +} + +ListNode * +list_unlink_tail (List *list) +{ + ListNode *n, *np; + + n = list->tailpred; + np = n->prev; + if (np) { + np->next = n->next; + list->tailpred = np; + return n; + } + + return NULL; +} + +ListNode * +list_prepend (List *list, ListNode *node) +{ + node->next = list->head; + node->prev = (ListNode *) &list->head; + list->head->prev = node; + list->head = node; + + return node; +} + +ListNode * +list_append (List *list, ListNode *node) +{ + node->next = (ListNode *) &list->tail; + node->prev = list->tailpred; + list->tailpred->next = node; + list->tailpred = node; + + return node; +} + +ListNode * +list_unlink (ListNode *node) +{ + node->next->prev = node->prev; + node->prev->next = node->next; + + return node; +} diff --git a/util/list.h b/util/list.h new file mode 100644 index 0000000..2659bd8 --- /dev/null +++ b/util/list.h @@ -0,0 +1,59 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifndef __LIST_H__ +#define __LIST_H__ + +#include <glib.h> +#include <string.h> + +G_BEGIN_DECLS + +typedef struct _ListNode { + struct _ListNode *next; + struct _ListNode *prev; +} ListNode; + +typedef struct { + ListNode *head; + ListNode *tail; + ListNode *tailpred; +} List; + +#define LIST_INITIALIZER(l) { (ListNode *) &l.tail, NULL, (ListNode *) &l.head } + +G_GNUC_INTERNAL void list_init (List *list); + +G_GNUC_INTERNAL int list_is_empty (List *list); + +G_GNUC_INTERNAL int list_length (List *list); + +G_GNUC_INTERNAL ListNode *list_unlink_head (List *list); +G_GNUC_INTERNAL ListNode *list_unlink_tail (List *list); + +G_GNUC_INTERNAL ListNode *list_prepend (List *list, ListNode *node); +G_GNUC_INTERNAL ListNode *list_append (List *list, ListNode *node); + +G_GNUC_INTERNAL ListNode *list_unlink (ListNode *node); + +G_END_DECLS + +#endif /* __LIST_H__ */ diff --git a/util/md5-utils.c b/util/md5-utils.c new file mode 100644 index 0000000..2b95af1 --- /dev/null +++ b/util/md5-utils.c @@ -0,0 +1,355 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* + * This code implements the MD5 message-digest algorithm. + * The algorithm is due to Ron Rivest. This code was + * written by Colin Plumb in 1993, no copyright is claimed. + * This code is in the public domain; do with it what you wish. + * + * Equivalent code is available from RSA Data Security, Inc. + * This code has been tested against that, and is equivalent, + * except that you don't need to include two pages of legalese + * with every copy. + * + * To compute the message digest of a chunk of bytes, declare an + * MD5Context structure, pass it to md5_init, call md5_update as + * needed on buffers full of bytes, and then call md5_Final, which + * will fill a supplied 16-byte array with the digest. + */ + +/* parts of this file are: + * Written March 1993 by Branko Lankester + * Modified June 1993 by Colin Plumb for altered md5.c. + * Modified October 1995 by Erik Troan for RPM + */ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include <stdio.h> +#include <string.h> +#include <sys/types.h> +#include "md5-utils.h" + +#define d(x) + +static void md5_transform (guint32 buf[4], const guint32 in[16]); + +static int _ie = 0x44332211; +static union _endian { int i; char b[4]; } *_endian = (union _endian *) &_ie; +#define IS_BIG_ENDIAN() (_endian->b[0] == '\x44') +#define IS_LITTLE_ENDIAN() (_endian->b[0] == '\x11') + + +/* + * Note: this code is harmless on little-endian machines. + */ +static void +_byte_reverse (unsigned char *buf, guint32 longs) +{ + guint32 t; + + do { + t = (guint32) ((guint32) buf[3] << 8 | buf[2]) << 16 | + ((guint32) buf[1] << 8 | buf[0]); + *(guint32 *) buf = t; + buf += 4; + } while (--longs); +} + + +/** + * md5_init: Initialise an md5 context object + * @ctx: md5 context + * + * Initialise an md5 buffer. + * + **/ +void +md5_init (MD5Context *ctx) +{ + ctx->buf[0] = 0x67452301; + ctx->buf[1] = 0xefcdab89; + ctx->buf[2] = 0x98badcfe; + ctx->buf[3] = 0x10325476; + + ctx->bits[0] = 0; + ctx->bits[1] = 0; + + if (IS_BIG_ENDIAN ()) + ctx->doByteReverse = 1; + else + ctx->doByteReverse = 0; +} + + +/** + * md5_update: add a buffer to md5 hash computation + * @ctx: conetxt object used for md5 computaion + * @buf: buffer to add + * @len: buffer length + * + * Update context to reflect the concatenation of another buffer full + * of bytes. Use this to progressively construct an md5 hash. + **/ +void +md5_update (MD5Context *ctx, const unsigned char *buf, guint32 len) +{ + guint32 t; + + /* Update bitcount */ + t = ctx->bits[0]; + if ((ctx->bits[0] = t + ((guint32) len << 3)) < t) + ctx->bits[1]++; /* Carry from low to high */ + ctx->bits[1] += len >> 29; + + t = (t >> 3) & 0x3f; /* Bytes already in shsInfo->data */ + + /* Handle any leading odd-sized chunks */ + if (t) { + unsigned char *p = (unsigned char *) ctx->in + t; + + t = 64 - t; + if (len < t) { + memcpy (p, buf, len); + return; + } + memcpy (p, buf, t); + if (ctx->doByteReverse) + _byte_reverse (ctx->in, 16); + md5_transform (ctx->buf, (guint32 *) ctx->in); + buf += t; + len -= t; + } + + /* Process data in 64-byte chunks */ + while (len >= 64) { + memcpy (ctx->in, buf, 64); + if (ctx->doByteReverse) + _byte_reverse (ctx->in, 16); + md5_transform (ctx->buf, (guint32 *) ctx->in); + buf += 64; + len -= 64; + } + + /* Handle any remaining bytes of data. */ + memcpy (ctx->in, buf, len); +} + + +/* + * Final wrapup - pad to 64-byte boundary with the bit pattern + * 1 0* (64-bit count of bits processed, MSB-first) + */ +/** + * md5_final: copy the final md5 hash to a bufer + * @digest: 16 bytes buffer + * @ctx: context containing the calculated md5 + * + * copy the final md5 hash to a bufer + **/ +void +md5_final (MD5Context *ctx, unsigned char digest[16]) +{ + guint32 count; + unsigned char *p; + + /* Compute number of bytes mod 64 */ + count = (ctx->bits[0] >> 3) & 0x3F; + + /* Set the first char of padding to 0x80. This is safe since there is + always at least one byte free */ + p = ctx->in + count; + *p++ = 0x80; + + /* Bytes of padding needed to make 64 bytes */ + count = 64 - 1 - count; + + /* Pad out to 56 mod 64 */ + if (count < 8) { + /* Two lots of padding: Pad the first block to 64 bytes */ + memset (p, 0, count); + if (ctx->doByteReverse) + _byte_reverse (ctx->in, 16); + md5_transform (ctx->buf, (guint32 *) ctx->in); + + /* Now fill the next block with 56 bytes */ + memset (ctx->in, 0, 56); + } else { + /* Pad block to 56 bytes */ + memset (p, 0, count - 8); + } + + if (ctx->doByteReverse) + _byte_reverse (ctx->in, 14); + + /* Append length in bits and transform */ + ((guint32 *) ctx->in)[14] = ctx->bits[0]; + ((guint32 *) ctx->in)[15] = ctx->bits[1]; + + md5_transform (ctx->buf, (guint32 *) ctx->in); + if (ctx->doByteReverse) + _byte_reverse ((unsigned char *) ctx->buf, 4); + memcpy (digest, ctx->buf, 16); +} + + +/* The four core functions - F1 is optimized somewhat */ + +/* #define F1(x, y, z) (x & y | ~x & z) */ +#define F1(x, y, z) (z ^ (x & (y ^ z))) +#define F2(x, y, z) F1(z, x, y) +#define F3(x, y, z) (x ^ y ^ z) +#define F4(x, y, z) (y ^ (x | ~z)) + +/* This is the central step in the MD5 algorithm. */ +#define MD5STEP(f, w, x, y, z, data, s) \ + ( w += f(x, y, z) + data, w = w<<s | w>>(32-s), w += x ) + +/* + * The core of the MD5 algorithm, this alters an existing MD5 hash to + * reflect the addition of 16 longwords of new data. md5_Update blocks + * the data and converts bytes into longwords for this routine. + */ +static void +md5_transform (guint32 buf[4], const guint32 in[16]) +{ + register guint32 a, b, c, d; + + a = buf[0]; + b = buf[1]; + c = buf[2]; + d = buf[3]; + + MD5STEP (F1, a, b, c, d, in[0] + 0xd76aa478, 7); + MD5STEP (F1, d, a, b, c, in[1] + 0xe8c7b756, 12); + MD5STEP (F1, c, d, a, b, in[2] + 0x242070db, 17); + MD5STEP (F1, b, c, d, a, in[3] + 0xc1bdceee, 22); + MD5STEP (F1, a, b, c, d, in[4] + 0xf57c0faf, 7); + MD5STEP (F1, d, a, b, c, in[5] + 0x4787c62a, 12); + MD5STEP (F1, c, d, a, b, in[6] + 0xa8304613, 17); + MD5STEP (F1, b, c, d, a, in[7] + 0xfd469501, 22); + MD5STEP (F1, a, b, c, d, in[8] + 0x698098d8, 7); + MD5STEP (F1, d, a, b, c, in[9] + 0x8b44f7af, 12); + MD5STEP (F1, c, d, a, b, in[10] + 0xffff5bb1, 17); + MD5STEP (F1, b, c, d, a, in[11] + 0x895cd7be, 22); + MD5STEP (F1, a, b, c, d, in[12] + 0x6b901122, 7); + MD5STEP (F1, d, a, b, c, in[13] + 0xfd987193, 12); + MD5STEP (F1, c, d, a, b, in[14] + 0xa679438e, 17); + MD5STEP (F1, b, c, d, a, in[15] + 0x49b40821, 22); + + MD5STEP (F2, a, b, c, d, in[1] + 0xf61e2562, 5); + MD5STEP (F2, d, a, b, c, in[6] + 0xc040b340, 9); + MD5STEP (F2, c, d, a, b, in[11] + 0x265e5a51, 14); + MD5STEP (F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20); + MD5STEP (F2, a, b, c, d, in[5] + 0xd62f105d, 5); + MD5STEP (F2, d, a, b, c, in[10] + 0x02441453, 9); + MD5STEP (F2, c, d, a, b, in[15] + 0xd8a1e681, 14); + MD5STEP (F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20); + MD5STEP (F2, a, b, c, d, in[9] + 0x21e1cde6, 5); + MD5STEP (F2, d, a, b, c, in[14] + 0xc33707d6, 9); + MD5STEP (F2, c, d, a, b, in[3] + 0xf4d50d87, 14); + MD5STEP (F2, b, c, d, a, in[8] + 0x455a14ed, 20); + MD5STEP (F2, a, b, c, d, in[13] + 0xa9e3e905, 5); + MD5STEP (F2, d, a, b, c, in[2] + 0xfcefa3f8, 9); + MD5STEP (F2, c, d, a, b, in[7] + 0x676f02d9, 14); + MD5STEP (F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20); + + MD5STEP (F3, a, b, c, d, in[5] + 0xfffa3942, 4); + MD5STEP (F3, d, a, b, c, in[8] + 0x8771f681, 11); + MD5STEP (F3, c, d, a, b, in[11] + 0x6d9d6122, 16); + MD5STEP (F3, b, c, d, a, in[14] + 0xfde5380c, 23); + MD5STEP (F3, a, b, c, d, in[1] + 0xa4beea44, 4); + MD5STEP (F3, d, a, b, c, in[4] + 0x4bdecfa9, 11); + MD5STEP (F3, c, d, a, b, in[7] + 0xf6bb4b60, 16); + MD5STEP (F3, b, c, d, a, in[10] + 0xbebfbc70, 23); + MD5STEP (F3, a, b, c, d, in[13] + 0x289b7ec6, 4); + MD5STEP (F3, d, a, b, c, in[0] + 0xeaa127fa, 11); + MD5STEP (F3, c, d, a, b, in[3] + 0xd4ef3085, 16); + MD5STEP (F3, b, c, d, a, in[6] + 0x04881d05, 23); + MD5STEP (F3, a, b, c, d, in[9] + 0xd9d4d039, 4); + MD5STEP (F3, d, a, b, c, in[12] + 0xe6db99e5, 11); + MD5STEP (F3, c, d, a, b, in[15] + 0x1fa27cf8, 16); + MD5STEP (F3, b, c, d, a, in[2] + 0xc4ac5665, 23); + + MD5STEP (F4, a, b, c, d, in[0] + 0xf4292244, 6); + MD5STEP (F4, d, a, b, c, in[7] + 0x432aff97, 10); + MD5STEP (F4, c, d, a, b, in[14] + 0xab9423a7, 15); + MD5STEP (F4, b, c, d, a, in[5] + 0xfc93a039, 21); + MD5STEP (F4, a, b, c, d, in[12] + 0x655b59c3, 6); + MD5STEP (F4, d, a, b, c, in[3] + 0x8f0ccc92, 10); + MD5STEP (F4, c, d, a, b, in[10] + 0xffeff47d, 15); + MD5STEP (F4, b, c, d, a, in[1] + 0x85845dd1, 21); + MD5STEP (F4, a, b, c, d, in[8] + 0x6fa87e4f, 6); + MD5STEP (F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10); + MD5STEP (F4, c, d, a, b, in[6] + 0xa3014314, 15); + MD5STEP (F4, b, c, d, a, in[13] + 0x4e0811a1, 21); + MD5STEP (F4, a, b, c, d, in[4] + 0xf7537e82, 6); + MD5STEP (F4, d, a, b, c, in[11] + 0xbd3af235, 10); + MD5STEP (F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15); + MD5STEP (F4, b, c, d, a, in[9] + 0xeb86d391, 21); + + buf[0] += a; + buf[1] += b; + buf[2] += c; + buf[3] += d; +} + + +/** + * md5_get_digest: get the md5 hash of a buffer + * @buffer: byte buffer + * @buffer_size: buffer size (in bytes) + * @digest: 16 bytes buffer receiving the hash code. + * + * Get the md5 hash of a buffer. The result is put in + * the 16 bytes buffer @digest . + **/ +void +md5_get_digest (const char *buffer, unsigned int buffer_size, unsigned char digest[16]) +{ + MD5Context ctx; + + md5_init (&ctx); + md5_update (&ctx, (unsigned char *) buffer, buffer_size); + md5_final (&ctx, digest); +} + + +/** + * md5_get_digest_from_file: get the md5 hash of a file + * @filename: file name + * @digest: 16 bytes buffer receiving the hash code. + * + * Get the md5 hash of a file. The result is put in + * the 16 bytes buffer @digest . + **/ +void +md5_get_digest_from_file (const char *filename, unsigned char digest[16]) +{ + MD5Context ctx; + unsigned char buf[1024]; + size_t nread; + FILE *fp; + + d(fprintf (stderr, "generating checksum\n")); + + if (!(fp = fopen (filename, "rb"))) + return; + + md5_init (&ctx); + + while ((nread = fread (buf, 1, 1024, fp)) > 0) + md5_update (&ctx, buf, nread); + + if (ferror (fp)) { + fclose (fp); + return; + } + + md5_final (&ctx, digest); + + fclose (fp); + d(fprintf (stderr, "checksum done\n")); +} diff --git a/util/md5-utils.h b/util/md5-utils.h new file mode 100644 index 0000000..aec2383 --- /dev/null +++ b/util/md5-utils.h @@ -0,0 +1,54 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* + * This code implements the MD5 message-digest algorithm. + * The algorithm is due to Ron Rivest. This code was + * written by Colin Plumb in 1993, no copyright is claimed. + * This code is in the public domain; do with it what you wish. + * + * Equivalent code is available from RSA Data Security, Inc. + * This code has been tested against that, and is equivalent, + * except that you don't need to include two pages of legalese + * with every copy. + * + * To compute the message digest of a chunk of bytes, declare an + * MD5Context structure, pass it to rpmMD5Init, call rpmMD5Update as + * needed on buffers full of bytes, and then call rpmMD5Final, which + * will fill a supplied 16-byte array with the digest. + */ + +/* parts of this file are : + * Written March 1993 by Branko Lankester + * Modified June 1993 by Colin Plumb for altered md5.c. + * Modified October 1995 by Erik Troan for RPM + */ + + +#ifndef MD5_UTILS_H +#define MD5_UTILS_H + +#include <glib.h> + +G_BEGIN_DECLS + +typedef struct { + guint32 buf[4]; + guint32 bits[2]; + unsigned char in[64]; + int doByteReverse; +} MD5Context; + + +G_GNUC_INTERNAL void md5_get_digest (const char *buffer, unsigned int buffer_size, unsigned char digest[16]); + +/* use this one when speed is needed */ +/* for use in provider code only */ +G_GNUC_INTERNAL void md5_get_digest_from_file (const char *filename, unsigned char digest[16]); + +/* raw routines */ +G_GNUC_INTERNAL void md5_init (MD5Context *ctx); +G_GNUC_INTERNAL void md5_update (MD5Context *ctx, const unsigned char *buf, guint32 len); +G_GNUC_INTERNAL void md5_final (MD5Context *ctx, unsigned char digest[16]); + +G_END_DECLS + +#endif /* MD5_UTILS_H */ diff --git a/util/url-scanner.c b/util/url-scanner.c new file mode 100644 index 0000000..aeb7787 --- /dev/null +++ b/util/url-scanner.c @@ -0,0 +1,583 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "gtrie.h" +#include "url-scanner.h" + + +struct _UrlScanner { + GPtrArray *patterns; + GTrie *trie; +}; + + +UrlScanner * +url_scanner_new (void) +{ + UrlScanner *scanner; + + scanner = g_new (UrlScanner, 1); + scanner->patterns = g_ptr_array_new (); + scanner->trie = g_trie_new (TRUE); + + return scanner; +} + + +void +url_scanner_free (UrlScanner *scanner) +{ + g_return_if_fail (scanner != NULL); + + g_ptr_array_free (scanner->patterns, TRUE); + g_trie_free (scanner->trie); + g_free (scanner); +} + + +void +url_scanner_add (UrlScanner *scanner, urlpattern_t *pattern) +{ + g_return_if_fail (scanner != NULL); + + g_trie_add (scanner->trie, pattern->pattern, scanner->patterns->len); + g_ptr_array_add (scanner->patterns, pattern); +} + + +gboolean +url_scanner_scan (UrlScanner *scanner, const char *in, size_t inlen, urlmatch_t *match) +{ + const char *pos, *inend; + urlpattern_t *pat; + int pattern_id; + + g_return_val_if_fail (scanner != NULL, FALSE); + g_return_val_if_fail (in != NULL, FALSE); + + if (!(pos = g_trie_search (scanner->trie, in, inlen, &pattern_id))) + return FALSE; + + pat = g_ptr_array_index (scanner->patterns, pattern_id); + + match->pattern = pat->pattern; + match->prefix = pat->prefix; + + inend = in + inlen; + if (!pat->start (in, pos, inend, match)) + return FALSE; + + if (!pat->end (in, pos, inend, match)) + return FALSE; + + return TRUE; +} + + +static unsigned char url_scanner_table[256] = { + 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 9, 1, 1, 9, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 24,128,160,128,128,128,128,128,160,160,128,128,160,192,160,160, + 68, 68, 68, 68, 68, 68, 68, 68, 68, 68,160,160, 32,128, 32,128, + 160, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, + 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,160,160,160,128,128, + 128, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, + 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,128,128,128,128, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 +}; + +enum { + IS_CTRL = (1 << 0), + IS_ALPHA = (1 << 1), + IS_DIGIT = (1 << 2), + IS_LWSP = (1 << 3), + IS_SPACE = (1 << 4), + IS_SPECIAL = (1 << 5), + IS_DOMAIN = (1 << 6), + IS_URLSAFE = (1 << 7), +}; + +#define is_ctrl(x) ((url_scanner_table[(unsigned char)(x)] & IS_CTRL) != 0) +#define is_lwsp(x) ((url_scanner_table[(unsigned char)(x)] & IS_LWSP) != 0) +#define is_atom(x) ((url_scanner_table[(unsigned char)(x)] & (IS_SPECIAL|IS_SPACE|IS_CTRL)) == 0) +#define is_alpha(x) ((url_scanner_table[(unsigned char)(x)] & IS_ALPHA) != 0) +#define is_digit(x) ((url_scanner_table[(unsigned char)(x)] & IS_DIGIT) != 0) +#define is_domain(x) ((url_scanner_table[(unsigned char)(x)] & IS_DOMAIN) != 0) +#define is_urlsafe(x) ((url_scanner_table[(unsigned char)(x)] & (IS_ALPHA|IS_DIGIT|IS_URLSAFE)) != 0) + +static struct { + char open; + char close; +} url_braces[] = { + { '(', ')' }, + { '{', '}' }, + { '[', ']' }, + { '<', '>' }, + { '|', '|' }, +}; + +static gboolean +is_open_brace (char c) +{ + int i; + + for (i = 0; i < G_N_ELEMENTS (url_braces); i++) { + if (c == url_braces[i].open) + return TRUE; + } + + return FALSE; +} + +static char +url_stop_at_brace (const char *in, size_t so) +{ + int i; + + if (so > 0) { + for (i = 0; i < 4; i++) { + if (in[so - 1] == url_braces[i].open) + return url_braces[i].close; + } + } + + return '\0'; +} + + +gboolean +url_addrspec_start (const char *in, const char *pos, const char *inend, urlmatch_t *match) +{ + register const char *inptr = pos; + + g_assert (*inptr == '@'); + + if (inptr == in) + return FALSE; + + inptr--; + + while (inptr > in) { + if (is_atom (*inptr)) + inptr--; + else + break; + + while (inptr > in && is_atom (*inptr)) + inptr--; + + if (inptr > in && *inptr == '.') + inptr--; + } + + if (!is_atom (*inptr) || is_open_brace (*inptr)) + inptr++; + + if (inptr == pos) + return FALSE; + + match->um_so = (inptr - in); + + return TRUE; +} + +gboolean +url_addrspec_end (const char *in, const char *pos, const char *inend, urlmatch_t *match) +{ + const char *inptr = pos; + int parts = 0, digits; + gboolean got_dot = FALSE; + + g_assert (*inptr == '@'); + + inptr++; + + if (*inptr == '[') { + /* domain literal */ + do { + inptr++; + + digits = 0; + while (inptr < inend && is_digit (*inptr) && digits < 3) { + inptr++; + digits++; + } + + parts++; + + if (*inptr != '.' && parts != 4) + return FALSE; + } while (parts < 4); + + if (inptr < inend && *inptr == ']') + inptr++; + else + return FALSE; + + got_dot = TRUE; + } else { + while (inptr < inend) { + if (is_domain (*inptr)) + inptr++; + else + break; + + while (inptr < inend && is_domain (*inptr)) + inptr++; + + if (inptr < inend && *inptr == '.' && is_domain (inptr[1])) { + if (*inptr == '.') + got_dot = TRUE; + inptr++; + } + } + } + + if (inptr == pos + 1 || !got_dot) + return FALSE; + + match->um_eo = (inptr - in); + + return TRUE; +} + + +gboolean +url_file_start (const char *in, const char *pos, const char *inend, urlmatch_t *match) +{ + match->um_so = (pos - in); + + return TRUE; +} + +gboolean +url_file_end (const char *in, const char *pos, const char *inend, urlmatch_t *match) +{ + register const char *inptr = pos; + char close_brace; + + inptr += strlen (match->pattern); + + if (*inptr == '/') + inptr++; + + close_brace = url_stop_at_brace (in, match->um_so); + + while (inptr < inend && is_urlsafe (*inptr) && *inptr != close_brace) + inptr++; + + if (inptr == pos) + return FALSE; + + match->um_eo = (inptr - in); + + return TRUE; +} + +gboolean +url_web_start (const char *in, const char *pos, const char *inend, urlmatch_t *match) +{ + match->um_so = (pos - in); + + return TRUE; +} + +gboolean +url_web_end (const char *in, const char *pos, const char *inend, urlmatch_t *match) +{ + register const char *inptr = pos; + gboolean openbracket = FALSE; + gboolean passwd = FALSE; + const char *save; + char close_brace; + int port, val, n; + char *end; + + inptr += strlen (match->pattern); + + close_brace = url_stop_at_brace (in, match->um_so); + + /* find the end of the domain */ + if (is_digit (*inptr)) { + goto ip_literal2; + } else if (is_atom (*inptr)) { + /* might be a domain or user@domain */ + save = inptr; + while (inptr < inend) { + if (!is_atom (*inptr)) + break; + + inptr++; + + while (inptr < inend && is_atom (*inptr)) + inptr++; + + if ((inptr + 1) < inend && *inptr == '.' && is_atom (inptr[1])) + inptr++; + } + + if (*inptr != '@') + inptr = save; + else + inptr++; + + if (*inptr == '[') { + /* IPv6 (or possibly IPv4) address literal */ + goto ip_literal; + } + + if (is_domain (*inptr)) { + /* domain name or IPv4 address */ + goto domain; + } + } else if (*inptr == '[') { + ip_literal: + openbracket = TRUE; + inptr++; + + if (is_digit (*inptr)) { + ip_literal2: + /* could be IPv4 or IPv6 */ + if ((val = strtol (inptr, &end, 10)) < 0) + return FALSE; + } else if ((*inptr >= 'A' && *inptr <= 'F') || (*inptr >= 'a' && *inptr <= 'f')) { + /* IPv6 address literals are in hex */ + if ((val = strtol (inptr, &end, 16)) < 0 || *end != ':') + return FALSE; + } else if (*inptr == ':') { + /* IPv6 can start with a ':' */ + end = (char *) inptr; + val = 256; /* invalid value */ + } else { + return FALSE; + } + + switch (*end) { + case '.': /* IPv4 address literal */ + n = 1; + do { + if (val > 255 || *end != '.') + return FALSE; + + inptr = end + 1; + if ((val = strtol (inptr, &end, 10)) < 0) + return FALSE; + + n++; + } while (n < 4); + + if (val > 255 || n < 4 || (openbracket && *end != ']')) + return FALSE; + + inptr = end + 1; + break; + case ':': /* IPv6 address literal */ + if (!openbracket) + return FALSE; + + do { + if (end[1] != ':') { + inptr = end + 1; + if ((val = strtol (inptr, &end, 16)) < 0) + return FALSE; + } else { + inptr = end; + end++; + } + } while (end > inptr && *end == ':'); + + if (*end != ']') + return FALSE; + + inptr = end + 1; + break; + default: + return FALSE; + } + } else if (is_domain (*inptr)) { + domain: + while (inptr < inend) { + if (!is_domain (*inptr)) + break; + + inptr++; + + while (inptr < inend && is_domain (*inptr)) + inptr++; + + if ((inptr + 1) < inend && *inptr == '.' && (is_domain (inptr[1]) || inptr[1] == '/')) + inptr++; + } + } else { + return FALSE; + } + + if (inptr < inend) { + switch (*inptr) { + case ':': /* we either have a port or a password */ + inptr++; + + if (is_digit (*inptr) || passwd) { + port = (*inptr++ - '0'); + + while (inptr < inend && is_digit (*inptr) && port < 65536) + port = (port * 10) + (*inptr++ - '0'); + + if (!passwd && (port >= 65536 || *inptr == '@')) { + if (inptr < inend) { + /* this must be a password? */ + goto passwd; + } + + inptr--; + } + } else { + passwd: + passwd = TRUE; + save = inptr; + + while (inptr < inend && is_atom (*inptr)) + inptr++; + + if ((inptr + 2) < inend) { + if (*inptr == '@') { + inptr++; + if (is_domain (*inptr)) + goto domain; + } + + return FALSE; + } + } + + if (inptr >= inend || *inptr != '/') + break; + + /* we have a '/' so there could be a path - fall through */ + case '/': /* we've detected a path component to our url */ + inptr++; + + while (inptr < inend && is_urlsafe (*inptr) && *inptr != close_brace) + inptr++; + + break; + default: + break; + } + } + + /* urls are extremely unlikely to end with any + * punctuation, so strip any trailing + * punctuation off. Also strip off any closing + * braces or quotes. */ + while (inptr > pos && strchr (",.:;?!-|)}]'\"", inptr[-1])) + inptr--; + + match->um_eo = (inptr - in); + + return TRUE; +} + + +#ifdef BUILD_TABLE + +#include <stdio.h> + +/* got these from rfc1738 */ +#define CHARS_LWSP " \t\n\r" /* linear whitespace chars */ +#define CHARS_SPECIAL "()<>@,;:\\\".[]" + +/* got these from rfc1738 */ +#define CHARS_URLSAFE "$-_.+!*'(),{}|\\^~[]`#%\";/?:@&=" + + +static void +table_init_bits (unsigned int mask, const unsigned char *vals) +{ + int i; + + for (i = 0; vals[i] != '\0'; i++) + url_scanner_table[vals[i]] |= mask; +} + +static void +url_scanner_table_init (void) +{ + int i; + + for (i = 0; i < 256; i++) { + url_scanner_table[i] = 0; + if (i < 32) + url_scanner_table[i] |= IS_CTRL; + if ((i >= '0' && i <= '9')) + url_scanner_table[i] |= IS_DIGIT | IS_DOMAIN; + if ((i >= 'a' && i <= 'z') || (i >= 'A' && i <= 'Z')) + url_scanner_table[i] |= IS_ALPHA | IS_DOMAIN; + if (i >= 127) + url_scanner_table[i] |= IS_CTRL; + } + + url_scanner_table[' '] |= IS_SPACE; + url_scanner_table['-'] |= IS_DOMAIN; + + /* not defined to be special in rfc0822, but when scanning + backwards to find the beginning of the email address we do + not want to include this char if we come accross it - so + this is kind of a hack, but it's ok */ + url_scanner_table['/'] |= IS_SPECIAL; + + table_init_bits (IS_LWSP, CHARS_LWSP); + table_init_bits (IS_SPECIAL, CHARS_SPECIAL); + table_init_bits (IS_URLSAFE, CHARS_URLSAFE); +} + +int main (int argc, char **argv) +{ + int i; + + url_scanner_table_init (); + + printf ("static unsigned char url_scanner_table[256] = {"); + for (i = 0; i < 256; i++) { + printf ("%s%3d%s", (i % 16) ? "" : "\n\t", + url_scanner_table[i], i != 255 ? "," : "\n"); + } + printf ("};\n\n"); + + return 0; +} + +#endif /* BUILD_TABLE */ diff --git a/util/url-scanner.h b/util/url-scanner.h new file mode 100644 index 0000000..3d35728 --- /dev/null +++ b/util/url-scanner.h @@ -0,0 +1,65 @@ +/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */ +/* GMime + * Copyright (C) 2000-2012 Jeffrey Stedfast + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 + * of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free + * Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA + * 02110-1301, USA. + */ + + +#ifndef __URL_SCANNER_H__ +#define __URL_SCANNER_H__ + +#include <glib.h> +#include <sys/types.h> + +G_BEGIN_DECLS + +typedef struct { + const char *pattern; + const char *prefix; + size_t um_so; + size_t um_eo; +} urlmatch_t; + +typedef gboolean (*UrlScanFunc) (const char *in, const char *pos, const char *inend, urlmatch_t *match); + +/* some default GUrlScanFunc's */ +G_GNUC_INTERNAL gboolean url_file_start (const char *in, const char *pos, const char *inend, urlmatch_t *match); +G_GNUC_INTERNAL gboolean url_file_end (const char *in, const char *pos, const char *inend, urlmatch_t *match); +G_GNUC_INTERNAL gboolean url_web_start (const char *in, const char *pos, const char *inend, urlmatch_t *match); +G_GNUC_INTERNAL gboolean url_web_end (const char *in, const char *pos, const char *inend, urlmatch_t *match); +G_GNUC_INTERNAL gboolean url_addrspec_start (const char *in, const char *pos, const char *inend, urlmatch_t *match); +G_GNUC_INTERNAL gboolean url_addrspec_end (const char *in, const char *pos, const char *inend, urlmatch_t *match); + +typedef struct { + char *pattern; + char *prefix; + UrlScanFunc start; + UrlScanFunc end; +} urlpattern_t; + +typedef struct _UrlScanner UrlScanner; + +G_GNUC_INTERNAL UrlScanner *url_scanner_new (void); +G_GNUC_INTERNAL void url_scanner_free (UrlScanner *scanner); + +G_GNUC_INTERNAL void url_scanner_add (UrlScanner *scanner, urlpattern_t *pattern); + +G_GNUC_INTERNAL gboolean url_scanner_scan (UrlScanner *scanner, const char *in, size_t inlen, urlmatch_t *match); + +G_END_DECLS + +#endif /* __URL_SCANNER_H__ */ |