[Commit] nickle/examples Makefile.am, 1.1, 1.2 mutextest.5c, 1.7, 1.8 skiplist.5c, NONE, 1.1 skiplisttest.5c, NONE, 1.1

[Keith Packard]

Committed by: keithp

Update of /local/src/CVS/nickle/examples
In directory home.keithp.com:/tmp/cvs-serv4806/examples

Modified Files:
	Makefile.am mutextest.5c 
Added Files:
	skiplist.5c skiplisttest.5c 
Log Message:
2004-07-28  Keith Packard  <keithp at keithp.com>

	* configure.in:
	* main.c: (main):
	Unlimit stack so that GC can recurse forever
	
	* examples/Makefile.am:
	* examples/mutextest.5c:
	* examples/skiplist.5c:
	* examples/skiplisttest.5c:
	Add skiplists
	
	* gram.y:
	Fix precedence of ** so that ++x**2 works
	
	* hash.c: (HashEqual):
	Make sure hash element in table is valid before comparing

	* lex.l:
	Track newlines in files better.

	* test/orderofoptest.5c:
	Add comments about x value for each test.


Index: Makefile.am
===================================================================
RCS file: /local/src/CVS/nickle/examples/Makefile.am,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- Makefile.am	26 May 2004 08:01:42 -0000	1.1
+++ Makefile.am	29 Jul 2004 00:23:32 -0000	1.2
@@ -21,6 +21,8 @@
 	roman.5c \
 	rsa-demo.5c \
 	rsa.5c \
+	skiplist.5c \
+	skiplisttest.5c \
 	sort.5c
 
 exampledir=$(pkgdatadir)/examples

Index: mutextest.5c
===================================================================
RCS file: /local/src/CVS/nickle/examples/mutextest.5c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- mutextest.5c	25 Jul 2002 18:15:48 -0000	1.7
+++ mutextest.5c	29 Jul 2004 00:23:32 -0000	1.8
@@ -17,7 +17,7 @@
 mutex		owned_mutex = Mutex::new();
 semaphore	started = Semaphore::new (0);
 
-function status ()
+void status ()
 {
     int nt = dim (owned);
     int i;
@@ -36,7 +36,7 @@
     }
 }
 
-function t (*(named_mutex[*]) mutexes, int self, int delay)
+void t (*(named_mutex[*]) mutexes, int self, int delay)
 {
     int i;
     
@@ -62,7 +62,7 @@
     }
 }
 
-function start (int nthread, int nmut_ex, int delay)
+void start (int nthread, int nmut_ex, int delay)
 {
     int i;
 
@@ -84,7 +84,7 @@
     }
 }
 
-function monitor (int delay)
+void monitor (int delay)
 {
     for (;;)
     {

--- NEW FILE: skiplist.5c ---
(This appears to be a binary file; contents omitted.)

--- NEW FILE: skiplisttest.5c ---
autoload Skiplist;

int gt_count = "hi"; 

bool int_gt (int a, int b) {
    ++gt_count;
    return a > b;
}

public int[*] rand_array (int n)
{
    int[n] a = { [i] = i };
    PRNG::shuffle (&a);
    return a;
}

public void validate (Sortlist::List l) {
    bool    first = true;
    poly    prev;

    void visit (poly x)
    {
	if (!first)
	    assert (int_gt (x, prev), "list out of order");
	assert (x == Sortlist::search (l, x), "list missing element");
    }

    Sortlist::walk (l, visit);
}

public void insert_int (Sortlist::List l, int i) {
    Sortlist::insert (l, i);
}

public void insert_ints (Sortlist::List l, int[*] i) {
    for (int j = 0; j < dim(i); j++)
	insert_int (l, i[j]);
}

public Sortlist::List rand_ints (int n)
{
    Sortlist::List    l = Sortlist::new (int_gt);
    
    insert_ints (l, rand_array(n));
    return l;
}

public int search_len (Sortlist::List l, int i)
{
    int	old_count = gt_count;

    Sortlist::search (l, i);
    return gt_count - old_count;
}

public void dump (Sortlist::List l)
{
    for (bool (&poly) next = Sortlist::iterate (l);
	 next (&(int value));)
    {
	printf ("%4d", value);
	for (int i = Sortlist::storage (l, value); i > 0; i--)
	    printf (" |");
	printf ("\n");
    }
}

public void histogram (real[*] l)
{
    int	largest = 0;
    for (int i = 0; i < dim (l); i++)
	if (l[i] > largest)
	    largest = l[i];

    int width = 80 - 17;
    real scale = width / largest;

    for (int i = 0; i < dim (l); i++)
    {
	printf ("%5d %10g ", i, l[i]);
	int lim = floor (l[i] * scale + 0.5);
	for (int j = 0; j < lim; j++)
	    printf ("*");
	printf ("\n");
    }
}

public void analyse (Sortlist::List l)
{
    int[...]	store = {};
    int[...]	search = {};
    
    void inc_array(&int[...] a, int i) {
	while (dim(a) <= i)
	    a[dim(a)] = 0;
	a[i]++;
    }

    for (bool (&poly) next = Sortlist::iterate (l); next (&(int value));)
    {
	inc_array (&store, Sortlist::storage (l, value));
	inc_array (&search, search_len (l, value));
    }

    printf ("storage distribution\n");
    histogram (store);
    
    printf ("search distribution\n");
    histogram (search);
}