- speedup large queries by ~50%.

- revert to presentation ordering Yet Again (#62158).
- non-glibc: on upgrade, mergesort is much faster than quicksort.

CVS patchset: 5377
CVS date: 2002/04/07 19:52:42

19 files changed, 572 insertions, 142 deletions

diff --git a/CHANGES b/CHANGES
index 2f2ba0639..6acac8be7 100644
--- a/CHANGES
+++ b/CHANGES
@@ -93,12 +93,10 @@
 `	- don't bother with signing check if 16 bits of hash don't match.
 	- only V3 signatures for now.
 	- wire --nodigest/--nosignature options to checksig/query/verify modes.
-	- make --addsign and --resign behave exactly the same.
 	- splint annotationsm, signature cleanup.
 	- drill ts/fi through verify mode, add methods to keep fi abstract.
 	- use mmap when calculating file digests on verify, ~20% faster.
 	- permit --dbpath and --root with signature (i.e. --import) modes.
-	- *really* dump signature header immutable region.
 
 4.0.3 -> 4.0.4:
 	- solaris: translate i86pc to i386 (#57182).
@@ -146,6 +144,11 @@
 	- rpm-4.0.4 release candidate.
 	- add cpanflute2, another perl.req fiddle.
 	- reapply Berkeley DB patch #4491.
+	- make --addsign and --resign behave exactly the same.
+	- *really* dump signature header immutable region.
+	- speedup large queries by ~50%.
+	- revert to presentation ordering Yet Again (#62158).
+	- non-glibc: on upgrade, mergesort is much faster than quicksort.
 
 4.0.2 -> 4.0.3:
 	- update per-interpreter dependency scripts, add sql/tcl (#20295).
diff --git a/Doxyfile.in b/Doxyfile.in
index 07df067e6..72bacf7e6 100644
--- a/Doxyfile.in
+++ b/Doxyfile.in
@@ -409,6 +409,7 @@ INPUT                  = \
 	@top_srcdir@/rpmdb/header_internal.h \
 	@top_srcdir@/rpmdb/legacy.c \
 	@top_srcdir@/rpmdb/legacy.h \
+	@top_srcdir@/rpmdb/merge.c \
 	@top_srcdir@/rpmdb/poptDB.c \
 	@top_srcdir@/rpmdb/rpmhash.c \
 	@top_srcdir@/rpmdb/rpmhash.h \
diff --git a/beecrypt/config.gnu.h.in b/beecrypt/config.gnu.h.in
index f93c9e1d6..b3590a496 100644
--- a/beecrypt/config.gnu.h.in
+++ b/beecrypt/config.gnu.h.in
@@ -202,9 +202,6 @@
 /* Define if you have the <unistd.h> header file. */
 #undef HAVE_UNISTD_H
 
-/* Name of package */
-#undef PACKAGE
-
 /* The size of a `char', as computed by sizeof. */
 #undef SIZEOF_CHAR
 
@@ -244,9 +241,6 @@
 /* Define if you have the ANSI C header files. */
 #undef STDC_HEADERS
 
-/* Version number of package */
-#undef VERSION
-
 /* Define if your processor stores words with the most significant byte first
    (like Motorola and SPARC, unlike Intel and VAX). */
 #undef WORDS_BIGENDIAN
diff --git a/build/pack.c b/build/pack.c
index 8fb2f1007..c130e0a19 100644
--- a/build/pack.c
+++ b/build/pack.c
@@ -398,7 +398,7 @@ int writeRPM(Header *hdrp, const char *fileName, int type,
 {
     FD_t fd = NULL;
     FD_t ifd = NULL;
-    int count, sigtype;
+    int_32 count, sigtag;
     const char * sigtarget;
     const char * rpmio_flags = NULL;
     const char * sha1 = NULL;
@@ -524,14 +524,14 @@ int writeRPM(Header *hdrp, const char *fileName, int type,
     }
 
     (void) Fflush(fd);
-    if (Fseek(fd, sizeof(header_magic), SEEK_SET) == -1) {
+    if (Fseek(fd, 0, SEEK_SET) == -1) {
 	rc = RPMERR_FSEEK;
 	rpmError(RPMERR_FSEEK, _("%s: Fseek failed: %s\n"),
 			sigtarget, Fstrerror(fd));
     }
 
     fdInitDigest(fd, PGPHASHALGO_SHA1, 0);
-    if (headerWrite(fd, h, HEADER_MAGIC_NO)) {
+    if (headerWrite(fd, h, HEADER_MAGIC_YES)) {
 	rc = RPMERR_NOSPACE;
 	rpmError(RPMERR_NOSPACE, _("Unable to write final header\n"));
     }
@@ -552,9 +552,9 @@ int writeRPM(Header *hdrp, const char *fileName, int type,
     (void) rpmAddSignature(sig, sigtarget, RPMSIGTAG_SIZE, passPhrase);
     (void) rpmAddSignature(sig, sigtarget, RPMSIGTAG_MD5, passPhrase);
 
-    if ((sigtype = rpmLookupSignatureType(RPMLOOKUPSIG_QUERY)) > 0) {
-	rpmMessage(RPMMESS_NORMAL, _("Generating signature: %d\n"), sigtype);
-	(void) rpmAddSignature(sig, sigtarget, sigtype, passPhrase);
+    if ((sigtag = rpmLookupSignatureType(RPMLOOKUPSIG_QUERY)) > 0) {
+	rpmMessage(RPMMESS_NORMAL, _("Generating signature: %d\n"), sigtag);
+	(void) rpmAddSignature(sig, sigtarget, sigtag, passPhrase);
     }
     
     if (sha1) {
diff --git a/db3/configure b/db3/configure
index b6724ac28..a96fb90d3 100755
--- a/db3/configure
+++ b/db3/configure
@@ -9,7 +9,7 @@ rm -f config.cache
 #ln -sf ../dist $db_dist
 
 # XXX edit CFLAGS= ... out of invocation args ???
-ARGS="`echo $* | sed -e 's% [^ ]*CFLAGS=[^ ]*%%' -e 's% -march=[^ ]*%%' -e 's% -mcpu=[^ ]*%%' -e 's%--cache-file=.*$%%'`"
+ARGS="`echo $* | sed -e 's% [^ ]*CFLAGS=[^ ]*%%' -e 's% -[^-][^ ]*%%g' -e 's%--cache-file=.*$%%'`"
 
 CC="$CC" CFLAGS="$CFLAGS" $db_dist/configure $ARGS \
 	--enable-shared --enable-static --enable-debug --enable-rpc \
diff --git a/doc/manual/conditionalbuilds b/doc/manual/conditionalbuilds
index 95039db17..35ab07921 100644
--- a/doc/manual/conditionalbuilds
+++ b/doc/manual/conditionalbuilds
@@ -45,7 +45,7 @@ So the spec file should be written
 \verbatim
     ...
     ./configure \
-	%{?_with_ldap:      %{_with_ldap}}   \
+	%{?_with_ldap}   \
     ...
 \endverbatim
 so that, if "--with ldap" was used as a build option, then confgure
@@ -67,22 +67,38 @@ for pine:
     %{!?_with_ssl: %{!?_without_ssl: %define _with_ssl --with-ssl}}
     ...
 
+    # You might want to make sure that one and only one of required and
+    # mutually exclusive options exists.
+    #
+    # Read: It's an error if both or neither required options exist.
+    %{?_with_ssl: %{?_without_ssl: %{error: both _with_ssl and _without_ssl}}}
+    %{!?_with_ssl: %{!?_without_ssl: %{error: neither _with_ssl nor _without_ssl}}}
+
     # Add build dependencies for ssl and ldap features if enabled.
+    # Note: Tag tokens must start at beginning-of-line.
     #
     # Read: If feature is enabled, then add the build dependency.
-    %{?_with_ssl:   BuildRequires: openssl-devel}}
-    %{?_with_ldap:  BuildRequires: openldap-devel}}
+    %{?_with_ssl:BuildRequires: openssl-devel}
+    %{?_with_ldap:BuildRequires: openldap-devel}
     ...
 
     # Configure with desired features.
     #
     # Read: Add any defined feature values to the configure invocation.
     %configure \
-	%{?_with_ssl:       %{_with_ssl}}    \  
-	%{?_without_ssl:    %{_without_ssl}} \  
-	%{?_with_ldap:      %{_with_ldap}}   \
-	%{?_without_ldap:   %{_without_ldap}}\
+	%{?_with_ssl}		\
+	%{?_without_ssl}	\
+	%{?_with_ldap}		\
+	%{?_without_ldap}
+    ...
+
+    # Conditional tests for desired features.
+    #
+    # Read: true if _with_ssl is defined, false if not defined.
+    %if %{?_with_ssl:1}%{!?_with_ssl:0}
     ...
+    %endif
+
 \endverbatim
 
 */
diff --git a/lib/fsm.c b/lib/fsm.c
index 766b41800..2bace93df 100644
--- a/lib/fsm.c
+++ b/lib/fsm.c
@@ -1499,7 +1499,9 @@ int fsmStage(FSM_t fsm, fileStage stage)
 #ifdef	NOTYET
 	rc = fsmStat(fsm);
 #else
-	if (fsm->path != NULL) {
+	if (fsm->path != NULL &&
+	    !(fsm->goal == FSM_PKGINSTALL && S_ISREG(st->st_mode)))
+	{
 	    rc = fsmStage(fsm, (!(fsm->mapFlags & CPIO_FOLLOW_SYMLINKS)
 			? FSM_LSTAT : FSM_STAT));
 	    if (rc == CPIOERR_LSTAT_FAILED && errno == ENOENT) {
@@ -1717,7 +1719,9 @@ if (!(fsm->mapFlags & CPIO_ALL_HARDLINKS)) break;
 	break;
     case FSM_COMMIT:
 	/* Rename pre-existing modified or unmanaged file. */
-	if (fsm->diskchecked && fsm->exists && fsm->osuffix) {
+	if (fsm->osuffix && fsm->diskchecked &&
+	  (fsm->exists || (fsm->goal == FSM_PKGINSTALL && S_ISREG(st->st_mode))))
+	{
 	    const char * opath = fsm->opath;
 	    const char * path = fsm->path;
 	    fsm->opath = fsmFsPath(fsm, st, NULL, NULL);
diff --git a/lib/query.c b/lib/query.c
index 58e5445e2..dd642635c 100644
--- a/lib/query.c
+++ b/lib/query.c
@@ -778,7 +778,7 @@ restart:
         for (i = 0, t = md5, s = arg; i < 16; i++, t++, s += 2)
             *t = (nibble(s[0]) << 4) | nibble(s[1]);
 	
-	qva->qva_mi = rpmtsInitIterator(ts, RPMTAG_SIGMD5, md5, 16);
+	qva->qva_mi = rpmtsInitIterator(ts, RPMTAG_SIGMD5, md5, sizeof(md5));
 	if (qva->qva_mi == NULL) {
 	    rpmError(RPMERR_QUERYINFO, _("no package matches %s: %s\n"),
 			"pkgid", arg);
@@ -807,6 +807,9 @@ restart:
 	break;
 
     case RPMQV_FILEID:
+    {	unsigned char md5[16];
+	unsigned char * t;
+
 	for (i = 0, s = arg; *s && isxdigit(*s); s++, i++)
 	    {};
 	if (i != 32) {
@@ -814,7 +817,11 @@ restart:
 	    return 1;
 	}
 
-	qva->qva_mi = rpmtsInitIterator(ts, RPMTAG_FILEMD5S, arg, 0);
+	md5[0] = '\0';
+        for (i = 0, t = md5, s = arg; i < 16; i++, t++, s += 2)
+            *t = (nibble(s[0]) << 4) | nibble(s[1]);
+
+	qva->qva_mi = rpmtsInitIterator(ts, RPMTAG_FILEMD5S, md5, sizeof(md5));
 	if (qva->qva_mi == NULL) {
 	    rpmError(RPMERR_QUERYINFO, _("no package matches %s: %s\n"),
 			"fileid", arg);
@@ -822,7 +829,7 @@ restart:
 	} else {
 	    res = showMatches(qva, ts);
 	}
-	break;
+    }	break;
 
     case RPMQV_TID:
     {	int mybase = 10;
diff --git a/po/POTFILES.in b/po/POTFILES.in
index d81ec1d57..7e454f64b 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -59,6 +59,7 @@ rpmdb/hdrNVR.c
 rpmdb/header.c
 rpmdb/header_internal.c
 rpmdb/legacy.c
+rpmdb/merge.c
 rpmdb/poptDB.c
 rpmdb/rpmhash.c
 rpmdb/rpmdb.c
diff --git a/python/rpmmodule.c b/python/rpmmodule.c
index 57241d314..9da144631 100644
--- a/python/rpmmodule.c
+++ b/python/rpmmodule.c
@@ -1612,10 +1612,10 @@ static PyObject * rpmtransRun(rpmtransObject * s, PyObject * args) {
     list = PyList_New(0);
     for (i = 0; i < probs->numProblems; i++) {
 	rpmProblem myprob = probs->probs + i;
-	prob = Py_BuildValue("s(isi)", rpmProblemString(myprob),
+	prob = Py_BuildValue("s(isN)", rpmProblemString(myprob),
 			     myprob->type,
 			     myprob->str1,
-			     myprob->ulong1);
+			     PyLong_FromLongLong(myprob->ulong1));
 	PyList_Append(list, prob);
 	Py_DECREF(prob);
     }
diff --git a/rpmdb/Makefile.am b/rpmdb/Makefile.am
index 5ce1b016f..dd14fc771 100644
--- a/rpmdb/Makefile.am
+++ b/rpmdb/Makefile.am
@@ -36,7 +36,7 @@ DB3LOBJS = $(shell cat $(top_builddir)/$(WITH_DB_SUBDIR)/db3lobjs)
 lib_LTLIBRARIES = librpmdb.la
 librpmdb_la_SOURCES = \
 	dbconfig.c fprint.c \
-	hdrNVR.c header.c header_internal.c legacy.c \
+	hdrNVR.c header.c header_internal.c legacy.c merge.c \
 	poptDB.c rpmhash.c rpmdb.c \
 	tagname.c tagtbl.c
 librpmdb_la_LDFLAGS = -release @VERSION@ @libdb3@
diff --git a/rpmdb/header.c b/rpmdb/header.c
index c160b69af..79b0422ef 100644
--- a/rpmdb/header.c
+++ b/rpmdb/header.c
@@ -2526,19 +2526,22 @@ static int getExtension(Header h, headerTagTagFunction fn,
 
 /**
  */
+/*@observer@*/
 static char * formatValue(sprintfTag tag, Header h, 
 		const headerSprintfExtension extensions,
-		extensionCache extCache, int element)
-	/*@modifies extCache @*/
+		extensionCache extCache, int element,
+		char ** valp, int * vallenp, int * allocedp)
+	/*@modifies extCache, *valp, *vallenp, *allocedp @*/
 {
-    int len;
+    char * val = NULL;
+    int need = 0;
+    char * t, * te;
     char buf[20];
     int_32 count, type;
     hPTR_t data;
     unsigned int intVal;
-    char * val = NULL;
     const char ** strarray;
-    int mayfree = 0;
+    int datafree = 0;
     int countBuf;
     headerTagFormatFunction tagtype = NULL;
     headerSprintfExtension ext;
@@ -2551,16 +2554,16 @@ static char * formatValue(sprintfTag tag, Header h,
 	{
 	    count = 1;
 	    type = RPM_STRING_TYPE;	
-	    data = "(none)";		/* XXX i18n? NO!, sez; gafton */
+	    data = "(none)";
 	}
     } else {
 	if (!headerGetEntry(h, tag->tag, &type, (void **)&data, &count)) {
 	    count = 1;
 	    type = RPM_STRING_TYPE;	
-	    data = "(none)";		/* XXX i18n? NO!, sez; gafton */
+	    data = "(none)";
 	}
 
-	mayfree = 1;
+	datafree = 1;
     }
     /*@=branchstate@*/
 
@@ -2602,18 +2605,19 @@ static char * formatValue(sprintfTag tag, Header h,
 	if (tagtype)
 	    val = tagtype(RPM_STRING_TYPE, strarray[element], buf, tag->pad, 0);
 
-	if (!val) {
+	if (val) {
+	    need = strlen(val);
+	} else {
+	    need = strlen(strarray[element]) + tag->pad + 20;
+	    val = xmalloc(need+1);
 	    strcat(buf, "s");
-
-	    len = strlen(strarray[element]) + tag->pad + 20;
-	    val = xmalloc(len);
 	    /*@-formatconst@*/
 	    sprintf(val, buf, strarray[element]);
 	    /*@=formatconst@*/
 	}
 
 	/*@-observertrans -modobserver@*/
-	if (mayfree) data = _free(data);
+	if (datafree) data = _free(data);
 	/*@=observertrans =modobserver@*/
 
 	break;
@@ -2622,11 +2626,12 @@ static char * formatValue(sprintfTag tag, Header h,
 	if (tagtype)
 	    val = tagtype(RPM_STRING_ARRAY_TYPE, data, buf, tag->pad,  0);
 
-	if (!val) {
+	if (val) {
+	    need = strlen(val);
+	} else {
+	    need = strlen(data) + tag->pad + 20;
+	    val = xmalloc(need+1);
 	    strcat(buf, "s");
-
-	    len = strlen(data) + tag->pad + 20;
-	    val = xmalloc(len);
 	    /*@-formatconst@*/
 	    sprintf(val, buf, data);
 	    /*@=formatconst@*/
@@ -2654,10 +2659,12 @@ static char * formatValue(sprintfTag tag, Header h,
 	if (tagtype)
 	    val = tagtype(RPM_INT32_TYPE, &intVal, buf, tag->pad,  element);
 
-	if (!val) {
+	if (val) {
+	    need = strlen(val);
+	} else {
+	    need = 10 + tag->pad + 20;
+	    val = xmalloc(need+1);
 	    strcat(buf, "d");
-	    len = 10 + tag->pad + 20;
-	    val = xmalloc(len);
 	    /*@-formatconst@*/
 	    sprintf(val, buf, intVal);
 	    /*@=formatconst@*/
@@ -2668,18 +2675,18 @@ static char * formatValue(sprintfTag tag, Header h,
 	if (tagtype)
 	    val = tagtype(RPM_BIN_TYPE, data, buf, tag->pad, count);
 
-	if (!val) {
+	if (val) {
+	    need = count;	/* XXX broken iff RPM_BIN_TYPE extension */
+	} else {
 #ifdef	NOTYET
 	    val = memcpy(xmalloc(count), data, count);
 #else
 	    /* XXX format string not used */
 	    static char hex[] = "0123456789abcdef";
 	    const char * s = data;
-	    char * t;
 
-	    strcat(buf, "s");
-	    len = 2*count + tag->pad + 1;
-	    val = t = xmalloc(len);
+	    need = 2*count + tag->pad;
+	    val = t = xmalloc(need+1);
 	    while (count-- > 0) {
 		unsigned int i;
 		i = *s++;
@@ -2692,30 +2699,48 @@ static char * formatValue(sprintfTag tag, Header h,
 	break;
 
     default:
-	val = xstrdup(_("(unknown type)"));
+	need = sizeof("(unknown type)") - 1;
+	val = xstrdup("(unknown type)");
 	break;
     }
     /*@=branchstate@*/
 
-    return val;
+    /*@-branchstate@*/
+    if (val && need > 0) {
+	if (((*vallenp) + need) >= (*allocedp)) {
+	    if ((*allocedp) <= need)
+		(*allocedp) += need;
+	    (*allocedp) <<= 1;
+/*@-unqualifiedtrans@*/ /* FIX: double indirection */
+	    (*valp) = xrealloc((*valp), (*allocedp)+1);	
+/*@=unqualifiedtrans@*/
+	}
+	t = (*valp) + (*vallenp);
+	te = stpcpy(t, val);
+	(*vallenp) += (te - t);
+	val = _free(val);
+    }
+    /*@=branchstate@*/
+
+    return ((*valp) + (*vallenp));
 }
 
 /**
  */
-static const char * singleSprintf(Header h, sprintfToken token,
+/*@observer@*/
+static char * singleSprintf(Header h, sprintfToken token,
 		const headerSprintfExtension extensions,
-		extensionCache extCache, int element)
-	/*@modifies h, extCache @*/
+		extensionCache extCache, int element,
+		char ** valp, int * vallenp, int * allocedp)
+	/*@modifies h, extCache, *valp, *vallenp, *allocedp @*/
 {
-    char * val;
-    const char * thisItem;
-    int thisItemLen;
-    int len, alloced;
+    char * t, * te;
     int i, j;
     int numElements;
     int type;
     sprintfToken condFormat;
     int condNumFormats;
+    int need;
 
     /* we assume the token and header have been validated already! */
 
@@ -2724,13 +2749,26 @@ static const char * singleSprintf(Header h, sprintfToken token,
 	break;
 
     case PTOK_STRING:
-	val = xmalloc(token->u.string.len + 1);
-	strcpy(val, token->u.string.string);
+	need = token->u.string.len;
+	if (need <= 0) break;
+	if (((*vallenp) + need) >= (*allocedp)) {
+	    if ((*allocedp) <= need)
+		(*allocedp) += need;
+	    (*allocedp) <<= 1;
+/*@-unqualifiedtrans@*/ /* FIX: double indirection */
+	    (*valp) = xrealloc((*valp), (*allocedp)+1);	
+/*@=unqualifiedtrans@*/
+	}
+	t = (*valp) + (*vallenp);
+	te = stpcpy(t, token->u.string.string);
+	(*vallenp) += (te - t);
 	break;
 
     case PTOK_TAG:
-	val = formatValue(&token->u.tag, h, extensions, extCache,
-			  token->u.tag.justOne ? 0 : element);
+	t = (*valp) + (*vallenp);
+	te = formatValue(&token->u.tag, h, extensions, extCache,
+			(token->u.tag.justOne ? 0 : element),
+			valp, vallenp, allocedp);
 	break;
 
     case PTOK_COND:
@@ -2743,25 +2781,21 @@ static const char * singleSprintf(Header h, sprintfToken token,
 	    condNumFormats = token->u.cond.numElseTokens;
 	}
 
-	alloced = condNumFormats * 20;
-	val = xmalloc(alloced ? alloced : 1);
-	*val = '\0';
-	len = 0;
-
-	if (condFormat)
-	for (i = 0; i < condNumFormats; i++) {
-	    thisItem = singleSprintf(h, condFormat + i, 
-				     extensions, extCache, element);
-	    thisItemLen = strlen(thisItem);
-	    if ((thisItemLen + len) >= alloced) {
-		alloced = (thisItemLen + len) + 200;
-		val = xrealloc(val, alloced);	
-	    }
-	    strcat(val, thisItem);
-	    len += thisItemLen;
-	    thisItem = _free(thisItem);
+	need = condNumFormats * 20;
+	if (condFormat == NULL || need <= 0) break;
+	if (((*vallenp) + need) >= (*allocedp)) {
+	    if ((*allocedp) <= need)
+		(*allocedp) += need;
+	    (*allocedp) <<= 1;
+/*@-unqualifiedtrans@*/ /* FIX: double indirection */
+	    (*valp) = xrealloc((*valp), (*allocedp)+1);	
+/*@=unqualifiedtrans@*/
 	}
 
+	t = (*valp) + (*vallenp);
+	for (i = 0; i < condNumFormats; i++)
+	    te = singleSprintf(h, condFormat + i, extensions, extCache,
+				element, valp, vallenp, allocedp);
 	break;
 
     case PTOK_ARRAY:
@@ -2780,41 +2814,49 @@ static const char * singleSprintf(Header h, sprintfToken token,
 		     continue;
 	    } else {
 		if (!headerGetEntry(h, token->u.array.format[i].u.tag.tag, 
-				    &type, (void **) &val, &numElements))
+				    &type, NULL, &numElements))
 		    continue;
-		val = headerFreeData(val, type);
 	    } 
 	    /*@loopbreak@*/ break;
 	}
 
 	if (numElements == -1) {
-	    val = xstrdup("(none)");	/* XXX i18n? NO!, sez; gafton */
+	    need = sizeof("(none)") - 1;
+	    if (((*vallenp) + need) >= (*allocedp)) {
+		if ((*allocedp) <= need)
+		    (*allocedp) += need;
+		(*allocedp) <<= 1;
+/*@-unqualifiedtrans@*/ /* FIX: double indirection */
+		(*valp) = xrealloc((*valp), (*allocedp)+1);	
+/*@=unqualifiedtrans@*/
+	    }
+	    t = (*valp) + (*vallenp);
+	    te = stpcpy(t, "(none)");
+	    (*vallenp) += (te - t);
 	} else {
-	    alloced = numElements * token->u.array.numTokens * 20;
-	    val = xmalloc(alloced);
-	    *val = '\0';
-	    len = 0;
+	    need = numElements * token->u.array.numTokens * 10;
+	    if (need <= 0) break;
+	    if (((*vallenp) + need) >= (*allocedp)) {
+		if ((*allocedp) <= need)
+		    (*allocedp) += need;
+		(*allocedp) <<= 1;
+/*@-unqualifiedtrans@*/ /* FIX: double indirection */
+		(*valp) = xrealloc((*valp), (*allocedp)+1);	
+/*@=unqualifiedtrans@*/
+	    }
 
+	    t = (*valp) + (*vallenp);
 	    for (j = 0; j < numElements; j++) {
-		for (i = 0; i < token->u.array.numTokens; i++) {
-		    thisItem = singleSprintf(h, token->u.array.format + i, 
-					     extensions, extCache, j);
-		    thisItemLen = strlen(thisItem);
-		    if ((thisItemLen + len) >= alloced) {
-			alloced = (thisItemLen + len) + 200;
-			val = xrealloc(val, alloced);	
-		    }
-		    strcat(val, thisItem);
-		    len += thisItemLen;
-		    thisItem = _free(thisItem);
-		}
+		for (i = 0; i < token->u.array.numTokens; i++)
+		    te = singleSprintf(h, token->u.array.format + i, 
+					extensions, extCache, j,
+					valp, vallenp, allocedp);
 	    }
 	}
-	   
 	break;
     }
 
-    return val;
+    return ((*valp) + (*vallenp));
 }
 
 /**
@@ -2886,12 +2928,13 @@ char * headerSprintf(Header h, const char * fmt,
     headerSprintfExtension exts = (headerSprintfExtension) extensions;
     headerTagTableEntry tags = (headerTagTableEntry) tbltags;
     /*@=castexpose@*/
+    char * t;
     char * fmtString;
     sprintfToken format;
     int numTokens;
-    char * answer;
-    int answerLength;
-    int answerAlloced;
+    char * val = NULL;
+    int vallen = 0;
+    int alloced = 0;
     int i;
     extensionCache extCache;
  
@@ -2906,37 +2949,21 @@ char * headerSprintf(Header h, const char * fmt,
 
     extCache = allocateExtensionCache(exts);
 
-    answerAlloced = 1024;
-    answerLength = 0;
-    answer = xmalloc(answerAlloced);
-    *answer = '\0';
-
     for (i = 0; i < numTokens; i++) {
-	const char * piece;
-	int pieceLength;
-
 	/*@-mods@*/
-	piece = singleSprintf(h, format + i, exts, extCache, 0);
+	t = singleSprintf(h, format + i, exts, extCache, 0,
+		&val, &vallen, &alloced);
 	/*@=mods@*/
-	if (piece) {
-	    pieceLength = strlen(piece);
-	    if ((answerLength + pieceLength) >= answerAlloced) {
-		while ((answerLength + pieceLength) >= answerAlloced) 
-		    answerAlloced += 1024;
-		answer = xrealloc(answer, answerAlloced);
-	    }
-
-	    strcat(answer, piece);
-	    answerLength += pieceLength;
-	    piece = _free(piece);
-	}
     }
 
+    if (val != NULL && vallen < alloced)
+	val = xrealloc(val, vallen+1);	
+
     fmtString = _free(fmtString);
     extCache = freeExtensionCache(exts, extCache);
     format = _free(format);
 
-    return answer;
+    return val;
 }
 
 /**
diff --git a/rpmdb/merge.c b/rpmdb/merge.c
new file mode 100644
index 000000000..7e244407f
--- /dev/null
+++ b/rpmdb/merge.c
@@ -0,0 +1,354 @@
+/*@-mustmod -sizeoftype @*/
+/*-
+ * Copyright (c) 1992, 1993
+ *	The Regents of the University of California.  All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Peter McIlroy.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if defined(LIBC_SCCS) && !defined(lint)
+static char sccsid[] = "@(#)merge.c	8.2 (Berkeley) 2/14/94";
+#endif /* LIBC_SCCS and not lint */
+
+/*
+ * Hybrid exponential search/linear search merge sort with hybrid
+ * natural/pairwise first pass.  Requires about .3% more comparisons
+ * for random data than LSMS with pairwise first pass alone.
+ * It works for objects as small as two bytes.
+ */
+
+#define NATURAL
+#define THRESHOLD 16	/* Best choice for natural merge cut-off. */
+
+/* #define NATURAL to get hybrid natural merge.
+ * (The default is pairwise merging.)
+ */
+
+#include "system.h"
+
+#define ISIZE sizeof(int)
+#define PSIZE sizeof(unsigned char *)
+#define ICOPY_LIST(src, dst, last)				\
+	do							\
+	*(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;	\
+	while(src < last)
+#define ICOPY_ELT(src, dst, i)					\
+	do							\
+	*(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;	\
+	while (i -= ISIZE)
+
+#define CCOPY_LIST(src, dst, last)		\
+	do					\
+		*dst++ = *src++;		\
+	while (src < last)
+#define CCOPY_ELT(src, dst, i)			\
+	do					\
+		*dst++ = *src++;		\
+	while (i -= 1)
+
+/*
+ * Find the next possible pointer head.  (Trickery for forcing an array
+ * to do double duty as a linked list when objects do not align with word
+ * boundaries.
+ */
+/* Assumption: PSIZE is a power of 2. */
+#define EVAL(p) (unsigned char **)					\
+    ((unsigned char *)0 +						\
+	(((unsigned char *)p + PSIZE - 1 - (unsigned char *) 0) & ~(PSIZE - 1)))
+
+#define	swap(a, b) {					\
+		s = b;					\
+		i = size;				\
+		do {					\
+			tmp = *a; *a++ = *s; *s++ = tmp; \
+		} while (--i);				\
+		a -= size;				\
+	}
+#define reverse(bot, top) {				\
+	s = top;					\
+	do {						\
+		i = size;				\
+		do {					\
+			tmp = *bot; *bot++ = *s; *s++ = tmp; \
+		} while (--i);				\
+		s -= size2;				\
+	} while(bot < s);				\
+}
+
+/*
+ * This is to avoid out-of-bounds addresses in sorting the
+ * last 4 elements.
+ */
+static void
+insertionsort(unsigned char *a, size_t n, size_t size,
+		int (*cmp) (const void *, const void *))
+	/*@modifies *a @*/
+{
+	u_char *ai, *s, *t, *u, tmp;
+	int i;
+
+	for (ai = a+size; --n >= 1; ai += size)
+		for (t = ai; t > a; t -= size) {
+			u = t - size;
+			if (cmp(u, t) <= 0)
+				/*@innerbreak@*/ break;
+			swap(u, t);
+		}
+}
+
+/*
+ * Optional hybrid natural/pairwise first pass.  Eats up list1 in runs of
+ * increasing order, list2 in a corresponding linked list.  Checks for runs
+ * when THRESHOLD/2 pairs compare with same sense.  (Only used when NATURAL
+ * is defined.  Otherwise simple pairwise merging is used.)
+ */
+static void
+setup(unsigned char *list1, /*@out@*/ unsigned char *list2,
+		size_t n, size_t size, int (*cmp) (const void *, const void *))
+	/*@modifies list1, list2 @*/
+{
+	int i, length, size2, tmp, sense;
+	unsigned char *f1, *f2, *s, *l2, *last, *p2;
+
+	size2 = size*2;
+	if (n <= 5) {
+		insertionsort(list1, n, size, cmp);
+		*EVAL(list2) = (unsigned char*) list2 + n*size;
+		return;
+	}
+	/*
+	 * Avoid running pointers out of bounds; limit n to evens
+	 * for simplicity.
+	 */
+	i = 4 + (n & 1);
+	insertionsort(list1 + (n - i) * size, i, size, cmp);
+	last = list1 + size * (n - i);
+	*EVAL(list2 + (last - list1)) = list2 + n * size;
+
+#ifdef NATURAL
+	p2 = list2;
+	f1 = list1;
+	sense = (cmp(f1, f1 + size) > 0);
+	for (; f1 < last; sense = !sense) {
+		length = 2;
+					/* Find pairs with same sense. */
+		for (f2 = f1 + size2; f2 < last; f2 += size2) {
+			if ((cmp(f2, f2+ size) > 0) != sense)
+				/*@innerbreak@*/ break;
+			length += 2;
+		}
+		if (length < THRESHOLD) {		/* Pairwise merge */
+			do {
+				p2 = *EVAL(p2) = f1 + size2 - list1 + list2;
+				if (sense > 0)
+					swap (f1, f1 + size);
+			} while ((f1 += size2) < f2);
+		} else {				/* Natural merge */
+			l2 = f2;
+			for (f2 = f1 + size2; f2 < l2; f2 += size2) {
+				if ((cmp(f2-size, f2) > 0) != sense) {
+					p2 = *EVAL(p2) = f2 - list1 + list2;
+					if (sense > 0)
+						reverse(f1, f2-size);
+					f1 = f2;
+				}
+			}
+			if (sense > 0)
+				reverse (f1, f2-size);
+			f1 = f2;
+			if (f2 < last || cmp(f2 - size, f2) > 0)
+				p2 = *EVAL(p2) = f2 - list1 + list2;
+			else
+				p2 = *EVAL(p2) = list2 + n*size;
+		}
+	}
+#else		/* pairwise merge only. */
+	for (f1 = list1, p2 = list2; f1 < last; f1 += size2) {
+		p2 = *EVAL(p2) = p2 + size2;
+		if (cmp (f1, f1 + size) > 0)
+			swap(f1, f1 + size);
+	}
+#endif /* NATURAL */
+}
+
+/*
+ * Arguments are as for qsort.
+ */
+int
+mergesort(void *base, size_t nmemb, size_t size,
+		int (*cmp) (const void *, const void *))
+{
+	register int i, sense;
+	int big, iflag;
+	register unsigned char *f1, *f2, *t, *b, *q, *l1, *l2;
+	/*@dependent@*/
+	register unsigned char *tp2;
+	/*@owned@*/
+	unsigned char *list2;
+	/*@dependent@*/
+	unsigned char *list1;
+	unsigned char *p2, *p, *last, **p1;
+
+	if (size < PSIZE / 2) {		/* Pointers must fit into 2 * size. */
+		errno = EINVAL;
+		return (-1);
+	}
+
+	if (nmemb == 0)
+		return (0);
+
+	/*
+	 * XXX
+	 * Stupid subtraction for the Cray.
+	 */
+	iflag = 0;
+	if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE))
+		iflag = 1;
+
+	if ((list2 = malloc(nmemb * size + PSIZE)) == NULL)
+		return (-1);
+
+	list1 = base;
+	setup(list1, list2, nmemb, size, cmp);
+	last = list2 + nmemb * size;
+	i = big = 0;
+/*@-branchstate@*/
+	while (*EVAL(list2) != last) {
+	    l2 = list1;
+	    p1 = EVAL(list1);
+	    for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) {
+	    	p2 = *EVAL(p2);
+	    	f1 = l2;
+	    	f2 = l1 = list1 + (p2 - list2);
+	    	if (p2 != last)
+	    		p2 = *EVAL(p2);
+	    	l2 = list1 + (p2 - list2);
+	    	while (f1 < l1 && f2 < l2) {
+	    		if ((*cmp)(f1, f2) <= 0) {
+	    			q = f2;
+	    			b = f1, t = l1;
+	    			sense = -1;
+	    		} else {
+	    			q = f1;
+	    			b = f2, t = l2;
+	    			sense = 0;
+	    		}
+	    		if (!big) {	/* here i = 0 */
+				while ((b += size) < t && cmp(q, b) >sense)
+	    				if (++i == 6) {
+	    					big = 1;
+	    					goto EXPONENTIAL;
+	    				}
+	    		} else {
+EXPONENTIAL:	    		for (i = size; ; i <<= 1)
+	    				if ((p = (b + i)) >= t) {
+	    					if ((p = t - size) > b &&
+						    (*cmp)(q, p) <= sense)
+	    						t = p;
+	    					else
+	    						b = p;
+	    					/*@innerbreak@*/ break;
+	    				} else if ((*cmp)(q, p) <= sense) {
+	    					t = p;
+	    					if (i == size)
+	    						big = 0;
+	    					goto FASTCASE;
+	    				} else
+	    					b = p;
+				/*@-infloopsuncon@*/
+				while (t > b+size) {
+	    				i = (((t - b) / size) >> 1) * size;
+	    				if ((*cmp)(q, p = b + i) <= sense)
+	    					t = p;
+	    				else
+	    					b = p;
+	    			}
+	    			goto COPY;
+FASTCASE:	    		while (i > size)
+	    				if ((*cmp)(q,
+	    					p = b + (i >>= 1)) <= sense)
+	    					t = p;
+	    				else
+	    					b = p;
+				/*@=infloopsuncon@*/
+COPY:	    			b = t;
+	    		}
+	    		i = size;
+	    		if (q == f1) {
+	    			if (iflag) {
+	    				ICOPY_LIST(f2, tp2, b);
+	    				ICOPY_ELT(f1, tp2, i);
+	    			} else {
+	    				CCOPY_LIST(f2, tp2, b);
+	    				CCOPY_ELT(f1, tp2, i);
+	    			}
+	    		} else {
+	    			if (iflag) {
+	    				ICOPY_LIST(f1, tp2, b);
+	    				ICOPY_ELT(f2, tp2, i);
+	    			} else {
+	    				CCOPY_LIST(f1, tp2, b);
+	    				CCOPY_ELT(f2, tp2, i);
+	    			}
+	    		}
+	    	}
+	    	if (f2 < l2) {
+	    		if (iflag)
+	    			ICOPY_LIST(f2, tp2, l2);
+	    		else
+	    			CCOPY_LIST(f2, tp2, l2);
+	    	} else if (f1 < l1) {
+	    		if (iflag)
+	    			ICOPY_LIST(f1, tp2, l1);
+	    		else
+	    			CCOPY_LIST(f1, tp2, l1);
+	    	}
+	    	*p1 = l2;
+	    }
+/*@-dependenttrans@*/
+	    tp2 = list1;	/* swap list1, list2 */
+	    list1 = list2;
+	    list2 = tp2;
+/*@=dependenttrans@*/
+	    last = list2 + nmemb*size;
+	}
+/*@=branchstate@*/
+	if (base == list2) {
+		memmove(list2, list1, nmemb*size);
+		list2 = list1;
+	}
+/*@-usereleased@*/
+	free(list2);
+/*@=usereleased@*/
+	return (0);
+}
+/*@=mustmod =sizeoftype @*/
diff --git a/rpmdb/rpmdb.c b/rpmdb/rpmdb.c
index 9c4c20f9c..3a6c19c73 100644
--- a/rpmdb/rpmdb.c
+++ b/rpmdb/rpmdb.c
@@ -730,11 +730,6 @@ static INLINE int dbiAppendSet(dbiIndexSet set, const void * recs,
     if (set == NULL || recs == NULL || nrecs <= 0 || recsize == 0)
 	return 1;
 
-#ifdef	DYING
-    if (set->count == 0)
-	set->recs = xmalloc(nrecs * sizeof(*(set->recs)));
-    else
-#endif
     set->recs = xrealloc(set->recs,
 			(set->count + nrecs) * sizeof(*(set->recs)));
 
@@ -1709,7 +1704,8 @@ int rpmdbGetIteratorCount(rpmdbMatchIterator mi) {
 
 /**
  * Return pattern match.
- * @param mi		rpm database iterator
+ * @param mire		match iterator regex
+ * @param val		value to match
  * @return		0 if pattern matches
  */
 static int miregexec(miRE mire, const char * val)
@@ -2236,8 +2232,17 @@ static void rpmdbSortIterator(/*@null@*/ rpmdbMatchIterator mi)
 	/*@modifies mi @*/
 {
     if (mi && mi->mi_set && mi->mi_set->recs && mi->mi_set->count > 0) {
-	qsort(mi->mi_set->recs, mi->mi_set->count, sizeof(*mi->mi_set->recs),
-		hdrNumCmp);
+    /*
+     * mergesort is much (~10x with lots of identical basenames) faster
+     * than pure quicksort, but glibc uses msort_with_tmp() on stack.
+     */
+#if defined(__GLIBC__)
+	qsort(mi->mi_set->recs, mi->mi_set->count,
+		sizeof(*mi->mi_set->recs), hdrNumCmp);
+#else
+	mergesort(mi->mi_set->recs, mi->mi_set->count,
+		sizeof(*mi->mi_set->recs), hdrNumCmp);
+#endif
 	mi->mi_sorted = 1;
     }
 }
diff --git a/rpmdb/rpmdb.h b/rpmdb/rpmdb.h
index c0fd4dd79..894afad36 100644
--- a/rpmdb/rpmdb.h
+++ b/rpmdb/rpmdb.h
@@ -556,6 +556,15 @@ unsigned int dbiIndexRecordOffset(dbiIndexSet set, int recno)
 unsigned int dbiIndexRecordFileNumber(dbiIndexSet set, int recno)
 	/*@*/;
 
+/**
+ * Mergesort, same arguments as qsort(2).
+ */
+/*@unused@*/
+int mergesort(void *base, size_t nmemb, size_t size,
+                int (*cmp) (const void *, const void *))
+	/*@globals errno @*/
+	/*@modifies base, errno @*/;
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/rpmdb/tjfn.c b/rpmdb/tjfn.c
index dfb9c81f8..2472aa4e8 100644
--- a/rpmdb/tjfn.c
+++ b/rpmdb/tjfn.c
@@ -86,6 +86,7 @@ static int
 db_put(DB * db, const char * kstr, int klen, const char * dstr, int dlen)
 {
     DBT key, data;
+    int ret;
 
     memset(&key, 0, sizeof(key));
     memset(&data, 0, sizeof(data));
@@ -99,7 +100,11 @@ db_put(DB * db, const char * kstr, int klen, const char * dstr, int dlen)
     data.data = (void *)dstr;
     data.size = dlen;
 
-    return db->put(db, NULL, &key, &data, 0);
+    ret = db->put(db, NULL, &key, &data, 0);
+    if (ret == DB_KEYEXIST)
+	ret = 0;
+
+    return ret;
 }
 
 static int
diff --git a/rpmio/rpmerr.h b/rpmio/rpmerr.h
index b3ca40685..677e499a1 100644
--- a/rpmio/rpmerr.h
+++ b/rpmio/rpmerr.h
@@ -131,7 +131,7 @@ typedef enum rpmerrCode_e {
     RPMDEBUG_UNLINK	= _dm(512u+16),	/*!< unlink(2) failed */
     RPMDEBUG_RMDIR	= _dm(512u+17),	/*!< rmdir(2) failed */
 /*@-enummemuse@*/
-    RPMWARN_FLOCK	= _wm(512u+27)	/*!< locking the database failed */
+    RPMWARN_FLOCK	= _wm(512u+27),	/*!< locking the database failed */
 /*@=enummemuse@*/
 } rpmerrCode;
 /*@=typeuse @*/
diff --git a/zlib/zconf.h b/zlib/zconf.h
index eb0ae2e1a..dc1910269 100644
--- a/zlib/zconf.h
+++ b/zlib/zconf.h
@@ -1,9 +1,10 @@
+/*@-constuse -typeuse@*/
 /* zconf.h -- configuration of the zlib compression library
  * Copyright (C) 1995-2002 Jean-loup Gailly.
  * For conditions of distribution and use, see copyright notice in zlib.h 
  */
 
-/* @(#) $Id$ */
+/* @(#) $Id: zconf.h,v 1.6 2002/03/17 15:46:23 jbj Exp $ */
 
 #ifndef _ZCONF_H
 #define _ZCONF_H
@@ -277,3 +278,4 @@ typedef uLong FAR uLongf;
 #endif
 
 #endif /* _ZCONF_H */
+/*@=constuse =typeuse@*/
diff --git a/zlib/zlib.h b/zlib/zlib.h
index 52cb529f6..1bc5ecf27 100644
--- a/zlib/zlib.h
+++ b/zlib/zlib.h
@@ -1,3 +1,4 @@
+/*@-declundef -fcnuse -typeuse @*/
 /* zlib.h -- interface of the 'zlib' general purpose compression library
   version 1.1.4, March 11th, 2002
 
@@ -891,3 +892,4 @@ ZEXTERN const uLongf * ZEXPORT get_crc_table    OF((void));
 #endif
 
 #endif /* _ZLIB_H */
+/*@=declundef =fcnuse =typeuse @*/