X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=libraries%2Fliblmdb%2Fmidl.c;h=5c6d841a7adcaeb713df9a21f6bdecec014cb564;hb=c322c4c76cc39cb69dd80890a9075a6f2c3fe403;hp=42c809fd4d93faf61fdf8457da615c0d07bbb8dd;hpb=66c839f0292d9aea12bf93ef6568ac2bd2ca0fc8;p=openldap
diff --git a/libraries/liblmdb/midl.c b/libraries/liblmdb/midl.c
index 42c809fd4d..5c6d841a7a 100644
--- a/libraries/liblmdb/midl.c
+++ b/libraries/liblmdb/midl.c
@@ -3,7 +3,7 @@
/* $OpenLDAP$ */
/* This work is part of OpenLDAP Software .
*
- * Copyright 2000-2013 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
#include
#include
+#include
#include
-#include
#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--)
@@ -120,8 +103,10 @@ int mdb_midl_insert( MDB_IDL ids, MDB_ID id )
MDB_IDL mdb_midl_alloc(int num)
{
MDB_IDL ids = malloc((num+2) * sizeof(MDB_ID));
- if (ids)
+ if (ids) {
*ids++ = num;
+ *ids = 0;
+ }
return ids;
}
@@ -131,19 +116,18 @@ void mdb_midl_free(MDB_IDL 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+2) * sizeof(MDB_ID))))
+ {
*ids++ = MDB_IDL_UM_MAX;
*idp = ids;
- return 1;
}
- return 0;
}
-int mdb_midl_grow( MDB_IDL *idp, int num )
+static int mdb_midl_grow( MDB_IDL *idp, int num )
{
MDB_IDL idn = *idp-1;
/* grow it */
@@ -155,6 +139,20 @@ int mdb_midl_grow( MDB_IDL *idp, int num )
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;
+}
+
int mdb_midl_append( MDB_IDL *idp, MDB_ID id )
{
MDB_IDL ids = *idp;
@@ -183,10 +181,40 @@ int mdb_midl_append_list( MDB_IDL *idp, MDB_IDL app )
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 )
@@ -214,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;
@@ -231,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;
@@ -289,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 */