X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libraries%2Fliblmdb%2Fmidl.c;h=57a9d4920e94d9c555dc6bcdac407af7195e2fd1;hb=dec097f8b0f6752f6fe16ccbb623accf211ca319;hp=7289f405d901b41f3693df6555266c6d14c118a5;hpb=f9d41ba98a8af4a4789edb9aeb033d70d4abc49c;p=openldap

diff --git a/libraries/liblmdb/midl.c b/libraries/liblmdb/midl.c
index 7289f405d9..57a9d4920e 100644
--- a/libraries/liblmdb/midl.c
+++ b/libraries/liblmdb/midl.c
@@ -3,7 +3,7 @@
 /* $OpenLDAP$ */
 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
  *
- * Copyright 2000-2012 The OpenLDAP Foundation.
+ * Copyright 2000-2015 The OpenLDAP Foundation.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -18,11 +18,11 @@
 #include <limits.h>
 #include <string.h>
 #include <stdlib.h>
+#include <errno.h>
 #include <sys/types.h>
-#include <assert.h>
 #include "midl.h"
 
-/** @defgroup internal	MDB Internals
+/** @defgroup internal	LMDB Internals
  *	@{
  */
 /** @defgroup idls	ID List Management
@@ -30,8 +30,7 @@
  */
 #define CMP(x,y)	 ( (x) < (y) ? -1 : (x) > (y) )
 
-#if 0	/* superseded by append/sort */
-static unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id )
+unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id )
 {
 	/*
 	 * binary search of id in ids
@@ -59,28 +58,18 @@ static unsigned mdb_midl_search( MDB_IDL ids, MDB_ID id )
 			return cursor;
 		}
 	}
-	
+
 	if( val > 0 ) {
 		++cursor;
 	}
 	return cursor;
 }
 
+#if 0	/* superseded by append/sort */
 int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
 {
 	unsigned x, i;
 
-	if (MDB_IDL_IS_RANGE( ids )) {
-		/* if already in range, treat as a dup */
-		if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
-			return -1;
-		if (id < MDB_IDL_RANGE_FIRST(ids))
-			ids[1] = id;
-		else if (id > MDB_IDL_RANGE_LAST(ids))
-			ids[2] = id;
-		return 0;
-	}
-
 	x = mdb_midl_search( ids, id );
 	assert( x > 0 );
 
@@ -96,16 +85,10 @@ int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
 	}
 
 	if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
-		if( id < ids[1] ) {
-			ids[1] = id;
-			ids[2] = ids[ids[0]-1];
-		} else if ( ids[ids[0]-1] < id ) {
-			ids[2] = id;
-		} else {
-			ids[2] = ids[ids[0]-1];
-		}
-		ids[0] = MDB_NOID;
-	
+		/* no room */
+		--ids[0];
+		return -2;
+
 	} else {
 		/* insert id */
 		for (i=ids[0]; i>x; i--)
@@ -117,26 +100,55 @@ int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
 }
 #endif
 
-MDB_IDL mdb_midl_alloc()
+MDB_IDL mdb_midl_alloc(int num)
 {
-	MDB_IDL ids = malloc((MDB_IDL_UM_MAX+1) * sizeof(MDB_ID));
-	*ids++ = MDB_IDL_UM_MAX;
+	MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID));
+	if (ids) {
+		*ids++ = num;
+		*ids = 0;
+	}
 	return ids;
 }
 
 void mdb_midl_free(MDB_IDL ids)
 {
-	free(ids-1);
+	if (ids)
+		free(ids-1);
 }
 
-int mdb_midl_shrink( MDB_IDL *idp )
+void mdb_midl_shrink( MDB_IDL *idp )
 {
 	MDB_IDL ids = *idp;
-	if (*(--ids) > MDB_IDL_UM_MAX) {
-		ids = realloc(ids, (MDB_IDL_UM_MAX+1) * sizeof(MDB_ID));
+	if (*(--ids) > MDB_IDL_UM_MAX &&
+		(ids = realloc(ids, (MDB_IDL_UM_MAX+1) * sizeof(MDB_ID))))
+	{
 		*ids++ = MDB_IDL_UM_MAX;
 		*idp = ids;
-		return 1;
+	}
+}
+
+static int mdb_midl_grow( MDB_IDL *idp, int num )
+{
+	MDB_IDL idn = *idp-1;
+	/* grow it */
+	idn = realloc(idn, (*idn + num + 2) * sizeof(MDB_ID));
+	if (!idn)
+		return ENOMEM;
+	*idn++ += num;
+	*idp = idn;
+	return 0;
+}
+
+int mdb_midl_need( MDB_IDL *idp, unsigned num )
+{
+	MDB_IDL ids = *idp;
+	num += ids[0];
+	if (num > ids[-1]) {
+		num = (num + num/4 + (256 + 2)) & -256;
+		if (!(ids = realloc(ids-1, num * sizeof(MDB_ID))))
+			return ENOMEM;
+		*ids++ = num - 2;
+		*idp = ids;
 	}
 	return 0;
 }
@@ -146,14 +158,9 @@ int mdb_midl_append( MDB_IDL *idp, MDB_ID id )
 	MDB_IDL ids = *idp;
 	/* Too big? */
 	if (ids[0] >= ids[-1]) {
-		MDB_IDL idn = ids-1;
-		/* grow it */
-		idn = realloc(idn, (*idn + MDB_IDL_UM_MAX + 1) * sizeof(MDB_ID));
-		if (!idn)
-			return -1;
-		*idn++ += MDB_IDL_UM_MAX;
-		ids = idn;
-		*idp = ids;
+		if (mdb_midl_grow(idp, MDB_IDL_UM_MAX))
+			return ENOMEM;
+		ids = *idp;
 	}
 	ids[0]++;
 	ids[ids[0]] = id;
@@ -165,24 +172,49 @@ int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app )
 	MDB_IDL ids = *idp;
 	/* Too big? */
 	if (ids[0] + app[0] >= ids[-1]) {
-		MDB_IDL idn = ids-1;
-		/* grow it */
-		idn = realloc(idn, (*idn + app[-1]) * sizeof(MDB_ID));
-		if (!idn)
-			return -1;
-		*idn++ += app[-1];
-		ids = idn;
-		*idp = ids;
+		if (mdb_midl_grow(idp, app[0]))
+			return ENOMEM;
+		ids = *idp;
 	}
 	memcpy(&ids[ids[0]+1], &app[1], app[0] * sizeof(MDB_ID));
 	ids[0] += app[0];
 	return 0;
 }
 
