Ignore:
Timestamp:
Jun 24, 2011, 6:25:56 PM (10 years ago)
Author:
jordan
Message:

(trunk libT) the edge condition bug in ptrarray's bsearch code seems to be fixed, so let's commit the fix with lots of assert()ions enabled so that the nightly build users can show me where I'm wrong :)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/libtransmission/ptrarray.c

    r12204 r12512  
    1212
    1313#include <assert.h>
    14 #include <stdlib.h>
     14#include <stdlib.h> /* tr_renew() -> realloc() */
    1515#include <string.h> /* memmove */
    1616
     
    103103
    104104    memmove( t->items + begin,
    105             t->items + end,
    106             sizeof( void* ) * ( t->n_items - end ) );
     105             t->items + end,
     106             sizeof( void* ) * ( t->n_items - end ) );
    107107
    108108    t->n_items -= ( end - begin );
     
    113113**/
    114114
     115#ifndef NDEBUG
     116static int
     117lowerBound2( const tr_ptrArray * t,
     118             const void * ptr,
     119             int compare( const void *, const void * ),
     120             bool * exact_match )
     121{
     122    int i;
     123    const int len = t->n_items;
     124
     125    for( i=0; i<len; ++i )
     126    {
     127        const int c = compare( t->items[i], ptr );
     128
     129        if( c == 0 ) {
     130            *exact_match = true;
     131            return i;
     132        }
     133
     134        if( c < 0 )
     135            continue;
     136
     137        *exact_match = false;
     138        return i;
     139    }
     140
     141    *exact_match = false;
     142    return len;
     143}
     144#endif
     145
    115146int
    116 tr_ptrArrayLowerBound( const tr_ptrArray *                t,
    117                        const void *                       ptr,
    118                        int                 compare( const void *,
    119                                                     const void * ),
    120                        bool *                    exact_match )
    121 {
    122     int len = t->n_items;
    123     int first = 0;
    124 
    125     while( len > 0 )
    126     {
    127         int       half = len / 2;
    128         int       middle = first + half;
    129         const int c = compare( t->items[middle], ptr );
    130         if( c < 0 )
     147tr_ptrArrayLowerBound( const tr_ptrArray  * t,
     148                       const void         * ptr,
     149                       int                  compare( const void *, const void * ),
     150                       bool               * exact_match )
     151{
     152    int pos = -1;
     153    bool match = false;
     154#ifndef NDEBUG
     155    bool match_2;
     156#endif
     157
     158    if( t->n_items == 0 )
     159    {
     160        pos = 0;
     161    }
     162    else
     163    {
     164        int first = 0;
     165        int last = t->n_items - 1;
     166
     167        for( ;; )
    131168        {
    132             first = middle + 1;
    133             len = len - half - 1;
     169            const int half = (last - first) / 2;
     170            const int c = compare( t->items[first + half], ptr );
     171
     172            if( c < 0 ) {
     173                const int new_first = first + half + 1;
     174                if( new_first > last ) {
     175                    pos = new_first;
     176                    break;
     177                }
     178                first = new_first;
     179            }
     180            else if( c > 0 ) {
     181                const int new_last = first + half - 1;
     182                if( new_last < first ) {
     183                    pos = first;
     184                    break;
     185                }
     186                last = new_last;
     187            }
     188            else {
     189                match = true;
     190                pos = first + half;
     191                break;
     192            }
    134193        }
    135         else if( !c )
    136         {
    137             if( exact_match )
    138                 *exact_match = true;
    139             return middle;
    140             break;
    141         }
    142         else
    143         {
    144             len = half;
    145         }
    146     }
     194    }
     195
     196    assert( pos == lowerBound2( t, ptr, compare, &match_2 ) );
     197    assert( match == match_2 );
    147198
    148199    if( exact_match )
    149         *exact_match = false;
    150 
    151     return first;
    152 }
    153 
    154 #ifdef NDEBUG
    155 #define assertSortedAndUnique(a,b)
    156 #else
     200        *exact_match = match;
     201    return pos;
     202}
     203
    157204static void
    158205assertSortedAndUnique( const tr_ptrArray * t,
    159206                    int compare(const void*, const void*) )
    160207{
     208#if 1
    161209    int i;
    162210
    163211    for( i = 0; i < t->n_items - 2; ++i )
    164         assert( compare( t->items[i], t->items[i + 1] ) <= 0 );
    165 }
     212        assert( compare( t->items[i], t->items[i + 1] ) < 0 );
    166213#endif
     214}
    167215
    168216int
     
    171219                         int           compare(const void*, const void*) )
    172220{
    173     const int pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
    174     const int ret = tr_ptrArrayInsert( t, ptr, pos );
    175 
    176     //assertSortedAndUnique( t, compare );
     221    int pos;
     222    int ret;
     223
     224    assertSortedAndUnique( t, compare );
     225
     226    pos = tr_ptrArrayLowerBound( t, ptr, compare, NULL );
     227    ret = tr_ptrArrayInsert( t, ptr, pos );
     228
     229    assertSortedAndUnique( t, compare );
    177230    return ret;
    178231}
     
    183236                       int           compare(const void*, const void*) )
    184237{
    185     bool   match;
     238    bool match = false;
    186239    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
    187 
    188240    return match ? t->items[pos] : NULL;
    189241}
     
    194246                         int           compare(const void*, const void*) )
    195247{
    196     void *    ret = NULL;
    197     bool   match;
     248    bool match;
     249    void * ret = NULL;
    198250    const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
     251    assertSortedAndUnique( t, compare );
    199252
    200253    if( match )
    201254    {
    202255        ret = t->items[pos];
     256        assert( compare( ret, ptr ) == 0 );
    203257        tr_ptrArrayErase( t, pos, pos + 1 );
    204258    }
    205259    assertSortedAndUnique( t, compare );
     260    assert( ( ret == NULL ) || ( compare( ret, ptr ) == 0 ) );
    206261    return ret;
    207262}
Note: See TracChangeset for help on using the changeset viewer.