summaryrefslogtreecommitdiff
path: root/jam-files/engine/lists.c
diff options
context:
space:
mode:
authorPatrick Simianer <simianer@cl.uni-heidelberg.de>2012-05-13 03:35:30 +0200
committerPatrick Simianer <simianer@cl.uni-heidelberg.de>2012-05-13 03:35:30 +0200
commit670a8f984fc6d8342180c59ae9e96b0b76f34d3d (patch)
tree9f2ce7eec1a77e56b3bb1ad0ad40f212d7a996b0 /jam-files/engine/lists.c
parenteb3ee28dc0eb1d3e5ed01ba0df843be329ae450d (diff)
parent2f64af3e06a518b93f7ca2c30a9d0aeb2c947031 (diff)
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'jam-files/engine/lists.c')
-rw-r--r--jam-files/engine/lists.c339
1 files changed, 339 insertions, 0 deletions
diff --git a/jam-files/engine/lists.c b/jam-files/engine/lists.c
new file mode 100644
index 00000000..ebabb63e
--- /dev/null
+++ b/jam-files/engine/lists.c
@@ -0,0 +1,339 @@
+/*
+ * Copyright 1993, 1995 Christopher Seiwald.
+ *
+ * This file is part of Jam - see jam.c for Copyright information.
+ */
+
+# include "jam.h"
+# include "newstr.h"
+# include "lists.h"
+
+/*
+ * lists.c - maintain lists of strings
+ *
+ * This implementation essentially uses a singly linked list, but
+ * guarantees that the head element of every list has a valid pointer
+ * to the tail of the list, so the new elements can efficiently and
+ * properly be appended to the end of a list.
+ *
+ * To avoid massive allocation, list_free() just tacks the whole freed
+ * chain onto freelist and list_new() looks on freelist first for an
+ * available list struct. list_free() does not free the strings in the
+ * chain: it lazily lets list_new() do so.
+ *
+ * 08/23/94 (seiwald) - new list_append()
+ * 09/07/00 (seiwald) - documented lol_*() functions
+ */
+
+static LIST *freelist = 0; /* junkpile for list_free() */
+
+/*
+ * list_append() - append a list onto another one, returning total
+ */
+
+LIST * list_append( LIST * l, LIST * nl )
+{
+ if ( !nl )
+ {
+ /* Just return l */
+ }
+ else if ( !l )
+ {
+ l = nl;
+ }
+ else
+ {
+ /* Graft two non-empty lists. */
+ l->tail->next = nl;
+ l->tail = nl->tail;
+ }
+
+ return l;
+}
+
+/*
+ * list_new() - tack a string onto the end of a list of strings
+ */
+
+LIST * list_new( LIST * head, char * string )
+{
+ LIST * l;
+
+ if ( DEBUG_LISTS )
+ printf( "list > %s <\n", string );
+
+ /* Get list struct from freelist, if one available. */
+ /* Otherwise allocate. */
+ /* If from freelist, must free string first */
+
+ if ( freelist )
+ {
+ l = freelist;
+ freestr( l->string );
+ freelist = freelist->next;
+ }
+ else
+ {
+ l = (LIST *)BJAM_MALLOC( sizeof( LIST ) );
+ }
+
+ /* If first on chain, head points here. */
+ /* If adding to chain, tack us on. */
+ /* Tail must point to this new, last element. */
+
+ if ( !head ) head = l;
+ else head->tail->next = l;
+ head->tail = l;
+ l->next = 0;
+
+ l->string = string;
+
+ return head;
+}
+
+
+/*
+ * list_copy() - copy a whole list of strings (nl) onto end of another (l).
+ */
+
+LIST * list_copy( LIST * l, LIST * nl )
+{
+ for ( ; nl; nl = list_next( nl ) )
+ l = list_new( l, copystr( nl->string ) );
+ return l;
+}
+
+
+/*
+ * list_sublist() - copy a subset of a list of strings.
+ */
+
+LIST * list_sublist( LIST * l, int start, int count )
+{
+ LIST * nl = 0;
+ for ( ; l && start--; l = list_next( l ) );
+ for ( ; l && count--; l = list_next( l ) )
+ nl = list_new( nl, copystr( l->string ) );
+ return nl;
+}
+
+
+static int str_ptr_compare( void const * va, void const * vb )
+{
+ char * a = *( (char * *)va );
+ char * b = *( (char * *)vb );
+ return strcmp(a, b);
+}
+
+
+LIST * list_sort( LIST * l )
+{
+ int len;
+ int ii;
+ char * * strings;
+ LIST * listp;
+ LIST * result = 0;
+
+ if ( !l )
+ return L0;
+
+ len = list_length( l );
+ strings = (char * *)BJAM_MALLOC( len * sizeof(char*) );
+
+ listp = l;
+ for ( ii = 0; ii < len; ++ii )
+ {
+ strings[ ii ] = listp->string;
+ listp = listp->next;
+ }
+
+ qsort( strings, len, sizeof( char * ), str_ptr_compare );
+
+ for ( ii = 0; ii < len; ++ii )
+ result = list_append( result, list_new( 0, strings[ ii ] ) );
+
+ BJAM_FREE( strings );
+
+ return result;
+}
+
+
+/*
+ * list_free() - free a list of strings
+ */
+
+void list_free( LIST * head )
+{
+ /* Just tack onto freelist. */
+ if ( head )
+ {
+ head->tail->next = freelist;
+ freelist = head;
+ }
+}
+
+
+/*
+ * list_pop_front() - remove the front element from a list of strings
+ */
+
+LIST * list_pop_front( LIST * l )
+{
+ LIST * result = l->next;
+ if ( result )
+ {
+ result->tail = l->tail;
+ l->next = L0;
+ l->tail = l;
+ }
+ list_free( l );
+ return result;
+}
+
+
+/*
+ * list_print() - print a list of strings to stdout
+ */
+
+void list_print( LIST * l )
+{
+ LIST * p = 0;
+ for ( ; l; p = l, l = list_next( l ) )
+ if ( p )
+ printf( "%s ", p->string );
+ if ( p )
+ printf( "%s", p->string );
+}
+
+
+/*
+ * list_length() - return the number of items in the list
+ */
+
+int list_length( LIST * l )
+{
+ int n = 0;
+ for ( ; l; l = list_next( l ), ++n );
+ return n;
+}
+
+
+int list_in( LIST * l, char * value )
+{
+ for ( ; l; l = l->next )
+ if ( strcmp( l->string, value ) == 0 )
+ return 1;
+ return 0;
+}
+
+
+LIST * list_unique( LIST * sorted_list )
+{
+ LIST * result = 0;
+ LIST * last_added = 0;
+
+ for ( ; sorted_list; sorted_list = sorted_list->next )
+ {
+ if ( !last_added || strcmp( sorted_list->string, last_added->string ) != 0 )
+ {
+ result = list_new( result, sorted_list->string );
+ last_added = sorted_list;
+ }
+ }
+ return result;
+}
+
+
+/*
+ * lol_init() - initialize a LOL (list of lists).
+ */
+
+void lol_init( LOL * lol )
+{
+ lol->count = 0;
+}
+
+
+/*
+ * lol_add() - append a LIST onto an LOL.
+ */
+
+void lol_add( LOL * lol, LIST * l )
+{
+ if ( lol->count < LOL_MAX )
+ lol->list[ lol->count++ ] = l;
+}
+
+
+/*
+ * lol_free() - free the LOL and its LISTs.
+ */
+
+void lol_free( LOL * lol )
+{
+ int i;
+ for ( i = 0; i < lol->count; ++i )
+ list_free( lol->list[ i ] );
+ lol->count = 0;
+}
+
+
+/*
+ * lol_get() - return one of the LISTs in the LOL.
+ */
+
+LIST * lol_get( LOL * lol, int i )
+{
+ return i < lol->count ? lol->list[ i ] : 0;
+}
+
+
+/*
+ * lol_print() - debug print LISTS separated by ":".
+ */
+
+void lol_print( LOL * lol )
+{
+ int i;
+
+ for ( i = 0; i < lol->count; ++i )
+ {
+ if ( i )
+ printf( " : " );
+ list_print( lol->list[ i ] );
+ }
+}
+
+#ifdef HAVE_PYTHON
+
+PyObject *list_to_python(LIST *l)
+{
+ PyObject *result = PyList_New(0);
+
+ for (; l; l = l->next)
+ {
+ PyObject* s = PyString_FromString(l->string);
+ PyList_Append(result, s);
+ Py_DECREF(s);
+ }
+
+ return result;
+}
+
+LIST *list_from_python(PyObject *l)
+{
+ LIST * result = 0;
+
+ Py_ssize_t i, n;
+ n = PySequence_Size(l);
+ for (i = 0; i < n; ++i)
+ {
+ PyObject *v = PySequence_GetItem(l, i);
+ result = list_new (result, newstr (PyString_AsString(v)));
+ Py_DECREF(v);
+ }
+
+ return result;
+}
+
+#endif