+int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n )
+{
+	MDB_ID *ids = *idp, len = ids[0];
+	/* Too big? */
+	if (len + n > ids[-1]) {
+		if (mdb_midl_grow(idp, n | MDB_IDL_UM_MAX))
+			return ENOMEM;
+		ids = *idp;
+	}
+	ids[0] = len + n;
+	ids += len;
+	while (n)
+		ids[n--] = id++;
+	return 0;
+}
+
+void mdb_midl_xmerge( MDB_IDL idl, MDB_IDL merge )
+{
+	MDB_ID old_id, merge_id, i = merge[0], j = idl[0], k = i+j, total = k;
+	idl[0] = (MDB_ID)-1;		/* delimiter for idl scan below */
+	old_id = idl[j];
+	while (i) {
+		merge_id = merge[i--];
+		for (; old_id < merge_id; old_id = idl[--j])
+			idl[k--] = old_id;
+		idl[k--] = merge_id;
+	}
+	idl[0] = total;
+}
+
 /* Quicksort + Insertion sort for small arrays */
 
 #define SMALL	8
-#define	SWAP(a,b)	{ itmp=(a); (a)=(b); (b)=itmp; }
+#define	MIDL_SWAP(a,b)	{ itmp=(a); (a)=(b); (b)=itmp; }
 
 void
 mdb_midl_sort( MDB_IDL ids )
@@ -192,7 +224,7 @@ mdb_midl_sort( MDB_IDL ids )
 	int i,j,k,l,ir,jstack;
 	MDB_ID a, itmp;
 
-	ir = ids[0];
+	ir = (int)ids[0];
 	l = 1;
 	jstack = 0;
 	for(;;) {
@@ -210,15 +242,15 @@ mdb_midl_sort( MDB_IDL ids )
 			l = istack[jstack--];
 		} else {
 			k = (l + ir) >> 1;	/* Choose median of left, center, right */
-			SWAP(ids[k], ids[l+1]);
+			MIDL_SWAP(ids[k], ids[l+1]);
 			if (ids[l] < ids[ir]) {
-				SWAP(ids[l], ids[ir]);
+				MIDL_SWAP(ids[l], ids[ir]);
 			}
 			if (ids[l+1] < ids[ir]) {
-				SWAP(ids[l+1], ids[ir]);
+				MIDL_SWAP(ids[l+1], ids[ir]);
 			}
 			if (ids[l] < ids[l+1]) {
-				SWAP(ids[l], ids[l+1]);
+				MIDL_SWAP(ids[l], ids[l+1]);
 			}
 			i = l+1;
 			j = ir;
@@ -227,7 +259,7 @@ mdb_midl_sort( MDB_IDL ids )
 				do i++; while(ids[i] > a);
 				do j--; while(ids[j] < a);
 				if (j < i) break;
-				SWAP(ids[i],ids[j]);
+				MIDL_SWAP(ids[i],ids[j]);
 			}
 			ids[l+1] = ids[j];
 			ids[j] = a;
@@ -255,7 +287,7 @@ unsigned mdb_mid2l_search( MDB_ID2L ids, MDB_ID id )
 	unsigned base = 0;
 	unsigned cursor = 1;
 	int val = 0;
-	unsigned n = ids[0].mid;
+	unsigned n = (unsigned)ids[0].mid;
 
 	while( 0 < n ) {
 		unsigned pivot = n >> 1;
@@ -285,7 +317,6 @@ int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id )
 	unsigned x, i;
 
 	x = mdb_mid2l_search( ids, id->mid );
-	assert( x > 0 );
 
 	if( x < 1 ) {
 		/* internal error */
@@ -304,7 +335,7 @@ int mdb_mid2l_insert( MDB_ID2L ids, MDB_ID2 *id )
 	} else {
 		/* insert id */
 		ids[0].mid++;
-		for (i=ids[0].mid; i>x; i--)
+		for (i=(unsigned)ids[0].mid; i>x; i--)
 			ids[i] = ids[i-1];
 		ids[x] = *id;
 	}