00001 /*
00002  * Copyright 1993, 1995 Christopher Seiwald.
00003  *
00004  * This file is part of Jam - see jam.c for Copyright information.
00005  */
00006 
00007 # include "jam.h"
00008 # include "newstr.h"
00009 # include "lists.h"
00010 
00011 /*
00012  * lists.c - maintain lists of strings
00013  *
00014  * This implementation essentially uses a singly linked list, but
00015  * guarantees that the head element of every list has a valid pointer
00016  * to the tail of the list, so the new elements can efficiently and 
00017  * properly be appended to the end of a list.
00018  *
00019  * To avoid massive allocation, list_free() just tacks the whole freed
00020  * chain onto freelist and list_new() looks on freelist first for an
00021  * available list struct.  list_free() does not free the strings in the 
00022  * chain: it lazily lets list_new() do so.
00023  *
00024  * 08/23/94 (seiwald) - new list_append()
00025  * 09/07/00 (seiwald) - documented lol_*() functions
00026  */
00027 
00028 static LIST *freelist = 0;      /* junkpile for list_free() */
00029 
00030 /*
00031  * list_append() - append a list onto another one, returning total
00032  */
00033 
00034 LIST *
00035 list_append( 
00036         LIST    *l,
00037         LIST    *nl )
00038 {
00039         if( !nl )
00040         {
00041             /* Just return l */
00042         }
00043         else if( !l )
00044         {
00045             l = nl;
00046         }
00047         else
00048         {
00049             /* Graft two non-empty lists. */
00050             l->tail->next = nl;
00051             l->tail = nl->tail;
00052         }
00053 
00054         return l;
00055 }
00056 
00057 /*
00058  * list_new() - tack a string onto the end of a list of strings
00059  */
00060 
00061 LIST *
00062 list_new( 
00063         LIST    *head,
00064         char    *string )
00065 {
00066         LIST *l;
00067 
00068         if( DEBUG_LISTS )
00069             printf( "list > %s <\n", string );
00070 
00071         /* Get list struct from freelist, if one available.  */
00072         /* Otherwise allocate. */
00073         /* If from freelist, must free string first */
00074 
00075         if( freelist )
00076         {
00077             l = freelist;
00078             freestr( l->string );
00079             freelist = freelist->next;
00080         }
00081         else
00082         {
00083             l = (LIST *)malloc( sizeof( *l ) );
00084         }
00085 
00086         /* If first on chain, head points here. */
00087         /* If adding to chain, tack us on. */
00088         /* Tail must point to this new, last element. */
00089 
00090         if( !head ) head = l;
00091         else head->tail->next = l;
00092         head->tail = l;
00093         l->next = 0;
00094 
00095         l->string = string;
00096 
00097         return head;
00098 }
00099 
00100 /*
00101  * list_copy() - copy a whole list of strings (nl) onto end of another (l)
00102  */
00103 
00104 LIST *
00105 list_copy( 
00106         LIST    *l,
00107         LIST    *nl )
00108 {
00109         for( ; nl; nl = list_next( nl ) )
00110             l = list_new( l, copystr( nl->string ) );
00111 
00112         return l;
00113 }
00114 
00115 /*
00116  * list_sublist() - copy a subset of a list of strings
00117  */
00118 
00119 LIST *
00120 list_sublist( 
00121         LIST    *l,
00122         int     start,
00123         int     count )
00124 {
00125         LIST    *nl = 0;
00126 
00127         for( ; l && start--; l = list_next( l ) )
00128             ;
00129 
00130         for( ; l && count--; l = list_next( l ) )
00131             nl = list_new( nl, copystr( l->string ) );
00132 
00133         return nl;
00134 }
00135 
00136 LIST *
00137 list_sort(
00138     LIST *l)
00139 {
00140 
00141     LIST* first = 0;
00142     LIST* second = 0;
00143     LIST* merged = l;
00144     LIST* result;
00145 
00146     if (!l)
00147         return L0;
00148 
00149     for(;;) {
00150         
00151         /* Split the list in two */
00152         LIST** dst = &first;
00153         LIST* src = merged;
00154         
00155         for(;;) {
00156             
00157             *dst = list_append(*dst, list_new(0, src->string));
00158             
00159             if (!src->next)
00160                 break;
00161 
00162             if (strcmp(src->string, src->next->string) > 0) 
00163             {
00164                 if (dst == &first)
00165                     dst = &second;
00166                 else
00167                     dst = &first;
00168             }
00169             
00170             src = src->next;
00171         }
00172 
00173         if (merged != l)
00174             list_free( merged );
00175         merged = 0;
00176         
00177         if (second == 0) {
00178             result = first;
00179             break;
00180         }
00181 
00182         
00183         /* Merge lists 'first' and 'second' into 'merged' and free
00184            'first'/'second'. */
00185         {
00186             LIST* f = first;
00187             LIST* s = second;
00188 
00189             while(f && s)
00190             {
00191                 if (strcmp(f->string, s->string) < 0)
00192                 {
00193                     merged = list_append( merged, list_new(0, f->string ));
00194                     f = f->next;
00195                 }
00196                 else
00197                 {
00198                     merged = list_append( merged, list_new(0, s->string ));
00199                     s = s->next;
00200                 }
00201             }
00202 
00203             merged = list_copy( merged, f );
00204             merged = list_copy( merged, s );
00205             list_free( first );
00206             list_free( second );
00207             first = 0;
00208             second = 0;
00209         }                            
00210     }
00211 
00212     return result;
00213 }
00214 
00215 /*
00216  * list_free() - free a list of strings
00217  */
00218 
00219 void
00220 list_free( LIST *head )
00221 {
00222         /* Just tack onto freelist. */
00223 
00224         if( head )
00225         {
00226             head->tail->next = freelist;
00227             freelist = head;
00228         }
00229 }
00230 
00231 /*
00232  * list_pop_front() - remove the front element from a list of strings
00233  */
00234 LIST *  list_pop_front( LIST *l )
00235 {
00236     LIST * result = l->next;
00237     if( result )
00238     {
00239         result->tail = l->tail;
00240         l->next = L0;
00241         l->tail = l;
00242     }
00243     list_free( l );
00244     return result;
00245 }
00246 
00247 /*
00248  * list_print() - print a list of strings to stdout
00249  */
00250 
00251 void
00252 list_print( LIST *l )
00253 {
00254         LIST *p = 0; 
00255         for( ; l; p = l, l = list_next( l ) )
00256             if ( p ) 
00257                 printf( "%s ", p->string );
00258         if ( p )
00259             printf( "%s", p->string );                
00260 }
00261 
00262 /*
00263  * list_length() - return the number of items in the list
00264  */
00265 
00266 int
00267 list_length( LIST *l )
00268 {
00269         int n = 0;
00270 
00271         for( ; l; l = list_next( l ), ++n )
00272             ;
00273 
00274         return n;
00275 }
00276 
00277 /*
00278  * lol_init() - initialize a LOL (list of lists)
00279  */
00280 
00281 void
00282 lol_init( LOL *lol )
00283 {
00284     lol->count = 0;
00285 }
00286 
00287 /*
00288  * lol_add() - append a LIST onto an LOL
00289  */
00290 
00291 void
00292 lol_add( 
00293         LOL     *lol,
00294         LIST    *l )
00295 {
00296         if( lol->count < LOL_MAX )
00297             lol->list[ lol->count++ ] = l;
00298 }
00299 
00300 /*
00301  * lol_free() - free the LOL and its LISTs
00302  */
00303 
00304 void
00305 lol_free( LOL *lol )
00306 {
00307         int i;
00308 
00309         for( i = 0; i < lol->count; i++ )
00310             list_free( lol->list[i] );
00311 
00312         lol->count = 0;
00313 }
00314 
00315 /*
00316  * lol_get() - return one of the LISTs in the LOL
00317  */
00318 
00319 LIST *
00320 lol_get( 
00321         LOL     *lol,
00322         int     i )
00323 {
00324         return i < lol->count ? lol->list[i] : 0;
00325 }
00326 
00327 /*
00328  * lol_print() - debug print LISTS separated by ":"
00329  */
00330 
00331 void
00332 lol_print( LOL *lol )
00333 {
00334         int i;
00335 
00336         for( i = 0; i < lol->count; i++ )
00337         {
00338             if( i )
00339                 printf( " : " );
00340             list_print( lol->list[i] );
00341         }
00342 }