git.sur5r.net Git - openldap/blob - servers/slapd/back-wt/idl.c

   1 /* OpenLDAP WiredTiger backend */
   2 /* $OpenLDAP$ */
   3 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
   4  *
   5  * Copyright 2002-2018 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 /* ACKNOWLEDGEMENTS:
  17  * This work was developed by HAMANO Tsukasa <hamano@osstech.co.jp>
  18  * based on back-bdb for inclusion in OpenLDAP Software.
  19  * WiredTiger is a product of MongoDB Inc.
  20  */
  21
  22 #include "portable.h"
  23
  24 #include <stdio.h>
  25 #include <ac/string.h>
  26
  27 #include "back-wt.h"
  28 #include "idl.h"
  29
  30 #define IDL_MAX(x,y)    ( (x) > (y) ? (x) : (y) )
  31 #define IDL_MIN(x,y)    ( (x) < (y) ? (x) : (y) )
  32 #define IDL_CMP(x,y)    ( (x) < (y) ? -1 : (x) > (y) )
  33
  34 #if IDL_DEBUG > 0
  35 static void idl_check( ID *ids )
  36 {
  37         if( WT_IDL_IS_RANGE( ids ) ) {
  38                 assert( WT_IDL_RANGE_FIRST(ids) <= WT_IDL_RANGE_LAST(ids) );
  39         } else {
  40                 ID i;
  41                 for( i=1; i < ids[0]; i++ ) {
  42                         assert( ids[i+1] > ids[i] );
  43                 }
  44         }
  45 }
  46
  47 #if IDL_DEBUG > 1
  48 static void idl_dump( ID *ids )
  49 {
  50         if( WT_IDL_IS_RANGE( ids ) ) {
  51                 Debug( LDAP_DEBUG_ANY,
  52                "IDL: range ( %ld - %ld )\n",
  53                (long) WT_IDL_RANGE_FIRST( ids ),
  54                (long) WT_IDL_RANGE_LAST( ids ),
  55                0);
  56
  57         } else {
  58                 ID i;
  59                 Debug( LDAP_DEBUG_ANY, "IDL: size %ld", (long) ids[0], 0, 0 );
  60
  61                 for( i=1; i<=ids[0]; i++ ) {
  62                         if( i % 16 == 1 ) {
  63                                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  64                         }
  65                         Debug( LDAP_DEBUG_ANY, "  %02lx", (long) ids[i], 0, 0 );
  66                 }
  67
  68                 Debug( LDAP_DEBUG_ANY, "\n", 0, 0, 0 );
  69         }
  70
  71         idl_check( ids );
  72 }
  73 #endif /* IDL_DEBUG > 1 */
  74 #endif /* IDL_DEBUG > 0 */
  75
  76 unsigned wt_idl_search( ID *ids, ID id )
  77 {
  78 #define IDL_BINARY_SEARCH 1
  79 #ifdef IDL_BINARY_SEARCH
  80         /*
  81          * binary search of id in ids
  82          * if found, returns position of id
  83          * if not found, returns first postion greater than id
  84          */
  85         unsigned base = 0;
  86         unsigned cursor = 1;
  87         int val = 0;
  88         unsigned n = ids[0];
  89
  90 #if IDL_DEBUG > 0
  91         idl_check( ids );
  92 #endif
  93
  94         while( 0 < n ) {
  95                 unsigned pivot = n >> 1;
  96                 cursor = base + pivot + 1;
  97                 val = IDL_CMP( id, ids[cursor] );
  98
  99                 if( val < 0 ) {
 100                         n = pivot;
 101
 102                 } else if ( val > 0 ) {
 103                         base = cursor;
 104                         n -= pivot + 1;
 105
 106                 } else {
 107                         return cursor;
 108                 }
 109         }
 110
 111         if( val > 0 ) {
 112                 ++cursor;
 113         }
 114         return cursor;
 115
 116 #else
 117         /* (reverse) linear search */
 118         int i;
 119
 120 #if IDL_DEBUG > 0
 121         idl_check( ids );
 122 #endif
 123
 124         for( i=ids[0]; i; i-- ) {
 125                 if( id > ids[i] ) {
 126                         break;
 127                 }
 128         }
 129
 130         return i+1;
 131 #endif
 132 }
 133
 134 int wt_idl_insert( ID *ids, ID id )
 135 {
 136         unsigned x;
 137
 138 #if IDL_DEBUG > 1
 139         Debug( LDAP_DEBUG_ANY, "insert: %04lx at %d\n", (long) id, x, 0 );
 140         idl_dump( ids );
 141 #elif IDL_DEBUG > 0
 142         idl_check( ids );
 143 #endif
 144
 145         if (WT_IDL_IS_RANGE( ids )) {
 146                 /* if already in range, treat as a dup */
 147                 if (id >= WT_IDL_RANGE_FIRST(ids) && id <= WT_IDL_RANGE_LAST(ids))
 148                         return -1;
 149                 if (id < WT_IDL_RANGE_FIRST(ids))
 150                         ids[1] = id;
 151                 else if (id > WT_IDL_RANGE_LAST(ids))
 152                         ids[2] = id;
 153                 return 0;
 154         }
 155
 156         x = wt_idl_search( ids, id );
 157         assert( x > 0 );
 158
 159         if( x < 1 ) {
 160                 /* internal error */
 161                 return -2;
 162         }
 163
 164         if ( x <= ids[0] && ids[x] == id ) {
 165                 /* duplicate */
 166                 return -1;
 167         }
 168
 169         if ( ++ids[0] >= WT_IDL_DB_MAX ) {
 170                 if( id < ids[1] ) {
 171                         ids[1] = id;
 172                         ids[2] = ids[ids[0]-1];
 173                 } else if ( ids[ids[0]-1] < id ) {
 174                         ids[2] = id;
 175                 } else {
 176                         ids[2] = ids[ids[0]-1];
 177                 }
 178                 ids[0] = NOID;
 179
 180         } else {
 181                 /* insert id */
 182                 AC_MEMCPY( &ids[x+1], &ids[x], (ids[0]-x) * sizeof(ID) );
 183                 ids[x] = id;
 184         }
 185
 186 #if IDL_DEBUG > 1
 187         idl_dump( ids );
 188 #elif IDL_DEBUG > 0
 189         idl_check( ids );
 190 #endif
 191
 192         return 0;
 193 }
 194
 195 static int wt_idl_delete( ID *ids, ID id )
 196 {
 197         unsigned x;
 198
 199 #if IDL_DEBUG > 1
 200         Debug( LDAP_DEBUG_ANY, "delete: %04lx at %d\n", (long) id, x, 0 );
 201         idl_dump( ids );
 202 #elif IDL_DEBUG > 0
 203         idl_check( ids );
 204 #endif
 205
 206         if (WT_IDL_IS_RANGE( ids )) {
 207                 /* If deleting a range boundary, adjust */
 208                 if ( ids[1] == id )
 209                         ids[1]++;
 210                 else if ( ids[2] == id )
 211                         ids[2]--;
 212                 /* deleting from inside a range is a no-op */
 213
 214                 /* If the range has collapsed, re-adjust */
 215                 if ( ids[1] > ids[2] )
 216                         ids[0] = 0;
 217                 else if ( ids[1] == ids[2] )
 218                         ids[1] = 1;
 219                 return 0;
 220         }
 221
 222         x = wt_idl_search( ids, id );
 223         assert( x > 0 );
 224
 225         if( x <= 0 ) {
 226                 /* internal error */
 227                 return -2;
 228         }
 229
 230         if( x > ids[0] || ids[x] != id ) {
 231                 /* not found */
 232                 return -1;
 233
 234         } else if ( --ids[0] == 0 ) {
 235                 if( x != 1 ) {
 236                         return -3;
 237                 }
 238
 239         } else {
 240                 AC_MEMCPY( &ids[x], &ids[x+1], (1+ids[0]-x) * sizeof(ID) );
 241         }
 242
 243 #if IDL_DEBUG > 1
 244         idl_dump( ids );
 245 #elif IDL_DEBUG > 0
 246         idl_check( ids );
 247 #endif
 248
 249         return 0;
 250 }
 251
 252 static char *
 253 wt_show_key(
 254         char            *buf,
 255         void            *val,
 256         size_t          len )
 257 {
 258         if ( len == 4 /* LUTIL_HASH_BYTES */ ) {
 259                 unsigned char *c = val;
 260                 sprintf( buf, "[%02x%02x%02x%02x]", c[0], c[1], c[2], c[3] );
 261                 return buf;
 262         } else {
 263                 return val;
 264         }
 265 }
 266
 267 /*
 268  * idl_intersection - return a = a intersection b
 269  */
 270 int
 271 wt_idl_intersection(
 272         ID *a,
 273         ID *b )
 274 {
 275         ID ida, idb;
 276         ID idmax, idmin;
 277         ID cursora = 0, cursorb = 0, cursorc;
 278         int swap = 0;
 279
 280         if ( WT_IDL_IS_ZERO( a ) || WT_IDL_IS_ZERO( b ) ) {
 281                 a[0] = 0;
 282                 return 0;
 283         }
 284
 285         idmin = IDL_MAX( WT_IDL_FIRST(a), WT_IDL_FIRST(b) );
 286         idmax = IDL_MIN( WT_IDL_LAST(a), WT_IDL_LAST(b) );
 287         if ( idmin > idmax ) {
 288                 a[0] = 0;
 289                 return 0;
 290         } else if ( idmin == idmax ) {
 291                 a[0] = 1;
 292                 a[1] = idmin;
 293                 return 0;
 294         }
 295
 296         if ( WT_IDL_IS_RANGE( a ) ) {
 297                 if ( WT_IDL_IS_RANGE(b) ) {
 298                 /* If both are ranges, just shrink the boundaries */
 299                         a[1] = idmin;
 300                         a[2] = idmax;
 301                         return 0;
 302                 } else {
 303                 /* Else swap so that b is the range, a is a list */
 304                         ID *tmp = a;
 305                         a = b;
 306                         b = tmp;
 307                         swap = 1;
 308                 }
 309         }
 310
 311         /* If a range completely covers the list, the result is
 312          * just the list. If idmin to idmax is contiguous, just
 313          * turn it into a range.
 314          */
 315         if ( WT_IDL_IS_RANGE( b )
 316                 && WT_IDL_RANGE_FIRST( b ) <= WT_IDL_FIRST( a )
 317                 && WT_IDL_RANGE_LAST( b ) >= WT_IDL_LLAST( a ) ) {
 318                 if (idmax - idmin + 1 == a[0])
 319                 {
 320                         a[0] = NOID;
 321                         a[1] = idmin;
 322                         a[2] = idmax;
 323                 }
 324                 goto done;
 325         }
 326
 327         /* Fine, do the intersection one element at a time.
 328          * First advance to idmin in both IDLs.
 329          */
 330         cursora = cursorb = idmin;
 331         ida = wt_idl_first( a, &cursora );
 332         idb = wt_idl_first( b, &cursorb );
 333         cursorc = 0;
 334
 335         while( ida <= idmax || idb <= idmax ) {
 336                 if( ida == idb ) {
 337                         a[++cursorc] = ida;
 338                         ida = wt_idl_next( a, &cursora );
 339                         idb = wt_idl_next( b, &cursorb );
 340                 } else if ( ida < idb ) {
 341                         ida = wt_idl_next( a, &cursora );
 342                 } else {
 343                         idb = wt_idl_next( b, &cursorb );
 344                 }
 345         }
 346         a[0] = cursorc;
 347 done:
 348         if (swap)
 349                 WT_IDL_CPY( b, a );
 350
 351         return 0;
 352 }
 353
 354
 355 /*
 356  * idl_union - return a = a union b
 357  */
 358 int
 359 wt_idl_union(
 360         ID      *a,
 361         ID      *b )
 362 {
 363         ID ida, idb;
 364         ID cursora = 0, cursorb = 0, cursorc;
 365
 366         if ( WT_IDL_IS_ZERO( b ) ) {
 367                 return 0;
 368         }
 369
 370         if ( WT_IDL_IS_ZERO( a ) ) {
 371                 WT_IDL_CPY( a, b );
 372                 return 0;
 373         }
 374
 375         if ( WT_IDL_IS_RANGE( a ) || WT_IDL_IS_RANGE(b) ) {
 376 over:           ida = IDL_MIN( WT_IDL_FIRST(a), WT_IDL_FIRST(b) );
 377                 idb = IDL_MAX( WT_IDL_LAST(a), WT_IDL_LAST(b) );
 378                 a[0] = NOID;
 379                 a[1] = ida;
 380                 a[2] = idb;
 381                 return 0;
 382         }
 383
 384         ida = wt_idl_first( a, &cursora );
 385         idb = wt_idl_first( b, &cursorb );
 386
 387         cursorc = b[0];
 388
 389         /* The distinct elements of a are cat'd to b */
 390         while( ida != NOID || idb != NOID ) {
 391                 if ( ida < idb ) {
 392                         if( ++cursorc > WT_IDL_UM_MAX ) {
 393                                 goto over;
 394                         }
 395                         b[cursorc] = ida;
 396                         ida = wt_idl_next( a, &cursora );
 397
 398                 } else {
 399                         if ( ida == idb )
 400                                 ida = wt_idl_next( a, &cursora );
 401                         idb = wt_idl_next( b, &cursorb );
 402                 }
 403         }
 404
 405         /* b is copied back to a in sorted order */
 406         a[0] = cursorc;
 407         cursora = 1;
 408         cursorb = 1;
 409         cursorc = b[0]+1;
 410         while (cursorb <= b[0] || cursorc <= a[0]) {
 411                 if (cursorc > a[0])
 412                         idb = NOID;
 413                 else
 414                         idb = b[cursorc];
 415                 if (cursorb <= b[0] && b[cursorb] < idb)
 416                         a[cursora++] = b[cursorb++];
 417                 else {
 418                         a[cursora++] = idb;
 419                         cursorc++;
 420                 }
 421         }
 422
 423         return 0;
 424 }
 425
 426
 427 #if 0
 428 /*
 429  * wt_idl_notin - return a intersection ~b (or a minus b)
 430  */
 431 int
 432 wt_idl_notin(
 433         ID      *a,
 434         ID      *b,
 435         ID *ids )
 436 {
 437         ID ida, idb;
 438         ID cursora = 0, cursorb = 0;
 439
 440         if( WT_IDL_IS_ZERO( a ) ||
 441                 WT_IDL_IS_ZERO( b ) ||
 442                 WT_IDL_IS_RANGE( b ) )
 443         {
 444                 WT_IDL_CPY( ids, a );
 445                 return 0;
 446         }
 447
 448         if( WT_IDL_IS_RANGE( a ) ) {
 449                 WT_IDL_CPY( ids, a );
 450                 return 0;
 451         }
 452
 453         ida = wt_idl_first( a, &cursora ),
 454         idb = wt_idl_first( b, &cursorb );
 455
 456         ids[0] = 0;
 457
 458         while( ida != NOID ) {
 459                 if ( idb == NOID ) {
 460                         /* we could shortcut this */
 461                         ids[++ids[0]] = ida;
 462                         ida = wt_idl_next( a, &cursora );
 463
 464                 } else if ( ida < idb ) {
 465                         ids[++ids[0]] = ida;
 466                         ida = wt_idl_next( a, &cursora );
 467
 468                 } else if ( ida > idb ) {
 469                         idb = wt_idl_next( b, &cursorb );
 470
 471                 } else {
 472                         ida = wt_idl_next( a, &cursora );
 473                         idb = wt_idl_next( b, &cursorb );
 474                 }
 475         }
 476
 477         return 0;
 478 }
 479 #endif
 480
 481 ID wt_idl_first( ID *ids, ID *cursor )
 482 {
 483         ID pos;
 484
 485         if ( ids[0] == 0 ) {
 486                 *cursor = NOID;
 487                 return NOID;
 488         }
 489
 490         if ( WT_IDL_IS_RANGE( ids ) ) {
 491                 if( *cursor < ids[1] ) {
 492                         *cursor = ids[1];
 493                 }
 494                 return *cursor;
 495         }
 496
 497         if ( *cursor == 0 )
 498                 pos = 1;
 499         else
 500                 pos = wt_idl_search( ids, *cursor );
 501
 502         if( pos > ids[0] ) {
 503                 return NOID;
 504         }
 505
 506         *cursor = pos;
 507         return ids[pos];
 508 }
 509
 510 ID wt_idl_next( ID *ids, ID *cursor )
 511 {
 512         if ( WT_IDL_IS_RANGE( ids ) ) {
 513                 if( ids[2] < ++(*cursor) ) {
 514                         return NOID;
 515                 }
 516                 return *cursor;
 517         }
 518
 519         if ( ++(*cursor) <= ids[0] ) {
 520                 return ids[*cursor];
 521         }
 522
 523         return NOID;
 524 }
 525
 526 /* Add one ID to an unsorted list. We ensure that the first element is the
 527  * minimum and the last element is the maximum, for fast range compaction.
 528  *   this means IDLs up to length 3 are always sorted...
 529  */
 530 int wt_idl_append_one( ID *ids, ID id )
 531 {
 532         if (WT_IDL_IS_RANGE( ids )) {
 533                 /* if already in range, treat as a dup */
 534                 if (id >= WT_IDL_RANGE_FIRST(ids) && id <= WT_IDL_RANGE_LAST(ids))
 535                         return -1;
 536                 if (id < WT_IDL_RANGE_FIRST(ids))
 537                         ids[1] = id;
 538                 else if (id > WT_IDL_RANGE_LAST(ids))
 539                         ids[2] = id;
 540                 return 0;
 541         }
 542         if ( ids[0] ) {
 543                 ID tmp;
 544
 545                 if (id < ids[1]) {
 546                         tmp = ids[1];
 547                         ids[1] = id;
 548                         id = tmp;
 549                 }
 550                 if ( ids[0] > 1 && id < ids[ids[0]] ) {
 551                         tmp = ids[ids[0]];
 552                         ids[ids[0]] = id;
 553                         id = tmp;
 554                 }
 555         }
 556         ids[0]++;
 557         if ( ids[0] >= WT_IDL_UM_MAX ) {
 558                 ids[0] = NOID;
 559                 ids[2] = id;
 560         } else {
 561                 ids[ids[0]] = id;
 562         }
 563         return 0;
 564 }
 565
 566 /* Append sorted list b to sorted list a. The result is unsorted but
 567  * a[1] is the min of the result and a[a[0]] is the max.
 568  */
 569 int wt_idl_append( ID *a, ID *b )
 570 {
 571         ID ida, idb, tmp, swap = 0;
 572
 573         if ( WT_IDL_IS_ZERO( b ) ) {
 574                 return 0;
 575         }
 576
 577         if ( WT_IDL_IS_ZERO( a ) ) {
 578                 WT_IDL_CPY( a, b );
 579                 return 0;
 580         }
 581
 582         ida = WT_IDL_LAST( a );
 583         idb = WT_IDL_LAST( b );
 584         if ( WT_IDL_IS_RANGE( a ) || WT_IDL_IS_RANGE(b) ||
 585                 a[0] + b[0] >= WT_IDL_UM_MAX ) {
 586                 a[2] = IDL_MAX( ida, idb );
 587                 a[1] = IDL_MIN( a[1], b[1] );
 588                 a[0] = NOID;
 589                 return 0;
 590         }
 591
 592         if ( b[0] > 1 && ida > idb ) {
 593                 swap = idb;
 594                 a[a[0]] = idb;
 595                 b[b[0]] = ida;
 596         }
 597
 598         if ( b[1] < a[1] ) {
 599                 tmp = a[1];
 600                 a[1] = b[1];
 601         } else {
 602                 tmp = b[1];
 603         }
 604         a[0]++;
 605         a[a[0]] = tmp;
 606
 607         if ( b[0] > 1 ) {
 608                 int i = b[0] - 1;
 609                 AC_MEMCPY(a+a[0]+1, b+2, i * sizeof(ID));
 610                 a[0] += i;
 611         }
 612         if ( swap ) {
 613                 b[b[0]] = swap;
 614         }
 615         return 0;
 616 }
 617
 618 #if 1
 619
 620 /* Quicksort + Insertion sort for small arrays */
 621
 622 #define SMALL   8
 623 #define SWAP(a,b)       itmp=(a);(a)=(b);(b)=itmp
 624
 625 void
 626 wt_idl_sort( ID *ids, ID *tmp )
 627 {
 628         int *istack = (int *)tmp; /* Private stack, not used by caller */
 629         int i,j,k,l,ir,jstack;
 630         ID a, itmp;
 631
 632         if ( WT_IDL_IS_RANGE( ids ))
 633                 return;
 634
 635         ir = ids[0];
 636         l = 1;
 637         jstack = 0;
 638         for(;;) {
 639                 if (ir - l < SMALL) {   /* Insertion sort */
 640                         for (j=l+1;j<=ir;j++) {
 641                                 a = ids[j];
 642                                 for (i=j-1;i>=1;i--) {
 643                                         if (ids[i] <= a) break;
 644                                         ids[i+1] = ids[i];
 645                                 }
 646                                 ids[i+1] = a;
 647                         }
 648                         if (jstack == 0) break;
 649                         ir = istack[jstack--];
 650                         l = istack[jstack--];
 651                 } else {
 652                         k = (l + ir) >> 1;      /* Choose median of left, center, right */
 653                         SWAP(ids[k], ids[l+1]);
 654                         if (ids[l] > ids[ir]) {
 655                                 SWAP(ids[l], ids[ir]);
 656                         }
 657                         if (ids[l+1] > ids[ir]) {
 658                                 SWAP(ids[l+1], ids[ir]);
 659                         }
 660                         if (ids[l] > ids[l+1]) {
 661                                 SWAP(ids[l], ids[l+1]);
 662                         }
 663                         i = l+1;
 664                         j = ir;
 665                         a = ids[l+1];
 666                         for(;;) {
 667                                 do i++; while(ids[i] < a);
 668                                 do j--; while(ids[j] > a);
 669                                 if (j < i) break;
 670                                 SWAP(ids[i],ids[j]);
 671                         }
 672                         ids[l+1] = ids[j];
 673                         ids[j] = a;
 674                         jstack += 2;
 675                         if (ir-i+1 >= j-l) {
 676                                 istack[jstack] = ir;
 677                                 istack[jstack-1] = i;
 678                                 ir = j-1;
 679                         } else {
 680                                 istack[jstack] = j-1;
 681                                 istack[jstack-1] = l;
 682                                 l = i;
 683                         }
 684                 }
 685         }
 686 }
 687
 688 #else
 689
 690 /* 8 bit Radix sort + insertion sort
 691  *
 692  * based on code from http://www.cubic.org/docs/radix.htm
 693  * with improvements by ebackes@symas.com and hyc@symas.com
 694  *
 695  * This code is O(n) but has a relatively high constant factor. For lists
 696  * up to ~50 Quicksort is slightly faster; up to ~100 they are even.
 697  * Much faster than quicksort for lists longer than ~100. Insertion
 698  * sort is actually superior for lists <50.
 699  */
 700
 701 #define BUCKETS (1<<8)
 702 #define SMALL   50
 703
 704 void
 705 wt_idl_sort( ID *ids, ID *tmp )
 706 {
 707         int count, soft_limit, phase = 0, size = ids[0];
 708         ID *idls[2];
 709         unsigned char *maxv = (unsigned char *)&ids[size];
 710
 711         if ( WT_IDL_IS_RANGE( ids ))
 712                 return;
 713
 714         /* Use insertion sort for small lists */
 715         if ( size <= SMALL ) {
 716                 int i,j;
 717                 ID a;
 718
 719                 for (j=1;j<=size;j++) {
 720                         a = ids[j];
 721                         for (i=j-1;i>=1;i--) {
 722                                 if (ids[i] <= a) break;
 723                                 ids[i+1] = ids[i];
 724                         }
 725                         ids[i+1] = a;
 726                 }
 727                 return;
 728         }
 729
 730         tmp[0] = size;
 731         idls[0] = ids;
 732         idls[1] = tmp;
 733
 734 #if BYTE_ORDER == BIG_ENDIAN
 735     for (soft_limit = 0; !maxv[soft_limit]; soft_limit++);
 736 #else
 737     for (soft_limit = sizeof(ID)-1; !maxv[soft_limit]; soft_limit--);
 738 #endif
 739
 740         for (
 741 #if BYTE_ORDER == BIG_ENDIAN
 742         count = sizeof(ID)-1; count >= soft_limit; --count
 743 #else
 744         count = 0; count <= soft_limit; ++count
 745 #endif
 746         ) {
 747                 unsigned int num[BUCKETS], * np, n, sum;
 748                 int i;
 749         ID *sp, *source, *dest;
 750         unsigned char *bp, *source_start;
 751
 752                 source = idls[phase]+1;
 753                 dest = idls[phase^1]+1;
 754                 source_start =  ((unsigned char *) source) + count;
 755
 756         np = num;
 757         for ( i = BUCKETS; i > 0; --i ) *np++ = 0;
 758
 759                 /* count occurences of every byte value */
 760                 bp = source_start;
 761         for ( i = size; i > 0; --i, bp += sizeof(ID) )
 762                                 num[*bp]++;
 763
 764                 /* transform count into index by summing elements and storing
 765                  * into same array
 766                  */
 767         sum = 0;
 768         np = num;
 769         for ( i = BUCKETS; i > 0; --i ) {
 770                 n = *np;
 771                 *np++ = sum;
 772                 sum += n;
 773         }
 774
 775                 /* fill dest with the right values in the right place */
 776                 bp = source_start;
 777         sp = source;
 778         for ( i = size; i > 0; --i, bp += sizeof(ID) ) {
 779                 np = num + *bp;
 780                 dest[*np] = *sp++;
 781                 ++(*np);
 782         }
 783                 phase ^= 1;
 784         }
 785
 786         /* copy back from temp if needed */
 787         if ( phase ) {
 788                 ids++; tmp++;
 789                 for ( count = 0; count < size; ++count )
 790                         *ids++ = *tmp++;
 791         }
 792 }
 793 #endif  /* Quick vs Radix */
 794