release/src/router/transmission/libtransmission/ptrarray.c

   1 /*
   2  * This file Copyright (C) Mnemosyne LLC
   3  *
   4  * This file is licensed by the GPL version 2. Works owned by the
   5  * Transmission project are granted a special exemption to clause 2(b)
   6  * so that the bulk of its code can remain under the MIT license.
   7  * This exemption does not extend to derived works not owned by
   8  * the Transmission project.
   9  *
  10  * $Id: ptrarray.c 12553 2011-07-17 14:33:20Z jordan $
  11  */
  12
  13 #include <assert.h>
  14 #include <stdlib.h> /* tr_renew() -> realloc() */
  15 #include <string.h> /* memmove */
  16
  17 #include "ptrarray.h"
  18 #include "utils.h"
  19
  20 #define FLOOR 32
  21
  22 const tr_ptrArray TR_PTR_ARRAY_INIT = { NULL, 0, 0 };
  23
  24 void
  25 tr_ptrArrayDestruct( tr_ptrArray * p, PtrArrayForeachFunc func )
  26 {
  27     assert( p );
  28     assert( p->items || !p->n_items );
  29
  30     if( func )
  31         tr_ptrArrayForeach( p, func );
  32
  33     tr_free( p->items );
  34
  35     memset( p, ~0, sizeof( tr_ptrArray ) );
  36 }
  37
  38 void
  39 tr_ptrArrayForeach( tr_ptrArray *       t,
  40                     PtrArrayForeachFunc func )
  41 {
  42     int i;
  43
  44     assert( t );
  45     assert( t->items || !t->n_items );
  46     assert( func );
  47
  48     for( i = 0; i < t->n_items; ++i )
  49         func( t->items[i] );
  50 }
  51
  52 void**
  53 tr_ptrArrayPeek( tr_ptrArray * t,
  54                  int *         size )
  55 {
  56     *size = t->n_items;
  57     return t->items;
  58 }
  59
  60 int
  61 tr_ptrArrayInsert( tr_ptrArray * t,
  62                    void        * ptr,
  63                    int           pos )
  64 {
  65     if( t->n_items >= t->n_alloc )
  66     {
  67         t->n_alloc = MAX( FLOOR, t->n_alloc * 2 );
  68         t->items = tr_renew( void*, t->items, t->n_alloc );
  69     }
  70
  71     if( pos < 0 || pos > t->n_items )
  72         pos = t->n_items;
  73     else
  74         memmove( t->items + pos + 1,
  75                  t->items + pos,
  76                  sizeof( void* ) * ( t->n_items - pos ) );
  77
  78     t->items[pos] = ptr;
  79     t->n_items++;
  80     return pos;
  81 }
  82
  83 void*
  84 tr_ptrArrayPop( tr_ptrArray* t )
  85 {
  86     void * ret = NULL;
  87
  88     if( t->n_items )
  89         ret = t->items[--t->n_items];
  90
  91     return ret;
  92 }
  93
  94 void
  95 tr_ptrArrayErase( tr_ptrArray * t,
  96                   int           begin,
  97                   int           end )
  98 {
  99     assert( begin >= 0 );
 100     if( end < 0 ) end = t->n_items;
 101     assert( begin < end );
 102     assert( end <= t->n_items );
 103
 104     memmove( t->items + begin,
 105              t->items + end,
 106              sizeof( void* ) * ( t->n_items - end ) );
 107
 108     t->n_items -= ( end - begin );
 109 }
 110
 111 /**
 112 ***
 113 **/
 114
 115 #ifndef NDEBUG
 116 static int
 117 lowerBound2( 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
 146 int
 147 tr_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( ;; )
 168         {
 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             }
 193         }
 194     }
 195
 196     assert( pos == lowerBound2( t, ptr, compare, &match_2 ) );
 197     assert( match == match_2 );
 198
 199     if( exact_match )
 200         *exact_match = match;
 201     return pos;
 202 }
 203
 204 static void
 205 assertSortedAndUnique( const tr_ptrArray * t UNUSED,
 206                        int compare(const void*, const void*) UNUSED )
 207 {
 208 #if 1
 209     int i;
 210
 211     for( i = 0; i < t->n_items - 2; ++i )
 212         assert( compare( t->items[i], t->items[i + 1] ) < 0 );
 213 #endif
 214 }
 215
 216 int
 217 tr_ptrArrayInsertSorted( tr_ptrArray * t,
 218                          void *        ptr,
 219                          int           compare(const void*, const void*) )
 220 {
 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 );
 230     return ret;
 231 }
 232
 233 void*
 234 tr_ptrArrayFindSorted( tr_ptrArray * t,
 235                        const void *  ptr,
 236                        int           compare(const void*, const void*) )
 237 {
 238     bool match = false;
 239     const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
 240     return match ? t->items[pos] : NULL;
 241 }
 242
 243 void*
 244 tr_ptrArrayRemoveSorted( tr_ptrArray * t,
 245                          const void  * ptr,
 246                          int           compare(const void*, const void*) )
 247 {
 248     bool match;
 249     void * ret = NULL;
 250     const int pos = tr_ptrArrayLowerBound( t, ptr, compare, &match );
 251     assertSortedAndUnique( t, compare );
 252
 253     if( match )
 254     {
 255         ret = t->items[pos];
 256         assert( compare( ret, ptr ) == 0 );
 257         tr_ptrArrayErase( t, pos, pos + 1 );
 258     }
 259     assertSortedAndUnique( t, compare );
 260     assert( ( ret == NULL ) || ( compare( ret, ptr ) == 0 ) );
 261     return ret;
 262 }