1 /* idl.c - ldap bdb back-end ID list functions */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 2000-2011 The OpenLDAP Foundation.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted only as authorized by the OpenLDAP
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>.
18 #include <sys/types.h>
22 typedef unsigned long pgno_t;
24 /* Sort the IDLs from highest to lowest */
25 #define IDL_CMP(x,y) ( x > y ? -1 : ( x < y ? 1 : 0 ) )
27 unsigned mdb_midl_search( ID *ids, ID id )
30 * binary search of id in ids
31 * if found, returns position of id
32 * if not found, returns first position greater than id
41 cursor = base + pivot;
42 val = IDL_CMP( id, ids[cursor + 1] );
47 } else if ( val > 0 ) {
63 int mdb_midl_insert( ID *ids, ID id )
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))
71 if (id < MDB_IDL_FIRST(ids))
73 else if (id > MDB_IDL_LAST(ids))
78 x = mdb_midl_search( ids, id );
86 if ( x <= ids[0] && ids[x] == id ) {
91 if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
94 ids[2] = ids[ids[0]-1];
95 } else if ( ids[ids[0]-1] < id ) {
98 ids[2] = ids[ids[0]-1];
104 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );