1 /* idl.c - ldap id list handling routines */
3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
5 * Copyright 2000-2013 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>.
20 #include <ac/string.h>
25 #define IDL_MAX(x,y) ( (x) > (y) ? (x) : (y) )
26 #define IDL_MIN(x,y) ( (x) < (y) ? (x) : (y) )
27 #define IDL_CMP(x,y) ( (x) < (y) ? -1 : (x) > (y) )
30 static void idl_check( ID *ids )
32 if( MDB_IDL_IS_RANGE( ids ) ) {
33 assert( MDB_IDL_RANGE_FIRST(ids) <= MDB_IDL_RANGE_LAST(ids) );
36 for( i=1; i < ids[0]; i++ ) {
37 assert( ids[i+1] > ids[i] );
43 static void idl_dump( ID *ids )
45 if( MDB_IDL_IS_RANGE( ids ) ) {
46 Debug( LDAP_DEBUG_ANY,
47 "IDL: range ( %ld - %ld )\n",
48 (long) MDB_IDL_RANGE_FIRST( ids ),
49 (long) MDB_IDL_RANGE_LAST( ids ) );
53 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
55 for( i=1; i<=ids[0]; i++ ) {
57 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
59 Debug( LDAP_DEBUG_ANY, " %02lx", (long) ids[i], 0, 0 );
62 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
67 #endif /* IDL_DEBUG > 1 */
68 #endif /* IDL_DEBUG > 0 */
70 unsigned mdb_idl_search( ID *ids, ID id )
72 #define IDL_BINARY_SEARCH 1
73 #ifdef IDL_BINARY_SEARCH
75 * binary search of id in ids
76 * if found, returns position of id
77 * if not found, returns first postion greater than id
89 unsigned pivot = n >> 1;
90 cursor = base + pivot + 1;
91 val = IDL_CMP( id, ids[cursor] );
96 } else if ( val > 0 ) {
111 /* (reverse) linear search */
118 for( i=ids[0]; i; i-- ) {
128 int mdb_idl_insert( ID *ids, ID id )
133 Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
139 if (MDB_IDL_IS_RANGE( ids )) {
140 /* if already in range, treat as a dup */
141 if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
143 if (id < MDB_IDL_RANGE_FIRST(ids))
145 else if (id > MDB_IDL_RANGE_LAST(ids))
150 x = mdb_idl_search( ids, id );
158 if ( x <= ids[0] && ids[x] == id ) {
163 if ( ++ids[0] >= MDB_IDL_DB_MAX ) {
166 ids[2] = ids[ids[0]-1];
167 } else if ( ids[ids[0]-1] < id ) {
170 ids[2] = ids[ids[0]-1];
176 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
189 static int mdb_idl_delete( ID *ids, ID id )
194 Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
200 if (MDB_IDL_IS_RANGE( ids )) {
201 /* If deleting a range boundary, adjust */
204 else if ( ids[2] == id )
206 /* deleting from inside a range is a no-op */
208 /* If the range has collapsed, re-adjust */
209 if ( ids[1] > ids[2] )
211 else if ( ids[1] == ids[2] )
216 x = mdb_idl_search( ids, id );
224 if( x > ids[0] || ids[x] != id ) {
228 } else if ( --ids[0] == 0 ) {
234 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
252 if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
253 unsigned char *c = val;
254 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
268 MDB_cursor **saved_cursor,
271 MDB_val data, key2, *kptr;
276 MDB_cursor_op opflag;
280 Debug( LDAP_DEBUG_ARGS,
281 "mdb_idl_fetch_key: %s\n",
282 mdb_show_key( keybuf, key->mv_data, key->mv_size ), 0, 0 );
284 assert( ids != NULL );
286 if ( saved_cursor && *saved_cursor ) {
288 } else if ( get_flag == LDAP_FILTER_GE ) {
289 opflag = MDB_SET_RANGE;
290 } else if ( get_flag == LDAP_FILTER_LE ) {
296 /* If we're not reusing an existing cursor, get a new one */
297 if( opflag != MDB_NEXT ) {
298 rc = mdb_cursor_open( txn, dbi, &cursor );
300 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
301 "cursor failed: %s (%d)\n", mdb_strerror(rc), rc, 0 );
305 cursor = *saved_cursor;
308 /* If this is a LE lookup, save original key so we can determine
309 * when to stop. If this is a GE lookup, save the key since it
310 * will be overwritten.
312 if ( get_flag == LDAP_FILTER_LE || get_flag == LDAP_FILTER_GE ) {
313 key2.mv_data = keybuf;
314 key2.mv_size = key->mv_size;
315 AC_MEMCPY( keybuf, key->mv_data, key->mv_size );
321 rc = mdb_cursor_get( cursor, kptr, &data, opflag );
323 /* skip presence key on range inequality lookups */
324 while (rc == 0 && kptr->mv_size != len) {
325 rc = mdb_cursor_get( cursor, kptr, &data, MDB_NEXT_NODUP );
327 /* If we're doing a LE compare and the new key is greater than
328 * our search key, we're done
330 if (rc == 0 && get_flag == LDAP_FILTER_LE && memcmp( kptr->mv_data,
331 key->mv_data, key->mv_size ) > 0 ) {
336 rc = mdb_cursor_get( cursor, key, &data, MDB_GET_MULTIPLE );
338 memcpy( i, data.mv_data, data.mv_size );
339 i += data.mv_size / sizeof(ID);
340 rc = mdb_cursor_get( cursor, key, &data, MDB_NEXT_MULTIPLE );
342 if ( rc == MDB_NOTFOUND ) rc = 0;
343 ids[0] = i - &ids[1];
344 /* On disk, a range is denoted by 0 in the first element */
346 if (ids[0] != MDB_IDL_RANGE_SIZE) {
347 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
348 "range size mismatch: expected %d, got %ld\n",
349 MDB_IDL_RANGE_SIZE, ids[0], 0 );
350 mdb_cursor_close( cursor );
353 MDB_IDL_RANGE( ids, ids[2], ids[3] );
355 data.mv_size = MDB_IDL_SIZEOF(ids);
358 if ( saved_cursor && rc == 0 ) {
359 if ( !*saved_cursor )
360 *saved_cursor = cursor;
363 mdb_cursor_close( cursor );
365 if( rc == MDB_NOTFOUND ) {
368 } else if( rc != 0 ) {
369 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
370 "get failed: %s (%d)\n",
371 mdb_strerror(rc), rc, 0 );
374 } else if ( data.mv_size == 0 || data.mv_size % sizeof( ID ) ) {
375 /* size not multiple of ID size */
376 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
377 "odd size: expected %ld multiple, got %ld\n",
378 (long) sizeof( ID ), (long) data.mv_size, 0 );
381 } else if ( data.mv_size != MDB_IDL_SIZEOF(ids) ) {
383 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_fetch_key: "
384 "get size mismatch: expected %ld, got %ld\n",
385 (long) ((1 + ids[0]) * sizeof( ID )), (long) data.mv_size, 0 );
399 struct mdb_info *mdb = be->be_private;
404 unsigned int flag = MDB_NODUPDATA;
405 #ifndef MISALIGNED_OK
411 Debug( LDAP_DEBUG_ARGS,
412 "mdb_idl_insert_keys: %lx %s\n",
413 (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
416 assert( id != NOID );
418 #ifndef MISALIGNED_OK
419 if (keys[0].bv_len & ALIGNER)
422 for ( k=0; keys[k].bv_val; k++ ) {
423 /* Fetch the first data item for this key, to see if it
424 * exists and if it's a range.
426 #ifndef MISALIGNED_OK
427 if (keys[k].bv_len & ALIGNER) {
428 key.mv_size = sizeof(kbuf);
430 memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
434 key.mv_size = keys[k].bv_len;
435 key.mv_data = keys[k].bv_val;
437 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
441 memcpy(&lo, data.mv_data, sizeof(ID));
443 /* not a range, count the number of items */
445 rc = mdb_cursor_count( cursor, &count );
450 if ( count >= MDB_IDL_DB_MAX ) {
451 /* No room, convert to a range */
453 rc = mdb_cursor_get( cursor, &key, &data, MDB_LAST_DUP );
454 if ( rc != 0 && rc != MDB_NOTFOUND ) {
455 err = "c_get last_dup";
460 /* Update hi/lo if needed */
463 } else if ( id > hi ) {
466 /* delete the old key */
467 rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
472 /* Store the range */
473 data.mv_size = sizeof(ID);
476 rc = mdb_cursor_put( cursor, &key, &data, 0 );
482 rc = mdb_cursor_put( cursor, &key, &data, 0 );
488 rc = mdb_cursor_put( cursor, &key, &data, 0 );
494 /* There's room, just store it */
495 if (id == mdb->mi_nextid)
496 flag |= MDB_APPENDDUP;
500 /* It's a range, see if we need to rewrite
505 if ( id < lo || id > hi ) {
507 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
514 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
520 data.mv_size = sizeof(ID);
522 /* Replace the current lo/hi */
523 rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
530 } else if ( rc == MDB_NOTFOUND ) {
531 flag &= ~MDB_APPENDDUP;
532 put1: data.mv_data = &id;
533 data.mv_size = sizeof(ID);
534 rc = mdb_cursor_put( cursor, &key, &data, flag );
535 /* Don't worry if it's already there */
536 if ( rc == MDB_KEYEXIST )
543 /* initial c_get failed, nothing was done */
545 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_insert_keys: "
546 "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
564 #ifndef MISALIGNED_OK
570 Debug( LDAP_DEBUG_ARGS,
571 "mdb_idl_delete_keys: %lx %s\n",
572 (long) id, mdb_show_key( buf, keys->bv_val, keys->bv_len ), 0 );
574 assert( id != NOID );
576 #ifndef MISALIGNED_OK
577 if (keys[0].bv_len & ALIGNER)
580 for ( k=0; keys[k].bv_val; k++) {
581 /* Fetch the first data item for this key, to see if it
582 * exists and if it's a range.
584 #ifndef MISALIGNED_OK
585 if (keys[k].bv_len & ALIGNER) {
586 key.mv_size = sizeof(kbuf);
588 memcpy(key.mv_data, keys[k].bv_val, keys[k].bv_len);
592 key.mv_size = keys[k].bv_len;
593 key.mv_data = keys[k].bv_val;
595 rc = mdb_cursor_get( cursor, &key, &data, MDB_SET );
598 memcpy( &tmp, data.mv_data, sizeof(ID) );
601 /* Not a range, just delete it */
603 rc = mdb_cursor_get( cursor, &key, &data, MDB_GET_BOTH );
608 rc = mdb_cursor_del( cursor, 0 );
614 /* It's a range, see if we need to rewrite
619 if ( id == lo || id == hi ) {
620 ID lo2 = lo, hi2 = hi;
623 } else if ( id == hi ) {
627 /* The range has collapsed... */
628 rc = mdb_cursor_del( cursor, MDB_NODUPDATA );
635 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
640 rc = mdb_cursor_get( cursor, &key, &data, MDB_NEXT_DUP );
643 /* Replace the current lo/hi */
644 data.mv_size = sizeof(ID);
645 rc = mdb_cursor_put( cursor, &key, &data, MDB_CURRENT );
654 /* initial c_get failed, nothing was done */
656 if ( rc == MDB_NOTFOUND )
659 Debug( LDAP_DEBUG_ANY, "=> mdb_idl_delete_key: "
660 "%s failed: %s (%d)\n", err, mdb_strerror(rc), rc );
670 * idl_intersection - return a = a intersection b
673 mdb_idl_intersection(
679 ID cursora = 0, cursorb = 0, cursorc;
682 if ( MDB_IDL_IS_ZERO( a ) || MDB_IDL_IS_ZERO( b ) ) {
687 idmin = IDL_MAX( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
688 idmax = IDL_MIN( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
689 if ( idmin > idmax ) {
692 } else if ( idmin == idmax ) {
698 if ( MDB_IDL_IS_RANGE( a ) ) {
699 if ( MDB_IDL_IS_RANGE(b) ) {
700 /* If both are ranges, just shrink the boundaries */
705 /* Else swap so that b is the range, a is a list */
713 /* If a range completely covers the list, the result is
714 * just the list. If idmin to idmax is contiguous, just
715 * turn it into a range.
717 if ( MDB_IDL_IS_RANGE( b )
718 && MDB_IDL_RANGE_FIRST( b ) <= MDB_IDL_FIRST( a )
719 && MDB_IDL_RANGE_LAST( b ) >= MDB_IDL_LLAST( a ) ) {
720 if (idmax - idmin + 1 == a[0])
729 /* Fine, do the intersection one element at a time.
730 * First advance to idmin in both IDLs.
732 cursora = cursorb = idmin;
733 ida = mdb_idl_first( a, &cursora );
734 idb = mdb_idl_first( b, &cursorb );
737 while( ida <= idmax || idb <= idmax ) {
740 ida = mdb_idl_next( a, &cursora );
741 idb = mdb_idl_next( b, &cursorb );
742 } else if ( ida < idb ) {
743 ida = mdb_idl_next( a, &cursora );
745 idb = mdb_idl_next( b, &cursorb );
758 * idl_union - return a = a union b
766 ID cursora = 0, cursorb = 0, cursorc;
768 if ( MDB_IDL_IS_ZERO( b ) ) {
772 if ( MDB_IDL_IS_ZERO( a ) ) {
777 if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ) {
778 over: ida = IDL_MIN( MDB_IDL_FIRST(a), MDB_IDL_FIRST(b) );
779 idb = IDL_MAX( MDB_IDL_LAST(a), MDB_IDL_LAST(b) );
786 ida = mdb_idl_first( a, &cursora );
787 idb = mdb_idl_first( b, &cursorb );
791 /* The distinct elements of a are cat'd to b */
792 while( ida != NOID || idb != NOID ) {
794 if( ++cursorc > MDB_IDL_UM_MAX ) {
798 ida = mdb_idl_next( a, &cursora );
802 ida = mdb_idl_next( a, &cursora );
803 idb = mdb_idl_next( b, &cursorb );
807 /* b is copied back to a in sorted order */
812 while (cursorb <= b[0] || cursorc <= a[0]) {
817 if (cursorb <= b[0] && b[cursorb] < idb)
818 a[cursora++] = b[cursorb++];
831 * mdb_idl_notin - return a intersection ~b (or a minus b)
840 ID cursora = 0, cursorb = 0;
842 if( MDB_IDL_IS_ZERO( a ) ||
843 MDB_IDL_IS_ZERO( b ) ||
844 MDB_IDL_IS_RANGE( b ) )
846 MDB_IDL_CPY( ids, a );
850 if( MDB_IDL_IS_RANGE( a ) ) {
851 MDB_IDL_CPY( ids, a );
855 ida = mdb_idl_first( a, &cursora ),
856 idb = mdb_idl_first( b, &cursorb );
860 while( ida != NOID ) {
862 /* we could shortcut this */
864 ida = mdb_idl_next( a, &cursora );
866 } else if ( ida < idb ) {
868 ida = mdb_idl_next( a, &cursora );
870 } else if ( ida > idb ) {
871 idb = mdb_idl_next( b, &cursorb );
874 ida = mdb_idl_next( a, &cursora );
875 idb = mdb_idl_next( b, &cursorb );
883 ID mdb_idl_first( ID *ids, ID *cursor )
892 if ( MDB_IDL_IS_RANGE( ids ) ) {
893 if( *cursor < ids[1] ) {
902 pos = mdb_idl_search( ids, *cursor );
912 ID mdb_idl_next( ID *ids, ID *cursor )
914 if ( MDB_IDL_IS_RANGE( ids ) ) {
915 if( ids[2] < ++(*cursor) ) {
921 if ( ++(*cursor) <= ids[0] ) {
928 /* Add one ID to an unsorted list. We ensure that the first element is the
929 * minimum and the last element is the maximum, for fast range compaction.
930 * this means IDLs up to length 3 are always sorted...
932 int mdb_idl_append_one( ID *ids, ID id )
934 if (MDB_IDL_IS_RANGE( ids )) {
935 /* if already in range, treat as a dup */
936 if (id >= MDB_IDL_RANGE_FIRST(ids) && id <= MDB_IDL_RANGE_LAST(ids))
938 if (id < MDB_IDL_RANGE_FIRST(ids))
940 else if (id > MDB_IDL_RANGE_LAST(ids))
952 if ( ids[0] > 1 && id < ids[ids[0]] ) {
959 if ( ids[0] >= MDB_IDL_UM_MAX ) {
968 /* Append sorted list b to sorted list a. The result is unsorted but
969 * a[1] is the min of the result and a[a[0]] is the max.
971 int mdb_idl_append( ID *a, ID *b )
973 ID ida, idb, tmp, swap = 0;
975 if ( MDB_IDL_IS_ZERO( b ) ) {
979 if ( MDB_IDL_IS_ZERO( a ) ) {
984 ida = MDB_IDL_LAST( a );
985 idb = MDB_IDL_LAST( b );
986 if ( MDB_IDL_IS_RANGE( a ) || MDB_IDL_IS_RANGE(b) ||
987 a[0] + b[0] >= MDB_IDL_UM_MAX ) {
988 a[2] = IDL_MAX( ida, idb );
989 a[1] = IDL_MIN( a[1], b[1] );
994 if ( b[0] > 1 && ida > idb ) {
1000 if ( b[1] < a[1] ) {
1011 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
1022 /* Quicksort + Insertion sort for small arrays */
1025 #define SWAP(a,b) itmp=(a);(a)=(b);(b)=itmp
1028 mdb_idl_sort( ID *ids, ID *tmp )
1030 int *istack = (int *)tmp; /* Private stack, not used by caller */
1031 int i,j,k,l,ir,jstack;
1034 if ( MDB_IDL_IS_RANGE( ids ))
1041 if (ir - l < SMALL) { /* Insertion sort */
1042 for (j=l+1;j<=ir;j++) {
1044 for (i=j-1;i>=1;i--) {
1045 if (ids[i] <= a) break;
1050 if (jstack == 0) break;
1051 ir = istack[jstack--];
1052 l = istack[jstack--];
1054 k = (l + ir) >> 1; /* Choose median of left, center, right */
1055 SWAP(ids[k], ids[l+1]);
1056 if (ids[l] > ids[ir]) {
1057 SWAP(ids[l], ids[ir]);
1059 if (ids[l+1] > ids[ir]) {
1060 SWAP(ids[l+1], ids[ir]);
1062 if (ids[l] > ids[l+1]) {
1063 SWAP(ids[l], ids[l+1]);
1069 do i++; while(ids[i] < a);
1070 do j--; while(ids[j] > a);
1072 SWAP(ids[i],ids[j]);
1077 if (ir-i+1 >= j-l) {
1078 istack[jstack] = ir;
1079 istack[jstack-1] = i;
1082 istack[jstack] = j-1;
1083 istack[jstack-1] = l;
1092 /* 8 bit Radix sort + insertion sort
1094 * based on code from http://www.cubic.org/docs/radix.htm
1095 * with improvements by ebackes@symas.com and hyc@symas.com
1097 * This code is O(n) but has a relatively high constant factor. For lists
1098 * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
1099 * Much faster than quicksort for lists longer than ~100. Insertion
1100 * sort is actually superior for lists <50.
1103 #define BUCKETS (1<<8)
1107 mdb_idl_sort( ID *ids, ID *tmp )
1109 int count, soft_limit, phase = 0, size = ids[0];
1111 unsigned char *maxv = (unsigned char *)&ids[size];
1113 if ( MDB_IDL_IS_RANGE( ids ))
1116 /* Use insertion sort for small lists */
1117 if ( size <= SMALL ) {
1121 for (j=1;j<=size;j++) {
1123 for (i=j-1;i>=1;i--) {
1124 if (ids[i] <= a) break;
1136 #if BYTE_ORDER == BIG_ENDIAN
1137 for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
1139 for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
1143 #if BYTE_ORDER == BIG_ENDIAN
1144 count = sizeof(ID)-1; count >= soft_limit; --count
1146 count = 0; count <= soft_limit; ++count
1149 unsigned int num[BUCKETS], * np, n, sum;
1151 ID *sp, *source, *dest;
1152 unsigned char *bp, *source_start;
1154 source = idls[phase]+1;
1155 dest = idls[phase^1]+1;
1156 source_start = ((unsigned char *) source) + count;
1159 for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
1161 /* count occurences of every byte value */
1163 for ( i = size; i > 0; --i, bp += sizeof(ID) )
1166 /* transform count into index by summing elements and storing
1171 for ( i = BUCKETS; i > 0; --i ) {
1177 /* fill dest with the right values in the right place */
1180 for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
1188 /* copy back from temp if needed */
1191 for ( count = 0; count < size; ++count )
1195 #endif /* Quick vs Radix */
1197 unsigned mdb_id2l_search( ID2L ids, ID id )
1200 * binary search of id in ids
1201 * if found, returns position of id
1202 * if not found, returns first position greater than id
1205 unsigned cursor = 1;
1207 unsigned n = ids[0].mid;
1210 unsigned pivot = n >> 1;
1211 cursor = base + pivot + 1;
1212 val = IDL_CMP( id, ids[cursor].mid );
1217 } else if ( val > 0 ) {
1232 int mdb_id2l_insert( ID2L ids, ID2 *id )
1236 x = mdb_id2l_search( ids, id->mid );
1240 /* internal error */
1244 if ( x <= ids[0].mid && ids[x].mid == id->mid ) {
1249 if ( ids[0].mid >= MDB_IDL_UM_MAX ) {
1256 for (i=ids[0].mid; i>x; i--)