]> git.sur5r.net Git - openldap/blob - libraries/libmdb/midl.c
64eefe82c868d18ba7f0f5958a6a8af7fd4c4526
[openldap] / 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) )
26
27 /* Sort the IDL2s from lowest to highest */
28 #define IDL2_CMP(x,y)    ( (x) < (y) ? -1 : (x) > (y) )
29
30 unsigned mdb_midl_search( ID *ids, ID id )
31 {
32         /*
33          * binary search of id in ids
34          * if found, returns position of id
35          * if not found, returns first position greater than id
36          */
37         unsigned base = 0;
38         unsigned cursor = 0;
39         int val = 0;
40         unsigned n = ids[0];
41
42         while( 0 < n ) {
43                 int pivot = n >> 1;
44                 cursor = base + pivot;
45                 val = IDL_CMP( id, ids[cursor + 1] );
46
47                 if( val < 0 ) {
48                         n = pivot;
49
50                 } else if ( val > 0 ) {
51                         base = cursor + 1;
52                         n -= pivot + 1;
53
54                 } else {
55                         return cursor + 1;
56                 }
57         }
58         
59         if( val > 0 ) {
60                 return cursor + 2;
61         } else {
62                 return cursor + 1;
63         }
64 }
65
66 int mdb_midl_insert( ID *ids, ID id )
67 {
68         unsigned x, i;
69
70         if (MDB_IDL_IS_RANGE( ids )) {
71                 /* if already in range, treat as a dup */
72                 if (id >= MDB_IDL_FIRST(ids) && id <= MDB_IDL_LAST(ids))
73                         return -1;
74                 if (id < MDB_IDL_FIRST(ids))
75                         ids[1] = id;
76                 else if (id > MDB_IDL_LAST(ids))
77                         ids[2] = id;
78                 return 0;
79         }
80
81         x = mdb_midl_search( ids, id );
82         assert( x > 0 );
83
84         if( x < 1 ) {
85                 /* internal error */
86                 return -2;
87         }
88
89         if ( x <= ids[0] && ids[x] == id ) {
90                 /* duplicate */
91                 return -1;
92         }
93
94         if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
95                 if( id < ids[1] ) {
96                         ids[1] = id;
97                         ids[2] = ids[ids[0]-1];
98                 } else if ( ids[ids[0]-1] < id ) {
99                         ids[2] = id;
100                 } else {
101                         ids[2] = ids[ids[0]-1];
102                 }
103                 ids[0] = NOID;
104         
105         } else {
106                 /* insert id */
107                 for (i=ids[0]; i>x; i--)
108                         ids[i] = ids[i-1];
109                 ids[x] = id;
110         }
111
112         return 0;
113 }
114
115 unsigned mdb_midl2_search( MIDL2 *ids, MIDL2 *id )
116 {
117         /*
118          * binary search of id in ids
119          * if found, returns position of id
120          * if not found, returns first position greater than id
121          */
122         unsigned base = 0;
123         unsigned cursor = 0;
124         int val = 0;
125         unsigned n = ids[0].mid;
126
127         while( 0 < n ) {
128                 int pivot = n >> 1;
129                 cursor = base + pivot;
130                 val = IDL2_CMP( id->mid, ids[cursor + 1].mid );
131
132                 if( val < 0 ) {
133                         n = pivot;
134
135                 } else if ( val > 0 ) {
136                         base = cursor + 1;
137                         n -= pivot + 1;
138
139                 } else {
140                         return cursor + 1;
141                 }
142         }
143
144         if( val > 0 ) {
145                 return cursor + 2;
146         } else {
147                 return cursor + 1;
148         }
149 }
150
151 int mdb_midl2_insert( MIDL2 *ids, MIDL2 *id )
152 {
153         unsigned x, i;
154
155         x = mdb_midl2_search( ids, id );
156         assert( x > 0 );
157
158         if( x < 1 ) {
159                 /* internal error */
160                 return -2;
161         }
162
163         if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
164                 /* duplicate */
165                 return -1;
166         }
167
168         if ( ids[0].mid >= MDB_IDL_DB_MAX ) {
169                 /* too big */
170                 return -2;
171
172         } else {
173                 /* insert id */
174                 ids[0].mid++;
175                 for (i=ids[0].mid; i>x; i--)
176                         ids[i] = ids[i-1];
177                 ids[x] = *id;
178         }
179
180         return 0;
181 }