libmdb/.gitignore += test[45], Doxygen output

[openldap] / libraries / libmdb / midl.c

diff --git a/libraries/libmdb/midl.c b/libraries/libmdb/midl.c
index 8b39acad6509f78e9576101ef3a698ce9befb522..7932d3caeea3dfe779f757d6707243e1a9eb0cbd 100644 (file)
--- a/libraries/libmdb/midl.c
+++ b/libraries/libmdb/midl.c
@@ -1,4 +1,5 @@
-/* idl.c - ldap bdb back-end ID list functions */
+/**    @file midl.c
+ *     @brief ldap bdb back-end ID List functions */
 /* $OpenLDAP$ */
 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
  *
@@ -19,12 +20,16 @@
 #include <assert.h>
 #include "midl.h"
 
-typedef unsigned long pgno_t;
-
-/* Sort the IDLs from highest to lowest */
-#define IDL_CMP(x,y)    ( x > y ? -1 : ( x < y ? 1 : 0 ) )
+/** @defgroup internal MDB Internals
+ *     @{
+ */
+/** @defgroup idls     ID List Management
+ *     @{
+ */
+#define CMP(x,y)        ( (x) < (y) ? -1 : (x) > (y) )
 
-unsigned mdb_midl_search( ID *ids, ID id )
+#if 0  /* superseded by append/sort */
+static unsigned mdb_midl_search( IDL ids, ID id )
 {
        /*
         * binary search of id in ids
@@ -39,7 +44,7 @@ unsigned mdb_midl_search( ID *ids, ID id )
        while( 0 < n ) {
                int pivot = n >> 1;
                cursor = base + pivot;
-               val = IDL_CMP( id, ids[cursor + 1] );
+               val = CMP( ids[cursor + 1], id );
 
                if( val < 0 ) {
                        n = pivot;
@@ -60,9 +65,9 @@ unsigned mdb_midl_search( ID *ids, ID id )
        }
 }
 
-int mdb_midl_insert( ID *ids, ID id )
+int mdb_midl_insert( IDL ids, ID id )
 {
-       unsigned x;
+       unsigned x, i;
 
        if (MDB_IDL_IS_RANGE( ids )) {
                /* if already in range, treat as a dup */
@@ -85,6 +90,7 @@ int mdb_midl_insert( ID *ids, ID id )
 
        if ( x <= ids[0] && ids[x] == id ) {
                /* duplicate */
+               assert(0);
                return -1;
        }
 
@@ -101,9 +107,156 @@ int mdb_midl_insert( ID *ids, ID id )
        
        } else {
                /* insert id */
-               AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
+               for (i=ids[0]; i>x; i--)
+                       ids[i] = ids[i-1];
                ids[x] = id;
        }
 
        return 0;
 }
+#endif
+
+int mdb_midl_append( IDL ids, ID id )
+{
+       /* Too big? */
+       if (ids[0] >= MDB_IDL_UM_MAX)
+               return -1;
+       ids[0]++;
+       ids[ids[0]] = id;
+       return 0;
+}
+
+/* Quicksort + Insertion sort for small arrays */
+
+#define SMALL  8
+#define        SWAP(a,b)       itmp=(a);(a)=(b);(b)=itmp
+
+void
+mdb_midl_sort( ID *ids )
+{
+       int istack[16*sizeof(int)];
+       int i,j,k,l,ir,jstack;
+       ID a, itmp;
+
+       ir = ids[0];
+       l = 1;
+       jstack = 0;
+       for(;;) {
+               if (ir - l < SMALL) {   /* Insertion sort */
+                       for (j=l+1;j<=ir;j++) {
+                               a = ids[j];
+                               for (i=j-1;i>=1;i--) {
+                                       if (ids[i] >= a) break;
+                                       ids[i+1] = ids[i];
+                               }
+                               ids[i+1] = a;
+                       }
+                       if (jstack == 0) break;
+                       ir = istack[jstack--];
+                       l = istack[jstack--];
+               } else {
+                       k = (l + ir) >> 1;      /* Choose median of left, center, right */
+                       SWAP(ids[k], ids[l+1]);
+                       if (ids[l] < ids[ir]) {
+                               SWAP(ids[l], ids[ir]);
+                       }
+                       if (ids[l+1] < ids[ir]) {
+                               SWAP(ids[l+1], ids[ir]);
+                       }
+                       if (ids[l] < ids[l+1]) {
+                               SWAP(ids[l], ids[l+1]);
+                       }
+                       i = l+1;
+                       j = ir;
+                       a = ids[l+1];
+                       for(;;) {
+                               do i++; while(ids[i] > a);
+                               do j--; while(ids[j] < a);
+                               if (j < i) break;
+                               SWAP(ids[i],ids[j]);
+                       }
+                       ids[l+1] = ids[j];
+                       ids[j] = a;
+                       jstack += 2;
+                       if (ir-i+1 >= j-1) {
+                               istack[jstack] = ir;
+                               istack[jstack-1] = i;
+                               ir = j-1;
+                       } else {
+                               istack[jstack] = j-1;
+                               istack[jstack-1] = l;
+                               l = i;
+                       }
+               }
+       }
+}
+
+unsigned mdb_mid2l_search( ID2L ids, 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 = 0;
+       int val = 0;
+       unsigned n = ids[0].mid;
+
+       while( 0 < n ) {
+               int pivot = n >> 1;
+               cursor = base + pivot;
+               val = CMP( id, ids[cursor + 1].mid );
+
+               if( val < 0 ) {
+                       n = pivot;
+
+               } else if ( val > 0 ) {
+                       base = cursor + 1;
+                       n -= pivot + 1;
+
+               } else {
+                       return cursor + 1;
+               }
+       }
+
+       if( val > 0 ) {
+               return cursor + 2;
+       } else {
+               return cursor + 1;
+       }
+}
+
+int mdb_mid2l_insert( ID2L ids, ID2 *id )
+{
+       unsigned x, i;
+
+       x = mdb_mid2l_search( ids, id->mid );
+       assert( x > 0 );
+
+       if( x < 1 ) {
+               /* internal error */
+               return -2;
+       }
+
+       if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
+               /* duplicate */
+               return -1;
+       }
+
+       if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
+               /* too big */
+               return -2;
+
+       } else {
+               /* insert id */
+               ids[0].mid++;
+               for (i=ids[0].mid; i>x; i--)
+                       ids[i] = ids[i-1];
+               ids[x] = *id;
+       }
+
+       return 0;
+}
+/** @} */
+/** @} */