GNOME.org
 

[genius] Mon Mar 28 18:17:52 2011 Jiri (George) Lebl <jirka 5z com>

commit 4394dccfa2ed49284aaa51bc514b6557067f8492
Author: Jiri (George) Lebl <jirka 5z com>
Date:   Mon Mar 28 18:18:02 2011 -0700

    Mon Mar 28 18:17:52 2011  Jiri (George) Lebl <jirka 5z com>
    
    	* src/calc.h, src/funclib.c, src/matrix.[ch],
    	  src/genius-readline-helper.c, ve/ve-config.c, src/graphing.c:
    	  Bunch of optimizations.  Use GQueues where useful, drop use of
    	  g_ptr_array for matrices which saves a tiny bit of overhead and
    	  will allow graceful handling of out of memory problems rather than
    	  just crashing.  Optimize Combinations/Permutations quite a bit.
    
    	* src/geniustests.txt: add some tests.

 ChangeLog                    |   11 +++++
 src/calc.h                   |    4 +-
 src/funclib.c                |  101 +++++++++++++++++++++++++++++++-----------
 src/genius-readline-helper.c |   30 +++++++++++--
 src/geniustests.txt          |    6 +++
 src/graphing.c               |   21 ++++-----
 src/matrix.c                 |   60 ++++++++++++-------------
 src/matrix.h                 |    6 +-
 ve/ve-config.c               |   18 +++-----
 9 files changed, 168 insertions(+), 89 deletions(-)
---
diff --git a/ChangeLog b/ChangeLog
index c64a9a9..b7a6ffd 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+Mon Mar 28 18:17:52 2011  Jiri (George) Lebl <jirka 5z com>
+
+	* src/calc.h, src/funclib.c, src/matrix.[ch],
+	  src/genius-readline-helper.c, ve/ve-config.c, src/graphing.c:
+	  Bunch of optimizations.  Use GQueues where useful, drop use of
+	  g_ptr_array for matrices which saves a tiny bit of overhead and
+	  will allow graceful handling of out of memory problems rather than
+	  just crashing.  Optimize Combinations/Permutations quite a bit.
+
+	* src/geniustests.txt: add some tests.
+
 Wed Feb 16 21:12:34 2011  Jiri (George) Lebl <jirka 5z com>
 
 	* src/gnome-genius.c: try gnome-help if gtk_open_uri don't work (am
