From ea5240a5edceccc6c6410a56b68ec4d8038da4bb Mon Sep 17 00:00:00 2001
From: Richard Levitte <levitte@openssl.org>
Date: Tue, 29 Apr 2003 20:25:21 +0000
Subject: [PATCH] Add an extended variant of OBJ_bsearch() that can be given a
 few flags.

---
 CHANGES                  | 15 +++++++++++++++
 crypto/objects/obj_dat.c | 35 +++++++++++++++++++++++++++--------
 crypto/objects/objects.h |  7 ++++++-
 3 files changed, 48 insertions(+), 9 deletions(-)

diff --git a/CHANGES b/CHANGES
index 6b1d73c5ef..c65cf1f5fc 100644
--- a/CHANGES
+++ b/CHANGES
@@ -4,6 +4,21 @@
 
  Changes between 0.9.7a and 0.9.8  [xx XXX xxxx]
 
+  *) Add the function OBJ_bsearch_ex() which works like OBJ_bsearch() but
+     takes an extra flags argument for optional functionality.  Currently,
+     the following flags are defined:
+
+	OBJ_BSEARCH_VALUE_ON_NOMATCH
+	This one gets OBJ_bsearch_ex() to return a pointer to the first
+	element where the comparing function returns a negative or zero
+	number.
+
+	OBJ_BSEARCH_FIRST_VALUE_ON_MATCH
+	This one gets OBJ_bsearch_ex() to return a pointer to the first
+	element where the comparing function returns zero.  This is useful
+	if there are more than one element where the comparing function
+	returns zero.
+
   *) Make it possible to create self-signed certificates with 'openssl ca'
      in such a way that the self-signed certificate becomes part of the
      CA database and uses the same mechanisms for serial number generation
diff --git a/crypto/objects/obj_dat.c b/crypto/objects/obj_dat.c
index 5d983e3ed4..adab7a7343 100644
--- a/crypto/objects/obj_dat.c
+++ b/crypto/objects/obj_dat.c
@@ -556,8 +556,14 @@ static int obj_cmp(const void *ap, const void *bp)
 const char *OBJ_bsearch(const char *key, const char *base, int num, int size,
 	int (*cmp)(const void *, const void *))
 	{
+	return OBJ_bsearch_ex(key, base, num, size, cmp, 0);
+	}
+
+const char *OBJ_bsearch_ex(const char *key, const char *base, int num,
+	int size, int (*cmp)(const void *, const void *), int flags)
+	{
 	int l,h,i,c;
-	const char *p;
+	const char *p = NULL;
 
 	if (num == 0) return(NULL);
 	l=0;
@@ -572,20 +578,33 @@ const char *OBJ_bsearch(const char *key, const char *base, int num, int size,
 		else if (c > 0)
 			l=i+1;
 		else
-			return(p);
+			break;
 		}
 #ifdef CHARSET_EBCDIC
 /* THIS IS A KLUDGE - Because the *_obj is sorted in ASCII order, and
  * I don't have perl (yet), we revert to a *LINEAR* search
  * when the object wasn't found in the binary search.
  */
-	for (i=0; i<num; ++i) {
-		p= &(base[i*size]);
-		if ((*cmp)(key,p) == 0)
-			return p;
-	}
+	if (c != 0)
+		{
+		for (i=0; i<num; ++i)
+			{
+			p= &(base[i*size]);
+			c = (*cmp)(key,p);
+			if (c == 0 || (c < 0 && (flags & OBJ_BSEARCH_VALUE_ON_NOMATCH)))
+				return p;
+			}
+		}
 #endif
-	return(NULL);
+	if (c != 0 && !(flags & OBJ_BSEARCH_VALUE_ON_NOMATCH))
+		p = NULL;
+	else if (c == 0 && (flags & OBJ_BSEARCH_FIRST_VALUE_ON_MATCH))
+		{
+		while(i > 0 && (*cmp)(key,&(base[(i-1)*size])) == 0)
+			i--;
+		p = &(base[i*size]);
+		}
+	return(p);
 	}
 
 int OBJ_create_objects(BIO *in)
diff --git a/crypto/objects/objects.h b/crypto/objects/objects.h
index de10532813..8b509516fc 100644
--- a/crypto/objects/objects.h
+++ b/crypto/objects/objects.h
@@ -966,7 +966,10 @@
 #define	OBJ_NAME_TYPE_COMP_METH		0x04
 #define	OBJ_NAME_TYPE_NUM		0x05
 
-#define	OBJ_NAME_ALIAS		0x8000
+#define	OBJ_NAME_ALIAS			0x8000
+
+#define OBJ_BSEARCH_VALUE_ON_NOMATCH		0x01
+#define OBJ_BSEARCH_FIRST_VALUE_ON_MATCH	0x02
 
 
 #ifdef  __cplusplus
@@ -1010,6 +1013,8 @@ int		OBJ_sn2nid(const char *s);
 int		OBJ_cmp(const ASN1_OBJECT *a,const ASN1_OBJECT *b);
 const char *	OBJ_bsearch(const char *key,const char *base,int num,int size,
 	int (*cmp)(const void *, const void *));
+const char *	OBJ_bsearch_ex(const char *key,const char *base,int num,
+	int size, int (*cmp)(const void *, const void *), int flags);
 
 int		OBJ_new_nid(int num);
 int		OBJ_add_object(const ASN1_OBJECT *obj);
-- 
2.25.1