?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Patrick Welche <prlw1@cam.ac.uk>
[netbsd-mini2440.git] / external / bsd / openldap / dist / servers / slapd / back-bdb / idl.c
blobbfe1e6a91479ade280a1d8e43eae4f54b305d3a5
1 /* idl.c - ldap id list handling routines */
2 /* $OpenLDAP: pkg/ldap/servers/slapd/back-bdb/idl.c,v 1.124.2.7 2008/02/11 23:26:45 kurt Exp $ */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
4 *
5 * Copyright 2000-2008 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 "portable.h"
18
19 #include <stdio.h>
20 #include <ac/string.h>
21
22 #include "back-bdb.h"
23 #include "idl.h"
24
25 #define IDL_MAX(x,y) ( x > y ? x : y )
26 #define IDL_MIN(x,y) ( x < y ? x : y )
27
28 #define IDL_CMP(x,y) ( x < y ? -1 : ( x > y ? 1 : 0 ) )
29
30 #define IDL_LRU_DELETE( bdb, e ) do { \
31 if ( (e) == (bdb)->bi_idl_lru_head ) { \
32 if ( (e)->idl_lru_next == (bdb)->bi_idl_lru_head ) { \
33 (bdb)->bi_idl_lru_head = NULL; \
34 } else { \
35 (bdb)->bi_idl_lru_head = (e)->idl_lru_next; \
36 } \
37 } \
38 if ( (e) == (bdb)->bi_idl_lru_tail ) { \
39 if ( (e)->idl_lru_prev == (bdb)->bi_idl_lru_tail ) { \
40 assert( (bdb)->bi_idl_lru_head == NULL ); \
41 (bdb)->bi_idl_lru_tail = NULL; \
42 } else { \
43 (bdb)->bi_idl_lru_tail = (e)->idl_lru_prev; \
44 } \
45 } \
46 (e)->idl_lru_next->idl_lru_prev = (e)->idl_lru_prev; \
47 (e)->idl_lru_prev->idl_lru_next = (e)->idl_lru_next; \
48 } while ( 0 )
49
50 static int
51 bdb_idl_entry_cmp( const void *v_idl1, const void *v_idl2 )
52 {
53 const bdb_idl_cache_entry_t *idl1 = v_idl1, *idl2 = v_idl2;
54 int rc;
55
56 if ((rc = SLAP_PTRCMP( idl1->db, idl2->db ))) return rc;
57 if ((rc = idl1->kstr.bv_len - idl2->kstr.bv_len )) return rc;
58 return ( memcmp ( idl1->kstr.bv_val, idl2->kstr.bv_val , idl1->kstr.bv_len ) );
59 }
60
61 #if IDL_DEBUG > 0
62 static void idl_check( ID *ids )
63 {
64 if( BDB_IDL_IS_RANGE( ids ) ) {
65 assert( BDB_IDL_RANGE_FIRST(ids) <= BDB_IDL_RANGE_LAST(ids) );
66 } else {
67 ID i;
68 for( i=1; i < ids[0]; i++ ) {
69 assert( ids[i+1] > ids[i] );
70 }
71 }
72 }
73
74 #if IDL_DEBUG > 1
75 static void idl_dump( ID *ids )
76 {
77 if( BDB_IDL_IS_RANGE( ids ) ) {
78 Debug( LDAP_DEBUG_ANY,
79 "IDL: range ( %ld - %ld )\n",
80 (long) BDB_IDL_RANGE_FIRST( ids ),
81 (long) BDB_IDL_RANGE_LAST( ids ) );
82
83 } else {
84 ID i;
85 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
86
87 for( i=1; i<=ids[0]; i++ ) {
88 if( i % 16 == 1 ) {
89 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
90 }
91 Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i], 0, 0 );
92 }
93
94 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
95 }
96
97 idl_check( ids );
98 }
99 #endif /* IDL_DEBUG > 1 */
100 #endif /* IDL_DEBUG > 0 */
101
102 unsigned bdb_idl_search( ID *ids, ID id )
103 {
104 #define IDL_BINARY_SEARCH 1
105 #ifdef IDL_BINARY_SEARCH
106 /*
107 * binary search of id in ids
108 * if found, returns position of id
109 * if not found, returns first postion greater than id
110 */
111 unsigned base = 0;
112 unsigned cursor = 0;
113 int val = 0;
114 unsigned n = ids[0];
115
116 #if IDL_DEBUG > 0
117 idl_check( ids );
118 #endif
119
120 while( 0 < n ) {
121 int pivot = n >> 1;
122 cursor = base + pivot;
123 val = IDL_CMP( id, ids[cursor + 1] );
124
125 if( val < 0 ) {
126 n = pivot;
127
128 } else if ( val > 0 ) {
129 base = cursor + 1;
130 n -= pivot + 1;
131
132 } else {
133 return cursor + 1;
134 }
135 }
136
137 if( val > 0 ) {
138 return cursor + 2;
139 } else {
140 return cursor + 1;
141 }
142
143 #else
144 /* (reverse) linear search */
145 int i;
146
147 #if IDL_DEBUG > 0
148 idl_check( ids );
149 #endif
150
151 for( i=ids[0]; i; i-- ) {
152 if( id > ids[i] ) {
153 break;
154 }
155 }
156
157 return i+1;
158 #endif
159 }
160
161 int bdb_idl_insert( ID *ids, ID id )
162 {
163 unsigned x;
164
165 #if IDL_DEBUG > 1
166 Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
167 idl_dump( ids );
168 #elif IDL_DEBUG > 0
169 idl_check( ids );
170 #endif
171
172 if (BDB_IDL_IS_RANGE( ids )) {
173 /* if already in range, treat as a dup */
174 if (id >= BDB_IDL_FIRST(ids) && id <= BDB_IDL_LAST(ids))
175 return -1;
176 if (id < BDB_IDL_FIRST(ids))
177 ids[1] = id;
178 else if (id > BDB_IDL_LAST(ids))
179 ids[2] = id;
180 return 0;
181 }
182
183 x = bdb_idl_search( ids, id );
184 assert( x > 0 );
185
186 if( x < 1 ) {
187 /* internal error */
188 return -2;
189 }
190
191 if ( x <= ids[0] && ids[x] == id ) {
192 /* duplicate */
193 return -1;
194 }
195
196 if ( ++ids[0] >= BDB_IDL_DB_MAX ) {
197 if( id < ids[1] ) {
198 ids[1] = id;
199 ids[2] = ids[ids[0]-1];
200 } else if ( ids[ids[0]-1] < id ) {
201 ids[2] = id;
202 } else {
203 ids[2] = ids[ids[0]-1];
204 }
205 ids[0] = NOID;
206
207 } else {
208 /* insert id */
209 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
210 ids[x] = id;
211 }
212
213 #if IDL_DEBUG > 1
214 idl_dump( ids );
215 #elif IDL_DEBUG > 0
216 idl_check( ids );
217 #endif
218
219 return 0;
220 }
221
222 static int bdb_idl_delete( ID *ids, ID id )
223 {
224 unsigned x;
225
226 #if IDL_DEBUG > 1
227 Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
228 idl_dump( ids );
229 #elif IDL_DEBUG > 0
230 idl_check( ids );
231 #endif
232
233 if (BDB_IDL_IS_RANGE( ids )) {
234 /* If deleting a range boundary, adjust */
235 if ( ids[1] == id )
236 ids[1]++;
237 else if ( ids[2] == id )
238 ids[2]--;
239 /* deleting from inside a range is a no-op */
240
241 /* If the range has collapsed, re-adjust */
242 if ( ids[1] > ids[2] )
243 ids[0] = 0;
244 else if ( ids[1] == ids[2] )
245 ids[1] = 1;
246 return 0;
247 }
248
249 x = bdb_idl_search( ids, id );
250 assert( x > 0 );
251
252 if( x <= 0 ) {
253 /* internal error */
254 return -2;
255 }
256
257 if( x > ids[0] || ids[x] != id ) {
258 /* not found */
259 return -1;
260
261 } else if ( --ids[0] == 0 ) {
262 if( x != 1 ) {
263 return -3;
264 }
265
266 } else {
267 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
268 }
269
270 #if IDL_DEBUG > 1
271 idl_dump( ids );
272 #elif IDL_DEBUG > 0
273 idl_check( ids );
274 #endif
275
276 return 0;
277 }
278
279 static char *
280 bdb_show_key(
281 DBT *key,
282 char *buf )
283 {
284 if ( key->size == 4 /* LUTIL_HASH_BYTES */ ) {
285 unsigned char *c = key->data;
286 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
287 return buf;
288 } else {
289 return key->data;
290 }
291 }
292
293 /* Find a db/key pair in the IDL cache. If ids is non-NULL,
294 * copy the cached IDL into it, otherwise just return the status.
295 */
296 int
297 bdb_idl_cache_get(
298 struct bdb_info *bdb,
299 DB *db,
300 DBT *key,
301 ID *ids )
302 {
303 bdb_idl_cache_entry_t idl_tmp;
304 bdb_idl_cache_entry_t *matched_idl_entry;
305 int rc = LDAP_NO_SUCH_OBJECT;
306
307 DBT2bv( key, &idl_tmp.kstr );
308 idl_tmp.db = db;
309 ldap_pvt_thread_rdwr_rlock( &bdb->bi_idl_tree_rwlock );
310 matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
311 bdb_idl_entry_cmp );
312 if ( matched_idl_entry != NULL ) {
313 if ( matched_idl_entry->idl && ids )
314 BDB_IDL_CPY( ids, matched_idl_entry->idl );
315 matched_idl_entry->idl_flags |= CACHE_ENTRY_REFERENCED;
316 if ( matched_idl_entry->idl )
317 rc = LDAP_SUCCESS;
318 else
319 rc = DB_NOTFOUND;
320 }
321 ldap_pvt_thread_rdwr_runlock( &bdb->bi_idl_tree_rwlock );
322
323 return rc;
324 }
325
326 void
327 bdb_idl_cache_put(
328 struct bdb_info *bdb,
329 DB *db,
330 DBT *key,
331 ID *ids,
332 int rc )
333 {
334 bdb_idl_cache_entry_t idl_tmp;
335 bdb_idl_cache_entry_t *ee, *eprev;
336
337 if ( rc == DB_NOTFOUND || BDB_IDL_IS_ZERO( ids ))
338 return;
339
340 DBT2bv( key, &idl_tmp.kstr );
341
342 ee = (bdb_idl_cache_entry_t *) ch_malloc(
343 sizeof( bdb_idl_cache_entry_t ) );
344 ee->db = db;
345 ee->idl = (ID*) ch_malloc( BDB_IDL_SIZEOF ( ids ) );
346 BDB_IDL_CPY( ee->idl, ids );
347
348 ee->idl_lru_prev = NULL;
349 ee->idl_lru_next = NULL;
350 ee->idl_flags = 0;
351 ber_dupbv( &ee->kstr, &idl_tmp.kstr );
352 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
353 if ( avl_insert( &bdb->bi_idl_tree, (caddr_t) ee,
354 bdb_idl_entry_cmp, avl_dup_error ))
355 {
356 ch_free( ee->kstr.bv_val );
357 ch_free( ee->idl );
358 ch_free( ee );
359 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
360 return;
361 }
362 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
363 /* LRU_ADD */
364 if ( bdb->bi_idl_lru_head ) {
365 assert( bdb->bi_idl_lru_tail != NULL );
366 assert( bdb->bi_idl_lru_head->idl_lru_prev != NULL );
367 assert( bdb->bi_idl_lru_head->idl_lru_next != NULL );
368
369 ee->idl_lru_next = bdb->bi_idl_lru_head;
370 ee->idl_lru_prev = bdb->bi_idl_lru_head->idl_lru_prev;
371 bdb->bi_idl_lru_head->idl_lru_prev->idl_lru_next = ee;
372 bdb->bi_idl_lru_head->idl_lru_prev = ee;
373 } else {
374 ee->idl_lru_next = ee->idl_lru_prev = ee;
375 bdb->bi_idl_lru_tail = ee;
376 }
377 bdb->bi_idl_lru_head = ee;
378
379 if ( ++bdb->bi_idl_cache_size > bdb->bi_idl_cache_max_size ) {
380 int i;
381 ee = bdb->bi_idl_lru_tail;
382 for ( i = 0; ee != NULL && i < 10; i++, ee = eprev ) {
383 eprev = ee->idl_lru_prev;
384 if ( eprev == ee ) {
385 eprev = NULL;
386 }
387 if ( ee->idl_flags & CACHE_ENTRY_REFERENCED ) {
388 ee->idl_flags ^= CACHE_ENTRY_REFERENCED;
389 continue;
390 }
391 if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) ee,
392 bdb_idl_entry_cmp ) == NULL ) {
393 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_put: "
394 "AVL delete failed\n",
395 0, 0, 0 );
396 }
397 IDL_LRU_DELETE( bdb, ee );
398 i++;
399 --bdb->bi_idl_cache_size;
400 ch_free( ee->kstr.bv_val );
401 ch_free( ee->idl );
402 ch_free( ee );
403 }
404 bdb->bi_idl_lru_tail = eprev;
405 assert( bdb->bi_idl_lru_tail != NULL
406 || bdb->bi_idl_lru_head == NULL );
407 }
408 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
409 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
410 }
411
412 void
413 bdb_idl_cache_del(
414 struct bdb_info *bdb,
415 DB *db,
416 DBT *key )
417 {
418 bdb_idl_cache_entry_t *matched_idl_entry, idl_tmp;
419 DBT2bv( key, &idl_tmp.kstr );
420 idl_tmp.db = db;
421 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
422 matched_idl_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
423 bdb_idl_entry_cmp );
424 if ( matched_idl_entry != NULL ) {
425 if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) matched_idl_entry,
426 bdb_idl_entry_cmp ) == NULL ) {
427 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
428 "AVL delete failed\n",
429 0, 0, 0 );
430 }
431 --bdb->bi_idl_cache_size;
432 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
433 IDL_LRU_DELETE( bdb, matched_idl_entry );
434 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
435 free( matched_idl_entry->kstr.bv_val );
436 if ( matched_idl_entry->idl )
437 free( matched_idl_entry->idl );
438 free( matched_idl_entry );
439 }
440 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
441 }
442
443 void
444 bdb_idl_cache_add_id(
445 struct bdb_info *bdb,
446 DB *db,
447 DBT *key,
448 ID id )
449 {
450 bdb_idl_cache_entry_t *cache_entry, idl_tmp;
451 DBT2bv( key, &idl_tmp.kstr );
452 idl_tmp.db = db;
453 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
454 cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
455 bdb_idl_entry_cmp );
456 if ( cache_entry != NULL ) {
457 if ( !BDB_IDL_IS_RANGE( cache_entry->idl ) &&
458 cache_entry->idl[0] < BDB_IDL_DB_MAX ) {
459 size_t s = BDB_IDL_SIZEOF( cache_entry->idl ) + sizeof(ID);
460 cache_entry->idl = ch_realloc( cache_entry->idl, s );
461 }
462 bdb_idl_insert( cache_entry->idl, id );
463 }
464 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
465 }
466
467 void
468 bdb_idl_cache_del_id(
469 struct bdb_info *bdb,
470 DB *db,
471 DBT *key,
472 ID id )
473 {
474 bdb_idl_cache_entry_t *cache_entry, idl_tmp;
475 DBT2bv( key, &idl_tmp.kstr );
476 idl_tmp.db = db;
477 ldap_pvt_thread_rdwr_wlock( &bdb->bi_idl_tree_rwlock );
478 cache_entry = avl_find( bdb->bi_idl_tree, &idl_tmp,
479 bdb_idl_entry_cmp );
480 if ( cache_entry != NULL ) {
481 bdb_idl_delete( cache_entry->idl, id );
482 if ( cache_entry->idl[0] == 0 ) {
483 if ( avl_delete( &bdb->bi_idl_tree, (caddr_t) cache_entry,
484 bdb_idl_entry_cmp ) == NULL ) {
485 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_cache_del: "
486 "AVL delete failed\n",
487 0, 0, 0 );
488 }
489 --bdb->bi_idl_cache_size;
490 ldap_pvt_thread_mutex_lock( &bdb->bi_idl_tree_lrulock );
491 IDL_LRU_DELETE( bdb, cache_entry );
492 ldap_pvt_thread_mutex_unlock( &bdb->bi_idl_tree_lrulock );
493 free( cache_entry->kstr.bv_val );
494 free( cache_entry->idl );
495 free( cache_entry );
496 }
497 }
498 ldap_pvt_thread_rdwr_wunlock( &bdb->bi_idl_tree_rwlock );
499 }
500
501 int
502 bdb_idl_fetch_key(
503 BackendDB *be,
504 DB *db,
505 BDB_LOCKER locker,
506 DBT *key,
507 ID *ids,
508 DBC **saved_cursor,
509 int get_flag )
510 {
511 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
512 int rc;
513 DBT data, key2, *kptr;
514 DBC *cursor;
515 ID *i;
516 void *ptr;
517 size_t len;
518 int rc2;
519 int flags = bdb->bi_db_opflags | DB_MULTIPLE;
520 int opflag;
521
522 /* If using BerkeleyDB 4.0, the buf must be large enough to
523 * grab the entire IDL in one get(), otherwise BDB will leak
524 * resources on subsequent get's. We can safely call get()
525 * twice - once for the data, and once to get the DB_NOTFOUND
526 * result meaning there's no more data. See ITS#2040 for details.
527 * This bug is fixed in BDB 4.1 so a smaller buffer will work if
528 * stack space is too limited.
529 *
530 * configure now requires Berkeley DB 4.1.
531 */
532 #if DB_VERSION_FULL < 0x04010000
533 # define BDB_ENOUGH 5
534 #else
535 /* We sometimes test with tiny IDLs, and BDB always wants buffers
536 * that are at least one page in size.
537 */
538 # if BDB_IDL_DB_SIZE < 4096
539 # define BDB_ENOUGH 2048
540 # else
541 # define BDB_ENOUGH 1
542 # endif
543 #endif
544 ID buf[BDB_IDL_DB_SIZE*BDB_ENOUGH];
545
546 char keybuf[16];
547
548 Debug( LDAP_DEBUG_ARGS,
549 "bdb_idl_fetch_key: %s\n",
550 bdb_show_key( key, keybuf ), 0, 0 );
551
552 assert( ids != NULL );
553
554 if ( saved_cursor && *saved_cursor ) {
555 opflag = DB_NEXT;
556 } else if ( get_flag == LDAP_FILTER_GE ) {
557 opflag = DB_SET_RANGE;
558 } else if ( get_flag == LDAP_FILTER_LE ) {
559 opflag = DB_FIRST;
560 } else {
561 opflag = DB_SET;
562 }
563
564 /* only non-range lookups can use the IDL cache */
565 if ( bdb->bi_idl_cache_size && opflag == DB_SET ) {
566 rc = bdb_idl_cache_get( bdb, db, key, ids );
567 if ( rc != LDAP_NO_SUCH_OBJECT ) return rc;
568 }
569
570 DBTzero( &data );
571
572 data.data = buf;
573 data.ulen = sizeof(buf);
574 data.flags = DB_DBT_USERMEM;
575
576 /* If we're not reusing an existing cursor, get a new one */
577 if( opflag != DB_NEXT ) {
578 rc = db->cursor( db, NULL, &cursor, bdb->bi_db_opflags );
579 if( rc != 0 ) {
580 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
581 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
582 return rc;
583 }
584 CURSOR_SETLOCKER( cursor, locker );
585 } else {
586 cursor = *saved_cursor;
587 }
588
589 /* If this is a LE lookup, save original key so we can determine
590 * when to stop. If this is a GE lookup, save the key since it
591 * will be overwritten.
592 */
593 if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
594 DBTzero( &key2 );
595 key2.flags = DB_DBT_USERMEM;
596 key2.ulen = sizeof(keybuf);
597 key2.data = keybuf;
598 key2.size = key->size;
599 AC_MEMCPY( keybuf, key->data, key->size );
600 kptr = &key2;
601 } else {
602 kptr = key;
603 }
604 len = key->size;
605 rc = cursor->c_get( cursor, kptr, &data, flags | opflag );
606
607 /* skip presence key on range inequality lookups */
608 while (rc == 0 && kptr->size != len) {
609 rc = cursor->c_get( cursor, kptr, &data, flags | DB_NEXT_NODUP );
610 }
611 /* If we're doing a LE compare and the new key is greater than
612 * our search key, we're done
613 */
614 if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->data,
615 key->data, key->size ) > 0 ) {
616 rc = DB_NOTFOUND;
617 }
618 if (rc == 0) {
619 i = ids;
620 while (rc == 0) {
621 u_int8_t *j;
622
623 DB_MULTIPLE_INIT( ptr, &data );
624 while (ptr) {
625 DB_MULTIPLE_NEXT(ptr, &data, j, len);
626 if (j) {
627 ++i;
628 BDB_DISK2ID( j, i );
629 }
630 }
631 rc = cursor->c_get( cursor, key, &data, flags | DB_NEXT_DUP );
632 }
633 if ( rc == DB_NOTFOUND ) rc = 0;
634 ids[0] = i - ids;
635 /* On disk, a range is denoted by 0 in the first element */
636 if (ids[1] == 0) {
637 if (ids[0] != BDB_IDL_RANGE_SIZE) {
638 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
639 "range size mismatch: expected %d, got %ld\n",
640 BDB_IDL_RANGE_SIZE, ids[0], 0 );
641 cursor->c_close( cursor );
642 return -1;
643 }
644 BDB_IDL_RANGE( ids, ids[2], ids[3] );
645 }
646 data.size = BDB_IDL_SIZEOF(ids);
647 }
648
649 if ( saved_cursor && rc == 0 ) {
650 if ( !*saved_cursor )
651 *saved_cursor = cursor;
652 rc2 = 0;
653 }
654 else
655 rc2 = cursor->c_close( cursor );
656 if (rc2) {
657 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
658 "close failed: %s (%d)\n", db_strerror(rc2), rc2, 0 );
659 return rc2;
660 }
661
662 if( rc == DB_NOTFOUND ) {
663 return rc;
664
665 } else if( rc != 0 ) {
666 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
667 "get failed: %s (%d)\n",
668 db_strerror(rc), rc, 0 );
669 return rc;
670
671 } else if ( data.size == 0 || data.size % sizeof( ID ) ) {
672 /* size not multiple of ID size */
673 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
674 "odd size: expected %ld multiple, got %ld\n",
675 (long) sizeof( ID ), (long) data.size, 0 );
676 return -1;
677
678 } else if ( data.size != BDB_IDL_SIZEOF(ids) ) {
679 /* size mismatch */
680 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_fetch_key: "
681 "get size mismatch: expected %ld, got %ld\n",
682 (long) ((1 + ids[0]) * sizeof( ID )), (long) data.size, 0 );
683 return -1;
684 }
685
686 if ( bdb->bi_idl_cache_max_size ) {
687 bdb_idl_cache_put( bdb, db, key, ids, rc );
688 }
689
690 return rc;
691 }
692
693
694 int
695 bdb_idl_insert_key(
696 BackendDB *be,
697 DB *db,
698 DB_TXN *tid,
699 DBT *key,
700 ID id )
701 {
702 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
703 int rc;
704 DBT data;
705 DBC *cursor;
706 ID lo, hi, nlo, nhi, nid;
707 char *err;
708
709 {
710 char buf[16];
711 Debug( LDAP_DEBUG_ARGS,
712 "bdb_idl_insert_key: %lx %s\n",
713 (long) id, bdb_show_key( key, buf ), 0 );
714 }
715
716 assert( id != NOID );
717
718 DBTzero( &data );
719 data.size = sizeof( ID );
720 data.ulen = data.size;
721 data.flags = DB_DBT_USERMEM;
722
723 BDB_ID2DISK( id, &nid );
724
725 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
726 if ( rc != 0 ) {
727 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
728 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
729 return rc;
730 }
731 data.data = &nlo;
732 /* Fetch the first data item for this key, to see if it
733 * exists and if it's a range.
734 */
735 rc = cursor->c_get( cursor, key, &data, DB_SET );
736 err = "c_get";
737 if ( rc == 0 ) {
738 if ( nlo != 0 ) {
739 /* not a range, count the number of items */
740 db_recno_t count;
741 rc = cursor->c_count( cursor, &count, 0 );
742 if ( rc != 0 ) {
743 err = "c_count";
744 goto fail;
745 }
746 if ( count >= BDB_IDL_DB_MAX ) {
747 /* No room, convert to a range */
748 DBT key2 = *key;
749 db_recno_t i;
750
751 key2.dlen = key2.ulen;
752 key2.flags |= DB_DBT_PARTIAL;
753
754 BDB_DISK2ID( &nlo, &lo );
755 data.data = &nhi;
756
757 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_NODUP );
758 if ( rc != 0 && rc != DB_NOTFOUND ) {
759 err = "c_get next_nodup";
760 goto fail;
761 }
762 if ( rc == DB_NOTFOUND ) {
763 rc = cursor->c_get( cursor, key, &data, DB_LAST );
764 if ( rc != 0 ) {
765 err = "c_get last";
766 goto fail;
767 }
768 } else {
769 rc = cursor->c_get( cursor, key, &data, DB_PREV );
770 if ( rc != 0 ) {
771 err = "c_get prev";
772 goto fail;
773 }
774 }
775 BDB_DISK2ID( &nhi, &hi );
776 /* Update hi/lo if needed, then delete all the items
777 * between lo and hi
778 */
779 if ( id < lo ) {
780 lo = id;
781 nlo = nid;
782 } else if ( id > hi ) {
783 hi = id;
784 nhi = nid;
785 }
786 data.data = &nid;
787 /* Don't fetch anything, just position cursor */
788 data.flags = DB_DBT_USERMEM | DB_DBT_PARTIAL;
789 data.dlen = data.ulen = 0;
790 rc = cursor->c_get( cursor, key, &data, DB_SET );
791 if ( rc != 0 ) {
792 err = "c_get 2";
793 goto fail;
794 }
795 rc = cursor->c_del( cursor, 0 );
796 if ( rc != 0 ) {
797 err = "c_del range1";
798 goto fail;
799 }
800 /* Delete all the records */
801 for ( i=1; i<count; i++ ) {
802 rc = cursor->c_get( cursor, &key2, &data, DB_NEXT_DUP );
803 if ( rc != 0 ) {
804 err = "c_get next_dup";
805 goto fail;
806 }
807 rc = cursor->c_del( cursor, 0 );
808 if ( rc != 0 ) {
809 err = "c_del range";
810 goto fail;
811 }
812 }
813 /* Store the range marker */
814 data.size = data.ulen = sizeof(ID);
815 data.flags = DB_DBT_USERMEM;
816 nid = 0;
817 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
818 if ( rc != 0 ) {
819 err = "c_put range";
820 goto fail;
821 }
822 nid = nlo;
823 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
824 if ( rc != 0 ) {
825 err = "c_put lo";
826 goto fail;
827 }
828 nid = nhi;
829 rc = cursor->c_put( cursor, key, &data, DB_KEYLAST );
830 if ( rc != 0 ) {
831 err = "c_put hi";
832 goto fail;
833 }
834 } else {
835 /* There's room, just store it */
836 goto put1;
837 }
838 } else {
839 /* It's a range, see if we need to rewrite
840 * the boundaries
841 */
842 hi = id;
843 data.data = &nlo;
844 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
845 if ( rc != 0 ) {
846 err = "c_get lo";
847 goto fail;
848 }
849 BDB_DISK2ID( &nlo, &lo );
850 if ( id > lo ) {
851 data.data = &nhi;
852 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
853 if ( rc != 0 ) {
854 err = "c_get hi";
855 goto fail;
856 }
857 BDB_DISK2ID( &nhi, &hi );
858 }
859 if ( id < lo || id > hi ) {
860 /* Delete the current lo/hi */
861 rc = cursor->c_del( cursor, 0 );
862 if ( rc != 0 ) {
863 err = "c_del";
864 goto fail;
865 }
866 data.data = &nid;
867 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
868 if ( rc != 0 ) {
869 err = "c_put lo/hi";
870 goto fail;
871 }
872 }
873 }
874 } else if ( rc == DB_NOTFOUND ) {
875 put1: data.data = &nid;
876 rc = cursor->c_put( cursor, key, &data, DB_NODUPDATA );
877 /* Don't worry if it's already there */
878 if ( rc != 0 && rc != DB_KEYEXIST ) {
879 err = "c_put id";
880 goto fail;
881 }
882 } else {
883 /* initial c_get failed, nothing was done */
884 fail:
885 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
886 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
887 cursor->c_close( cursor );
888 return rc;
889 }
890 /* If key was added (didn't already exist) and using IDL cache,
891 * update key in IDL cache.
892 */
893 if ( !rc && bdb->bi_idl_cache_max_size ) {
894 bdb_idl_cache_add_id( bdb, db, key, id );
895 }
896 rc = cursor->c_close( cursor );
897 if( rc != 0 ) {
898 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_insert_key: "
899 "c_close failed: %s (%d)\n",
900 db_strerror(rc), rc, 0 );
901 }
902 return rc;
903 }
904
905 int
906 bdb_idl_delete_key(
907 BackendDB *be,
908 DB *db,
909 DB_TXN *tid,
910 DBT *key,
911 ID id )
912 {
913 struct bdb_info *bdb = (struct bdb_info *) be->be_private;
914 int rc;
915 DBT data;
916 DBC *cursor;
917 ID lo, hi, tmp, nid, nlo, nhi;
918 char *err;
919
920 {
921 char buf[16];
922 Debug( LDAP_DEBUG_ARGS,
923 "bdb_idl_delete_key: %lx %s\n",
924 (long) id, bdb_show_key( key, buf ), 0 );
925 }
926 assert( id != NOID );
927
928 if ( bdb->bi_idl_cache_size ) {
929 bdb_idl_cache_del( bdb, db, key );
930 }
931
932 BDB_ID2DISK( id, &nid );
933
934 DBTzero( &data );
935 data.data = &tmp;
936 data.size = sizeof( id );
937 data.ulen = data.size;
938 data.flags = DB_DBT_USERMEM;
939
940 rc = db->cursor( db, tid, &cursor, bdb->bi_db_opflags );
941 if ( rc != 0 ) {
942 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
943 "cursor failed: %s (%d)\n", db_strerror(rc), rc, 0 );
944 return rc;
945 }
946 /* Fetch the first data item for this key, to see if it
947 * exists and if it's a range.
948 */
949 rc = cursor->c_get( cursor, key, &data, DB_SET );
950 err = "c_get";
951 if ( rc == 0 ) {
952 if ( tmp != 0 ) {
953 /* Not a range, just delete it */
954 if (tmp != nid) {
955 /* position to correct item */
956 tmp = nid;
957 rc = cursor->c_get( cursor, key, &data, DB_GET_BOTH );
958 if ( rc != 0 ) {
959 err = "c_get id";
960 goto fail;
961 }
962 }
963 rc = cursor->c_del( cursor, 0 );
964 if ( rc != 0 ) {
965 err = "c_del id";
966 goto fail;
967 }
968 } else {
969 /* It's a range, see if we need to rewrite
970 * the boundaries
971 */
972 data.data = &nlo;
973 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
974 if ( rc != 0 ) {
975 err = "c_get lo";
976 goto fail;
977 }
978 BDB_DISK2ID( &nlo, &lo );
979 data.data = &nhi;
980 rc = cursor->c_get( cursor, key, &data, DB_NEXT_DUP );
981 if ( rc != 0 ) {
982 err = "c_get hi";
983 goto fail;
984 }
985 BDB_DISK2ID( &nhi, &hi );
986 if ( id == lo || id == hi ) {
987 if ( id == lo ) {
988 id++;
989 lo = id;
990 } else if ( id == hi ) {
991 id--;
992 hi = id;
993 }
994 if ( lo >= hi ) {
995 /* The range has collapsed... */
996 rc = db->del( db, tid, key, 0 );
997 if ( rc != 0 ) {
998 err = "del";
999 goto fail;
1000 }
1001 } else {
1002 if ( id == lo ) {
1003 /* reposition on lo slot */
1004 data.data = &nlo;
1005 cursor->c_get( cursor, key, &data, DB_PREV );
1006 }
1007 rc = cursor->c_del( cursor, 0 );
1008 if ( rc != 0 ) {
1009 err = "c_del";
1010 goto fail;
1011 }
1012 }
1013 if ( lo <= hi ) {
1014 BDB_ID2DISK( id, &nid );
1015 data.data = &nid;
1016 rc = cursor->c_put( cursor, key, &data, DB_KEYFIRST );
1017 if ( rc != 0 ) {
1018 err = "c_put lo/hi";
1019 goto fail;
1020 }
1021 }
1022 }
1023 }
1024 } else {
1025 /* initial c_get failed, nothing was done */
1026 fail:
1027 if ( rc != DB_NOTFOUND ) {
1028 Debug( LDAP_DEBUG_ANY, "=> bdb_idl_delete_key: "
1029 "%s failed: %s (%d)\n", err, db_strerror(rc), rc );
1030 }
1031 cursor->c_close( cursor );
1032 return rc;
1033 }
1034 rc = cursor->c_close( cursor );
1035 if( rc != 0 ) {
1036 Debug( LDAP_DEBUG_ANY,
1037 "=> bdb_idl_delete_key: c_close failed: %s (%d)\n",
1038 db_strerror(rc), rc, 0 );
1039 }
1040
1041 return rc;
1042 }
1043
1044
1045 /*
1046 * idl_intersection - return a = a intersection b
1047 */
1048 int
1049 bdb_idl_intersection(
1050 ID *a,
1051 ID *b )
1052 {
1053 ID ida, idb;
1054 ID idmax, idmin;
1055 ID cursora = 0, cursorb = 0, cursorc;
1056 int swap = 0;
1057
1058 if ( BDB_IDL_IS_ZERO( a ) || BDB_IDL_IS_ZERO( b ) ) {
1059 a[0] = 0;
1060 return 0;
1061 }
1062
1063 idmin = IDL_MAX( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1064 idmax = IDL_MIN( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1065 if ( idmin > idmax ) {
1066 a[0] = 0;
1067 return 0;
1068 } else if ( idmin == idmax ) {
1069 a[0] = 1;
1070 a[1] = idmin;
1071 return 0;
1072 }
1073
1074 if ( BDB_IDL_IS_RANGE( a ) ) {
1075 if ( BDB_IDL_IS_RANGE(b) ) {
1076 /* If both are ranges, just shrink the boundaries */
1077 a[1] = idmin;
1078 a[2] = idmax;
1079 return 0;
1080 } else {
1081 /* Else swap so that b is the range, a is a list */
1082 ID *tmp = a;
1083 a = b;
1084 b = tmp;
1085 swap = 1;
1086 }
1087 }
1088
1089 /* If a range completely covers the list, the result is
1090 * just the list. If idmin to idmax is contiguous, just
1091 * turn it into a range.
1092 */
1093 if ( BDB_IDL_IS_RANGE( b )
1094 && BDB_IDL_FIRST( b ) <= BDB_IDL_FIRST( a )
1095 && BDB_IDL_LAST( b ) >= BDB_IDL_LAST( a ) ) {
1096 if (idmax - idmin + 1 == a[0])
1097 {
1098 a[0] = NOID;
1099 a[1] = idmin;
1100 a[2] = idmax;
1101 }
1102 goto done;
1103 }
1104
1105 /* Fine, do the intersection one element at a time.
1106 * First advance to idmin in both IDLs.
1107 */
1108 cursora = cursorb = idmin;
1109 ida = bdb_idl_first( a, &cursora );
1110 idb = bdb_idl_first( b, &cursorb );
1111 cursorc = 0;
1112
1113 while( ida <= idmax || idb <= idmax ) {
1114 if( ida == idb ) {
1115 a[++cursorc] = ida;
1116 ida = bdb_idl_next( a, &cursora );
1117 idb = bdb_idl_next( b, &cursorb );
1118 } else if ( ida < idb ) {
1119 ida = bdb_idl_next( a, &cursora );
1120 } else {
1121 idb = bdb_idl_next( b, &cursorb );
1122 }
1123 }
1124 a[0] = cursorc;
1125 done:
1126 if (swap)
1127 BDB_IDL_CPY( b, a );
1128
1129 return 0;
1130 }
1131
1132
1133 /*
1134 * idl_union - return a = a union b
1135 */
1136 int
1137 bdb_idl_union(
1138 ID *a,
1139 ID *b )
1140 {
1141 ID ida, idb;
1142 ID cursora = 0, cursorb = 0, cursorc;
1143
1144 if ( BDB_IDL_IS_ZERO( b ) ) {
1145 return 0;
1146 }
1147
1148 if ( BDB_IDL_IS_ZERO( a ) ) {
1149 BDB_IDL_CPY( a, b );
1150 return 0;
1151 }
1152
1153 if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ) {
1154 over: ida = IDL_MIN( BDB_IDL_FIRST(a), BDB_IDL_FIRST(b) );
1155 idb = IDL_MAX( BDB_IDL_LAST(a), BDB_IDL_LAST(b) );
1156 a[0] = NOID;
1157 a[1] = ida;
1158 a[2] = idb;
1159 return 0;
1160 }
1161
1162 ida = bdb_idl_first( a, &cursora );
1163 idb = bdb_idl_first( b, &cursorb );
1164
1165 cursorc = b[0];
1166
1167 /* The distinct elements of a are cat'd to b */
1168 while( ida != NOID || idb != NOID ) {
1169 if ( ida < idb ) {
1170 if( ++cursorc > BDB_IDL_UM_MAX ) {
1171 goto over;
1172 }
1173 b[cursorc] = ida;
1174 ida = bdb_idl_next( a, &cursora );
1175
1176 } else {
1177 if ( ida == idb )
1178 ida = bdb_idl_next( a, &cursora );
1179 idb = bdb_idl_next( b, &cursorb );
1180 }
1181 }
1182
1183 /* b is copied back to a in sorted order */
1184 a[0] = cursorc;
1185 cursora = 1;
1186 cursorb = 1;
1187 cursorc = b[0]+1;
1188 while (cursorb <= b[0] || cursorc <= a[0]) {
1189 if (cursorc > a[0])
1190 idb = NOID;
1191 else
1192 idb = b[cursorc];
1193 if (cursorb <= b[0] && b[cursorb] < idb)
1194 a[cursora++] = b[cursorb++];
1195 else {
1196 a[cursora++] = idb;
1197 cursorc++;
1198 }
1199 }
1200
1201 return 0;
1202 }
1203
1204
1205 #if 0
1206 /*
1207 * bdb_idl_notin - return a intersection ~b (or a minus b)
1208 */
1209 int
1210 bdb_idl_notin(
1211 ID *a,
1212 ID *b,
1213 ID *ids )
1214 {
1215 ID ida, idb;
1216 ID cursora = 0, cursorb = 0;
1217
1218 if( BDB_IDL_IS_ZERO( a ) ||
1219 BDB_IDL_IS_ZERO( b ) ||
1220 BDB_IDL_IS_RANGE( b ) )
1221 {
1222 BDB_IDL_CPY( ids, a );
1223 return 0;
1224 }
1225
1226 if( BDB_IDL_IS_RANGE( a ) ) {
1227 BDB_IDL_CPY( ids, a );
1228 return 0;
1229 }
1230
1231 ida = bdb_idl_first( a, &cursora ),
1232 idb = bdb_idl_first( b, &cursorb );
1233
1234 ids[0] = 0;
1235
1236 while( ida != NOID ) {
1237 if ( idb == NOID ) {
1238 /* we could shortcut this */
1239 ids[++ids[0]] = ida;
1240 ida = bdb_idl_next( a, &cursora );
1241
1242 } else if ( ida < idb ) {
1243 ids[++ids[0]] = ida;
1244 ida = bdb_idl_next( a, &cursora );
1245
1246 } else if ( ida > idb ) {
1247 idb = bdb_idl_next( b, &cursorb );
1248
1249 } else {
1250 ida = bdb_idl_next( a, &cursora );
1251 idb = bdb_idl_next( b, &cursorb );
1252 }
1253 }
1254
1255 return 0;
1256 }
1257 #endif
1258
1259 ID bdb_idl_first( ID *ids, ID *cursor )
1260 {
1261 ID pos;
1262
1263 if ( ids[0] == 0 ) {
1264 *cursor = NOID;
1265 return NOID;
1266 }
1267
1268 if ( BDB_IDL_IS_RANGE( ids ) ) {
1269 if( *cursor < ids[1] ) {
1270 *cursor = ids[1];
1271 }
1272 return *cursor;
1273 }
1274
1275 if ( *cursor == 0 )
1276 pos = 1;
1277 else
1278 pos = bdb_idl_search( ids, *cursor );
1279
1280 if( pos > ids[0] ) {
1281 return NOID;
1282 }
1283
1284 *cursor = pos;
1285 return ids[pos];
1286 }
1287
1288 ID bdb_idl_next( ID *ids, ID *cursor )
1289 {
1290 if ( BDB_IDL_IS_RANGE( ids ) ) {
1291 if( ids[2] < ++(*cursor) ) {
1292 return NOID;
1293 }
1294 return *cursor;
1295 }
1296
1297 if ( ++(*cursor) <= ids[0] ) {
1298 return ids[*cursor];
1299 }
1300
1301 return NOID;
1302 }
1303
1304 #ifdef BDB_HIER
1305
1306 /* Add one ID to an unsorted list. We ensure that the first element is the
1307 * minimum and the last element is the maximum, for fast range compaction.
1308 * this means IDLs up to length 3 are always sorted...
1309 */
1310 int bdb_idl_append_one( ID *ids, ID id )
1311 {
1312 if (BDB_IDL_IS_RANGE( ids )) {
1313 /* if already in range, treat as a dup */
1314 if (id >= BDB_IDL_FIRST(ids) && id <= BDB_IDL_LAST(ids))
1315 return -1;
1316 if (id < BDB_IDL_FIRST(ids))
1317 ids[1] = id;
1318 else if (id > BDB_IDL_LAST(ids))
1319 ids[2] = id;
1320 return 0;
1321 }
1322 if ( ids[0] ) {
1323 ID tmp;
1324
1325 if (id < ids[1]) {
1326 tmp = ids[1];
1327 ids[1] = id;
1328 id = tmp;
1329 }
1330 if ( ids[0] > 1 && id < ids[ids[0]] ) {
1331 tmp = ids[ids[0]];
1332 ids[ids[0]] = id;
1333 id = tmp;
1334 }
1335 }
1336 ids[0]++;
1337 if ( ids[0] >= BDB_IDL_UM_MAX ) {
1338 ids[0] = NOID;
1339 ids[2] = id;
1340 } else {
1341 ids[ids[0]] = id;
1342 }
1343 return 0;
1344 }
1345
1346 /* Append sorted list b to sorted list a. The result is unsorted but
1347 * a[1] is the min of the result and a[a[0]] is the max.
1348 */
1349 int bdb_idl_append( ID *a, ID *b )
1350 {
1351 ID ida, idb, tmp, swap = 0;
1352
1353 if ( BDB_IDL_IS_ZERO( b ) ) {
1354 return 0;
1355 }
1356
1357 if ( BDB_IDL_IS_ZERO( a ) ) {
1358 BDB_IDL_CPY( a, b );
1359 return 0;
1360 }
1361
1362 ida = BDB_IDL_LAST( a );
1363 idb = BDB_IDL_LAST( b );
1364 if ( BDB_IDL_IS_RANGE( a ) || BDB_IDL_IS_RANGE(b) ||
1365 a[0] + b[0] >= BDB_IDL_UM_MAX ) {
1366 a[2] = IDL_MAX( ida, idb );
1367 a[1] = IDL_MIN( a[1], b[1] );
1368 a[0] = NOID;
1369 return 0;
1370 }
1371
1372 if ( b[0] > 1 && ida > idb ) {
1373 swap = idb;
1374 a[a[0]] = idb;
1375 b[b[0]] = ida;
1376 }
1377
1378 if ( b[1] < a[1] ) {
1379 tmp = a[1];
1380 a[1] = b[1];
1381 } else {
1382 tmp = b[1];
1383 }
1384 a[0]++;
1385 a[a[0]] = tmp;
1386
1387 if ( b[0] > 1 ) {
1388 int i = b[0] - 1;
1389 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
1390 a[0] += i;
1391 }
1392 if ( swap ) {
1393 b[b[0]] = swap;
1394 }
1395 return 0;
1396 }
1397
1398 #if 1
1399
1400 /* Quicksort + Insertion sort for small arrays */
1401
1402 #define SMALL 8
1403 #define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp
1404
1405 void
1406 bdb_idl_sort( ID *ids, ID *tmp )
1407 {
1408 int *istack = (int *)tmp;
1409 int i,j,k,l,ir,jstack;
1410 ID a, itmp;
1411
1412 if ( BDB_IDL_IS_RANGE( ids ))
1413 return;
1414
1415 ir = ids[0];
1416 l = 1;
1417 jstack = 0;
1418 for(;;) {
1419 if (ir - l < SMALL) { /* Insertion sort */
1420 for (j=l+1;j<=ir;j++) {
1421 a = ids[j];
1422 for (i=j-1;i>=1;i--) {
1423 if (ids[i] <= a) break;
1424 ids[i+1] = ids[i];
1425 }
1426 ids[i+1] = a;
1427 }
1428 if (jstack == 0) break;
1429 ir = istack[jstack--];
1430 l = istack[jstack--];
1431 } else {
1432 k = (l + ir) >> 1; /* Choose median of left, center, right */
1433 SWAP(ids[k], ids[l+1]);
1434 if (ids[l] > ids[ir]) {
1435 SWAP(ids[l], ids[ir]);
1436 }
1437 if (ids[l+1] > ids[ir]) {
1438 SWAP(ids[l+1], ids[ir]);
1439 }
1440 if (ids[l] > ids[l+1]) {
1441 SWAP(ids[l], ids[l+1]);
1442 }
1443 i = l+1;
1444 j = ir;
1445 a = ids[l+1];
1446 for(;;) {
1447 do i++; while(ids[i] < a);
1448 do j--; while(ids[j] > a);
1449 if (j < i) break;
1450 SWAP(ids[i],ids[j]);
1451 }
1452 ids[l+1] = ids[j];
1453 ids[j] = a;
1454 jstack += 2;
1455 if (ir-i+1 >= j-1) {
1456 istack[jstack] = ir;
1457 istack[jstack-1] = i;
1458 ir = j-1;
1459 } else {
1460 istack[jstack] = j-1;
1461 istack[jstack-1] = l;
1462 l = i;
1463 }
1464 }
1465 }
1466 }
1467
1468 #else
1469
1470 /* 8 bit Radix sort + insertion sort
1471 *
1472 * based on code from http://www.cubic.org/docs/radix.htm
1473 * with improvements by mbackes@symas.com and hyc@symas.com
1474 *
1475 * This code is O(n) but has a relatively high constant factor. For lists
1476 * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
1477 * Much faster than quicksort for lists longer than ~100. Insertion
1478 * sort is actually superior for lists <50.
1479 */
1480
1481 #define BUCKETS (1<<8)
1482 #define SMALL 50
1483
1484 void
1485 bdb_idl_sort( ID *ids, ID *tmp )
1486 {
1487 int count, soft_limit, phase = 0, size = ids[0];
1488 ID *idls[2];
1489 unsigned char *maxv = (unsigned char *)&ids[size];
1490
1491 if ( BDB_IDL_IS_RANGE( ids ))
1492 return;
1493
1494 /* Use insertion sort for small lists */
1495 if ( size <= SMALL ) {
1496 int i,j;
1497 ID a;
1498
1499 for (j=1;j<=size;j++) {
1500 a = ids[j];
1501 for (i=j-1;i>=1;i--) {
1502 if (ids[i] <= a) break;
1503 ids[i+1] = ids[i];
1504 }
1505 ids[i+1] = a;
1506 }
1507 return;
1508 }
1509
1510 tmp[0] = size;
1511 idls[0] = ids;
1512 idls[1] = tmp;
1513
1514 #if BYTE_ORDER == BIG_ENDIAN
1515 for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
1516 #else
1517 for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
1518 #endif
1519
1520 for (
1521 #if BYTE_ORDER == BIG_ENDIAN
1522 count = sizeof(ID)-1; count >= soft_limit; --count
1523 #else
1524 count = 0; count <= soft_limit; ++count
1525 #endif
1526 ) {
1527 unsigned int num[BUCKETS], * np, n, sum;
1528 int i;
1529 ID *sp, *source, *dest;
1530 unsigned char *bp, *source_start;
1531
1532 source = idls[phase]+1;
1533 dest = idls[phase^1]+1;
1534 source_start = ((unsigned char *) source) + count;
1535
1536 np = num;
1537 for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
1538
1539 /* count occurences of every byte value */
1540 bp = source_start;
1541 for ( i = size; i > 0; --i, bp += sizeof(ID) )
1542 num[*bp]++;
1543
1544 /* transform count into index by summing elements and storing
1545 * into same array
1546 */
1547 sum = 0;
1548 np = num;
1549 for ( i = BUCKETS; i > 0; --i ) {
1550 n = *np;
1551 *np++ = sum;
1552 sum += n;
1553 }
1554
1555 /* fill dest with the right values in the right place */
1556 bp = source_start;
1557 sp = source;
1558 for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
1559 np = num + *bp;
1560 dest[*np] = *sp++;
1561 ++(*np);
1562 }
1563 phase ^= 1;
1564 }
1565
1566 /* copy back from temp if needed */
1567 if ( phase ) {
1568 ids++; tmp++;
1569 for ( count = 0; count < size; ++count )
1570 *ids++ = *tmp++;
1571 }
1572 }
1573 #endif /* Quick vs Radix */
1574
1575 #endif /* BDB_HIER */
NetBSD on the FriendlyARM MINI2440