diff --git a/src/calc.h b/src/calc.h
index 93b86bf..4501852 100644
--- a/src/calc.h
+++ b/src/calc.h
@@ -1,5 +1,5 @@
 /* GENIUS Calculator
- * Copyright (C) 1997-2010 Jiri (George) Lebl
+ * Copyright (C) 1997-2011 Jiri (George) Lebl
  *
  * Author: Jiri (George) Lebl
  *
@@ -29,7 +29,7 @@
 
 #include "structs.h"
 
-#define GENIUS_COPYRIGHT_STRING N_("Copyright (C) 1997-2010 JiÅ?í (George) Lebl, Ph.D.")
+#define GENIUS_COPYRIGHT_STRING N_("Copyright (C) 1997-2011 JiÅ?í (George) Lebl, Ph.D.")
 
 typedef enum {
 	GEL_NO_ERROR = 0,
diff --git a/src/funclib.c b/src/funclib.c
index 148558b..6147ace 100644
--- a/src/funclib.c
+++ b/src/funclib.c
@@ -1,5 +1,5 @@
 /* GENIUS Calculator
- * Copyright (C) 1997-2010 Jiri (George) Lebl
+ * Copyright (C) 1997-2011 Jiri (George) Lebl
  *
  * Author: Jiri (George) Lebl
  *
@@ -5098,11 +5098,12 @@ etree_out_of_int_vector (int *vec, int len)
 	return n;
 }
 
+#if 0
 static GelETree *
-etree_out_of_etree_list (GSList *list, int len)
+etree_out_of_etree_list (GList *list, int len)
 {
 	GelMatrix *mm;
-	GSList *li;
+	GList *li;
 	int i;
 	GelETree *n;
 
@@ -5122,6 +5123,7 @@ etree_out_of_etree_list (GSList *list, int len)
 
 	return n;
 }
+#endif
 
 static gboolean
 comb_get_next_combination (int *vec, int len, int n)
@@ -5210,14 +5212,45 @@ perm_switch_all_above (int *perm, char *arrow, int pos, int n)
 	}
 }
 
+int
+nPr (unsigned int n, unsigned int k)
+{
+	/* assume k+1 <= n */
+	guint64 m = 1;
+	guint s = n-k+1;
+	while (s <= n) {
+		m *= (guint64)s;
+		if (m > G_MAXINT32) return -1;
+		s += 1;
+	}
+	return (int)m;
+}
+
+int
+nCr (unsigned int n, unsigned int k)
+{
+	mpz_t ret;
+	int r;
+	mpz_init (ret);
+
+	mpz_bin_uiui (ret, n, k);
+	if (mpz_fits_sint_p (ret)) {
+		r = mpz_get_si (ret);
+	} else {
+		r = -1;
+	}
+	mpz_clear (ret);
+	return r;
+}
+
 static GelETree *
 Combinations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 {
 	long k, n;
 	int *comb;
 	int i;
-	GSList *list;
 	int len;
+	GelMatrix *mm;
 	GelETree *r;
 
 	if G_UNLIKELY ( ! check_argument_integer (a, 0, "Combinations") ||
@@ -5241,26 +5274,33 @@ Combinations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 		return NULL;
 	}
 
-	list = NULL;
-	len = 0;
+	len = nCr (n, k);
+	if (len < 0) {
+		gel_errorout (_("%s: value out of range"),
+			      "Combinations");
+		return NULL;
+	}
 
 	comb = g_new (int, k);
 	for (i = 0; i < k; i++)
 		comb[i] = i+1;
 
+	mm = gel_matrix_new ();
+	gel_matrix_set_size (mm, len, 1, FALSE /* padding */);
+
+	GEL_GET_NEW_NODE (r);
+	r->type = GEL_MATRIX_NODE;
+	r->mat.matrix = gel_matrixw_new_with_matrix (mm);
+	r->mat.quoted = FALSE;
+
+	i = 0;
 	do {
-		list = g_slist_prepend (list, etree_out_of_int_vector (comb, k));
-		len++;
+		gel_matrix_index (mm, i, 0) = etree_out_of_int_vector (comb, k);
+		i++;
 	} while (comb_get_next_combination (comb, k, n));
 
 	g_free (comb);
 
-	list = g_slist_reverse (list);
-
-	r = etree_out_of_etree_list (list, len);
-
-	g_slist_free (list);
-
 	return r;
 }
 
@@ -5268,12 +5308,13 @@ static GelETree *
 Permutations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 {
 	GelETree *r;
-	GSList *list;
+	GQueue queue = G_QUEUE_INIT;
 	long k, n, len;
 	int *comb;
 	int *perm;
 	char *arrow;
-	int i;
+	int i, j;
+	GelMatrix *mm;
 
 	if G_UNLIKELY ( ! check_argument_integer (a, 0, "Permutations") ||
 			! check_argument_integer (a, 1, "Permutations"))
@@ -5296,6 +5337,13 @@ Permutations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 		return NULL;
 	}
 
+	len = nPr (n, k);
+	if (len < 0) {
+		gel_errorout (_("%s: value out of range"),
+			      "Permutations");
+		return NULL;
+	}
+
 	arrow = g_new (char, k);
 	perm = g_new (int, k);
 	comb = g_new (int, k);
@@ -5303,9 +5351,15 @@ Permutations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 	for (i = 0; i < k; i++)
 		comb[i] = i+1;
 
-	list = NULL;
-	len = 0;
+	mm = gel_matrix_new ();
+	gel_matrix_set_size (mm, len, 1, FALSE /* padding */);
+
+	GEL_GET_NEW_NODE (r);
+	r->type = GEL_MATRIX_NODE;
+	r->mat.matrix = gel_matrixw_new_with_matrix (mm);
+	r->mat.quoted = FALSE;
 
