Use binary search for looking up tag values + types.

Mostly derived from rpm5.org work of Jeff Johnsson, additionally
- fix thinko in bsearch result stabilization logic
- fix querytags in verbose mode to actually show the types as intended

2 files changed, 223 insertions, 24 deletions

diff --git a/rpmdb/header.h b/rpmdb/header.h
index ce4131e42..4a097a0a8 100644
--- a/rpmdb/header.h
+++ b/rpmdb/header.h
@@ -131,6 +131,31 @@ struct headerTagTableEntry_s {
     int type;			/*!< Tag type. */
 };
 
+/**
+ */
+typedef /*@abstract@*/ struct headerTagIndices_s * headerTagIndices;
+struct headerTagIndices_s {
+    int (*loadIndex) (headerTagTableEntry ** ipp, int * np,
+                int (*cmp) (const void * avp, const void * bvp))
+        /*@ modifies *ipp, *np */;	/*!< load sorted tag index. */
+/*@relnull@*/
+    headerTagTableEntry * byName;	/*!< header tags sorted by name. */
+    int byNameSize;			/*!< no. of entries. */
+    int (*byNameCmp) (const void * avp, const void * bvp)
+        /*@*/;				/*!< compare entries by name. */
+    int (*tagValue) (const char * name)
+	/*@*/;				/* return value from name. */
+/*@relnull@*/
+    headerTagTableEntry * byValue;	/*!< header tags sorted by value. */
+    int byValueSize;			/*!< no. of entries. */
+    int (*byValueCmp) (const void * avp, const void * bvp)
+        /*@*/;				/*!< compare entries by value. */
+    const char * (*tagName) (int value)
+	/*@*/;				/* Return name from value. */
+    int (*tagType) (int value)
+	/*@*/;				/* Return type from value. */
+};
+
 /** \ingroup header
  */
 enum headerSprintfExtensionType {
diff --git a/rpmdb/tagname.c b/rpmdb/tagname.c
index 49143da3b..e92f79e63 100644
--- a/rpmdb/tagname.c
+++ b/rpmdb/tagname.c
@@ -5,27 +5,106 @@
 #include "system.h"
 
 #include <rpmlib.h>
+#include <rpmio.h>
 #include "debug.h"
 
-int tagType(int tag)
+/*@access headerTagTableEntry @*/
+/*@access headerTagIndices @*/
+
+/**
+ * Compare tag table entries by name.
+ * @param *avp		tag table entry a
+ * @param *bvp		tag table entry b
+ * @return		comparison
+ */
+static int tagCmpName(const void * avp, const void * bvp)
+        /*@*/
 {
-    int tagtype = RPM_NULL_TYPE;
-    int i;
+    headerTagTableEntry a = *(headerTagTableEntry *) avp;
+    headerTagTableEntry b = *(headerTagTableEntry *) bvp;
+    return strcmp(a->name, b->name);
+}
 
-    for (i = 0; i < rpmTagTableSize; i++) {
-        if (tag != rpmTagTable[i].val)
-		continue;
-	tagtype = rpmTagTable[i].type;
-	break;
+/**
+ * Compare tag table entries by value.
+ * @param *avp		tag table entry a
+ * @param *bvp		tag table entry b
+ * @return		comparison
+ */
+static int tagCmpValue(const void * avp, const void * bvp)
+        /*@*/
+{
+    headerTagTableEntry a = *(headerTagTableEntry *) avp;
+    headerTagTableEntry b = *(headerTagTableEntry *) bvp;
+    int ret = (a->val - b->val);
+    /* Make sure that sort is stable, longest name first. */
+    if (ret == 0)
+	ret = (strlen(b->name) - strlen(a->name));
+    return ret;
+}
+
+/**
+ * Load/sort a tag index.
+ * @retval *ipp		tag index
+ * @retval *np		no. of tags
+ * @param cmp		sort compare routine
+ * @return		0 always
+ */
+static int tagLoadIndex(headerTagTableEntry ** ipp, int * np,
+		int (*cmp) (const void * avp, const void * bvp))
+	/*@modifies *ipp, *np @*/
+{
+    headerTagTableEntry tte, *ip;
+    int n = 0;
+
+    ip = xcalloc(rpmTagTableSize, sizeof(*ip));
+    n = 0;
+/*@-dependenttrans@*/ /*@-observertrans@*/ /*@-castexpose@*/ /*@-mods@*/ /*@-modobserver@*/
+    for (tte = (headerTagTableEntry)rpmTagTable; tte->name != NULL; tte++) {
+	ip[n] = tte;
+	n++;
     }
-    return tagtype;
+assert(n == rpmTagTableSize);
+/*@=dependenttrans@*/ /*@=observertrans@*/ /*@=castexpose@*/ /*@=mods@*/ /*@=modobserver@*/
+
+    if (n > 1)
+	qsort(ip, n, sizeof(*ip), cmp);
+    *ipp = ip;
+    *np = n;
+    return 0;
 }
 
-const char * tagName(int tag)
+
+/* forward refs */
+static const char * _tagName(int tag)
+	/*@*/;
+static int _tagType(int tag)
+	/*@*/;
+static int _tagValue(const char * tagstr)
+	/*@*/;
+
+/*@unchecked@*/
+static struct headerTagIndices_s _rpmTags = {
+    tagLoadIndex,
+    NULL, 0, tagCmpName, _tagValue,
+    NULL, 0, tagCmpValue, _tagName, _tagType,
+};
+
+/*@-compmempass@*/
+/*@unchecked@*/
+headerTagIndices rpmTags = &_rpmTags;
+/*@=compmempass@*/
+
+static const char * _tagName(int tag)
 {
     static char nameBuf[128];	/* XXX yuk */
+    const struct headerTagTableEntry_s *t;
+    int comparison, i, l, u;
+    int xx;
     char *s;
-    int i;
+
+    if (_rpmTags.byValue == NULL)
+	xx = tagLoadIndex(&_rpmTags.byValue, &_rpmTags.byValueSize, tagCmpValue);
 
     switch (tag) {
     case RPMDBI_PACKAGES:
@@ -52,28 +131,107 @@ const char * tagName(int tag)
     case RPMDBI_FTSWALK:
 	strcpy(nameBuf, "Ftswalk");
 	break;
+
+    /* XXX make sure rpmdb indices are identically named. */
+    case RPMTAG_CONFLICTS:
+	strcpy(nameBuf, "Conflictname");
+	break;
+    case RPMTAG_HDRID:
+	strcpy(nameBuf, "Sha1header");
+	break;
+
     default:
 	strcpy(nameBuf, "(unknown)");
+	if (_rpmTags.byValue == NULL)
+	    break;
 /*@-boundswrite@*/
-	for (i = 0; i < rpmTagTableSize; i++) {
-	    if (tag != rpmTagTable[i].val)
-		continue;
-	    nameBuf[0] = nameBuf[1] = '\0';
-	    if (rpmTagTable[i].name != NULL)	/* XXX programmer error. */
-		strcpy(nameBuf, rpmTagTable[i].name + (sizeof("RPMTAG_")-1));
-	    for (s = nameBuf+1; *s != '\0'; s++)
-		*s = xtolower(*s);
-	    /*@loopbreak@*/ break;
+	l = 0;
+	u = _rpmTags.byValueSize;
+	while (l < u) {
+	    i = (l + u) / 2;
+	    t = _rpmTags.byValue[i];
+	
+	    comparison = (tag - t->val);
+
+	    if (comparison < 0)
+		u = i;
+	    else if (comparison > 0)
+		l = i + 1;
+	    else {
+		nameBuf[0] = nameBuf[1] = '\0';
+		/* Make sure that the bsearch retrieve is stable. */
+		while (i > 0 && tag == _rpmTags.byValue[i-1]->val) {
+		    i--;
+		}
+		t = _rpmTags.byValue[i];
+		if (t->name != NULL)
+		    strcpy(nameBuf, t->name + (sizeof("RPMTAG_")-1));
+		for (s = nameBuf+1; *s != '\0'; s++)
+		    *s = xtolower(*s);
+		/*@loopbreak@*/ break;
+	    }
 	}
-/*@=boundswrite@*/
 	break;
     }
+/*@-statictrans@*/
     return nameBuf;
+/*@=statictrans@*/
 }
 
-int tagValue(const char * tagstr)
+static int _tagType(int tag)
 {
     const struct headerTagTableEntry_s *t;
+    int comparison, i, l, u;
+    int xx;
+
+    if (_rpmTags.byValue == NULL)
+	xx = tagLoadIndex(&_rpmTags.byValue, &_rpmTags.byValueSize, tagCmpValue);
+
+    switch (tag) {
+    case RPMDBI_PACKAGES:
+    case RPMDBI_DEPENDS:
+    case RPMDBI_ADDED:
+    case RPMDBI_REMOVED:
+    case RPMDBI_AVAILABLE:
+    case RPMDBI_HDLIST:
+    case RPMDBI_ARGLIST:
+    case RPMDBI_FTSWALK:
+	break;
+    default:
+	if (_rpmTags.byValue == NULL)
+	    break;
+/*@-boundswrite@*/
+	l = 0;
+	u = _rpmTags.byValueSize;
+	while (l < u) {
+	    i = (l + u) / 2;
+	    t = _rpmTags.byValue[i];
+	
+	    comparison = (tag - t->val);
+
+	    if (comparison < 0)
+		u = i;
+	    else if (comparison > 0)
+		l = i + 1;
+	    else {
+		/* Make sure that the bsearch retrieve is stable. */
+		while (i > 0 && t->val == _rpmTags.byValue[i-1]->val) {
+		    i--;
+		}
+		t = _rpmTags.byValue[i];
+		return t->type;
+	    }
+	}
+	break;
+    }
+    return RPM_NULL_TYPE;
+}
+
+static int _tagValue(const char * tagstr)
+{
+    const struct headerTagTableEntry_s *t;
+    int comparison, i, l, u;
+    int xx;
 
     if (!xstrcasecmp(tagstr, "Packages"))
 	return RPMDBI_PACKAGES;
@@ -92,8 +250,24 @@ int tagValue(const char * tagstr)
     if (!xstrcasecmp(tagstr, "Ftswalk"))
 	return RPMDBI_FTSWALK;
 
-    for (t = rpmTagTable; t->name != NULL; t++) {
-	if (!xstrcasecmp(t->name + (sizeof("RPMTAG_")-1), tagstr))
+    if (_rpmTags.byName == NULL)
+	xx = tagLoadIndex(&_rpmTags.byName, &_rpmTags.byNameSize, tagCmpName);
+    if (_rpmTags.byName == NULL)
+	return -1;
+
+    l = 0;
+    u = _rpmTags.byNameSize;
+    while (l < u) {
+	i = (l + u) / 2;
+	t = _rpmTags.byName[i];
+	
+	comparison = xstrcasecmp(tagstr, t->name + (sizeof("RPMTAG_")-1));
+
+	if (comparison < 0)
+	    u = i;
+	else if (comparison > 0)
+	    l = i + 1;
+	else
 	    return t->val;
     }
     return -1;