git.sur5r.net Git - openldap/blob - libraries/libmdb/idl.c

   1 /* Lifted from OpenLDAP back-bdb/idl.c */
   2
   3 #include <strings.h>
   4 #include <sys/types.h>
   5 #include <assert.h>
   6 #include "idl.h"
   7
   8 typedef unsigned long pgno_t;
   9
  10 /* Sort the IDLs from highest to lowest */
  11 #define IDL_CMP(x,y)     ( x > y ? -1 : ( x < y ? 1 : 0 ) )
  12
  13 unsigned mdb_idl_search( ID *ids, ID id )
  14 {
  15         /*
  16          * binary search of id in ids
  17          * if found, returns position of id
  18          * if not found, returns first position greater than id
  19          */
  20         unsigned base = 0;
  21         unsigned cursor = 0;
  22         int val = 0;
  23         unsigned n = ids[0];
  24
  25         while( 0 < n ) {
  26                 int pivot = n >> 1;
  27                 cursor = base + pivot;
  28                 val = IDL_CMP( id, ids[cursor + 1] );
  29
  30                 if( val < 0 ) {
  31                         n = pivot;
  32
  33                 } else if ( val > 0 ) {
  34                         base = cursor + 1;
  35                         n -= pivot + 1;
  36
  37                 } else {
  38                         return cursor + 1;
  39                 }
  40         }
  41
  42         if( val > 0 ) {
  43                 return cursor + 2;
  44         } else {
  45                 return cursor + 1;
  46         }
  47 }
  48
  49 int mdb_idl_insert( ID *ids, ID id )
  50 {
  51         unsigned x;
  52
  53         if (MDB_IDL_IS_RANGE( ids )) {
  54                 /* if already in range, treat as a dup */
  55                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
  56                         return -1;
  57                 if (id < MDB_IDL_FIRST(ids))
  58                         ids[1] = id;
  59                 else if (id > MDB_IDL_LAST(ids))
  60                         ids[2] = id;
  61                 return 0;
  62         }
  63
  64         x = mdb_idl_search( ids, id );
  65         assert( x > 0 );
  66
  67         if( x < 1 ) {
  68                 /* internal error */
  69                 return -2;
  70         }
  71
  72         if ( x <= ids[0] && ids[x] == id ) {
  73                 /* duplicate */
  74                 return -1;
  75         }
  76
  77         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
  78                 if( id < ids[1] ) {
  79                         ids[1] = id;
  80                         ids[2] = ids[ids[0]-1];
  81                 } else if ( ids[ids[0]-1] < id ) {
  82                         ids[2] = id;
  83                 } else {
  84                         ids[2] = ids[ids[0]-1];
  85                 }
  86                 ids[0] = NOID;
  87
  88         } else {
  89                 /* insert id */
  90                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
  91                 ids[x] = id;
  92         }
  93
  94         return 0;
  95 }