+	j = 0;
 	do {
 		for (i = 0; i < k; i++)
 			perm[i] = comb[i];
@@ -5314,8 +5368,9 @@ Permutations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 		for (;;) {
 			int m;
 
-			list = g_slist_prepend (list, etree_out_of_int_vector (perm, k));
-			len++;
+			gel_matrix_index (mm, j, 0) =
+				etree_out_of_int_vector (perm, k);
+			j++;
 
 			m = perm_get_highest_mobile (perm, arrow, k);
 			if (m == -1)
@@ -5329,12 +5384,6 @@ Permutations_op (GelCtx *ctx, GelETree * * a, gboolean *exception)
 	g_free (perm);
 	g_free (arrow);
 
-	list = g_slist_reverse (list);
-
-	r = etree_out_of_etree_list (list, len);
-
-	g_slist_free (list);
-
 	return r;
 }
 
diff --git a/src/genius-readline-helper.c b/src/genius-readline-helper.c
index b71c8f8..187c887 100644
--- a/src/genius-readline-helper.c
+++ b/src/genius-readline-helper.c
@@ -1,3 +1,23 @@
+/* GENIUS Calculator
+ * Copyright (C) 1997-2011 Jiri (George) Lebl
+ *
+ * Author: Jiri (George) Lebl
+ *
+ * This file is part of Genius.
+ *
+ * Genius is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
 #include <stdio.h>
 #include <stdlib.h>
 #include <unistd.h>
@@ -170,6 +190,7 @@ main(int argc, char *argv[])
 		int count;
 		if(sscanf(buf,"PLUGINS %d\n",&count) == 1) {
 			int i;
+			GQueue queue = G_QUEUE_INIT;
 			if(plugins) {
 				g_list_foreach(plugins,(GFunc)g_free,NULL);
 				g_list_free(plugins);
@@ -181,11 +202,12 @@ main(int argc, char *argv[])
 					goto end_with_an_error;
 				p = strchr(buf,'\n');
 				if(p) *p = '\0';
-				plugins = g_list_prepend(plugins,g_strdup(buf));
+				g_queue_push_tail (&queue, g_strdup (buf));
 			}
-			plugins = g_list_reverse(plugins);
+			plugins = queue.head;
 		} else if(sscanf(buf,"FUNCTIONS %d\n",&count) == 1) {
 			int i;
+			GQueue queue = G_QUEUE_INIT;
 			if(functions) {
 				g_list_foreach(functions,(GFunc)g_free,NULL);
 				g_list_free(functions);
@@ -197,9 +219,9 @@ main(int argc, char *argv[])
 					goto end_with_an_error;
 				p = strchr(buf,'\n');
 				if(p) *p = '\0';
-				functions = g_list_prepend(functions,g_strdup(buf));
+				g_queue_push_tail (&queue, g_strdup (buf));
 			}
-			functions = g_list_reverse(functions);
+			functions = queue.head;
 		} else if (strncmp (buf, "CWD ", strlen ("CWD "))==0) {
 			char *r = strrchr (buf, '\n');
 			if (r != NULL)
diff --git a/src/geniustests.txt b/src/geniustests.txt
index f87dd38..9df2500 100644
--- a/src/geniustests.txt
+++ b/src/geniustests.txt
@@ -1022,6 +1022,12 @@ SetMatrixSize(null,2,3)						[0,0,0;0,0,0]
 ExpandMatrix(null)+1						((null)+1)
 CrossProduct ([-2,1,4],[3,2,5])					[-3;22;-7]
 CrossProduct ([3;2;5],[-2;1;4])					[3;-22;7]
+Permutations(2,3)						[[1,2],[2,1],[1,3],[3,1],[2,3],[3,2]]
+Combinations(2,3)						[[1,2],[1,3],[2,3]]
+Combinations(3,2)						Combinations(3,2)
+Permutations(3,2)						Permutations(3,2)
+Combinations(-1,2)						Combinations(-1,2)
+Permutations(-1,2)						Permutations(-1,2)
 load "nullspacetest.gel"					true
 load "longtest.gel"						true
 load "testprec.gel"						true
diff --git a/src/graphing.c b/src/graphing.c
index d49936f..704be83 100644
--- a/src/graphing.c
+++ b/src/graphing.c
@@ -1,5 +1,5 @@
 /* GENIUS Calculator
- * Copyright (C) 2003-2010 Jiri (George) Lebl
+ * Copyright (C) 2003-2011 Jiri (George) Lebl
  *
  * Author: Jiri (George) Lebl
  *
@@ -3403,9 +3403,10 @@ slopefield_draw_solution (double x, double y, double dx)
 	int len1, len2, len;
 	int i;
 	GdkColor color;
-	GSList *points1 = NULL;
+	GQueue points1 = G_QUEUE_INIT;
 	GSList *points2 = NULL;
-	GSList *li;
+	GList *li;
+	GSList *sli;
 	GtkPlotData *data;
 	double fudgey;
 
@@ -3449,11 +3450,9 @@ slopefield_draw_solution (double x, double y, double dx)
 		pt[0] = cx;
 		pt[1] = cy;
 
-		points1 = g_slist_prepend (points1, pt);
+		g_queue_push_tail (&points1, pt);
 	}
 
-	points1 = g_slist_reverse (points1);
-
 	len2 = 0;
 	cx = x;
 	cy = y;
@@ -3495,9 +3494,9 @@ slopefield_draw_solution (double x, double y, double dx)
 	yy = g_new0 (double, len);
 
 	i = 0;
-	for (li = points2; li != NULL; li = li->next) {
-		double *pt = li->data;
-		li->data = NULL;
+	for (sli = points2; sli != NULL; sli = sli->next) {
+		double *pt = sli->data;
+		sli->data = NULL;
 
 		xx[i] = pt[0];
 		yy[i] = pt[1];
@@ -3512,7 +3511,7 @@ slopefield_draw_solution (double x, double y, double dx)
 
 	i++;
 
-	for (li = points1; li != NULL; li = li->next) {
+	for (li = points1.head; li != NULL; li = li->next) {
 		double *pt = li->data;
 		li->data = NULL;
 
@@ -3524,7 +3523,7 @@ slopefield_draw_solution (double x, double y, double dx)
 		i++;
 	}
 
-	g_slist_free (points1);
+	g_queue_clear (&points1);
 	g_slist_free (points2);
 
 	/* Adjust ends */
diff --git a/src/matrix.c b/src/matrix.c
index 52b4b2d..5dcd301 100644
--- a/src/matrix.c
+++ b/src/matrix.c
@@ -1,5 +1,5 @@
 /* GENIUS Calculator
- * Copyright (C) 1997-2006 George Lebl
+ * Copyright (C) 1997-2011 George Lebl
  *
  * Author: George Lebl
  *
@@ -58,7 +58,7 @@ gel_matrix_new(void)
 	m->width = 0;
 	m->height = 0;
 	
-	m->data = NULL;
+	m->thedata = NULL;
 	
 	m->realwidth = 0;
 	m->fullsize = 0;
@@ -72,7 +72,7 @@ gel_matrix_new(void)
 void
 gel_matrix_set_size (GelMatrix *matrix, int width, int height, gboolean padding)
 {
-	GPtrArray *na;
+	gpointer *na;
 	int i;
 	int wpadding;
 	int hpadding;
@@ -91,32 +91,29 @@ gel_matrix_set_size (GelMatrix *matrix, int width, int height, gboolean padding)
 		if(hpadding > 10) hpadding = 10;
 	}
 	
-	if(!matrix->data) {
+	if (matrix->thedata == NULL) {
 		matrix->width = width;
 		matrix->realwidth = width+wpadding;
 		matrix->height = height;
 		matrix->fullsize=(width+wpadding)*(height+hpadding);
 
-		matrix->data = g_ptr_array_new();
-		g_ptr_array_set_size(matrix->data,matrix->fullsize);
-
-		memset(matrix->data->pdata, 0,
-		       (matrix->fullsize*sizeof(void *)));
+		matrix->thedata = g_new0 (gpointer, matrix->fullsize);
 		return;
 	}
 	
-	if(width<=matrix->realwidth) {
+	if (width <= matrix->realwidth) {
 		int newsize = matrix->realwidth*height;
-		if(newsize>matrix->fullsize) {
+		if (newsize > matrix->fullsize) {
+			matrix->thedata = g_renew (gpointer, matrix->thedata, newsize);
+			memset (matrix->thedata + matrix->fullsize, 0, (newsize - matrix->fullsize) * sizeof(void *));
 			matrix->fullsize = newsize;
-			g_ptr_array_set_size(matrix->data,matrix->fullsize);
 		}
-		if(width<matrix->width) {
+		if (width < matrix->width) {
 			for(i=0;i<matrix->height;i++)
-				memset(matrix->data->pdata+((matrix->realwidth*i)+width),0,(matrix->width-width)*sizeof(void *));
+				memset(matrix->thedata+((matrix->realwidth*i)+width),0,(matrix->width-width)*sizeof(void *));
 		}
-		if(height<matrix->height) {
-			memset(matrix->data->pdata+(matrix->realwidth*height),0,
+		if (height < matrix->height) {
+			memset(matrix->thedata+(matrix->realwidth*height),0,
 			       ((matrix->realwidth*matrix->height)-(matrix->realwidth*height))*sizeof(void *));
 		}
 		matrix->width = width;
@@ -125,13 +122,11 @@ gel_matrix_set_size (GelMatrix *matrix, int width, int height, gboolean padding)
 	}
 
 	matrix->fullsize = (width+wpadding)*(height+hpadding);
-	na = g_ptr_array_new();
-	g_ptr_array_set_size(na,matrix->fullsize);
-	memset(na->pdata,0,matrix->fullsize*sizeof(void *));
+	na = g_new0 (gpointer, matrix->fullsize);
 	
 	for(i=0;i<matrix->height;i++) {
-		memcpy(na->pdata+((width+wpadding)*i),
-		       matrix->data->pdata+(matrix->realwidth*i),
+		memcpy(na+((width+wpadding)*i),
+		       matrix->thedata+(matrix->realwidth*i),
 		       matrix->width*sizeof(void *));
 	}
 	
@@ -139,9 +134,9 @@ gel_matrix_set_size (GelMatrix *matrix, int width, int height, gboolean padding)
 	matrix->width = width;
 	matrix->height = height;
 
-	g_ptr_array_free(matrix->data,TRUE);
+	g_free (matrix->thedata);
 	
-	matrix->data = na;
+	matrix->thedata = na;
 }
 
 /*set the size of the matrix to be at least this*/
@@ -172,9 +167,9 @@ gel_matrix_set_element(GelMatrix *matrix, int x, int y, gpointer data)
 				     MAX(x+1,matrix->width),
 				     MAX(y+1,matrix->height),
 				     TRUE /* padding */);
