ll.c

Go to the documentation of this file.
00001 
00009 #include "ctl/ctldef.h"
00010 #include "ctl/ll.h"
00011 
00012 #ifndef CTL_UNIT
00013 #else /* CTL_UNIT */
00014 #include "unit/unit.h"
00015 
00016 /*
00017  * Declars something linked two ways (may be in two lists at once)
00018  */
00019 typedef struct TestThing
00020 {
00021     sll_decllink( struct TestThing, t1next );
00022     sll_decllink( struct TestThing, t2next );
00023     int value;
00024 } TestThing;
00025 
00026 int BIGGER( const TestThing* t1 ,const TestThing* t2 ) { return (t1)->value - (t2)->value; }
00027 #define deref_Sort(val) val
00028 sll_mfg_qsort(TestThing,t1next, test1, deref_Sort, Sort1);
00029 
00036 void Test_SLL(void)
00037 {
00038     TestThing   a1[30];
00039     TestThing   leftover;
00040     sll_decllist(TestThing,t1next, test1);
00041     sll_decllist(TestThing,t2next, test2);
00042     sll_decllist(TestThing,t1next, scratch1);
00043     sll_decllist(TestThing,t2next, scratch2);
00044     sll_initlist(TestThing,t1next, scratch1);
00045     sll_initlist(TestThing,t2next, scratch2);
00046 
00047     {
00048         array_foreach( TestThing, a1, curr )
00049         {
00050             curr->value = (int)indexof(a1,curr);
00051         }
00052     }
00053 
00054     sll_initarray(TestThing,t1next, test1, a1, countof(a1));
00055     sll_initarray(TestThing,t2next, test2, a1, countof(a1));
00056 
00057     {
00058         size_t count;
00059         sll_size(TestThing,t1next, test1, count);
00060         Test_Error( count == countof(a1) );
00061         sll_size(TestThing,t1next, test2, count);
00062         Test_Error( count == countof(a1) );
00063     }
00064 
00065     {
00066         sll_foreach_deletable_reverse(TestThing,t1next, test1, fwd )
00067         {
00068             /*printf( "%d ", fwd->value ); */
00069         }
00070         /*printf( "\n" ); */
00071     }
00072     {
00073         sll_foreach_deletable_reverse(TestThing,t1next, test1, fwd )
00074         {
00075             /*printf( "%d ", fwd->value ); */
00076         }
00077         /*printf( "\n" ); */
00078     }
00079 
00080     #define ODD(v)  ((v)->value & 1)
00081     sll_remove_filter(TestThing,t1next, test1, ODD );
00082 
00083     #define EVEN(v) !((v)->value & 1)
00084     sll_remove_filter(TestThing,t2next, test2, EVEN );
00085     {
00086         size_t count;
00087         sll_size(TestThing,t1next, test1, count);
00088         Test_Error( count == countof(a1)/2 );
00089         sll_size(TestThing,t2next, test2, count);
00090         Test_Error( count == countof(a1)/2 );
00091     }
00092     /* See if odd-filtered array is all odd, now */
00093     {
00094         sll_foreach(TestThing,t1next, test1, fwd )
00095         {
00096             /*printf( "%d ", fwd->value ); */
00097             Test_Error( !(fwd->value & 1) );
00098         }
00099         /*printf( "\n" ); */
00100     }
00101     /* See if even filtered array is all even, now */
00102     {
00103         sll_foreach(TestThing,t2next, test2, fwd )
00104         {
00105             /*printf( "%d ", fwd->value ); */
00106             Test_Error( fwd->value & 1 );
00107         }
00108         /*printf( "\n" ); */
00109     }
00110     /*printf( "\n" ); */
00111 
00112     /* Re-init pool from scratch */
00113     sll_initarray(TestThing,t1next, test1, a1, countof(a1));
00114     sll_initarray(TestThing,t2next, test2, a1, countof(a1));
00115 
00116 /*  #define ODD(v)  ((v)->value & 1) */
00117     sll_move_filter(TestThing,t1next, test1, ODD, scratch1 );
00118     sll_splice(TestThing,t1next, test1, scratch1);
00119 
00120 /*  #define EVEN(v) !((v)->value & 1) */
00121     sll_move_filter(TestThing,t2next, test2, EVEN, scratch2 );
00122     sll_splice(TestThing,t2next, test2, scratch2);
00123     {
00124         size_t count;
00125         sll_size(TestThing,t1next, test1, count);
00126         Test_Error( count == countof(a1) );
00127         sll_size(TestThing,t2next, test2, count);
00128         Test_Error( count == countof(a1) );
00129     }
00130     leftover.value = -1;
00131     leftover.t1next = leftover.t2next = NULL;
00132     sll_push_back( TestThing,t1next, test1, &leftover );
00133     
00134     sll_qsort(TestThing,t1next, test1, Sort1, BIGGER);
00135     #define SMALLER(t1,t2) ((t2)->value - (t1)->value)
00136     sll_bsort(TestThing,t2next, test2, SMALLER );
00137     /* See if both arrays are sorted. */
00138     {
00139         int prev = -1000;
00140         sll_foreach(TestThing,t1next, test1, fwd )
00141         {
00142             Test_Error( prev < fwd->value );
00143             /*printf( "%d ", fwd->value ); */
00144             prev = fwd->value;
00145         }
00146         /*printf( "\n\n" ); */
00147     }
00148     /* See if even filtered array is all even, now */
00149     {
00150         int prev = 1+countof(a1);
00151         sll_foreach(TestThing,t2next, test2, fwd )
00152         {
00153             Test_Error( prev > fwd->value );
00154             /*printf( "%d ", fwd->value ); */
00155             prev = fwd->value;
00156         }
00157         /*printf( "\n" ); */
00158     }
00159 
00160 #undef ODD
00161 #undef EVEN
00162 #undef SMALLER
00163 }
00164 
00165 /*
00166  * Declars something doubly linked two ways (may be in two lists at once)
00167  */
00168 typedef struct TestThing2
00169 {
00170     dll_decllink( struct TestThing2, t1 );
00171     dll_decllink( struct TestThing2, t2 );
00172     int value;
00173 } TestThing2;
00174 
00175 int BIGGER2( const TestThing2* t1 ,const TestThing2* t2 ) { return (t1)->value - (t2)->value; }
00176 dll_mfg_qsort(TestThing2,t1, test3, deref_Sort, DSort);
00177 
00184 void Test_DLL(void)
00185 {
00186     TestThing2  a1[30];
00187     dll_decllist(TestThing2,t1, test1);
00188     dll_decllist(TestThing2,t2, test2);
00189 
00190     {
00191         array_foreach( TestThing2, a1, curr )
00192         {
00193             curr->value = (int)indexof(a1,curr);
00194             dll_initlink(struct TestThing2, t1, curr);
00195             dll_initlink(struct TestThing2, t2, curr);
00196         }
00197     }
00198 
00199     /* Fill up the lists */
00200     dll_initarray(TestThing2,t1, test1, a1,countof(a1));
00201     dll_initarray(TestThing2,t2, test2, a1,countof(a1));
00202 
00203     {
00204         size_t count;
00205         dll_size(TestThing2,t1, test1, count);
00206         Test_Error( count == countof(a1) );
00207         dll_size(TestThing2,t1, test2, count);
00208         Test_Error( count == countof(a1) );
00209     }
00210 
00211     #define ODD(v)  ((v)->value & 1)
00212     dll_remove_filter(TestThing2,t1, test1, ODD );
00213 
00214     #define EVEN(v) !((v)->value & 1)
00215     dll_remove_filter(TestThing2,t2, test2, EVEN );
00216 
00217     /* See if odd-filtered array is all odd, now */
00218     {
00219         dll_foreach(TestThing2,t1, test1, fwd )
00220         {
00221             /*printf( "%d ", fwd->value ); */
00222             Test_Error( !(fwd->value & 1) );
00223         }
00224         /*printf( "\n" ); */
00225     }
00226     /* See if even filtered array is all even, now */
00227     {
00228         dll_foreach(TestThing2,t2, test2, fwd )
00229         {
00230             /*printf( "%d ", fwd->value ); */
00231             Test_Error( fwd->value & 1 );
00232         }
00233         /*printf( "\n" ); */
00234     }
00235     /*printf( "\n" ); */
00236 
00237     {
00238         dll_decllist(TestThing2,t1, test3);
00239         dll_initlist(TestThing2,t1, test3);
00240 
00241         dll_splice(TestThing2,t1, test3, test1);
00242         {
00243             size_t count;
00244             dll_size(TestThing2,t1, test3, count);
00245             Test_Error( count == countof(a1)/2 );
00246         }
00247         #define FAIL_SANITY( failure, front,back, curr ) printf( "List link sanity failure: %s %p %p %p\n", failure, front,back, curr );
00248         Test_Error( dll_check(TestThing2,t1, test3 ) );
00249         dll_check_thorough(TestThing2,t1, test3, FAIL_SANITY );
00250         {
00251             dll_foreach(TestThing2,t1, test3, fwd )
00252             {
00253                 /*printf( "%d ", fwd->value ); */
00254             }
00255             /*printf( "\n" ); */
00256         }
00257         {
00258             dll_foreach_deletable(TestThing2,t2, test2, victim )
00259             {
00260                 dll_erase(TestThing2,t2, test2, victim );
00261                 dll_push_back(TestThing2,t1, test3, victim);
00262             }
00263             dll_check_thorough(TestThing2,t1, test3, FAIL_SANITY );
00264         }
00265         {
00266             size_t count;
00267             dll_size(TestThing2,t1, test3, count);
00268             Test_Error( count == countof(a1) );
00269         }
00270         dll_qsort(TestThing2,t1, test3, DSort, BIGGER2)
00271         dll_check_thorough(TestThing2,t1, test3, FAIL_SANITY );
00272         {
00273             size_t count;
00274             dll_size(TestThing2,t1, test3, count);
00275             Test_Error( count == countof(a1) );
00276         }
00277         /*printf( "Sorted?\n" ); */
00278         {
00279             int prev = -1;
00280             dll_foreach(TestThing2,t1, test3, fwd )
00281             {
00282                 Test_Error( prev < fwd->value );
00283                 /*printf( "%d ", fwd->value ); */
00284                 prev = fwd->value;
00285 
00286             }
00287             /*printf( "\n" ); */
00288         }
00289         {
00290             int prev = 1+countof(a1);
00291             dll_foreach_reverse(TestThing2,t1, test3, rev )
00292             {
00293                 Test_Error( prev > rev->value );
00294                 /*printf( "%d ", rev->value ); */
00295                 prev = rev->value;
00296             }
00297             /*printf( "\n" ); */
00298         }
00299         
00300         /* Invoke "rebuilds" on list and see that it's all kosher */
00301         dll_initarray(TestThing2,t2, test2, a1,countof(a1));
00302         dll_assert_size(TestThing2,t2, test2, countof(a1));
00303         dll_rebuild_back(TestThing2,t2, test2 );
00304         dll_rebuild_front(TestThing2,t2, test2 );
00305         dll_check_thorough(TestThing2,t1, test3, FAIL_SANITY );
00306         dll_assert_size(TestThing2,t2, test2, countof(a1));
00307     }
00308 #undef ODD
00309 #undef EVEN
00310 #undef FAIL_SANITY
00311     {
00312         array_foreach( TestThing2, a1, curr )
00313         {
00314             curr->value = (int)indexof(a1,curr);
00315             dll_initlink(struct TestThing2, t1, curr);
00316             dll_initlink(struct TestThing2, t2, curr);
00317         }
00318     }
00319 }
00320 
00321 
00322 #endif /* CTL_UNIT */
00323 

Generated on Fri Jan 2 15:28:34 2009 for Squat by  doxygen 1.5.6