Happy New Year

[openldap] / libraries / liblmdb / midl.c

diff --git a/libraries/liblmdb/midl.c b/libraries/liblmdb/midl.c
index 4ef3b99995496f7053fda4c6171b8446965ae12e..9748d8dba84d1745af38fbeea8ac05415b0cd53f 100644 (file)
--- 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-2013 The OpenLDAP Foundation.
+ * Copyright 2000-2016 The OpenLDAP Foundation.
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -20,10 +20,9 @@
 #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
@@ -117,17 +116,15 @@ 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))))
+               (ids = realloc(ids, (MDB_IDL_UM_MAX+2) * sizeof(MDB_ID))))
        {
                *ids++ = MDB_IDL_UM_MAX;
                *idp = ids;
-               return 1;
        }
-       return 0;
 }
 
 static int mdb_midl_grow( MDB_IDL *idp, int num )
@@ -200,6 +197,20 @@ int mdb_midl_append_range( MDB_IDL *idp, MDB_ID id, unsigned n )
        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
@@ -306,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 */
@@ -344,5 +354,67 @@ int mdb_mid2l_append( MDB_ID2L ids, MDB_ID2 *id )
        return 0;
 }
 
+#ifdef MDB_VL32
+unsigned mdb_mid3l_search( MDB_ID3L ids, MDB_ID id )
+{
+       /*
+        * binary search of id in ids
+        * if found, returns position of id
+        * if not found, returns first position greater than id
+        */
+       unsigned base = 0;
+       unsigned cursor = 1;
+       int val = 0;
+       unsigned n = (unsigned)ids[0].mid;
+
+       while( 0 < n ) {
+               unsigned pivot = n >> 1;
+               cursor = base + pivot + 1;
+               val = CMP( id, ids[cursor].mid );
+
+               if( val < 0 ) {
+                       n = pivot;
+
+               } else if ( val > 0 ) {
+                       base = cursor;
+                       n -= pivot + 1;
+
+               } else {
+                       return cursor;
+               }
+       }
+
+       if( val > 0 ) {
+               ++cursor;
+       }
+       return cursor;
+}
+
+int mdb_mid3l_insert( MDB_ID3L ids, MDB_ID3 *id )
+{
+       unsigned x, i;
+
+       x = mdb_mid3l_search( ids, id->mid );
+
+       if( x < 1 ) {
+               /* internal error */
+               return -2;
+       }
+
+       if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
+               /* duplicate */
+               return -1;
+       }
+
+       /* insert id */
+       ids[0].mid++;
+       for (i=(unsigned)ids[0].mid; i>x; i--)
+               ids[i] = ids[i-1];
+       ids[x] = *id;
+
+       return 0;
+}
+#endif /* MDB_VL32 */
+
 /** @} */
 /** @} */