-	g_return_if_fail(matrix->data!=NULL);
+	g_return_if_fail(matrix->thedata!=NULL);
 	
-	matrix->data->pdata[x+y*matrix->realwidth]=data;
+	matrix->thedata[x+y*matrix->realwidth]=data;
 }
 
 /*copy a matrix*/
@@ -191,9 +186,9 @@ gel_matrix_copy(GelMatrix *source, GelElementCopyFunc el_copy, gpointer func_dat
 	/*copy over the structure*/
 	*matrix = *source;
 	
-	matrix->data = NULL;
+	matrix->thedata = NULL;
 	
-	if(source->data==NULL)
+	if(source->thedata==NULL)
 		return matrix;
 
 	/*make us a new matrix data array*/
@@ -228,7 +223,7 @@ gel_matrix_transpose(GelMatrix *matrix)
 	
 	new = gel_matrix_new();
 
-	if(!matrix->data)
+	if (matrix->thedata == NULL)
 		return new;
 
 	gel_matrix_set_size (new, matrix->height, matrix->width, TRUE /* padding */);
@@ -249,7 +244,7 @@ gel_matrix_foreach(GelMatrix *matrix, GFunc func, gpointer func_data)
 	g_return_if_fail(matrix != NULL);
 	g_return_if_fail(func != NULL);
 	
-	if(matrix->data==NULL)
+	if (matrix->thedata == NULL)
 		return;
 
 	for(i=0;i<matrix->width;i++)
@@ -270,9 +265,10 @@ gel_matrix_free(GelMatrix *matrix)
 	
 	mf = (GelMatrixFreeList *)matrix;
 
-	if(matrix->data)
-		g_ptr_array_free(matrix->data,TRUE);
-	matrix->data = NULL;
+	if (matrix->thedata != NULL) {
+		g_free (matrix->thedata);
+		matrix->thedata = NULL;
+	}
 #ifdef MEM_DEBUG_FRIENDLY
 	memset (matrix, 0xaa, sizeof (GelMatrix));
 	g_free (matrix);
diff --git a/src/matrix.h b/src/matrix.h
index da093c5..941c5d1 100644
--- a/src/matrix.h
+++ b/src/matrix.h
@@ -1,5 +1,5 @@
 /* GENIUS Calculator
- * Copyright (C) 1997-2002 George Lebl
+ * Copyright (C) 1997-2011 George Lebl
  *
  * Author: George Lebl
  *
@@ -29,7 +29,7 @@ struct _GelMatrix {
 	int width;
 	int height;
 
-	GPtrArray *data;
+	gpointer *thedata;
 
 	/*private data*/
 	int realwidth;
@@ -65,6 +65,6 @@ void gel_matrix_foreach(GelMatrix *matrix, GFunc func, gpointer func_data);
 void gel_matrix_free(GelMatrix *matrix);
 
 /*get the value at*/
-#define gel_matrix_index(m,x,y) (g_ptr_array_index((m)->data,(x)+(y)*(m)->realwidth))
+#define gel_matrix_index(m,x,y) ((m)->thedata[(x)+(y)*(m)->realwidth])
 
 #endif
diff --git a/ve/ve-config.c b/ve/ve-config.c
index ae65531..5594052 100644
--- a/ve/ve-config.c
+++ b/ve/ve-config.c
@@ -1,6 +1,6 @@
 /* Config reader routines
  *
- * (c) 2002 George Lebl
+ * (c) 2002,2011 George Lebl
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Library General Public
@@ -861,17 +861,15 @@ GList *
 ve_config_get_sections (VeConfig *config)
 {
 	GList *li;
-	GList *list;
+	GQueue queue = G_QUEUE_INIT;
 
 	g_return_val_if_fail (config != NULL, NULL);
 
-	list = NULL;
-
 	for (li = config->sections; li != NULL; li = li->next) {
 		VeSection *section = li->data;
-		list = g_list_prepend (list, g_strdup (section->name));
+		g_queue_push_tail (&queue, g_strdup (section->name));
 	}
-	return g_list_reverse (list);
+	return queue.head;
 }
 
 GList *
@@ -879,7 +877,7 @@ ve_config_get_keys (VeConfig *config, const char *section)
 {
 	VeSection *sec;
 	GList *li;
-	GList *list;
+	GQueue queue = G_QUEUE_INIT;
 
 	g_return_val_if_fail (config != NULL, NULL);
 	g_return_val_if_fail (section != NULL, NULL);
@@ -888,15 +886,13 @@ ve_config_get_keys (VeConfig *config, const char *section)
 	if (sec == NULL)
 		return NULL;
 
-	list = NULL;
-
 	for (li = sec->lines; li != NULL; li = li->next) {
 		VeLine *ll = li->data;
 		if (ll->type == VE_LINE_KEY &&
 		    ! ve_string_empty (ll->key))
-			list = g_list_prepend (list, g_strdup (ll->key));
+			g_queue_push_tail (&queue, g_strdup (ll->key));
 	}
-	return g_list_reverse (list);
+	return queue.head;
 }
 
 void
[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]