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

   1 /* idl.c - ldap bdb back-end ID list functions */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2000-2011 The OpenLDAP Foundation.
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted only as authorized by the OpenLDAP
  10  * Public License.
  11  *
  12  * A copy of this license is available in the file LICENSE in the
  13  * top-level directory of the distribution or, alternatively, at
  14  * <http://www.OpenLDAP.org/license.html>.
  15  */
  16
  17 #include <string.h>
  18 #include <sys/types.h>
  19 #include <assert.h>
  20 #include "midl.h"
  21
  22 typedef unsigned long pgno_t;
  23
  24 /* Sort the IDLs from highest to lowest */
  25 #define IDL_CMP(x,y)     ( x > y ? -1 : ( x < y ? 1 : 0 ) )
  26
  27 unsigned mdb_midl_search( ID *ids, ID id )
  28 {
  29         /*
  30          * binary search of id in ids
  31          * if found, returns position of id
  32          * if not found, returns first position greater than id
  33          */
  34         unsigned base = 0;
  35         unsigned cursor = 0;
  36         int val = 0;
  37         unsigned n = ids[0];
  38
  39         while( 0 < n ) {
  40                 int pivot = n >> 1;
  41                 cursor = base + pivot;
  42                 val = IDL_CMP( id, ids[cursor + 1] );
  43
  44                 if( val < 0 ) {
  45                         n = pivot;
  46
  47                 } else if ( val > 0 ) {
  48                         base = cursor + 1;
  49                         n -= pivot + 1;
  50
  51                 } else {
  52                         return cursor + 1;
  53                 }
  54         }
  55
  56         if( val > 0 ) {
  57                 return cursor + 2;
  58         } else {
  59                 return cursor + 1;
  60         }
  61 }
  62
  63 int mdb_midl_insert( ID *ids, ID id )
  64 {
  65         unsigned x;
  66
  67         if (MDB_IDL_IS_RANGE( ids )) {
  68                 /* if already in range, treat as a dup */
  69                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
  70                         return -1;
  71                 if (id < MDB_IDL_FIRST(ids))
  72                         ids[1] = id;
  73                 else if (id > MDB_IDL_LAST(ids))
  74                         ids[2] = id;
  75                 return 0;
  76         }
  77
  78         x = mdb_midl_search( ids, id );
  79         assert( x > 0 );
  80
  81         if( x < 1 ) {
  82                 /* internal error */
  83                 return -2;
  84         }
  85
  86         if ( x <= ids[0] && ids[x] == id ) {
  87                 /* duplicate */
  88                 return -1;
  89         }
  90
  91         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
  92                 if( id < ids[1] ) {
  93                         ids[1] = id;
  94                         ids[2] = ids[ids[0]-1];
  95                 } else if ( ids[ids[0]-1] < id ) {
  96                         ids[2] = id;
  97                 } else {
  98                         ids[2] = ids[ids[0]-1];
  99                 }
 100                 ids[0] = NOID;
 101
 102         } else {
 103                 /* insert id */
 104                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 105                 ids[x] = id;
 106         }
 107
 108         return 0;
 109 }