LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 09-11-2008, 09:36 AM   #1
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Rep: Reputation: 33
glibc detected *** corrupted double-linked list


Hi,

I've looked around in solving this but cannot work out why, I thought I knew but tests proved different (I think)(my lists?).

I've run through GDB and installed all the extra packages, and updated 'everything', you can see the backtrace later (i'm no real GDB expert yet).

Any way the code comes in two files, excuses for length of post!

main.c
Code:
#include <gtk/gtk.h>


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
//#include <time.h>

#include "lists.h"

#define MAXLINE 1024


GtkWidget *window;
GtkWidget *status_bar;
GtkWidget *entry_search;

enum
{
	COL_NAME = 0, 
	COL_SIZE,
	NUM_COLS
};


GtkListStore  		*the_store;
GtkTreeModel        *the_model;
GtkWidget           *the_view;


char *fin_default = "/usr/share/dict/words";


int curr_size = 0;

void test_print(void *s);

GtkWidget *get_menubar_menu( GtkWidget  *window);
void show_help(void);

static void enter_callback_search( GtkWidget *widget, GtkWidget *entry );


void set_status(const gchar *text);

void add_entry(char *nm, int size);

void empty_list(void);




static GtkItemFactoryEntry menu_items[] = {
	{ "/_File",         NULL,         NULL,           0, "<Branch>" },
	{ "/File/Quit",     "<control>Q", gtk_main_quit,  0, "<Item>" },
	{ "/_Help",         NULL,         NULL,           0, "<LastBranch>" },
	{ "/_Help/About",   NULL,         show_help,           0, "<Item>" },
};

static gint nmenu_items = sizeof (menu_items) / sizeof (menu_items[0]);

GtkWidget *get_menubar_menu( GtkWidget  *window)
{
	GtkItemFactory *item_factory;
	GtkAccelGroup *accel_group;
	accel_group = gtk_accel_group_new();
	item_factory = gtk_item_factory_new(GTK_TYPE_MENU_BAR, "<main>", accel_group);
	gtk_item_factory_create_items(item_factory, nmenu_items, menu_items, NULL);
	gtk_window_add_accel_group(GTK_WINDOW (window), accel_group);
	return gtk_item_factory_get_widget(item_factory, "<main>");
}

void show_help(void)
{
	GtkWidget *dialog, *label;
	dialog = gtk_dialog_new_with_buttons("About", GTK_WINDOW (window), GTK_DIALOG_MODAL | GTK_DIALOG_DESTROY_WITH_PARENT, GTK_STOCK_OK, GTK_RESPONSE_NONE, NULL);
	label = gtk_label_new("\n www.rawstar7.co.uk \n");
	g_signal_connect_swapped(dialog, "response", G_CALLBACK (gtk_widget_destroy), dialog);
	gtk_container_add(GTK_CONTAINER (GTK_DIALOG(dialog)->vbox), label);
	gtk_widget_show_all(dialog);
}


void set_status(const gchar *text)
{
	gtk_statusbar_push (GTK_STATUSBAR (status_bar), GPOINTER_TO_INT (text), text);
}









//	LIST STUFF
//	=====================================================================================================


void add_entry(char *nm, int size)
{
	GtkTreeIter             iter;
	char *len = "";
	
	gtk_list_store_append (the_store, &iter);
	gtk_list_store_set (the_store, &iter, COL_NAME, nm, COL_SIZE, len, -1);
	
	//	LIVE UPDATE
	while (gtk_events_pending())
	{
		gtk_main_iteration();
	}
}

void empty_list(void)
{
	g_message("Clearing\n");
	gtk_list_store_clear(the_store);
}

static GtkTreeModel *create_and_fill_model (void)
{
	GtkListStore  *store;
	//	CREATE A MODEL SPECIFYING NUMBER OF COLUMNS AND TYPES
	store = gtk_list_store_new (NUM_COLS, G_TYPE_STRING, G_TYPE_STRING);
	the_store = store;
	return GTK_TREE_MODEL (store);
}

static GtkWidget *create_view_and_model (void)
{
	GtkCellRenderer     *renderer;
	GtkTreeModel        *model;
	GtkWidget           *view;
	
	view = gtk_tree_view_new ();
	
	/* --- Column #1 --- */
	renderer = gtk_cell_renderer_text_new ();
	gtk_tree_view_insert_column_with_attributes (GTK_TREE_VIEW (view), -1, "Name", renderer, "text", COL_NAME, NULL);
	
	/* --- Column #2 --- */
	renderer = gtk_cell_renderer_text_new ();
	gtk_tree_view_insert_column_with_attributes (GTK_TREE_VIEW (view), -1, "Length", renderer, "text", COL_SIZE, NULL);
	
	the_view = view;
	model = create_and_fill_model();
	the_model = model;
	gtk_tree_view_set_model(GTK_TREE_VIEW (view), model);
	return view;
}










void str_trim_r(char *(*s))
{
	char * ss;
	int len = strlen(*s);
	ss = (char*)calloc( (len + 1) , sizeof(char));
	ss = *s;
	if ( ( strcmp(&ss[len-1], " ") == 0) || ( strcmp(&ss[len-1], "\t") == 0) || ( strcmp(&ss[len-1], "\n") == 0) )
	{
		char *stmp;
		stmp = (char*)calloc(len+1,  sizeof(char));
		strncpy(stmp, ss, len-1);
		
		str_trim_r(&stmp);
		
		// copy
		*s = (char*) calloc( strlen(stmp) + 1, sizeof(char) );
		strcpy(*s, stmp);
	}
	else
	{
		// copy
		*s = (char*) malloc( (strlen(ss) + 1) * sizeof(char) );
		strcpy(*s, ss);
	}
}













int factorial(int n)
{
	int N = n;
	int i = n-1;
	for(;i>0;i--)
	{
		N *= i;
	}
	return N;
}

int calc_combinations(int N)
{
	int i, nn;
	int tot = 0;
	for(i=N;i>0;i--)
	{
		nn = N-i;
		if(nn==0)
		{
			nn = 1;
		}
		tot += (factorial(N)/(factorial(i)*factorial(nn)) );
	}
	return tot;
}

int nexty(int mask[], int n)
{
	int i;
	for (i = 0; (i < n) && mask[i]; ++i)
		mask[i] = 0;
	
	if (i < n) {
		mask[i] = 1;
		return 1;
	}
	return 0;
}

char *char_set(int mask[], int n)
{
	char *sret;
	sret = (char*)malloc(n*1);
	int i;
	for (i = 0; i < n; ++i)
	{
		if (mask[i])
		{
			sprintf(sret, "%s%d", sret, i+1);
		}
	}
	return sret;
}

int do_subset(int n, char **sa, int num, int min)
{
	int mask[16];
	int i;
	for (i = 0; i < n; ++i)
	{
		mask[i] = 0;
	}
	
	int c = 0;
	int len;
	char *sret;
	while (nexty(mask, n))
	{
		sret = char_set(mask, n);
		len = strlen(sret);
		if(len>=min)
		{
			sa[c] = malloc((len+1) * sizeof(char));
			strcpy(sa[c], sret);
			c++;
		}
	}
	return c;
}

void assign_letters(int num, char **sa, char *word)
{
	int i, j, n;
	int len;
	
	for(i=0;i<num;i++)
	{
		len = strlen(sa[i]);
		for(j=0;j<len;j++)
		{
			n = sa[i][j]-49;
			sa[i][j] = word[n];
		}
	}
}

int sorder_cmp(const void *a, const void *b)
{
	return strcmp((char*)a, (char*)b);
}

char *sorder(char *s)
{
	char ss[strlen(s)+1];
	strcpy(ss, s);
	qsort (ss, strlen(ss), sizeof(char), sorder_cmp );
	
	s = (char *)malloc(strlen(s)+1);
	strcpy(s, ss);
	return s;
}

int list_cmp(char **sa, int tot, char *w)
{
	int i;
	for(i=0;i<tot;i++)
	{
		if(strcmp(sa[i], w)==0)
		{
			return 1;
		}
	}
	return 0;
}

void test_print(void *s)
{
	int len = strlen((char*)s);
	if(len==curr_size)
	{
		printf("%s (%d)\n", (char*)s, len);
		add_entry((char*)s, len);
	}
}

static void do_anagram(const gchar *search)
{
	//printf ("Search for anagrams: %s \n", search);
	set_status("Starting anagram search");
	
	
	FILE *fi;
	char *fin = "/usr/share/dict/words";
	int i;
	char line[MAXLINE];
	char *word = "allocate";
	
	word = (char*)calloc( (strlen(search) + 1) , sizeof(char));
	memcpy(word, search, strlen(search));
	
	
	int min = 1;
	int verbose = 1;
	
	
	int N = strlen(word);
	
	if(min>N)
	{
		min = N;
	}
	
	for(i=0;i<N;i++)
	{
		word[i] = tolower(word[i]);
	}
	
	int num = calc_combinations(N);
	
	char *sa[num];
	num = do_subset(N, sa, num, min);
	
	//	ASSIGN TO LETTERS
	assign_letters(num, sa, word);
	
	//	ORDER CHECK LIST
	for(i=0;i<num;i++)
	{
		sa[i] = sorder(sa[i]);
	}
	
	int num_entries = 0;
	int num_hits = 0;
	
	struct S_LIST l = slist_init();
	
	int ret, len;
	if ((fi = fopen(fin, "rb")) != NULL)
	{
		char *w;
		while (fgets(line, MAXLINE, fi) != NULL)
		{
			w = (char*)calloc( (strlen(line) + 1) , sizeof(char));
			memcpy(w, line, strlen(line));
			
			str_trim_r(&w);
			
			len = strlen(w);
			if( (len >= min) && (len <= N) )
			{
				for(i=0;i<len;i++)
				{
					w[i] = tolower(w[i]);
				}
				char *ww = sorder(w);
				ret = list_cmp(sa, num, ww);
				
				if(ret == 1)
				{
					num_hits++;
					//printf("%s (%d) \n", w, strlen(w));
					slist_add(&l, w);
				}
			}
			num_entries++;
		}
		
		fclose(fi);
		
		printf("\n");
		for(i=N;i>=min;i--)
		{
			printf("................ SIZE %d \n", i);
			curr_size = i;
			slist_foreach(&l, &test_print);
		}
		printf("\n");
		
		printf("\n");
		if(verbose==1)
		{
			printf("Length of search input: %d\n", N);
			printf("Number of search combinations: %d\n", num);
			printf("Number of dictionary entries: %d\n", num_entries);
		}
		printf("Number of matches: %d\n", num_hits);
		
	}
	
	
	//	FREE LIST
	slist_delete_all(&l);
	//free(*l);
	//&l = NULL;
	//*l = NULL;
	//free(&l);
}

static void do_crossword(const gchar *search)
{
	//printf ("Search for crosswords: %s \n", search);
	set_status("Starting crossword search");
	
	FILE *fi;
	char *fin = "/usr/share/dict/words";
	int i;
	char line[MAXLINE];
	char *word = "r*b";
	
	word = (char*)calloc( (strlen(search) + 1) , sizeof(char));
	memcpy(word, search, strlen(search));
	
	int wlen = strlen(word);
	for(i=0;i<wlen;i++)		//	convert to lower
	{
		word[i] = tolower(word[i]);
	}
	
	int num_entries = 0;
	int num_hits = 0;
	
	int fail, len;
	if ((fi = fopen(fin, "rb")) != NULL)
	{
		char *w;
		while (fgets(line, MAXLINE, fi) != NULL)
		{
			w = (char*)calloc( (strlen(line) + 1) , sizeof(char));
			memcpy(w, line, strlen(line));
			
			str_trim_r(&w);
			
			len = strlen(w);
			if(len == wlen)	//	only check if same length
			{
				for(i=0;i<len;i++)	//	convert line to lower
				{
					w[i] = tolower(w[i]);
				}
				
				fail = 1;
				for(i=0;i<wlen;i++)
				{
					if( (word[i]>=97) && (word[i]<=122) )	//	only handle lowercase letters, anything else is wild!
					{
						if(word[i]!=w[i])
						{
							fail = 0;
							break;
						}
					}
				}
				
				if(fail == 1)
				{
					add_entry(w, -1);
					num_hits++;
					printf("%s \n", w);
				}
			}
			num_entries++;
		}
		
		fclose(fi);
		printf("Number of matches: %d\n", num_hits);
	}
	else
	{
		//	error opening dictionary
	}
	
}

static void do_search(const gchar *type)
{
	const gchar *entry_s_text;
	entry_s_text = gtk_entry_get_text (GTK_ENTRY (entry_search));
	empty_list();
	
	if(strcmp(type,"anagram")==0)
	{
		do_anagram(entry_s_text);
	}
	else
	{
		do_crossword(entry_s_text);
	}
	
	printf ("Finished \n");
}


static void callback(GtkWidget *widget, gpointer data)
{
	do_search(data);
}

static void enter_callback_search(GtkWidget *widget, GtkWidget *entry)
{
	//	check to see if contain non characters, if so do a crossword search instead
	do_search("anagram");
}


int main (int argc, char **argv)
{
	GtkWidget *view;
	
	gtk_init (&argc, &argv);
	
	window = gtk_window_new (GTK_WINDOW_TOPLEVEL);
	g_signal_connect (window, "delete_event", gtk_main_quit, NULL); /* dirty */
	
	gtk_window_set_title (GTK_WINDOW (window), "WordSolve");
	gtk_widget_set_size_request (GTK_WIDGET(window), 500, 300);
	
	GtkTooltips *button_bar_tips;
	button_bar_tips = gtk_tooltips_new();
	
	GtkWidget *main_vbox, *hbox1;
	GtkWidget *menubar;
	GtkWidget *label;
	GtkWidget *button;
	
	//	MAIN BODY
	main_vbox = gtk_vbox_new (FALSE, 1);	//	homogeneous(bool), spacing(int)
	gtk_container_set_border_width (GTK_CONTAINER (main_vbox), 2);
	gtk_container_add (GTK_CONTAINER (window), main_vbox);
	
	//	MENU
	menubar = get_menubar_menu (window);
	gtk_box_pack_start (GTK_BOX (main_vbox), menubar, FALSE, TRUE, 0);
	
	//	INPUT
	hbox1 = gtk_hbox_new (FALSE, 1);	//	homogeneous(bool), spacing(int)
	
	label = gtk_label_new ("Search:");
	gtk_label_set_justify (GTK_LABEL (label), GTK_JUSTIFY_RIGHT);
	gtk_box_pack_start (GTK_BOX (hbox1), label, FALSE, FALSE, 0);	//	expand(bool), fill(bool), padding(uint)
	
	//	SEARCH ENTRY
	entry_search = gtk_entry_new ();
	gtk_entry_set_max_length (GTK_ENTRY (entry_search), 50);
	g_signal_connect (G_OBJECT (entry_search), "activate", G_CALLBACK (enter_callback_search), (gpointer) entry_search);
	gtk_entry_set_text (GTK_ENTRY (entry_search), "");
	int tmp_pos = GTK_ENTRY (entry_search)->text_length;
	//gtk_editable_insert_text (GTK_EDITABLE (entry_search), "w*rd", -1, &tmp_pos);
	gtk_editable_insert_text (GTK_EDITABLE (entry_search), "hello", -1, &tmp_pos);
	gtk_box_pack_start (GTK_BOX (hbox1), entry_search, TRUE, TRUE, 0);
	gtk_tooltips_set_tip (GTK_TOOLTIPS (button_bar_tips), entry_search, "Search", "");
	
	
	button = gtk_button_new_with_label ("Anagram");
	g_signal_connect (G_OBJECT (button), "clicked", G_CALLBACK (callback), (gpointer) "anagram");
	gtk_box_pack_start (GTK_BOX (hbox1), button, FALSE, FALSE, 0);	//	expand(bool), fill(bool), padding(uint)
	
	button = gtk_button_new_with_label ("Crossword");
	g_signal_connect (G_OBJECT (button), "clicked", G_CALLBACK (callback), (gpointer) "crossword");
	gtk_box_pack_start (GTK_BOX (hbox1), button, FALSE, FALSE, 0);	//	expand(bool), fill(bool), padding(uint)
	
	gtk_box_pack_start (GTK_BOX (main_vbox), hbox1, FALSE, TRUE, 3);	//	expand(bool), fill(bool), padding(uint)
	
	//	LIST
	GtkWidget *scrolled_window;
	scrolled_window = gtk_scrolled_window_new (NULL, NULL);
	gtk_container_set_border_width (GTK_CONTAINER (scrolled_window), 0);
	gtk_scrolled_window_set_policy (GTK_SCROLLED_WINDOW (scrolled_window), GTK_POLICY_AUTOMATIC, GTK_POLICY_AUTOMATIC);
	
	view = create_view_and_model ();
	
	gtk_scrolled_window_add_with_viewport (GTK_SCROLLED_WINDOW (scrolled_window), view);	//	pack into the scrolled window
	gtk_tooltips_set_tip (GTK_TOOLTIPS (button_bar_tips), view, "Results", "");
	gtk_box_pack_start (GTK_BOX (main_vbox), scrolled_window, TRUE, TRUE, 3);
	
	//	STATUS BAR
	gint context_id;
    status_bar = gtk_statusbar_new ();      
    gtk_box_pack_start (GTK_BOX (main_vbox), status_bar, FALSE, TRUE, 0);
    gtk_widget_show (status_bar);
    context_id = gtk_statusbar_get_context_id(GTK_STATUSBAR (status_bar), "Statusbar example");
	
	//	SHOW APP
	gtk_widget_show_all (window);
	gtk_main ();
	
	return 0;
}

lists.h
Code:
#ifndef S_LIST_H_INCLUDED
#  define S_LIST_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>

/*

	TODO:
		- copy list
		- order list
		- search???

*/

struct S_LIST
{
	int count;
	struct S_LIST_E *head;
	struct S_LIST_E *tail;
};

struct S_LIST_E
{
	void *data;
	struct S_LIST_E *next;
	struct S_LIST_E *prev;
};




struct S_LIST slist_init()
{
	struct S_LIST l = {0,NULL,NULL};
	return l;
}

void slist_add(struct S_LIST *sl, void *data)
{
	struct S_LIST_E *e;
	if((e = (struct S_LIST_E*) malloc(sizeof(struct S_LIST_E))) != NULL)
	{
		if(sl->head==NULL)
		{
		
			sl->head = e;
			sl->tail = sl->head;
			sl->tail->next = NULL;
			sl->tail->prev = NULL;
		}
		else
		{
			sl->tail->next = e;
			sl->tail->next->prev = sl->tail;
			sl->tail = sl->tail->next;
			sl->tail->next = NULL;
		}
		sl->tail->data = data;
		sl->count++;
	}
}


void slist_insert(struct S_LIST *sl, void *data, int pos)
{
	struct S_LIST_E *e;
	if((e = (struct S_LIST_E*) malloc(sizeof(struct S_LIST_E))) != NULL)
	{
		e->data = data;
		
		if(sl->head==NULL)	//	an empty list
		{
			sl->head = e;
			sl->tail = sl->head;
			sl->tail->next = NULL;
			sl->tail->prev = NULL;
		}
		else if(pos==0)	//	first pos
		{
			e->prev = NULL;
			e->next = sl->head;
			sl->head->prev = e;
			sl->head = e;
		}
		else if(pos>=sl->count-1)	//	last pos (or above)
		{
			sl->tail->next = e;
			sl->tail->next->prev = sl->tail;
			sl->tail = sl->tail->next;
			sl->tail->next = NULL;
		}
		else	//	somewhere in between
		{
			struct S_LIST_E *v = sl->head;
			int c = 0;
			while(v!=NULL)
			{
				if(c == pos)
				{
					e->next = v->next;
					e->next->prev = e;
					v->next = e;
					e->prev= v;
					break;
				}
				v = v->next;
				c++;
			}
		}
		sl->count++;
	}
}

void slist_delete(struct S_LIST *sl, int pos)
{
	struct S_LIST_E *e = sl->head;
	int c = 0;
	while(e!=NULL)
	{
		if(c == pos)
		{
			struct S_LIST_E *tmp = e;
			e->prev->next = tmp->next;
			e->next->prev = tmp->prev;
			//free(tmp);
			free(e);
			sl->count--;
			return;
		}
		e = e->next;
		c++;
	}
}

void slist_delete_all(struct S_LIST *sl)
{
	struct S_LIST_E *e = sl->head;
	struct S_LIST_E *v = NULL;
	while(e != NULL)
	{
		v = e;
		e = e->next;
		free(v);
	}
	free(e);
	sl->head = NULL;
	sl->tail = NULL;
	sl->count = 0;
}

//int slist_search(struct S_LIST *sl, void (*func)(void *data))
int slist_search(struct S_LIST *sl, void *data)
{
	int num = 0;
	struct S_LIST_E *e = sl->head;
	while(e!=NULL)
	{
		//func(e->data);
		if(e->data==data)
		{
			return num;
		}
		e = e->next;
		num++;
	}
	return -1;
}

void slist_print(struct S_LIST *sl)
{
	struct S_LIST_E *e = sl->head;
	while(e!=NULL)
	{
		printf("%s \n", (char*)e->data);
		e = e->next;
	}
}

void print_it(void *s)
{
	printf("%s \n", (char*)s);
}

void print_nums(void *n)
{
	printf("%d \n", n);
}

void slist_foreach(struct S_LIST *sl, void (*func)(void *data))
{
	struct S_LIST_E *e = sl->head;
	while(e!=NULL)
	{
		func(e->data);
		e = e->next;
	}
}
#endif
compile
Code:
gcc main.c -o wordsolve -g -Wall `pkg-config --cflags --libs gtk+-2.0`


gdb dump
Code:
...

*** glibc detected *** /home/ai/iword/wordsolve.0.0.1/wordsolve: corrupted double-linked list: 0x08325e18 ***
^C
Program received signal SIGINT, Interrupt.
[Switching to Thread -1208325936 (LWP 5789)]
0x00110416 in __kernel_vsyscall ()
(gdb) bt
#0  0x00110416 in __kernel_vsyscall ()
#1  0x00b4c953 in __lll_lock_wait_private () from /lib/libc.so.6
#2  0x00ad9e48 in _L_lock_14708 () from /lib/libc.so.6
#3  0x00ad90e4 in __libc_free (mem=0x81a1f18) at malloc.c:3624
#4  0x00a5eabf in _dl_scope_free (old=0x81a1f18) at dl-open.c:175
#5  0x00a5a19d in _dl_map_object_deps (map=0x81a1c60, preloads=0x0, 
    npreloads=<value optimized out>, trace_mode=0, open_mode=-2147483648)
    at dl-deps.c:668
#6  0x00a5eecd in dl_open_worker (a=0xbf9bde5c) at dl-open.c:330
#7  0x00a5b1b6 in _dl_catch_error (objname=0xbf9bde84, errstring=0xbf9bde80, 
    mallocedp=0xbf9bde8b, operate=0xa5ed30 <dl_open_worker>, args=0xbf9bde5c)
    at dl-error.c:178
#8  0x00a5e852 in _dl_open (file=0xb9398d "libgcc_s.so.1", 
    mode=<value optimized out>, caller_dlopen=0x0, nsid=-2, argc=1, 
    argv=0xbf9bfef4, env=0xbf9bfefc) at dl-open.c:596
#9  0x00b765d2 in do_dlopen (ptr=0xbf9bdfb4) at dl-libc.c:86
#10 0x00a5b1b6 in _dl_catch_error (objname=0xbf9bdfc4, errstring=0xbf9bdfc0, 
    mallocedp=0xbf9bdfcb, operate=0xb76570 <do_dlopen>, args=0xbf9bdfb4)
    at dl-error.c:178
#11 0x00b76785 in __libc_dlopen_mode (name=0xb9398d "libgcc_s.so.1", 
    mode=-2147483647) at dl-libc.c:47
#12 0x00b52e89 in init () at ../sysdeps/i386/backtrace.c:43
#13 0x00c039e0 in pthread_once () from /lib/libpthread.so.0
#14 0x00b53065 in __backtrace (array=0xbf9be594, size=64)
    at ../sysdeps/i386/backtrace.c:116
#15 0x00acda01 in __libc_message (do_abort=2, 
    fmt=0xb96864 "*** glibc detected *** %s: %s: 0x%s ***\n")
    at ../sysdeps/unix/sysv/linux/libc_fatal.c:150
#16 0x00ad3e1b in malloc_consolidate (av=0xbc2120) at malloc.c:5891
#17 0x00ad6152 in _int_malloc (av=0xbc2120, bytes=11) at malloc.c:4509
#18 0x00ad789a in __libc_calloc (n=11, elem_size=1) at malloc.c:3892
#19 0x0804a7c4 in do_anagram (search=0x81dcc68 "hello") at main.c:401
#20 0x0804ad2f in do_search (type=0x804b66b "anagram") at main.c:550
#21 0x0804ad5b in callback (widget=0x81b6218, data=0x804b66b) at main.c:563
#22 0x00d89409 in IA__g_cclosure_marshal_VOID__VOID (closure=0x81e1428, 
    return_value=0x0, n_param_values=1, param_values=0xbf9bef7c, 
    invocation_hint=0xbf9bee8c, marshal_data=0x804ad4a) at gmarshal.c:77
#23 0x00d7bf83 in IA__g_closure_invoke (closure=0x81e1428, return_value=0x0, 
    n_param_values=1, param_values=0xbf9bef7c, invocation_hint=0xbf9bee8c)
    at gclosure.c:490
#24 0x00d8c48d in signal_emit_unlocked_R (node=0x81e2308, detail=0, 
    instance=0x81b6218, emission_return=0x0, instance_and_params=0xbf9bef7c)
    at gsignal.c:2440
#25 0x00d8d997 in IA__g_signal_emit_valist (instance=0x81b6218, signal_id=129, 
    detail=0, var_args=0xbf9bf1bc "t&�") at gsignal.c:2199
#26 0x00d8db59 in IA__g_signal_emit (instance=0x81b6218, signal_id=129, 
    detail=0) at gsignal.c:2243
#27 0x00533cc9 in IA__gtk_button_clicked (button=0x81b6218) at gtkbutton.c:889
#28 0x00535616 in gtk_real_button_released (button=0x81b6218)
    at gtkbutton.c:1484
#29 0x00d89409 in IA__g_cclosure_marshal_VOID__VOID (closure=0x81e2260, 
    return_value=0x0, n_param_values=1, param_values=0xbf9bf44c, 
    invocation_hint=0xbf9bf35c, marshal_data=0x5355d2) at gmarshal.c:77
#30 0x00d7a779 in g_type_class_meta_marshal (closure=0x81e2260, 
    return_value=0x0, n_param_values=1, param_values=0xbf9bf44c, 
    invocation_hint=0xbf9bf35c, marshal_data=0x1a4) at gclosure.c:567
#31 0x00d7bf83 in IA__g_closure_invoke (closure=0x81e2260, return_value=0x0, 
    n_param_values=1, param_values=0xbf9bf44c, invocation_hint=0xbf9bf35c)
    at gclosure.c:490
#32 0x00d8c91a in signal_emit_unlocked_R (node=0x81e2298, detail=0, 
    instance=0x81b6218, emission_return=0x0, instance_and_params=0xbf9bf44c)
    at gsignal.c:2370
#33 0x00d8d997 in IA__g_signal_emit_valist (instance=0x81b6218, signal_id=128, 
    detail=0, var_args=0xbf9bf68c "\221\205�") at gsignal.c:2199
#34 0x00d8db59 in IA__g_signal_emit (instance=0x81b6218, signal_id=128, 
    detail=0) at gsignal.c:2243
#35 0x00533c22 in IA__gtk_button_released (button=0x81b6218) at gtkbutton.c:881
#36 0x00535368 in gtk_button_button_release (widget=0x81b6218, event=0x81b24a8)
    at gtkbutton.c:1377
#37 0x00653434 in _gtk_marshal_BOOLEAN__BOXED (closure=0x81b9998, 
    return_value=0xbf9bf880, n_param_values=2, param_values=0xbf9bf95c, 
    invocation_hint=0xbf9bf86c, marshal_data=0x535329) at gtkmarshalers.c:84
#38 0x00d7a779 in g_type_class_meta_marshal (closure=0x81b9998, 
    return_value=0xbf9bf880, n_param_values=2, param_values=0xbf9bf95c, 
    invocation_hint=0xbf9bf86c, marshal_data=0xb4) at gclosure.c:567
#39 0x00d7bf83 in IA__g_closure_invoke (closure=0x81b9998, 
    return_value=0xbf9bf880, n_param_values=2, param_values=0xbf9bf95c, 
    invocation_hint=0xbf9bf86c) at gclosure.c:490
#40 0x00d8cad3 in signal_emit_unlocked_R (node=0x81b9a80, detail=0, 
    instance=0x81b6218, emission_return=0xbf9bfb1c, 
    instance_and_params=0xbf9bf95c) at gsignal.c:2478
#41 0x00d8d75f in IA__g_signal_emit_valist (instance=0x81b6218, signal_id=30, 
    detail=0, var_args=<value optimized out>) at gsignal.c:2209
#42 0x00d8db59 in IA__g_signal_emit (instance=0x81b6218, signal_id=30, 
    detail=0) at gsignal.c:2243
#43 0x007df494 in gtk_widget_event_internal (widget=0x81b6218, event=0x81b24a8)
    at gtkwidget.c:4678
#44 0x007def98 in IA__gtk_widget_event (widget=0x81b6218, event=0x81b24a8)
    at gtkwidget.c:4478
#45 0x006517cb in IA__gtk_propagate_event (widget=0x81b6218, event=0x81b24a8)
    at gtkmain.c:2336
#46 0x0065010a in IA__gtk_main_do_event (event=0x81b24a8) at gtkmain.c:1556
#47 0x003a760a in gdk_event_dispatch (source=0x81b5aa8, callback=0, 
    user_data=0x0) at gdkevents-x11.c:2351
#48 0x0013e1ac in IA__g_main_context_dispatch (context=0x81b5af0)
    at gmain.c:2061
#49 0x001415ef in g_main_context_iterate (context=0x81b5af0, block=1, 
    dispatch=1, self=0x819f990) at gmain.c:2694
#50 0x00141999 in IA__g_main_loop_run (loop=0x8321878) at gmain.c:2898
#51 0x0064f7ee in IA__gtk_main () at gtkmain.c:1163
#52 0x0804b3d7 in main (argc=Cannot access memory at address 0x80
) at main.c:671
(gdb) quit

...
I can invoke the problem on the second run of an 'anagram', usually the word anagram is used. This obviously leads to thinking it's the deletion of my list from the first usage of the function, but in stand alone tests the same problem does not present (hence the long post).

Any help appreciated, a solution hailed!

Cheers, R
 
Old 09-11-2008, 11:21 AM   #2
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
To start with, a few comments about the code you displayed:

1) Rather than writing your own linked list code, check out the standard template library. Unless this is a learning exercise, there's no reason to reinvent the wheel.
2) Your "factorial" function can, fairly rapidly, cause computational inaccuracies.
3) Formulas exist for combinatorial sums, so actually computing the sum seems somewhat perverse.
4) Using two structures when one would suffice is, um, less than optimal.
5) Locating "linked_list[pos]" by counting from 0 when you can insert a list element anywhere in the list means that ll[pos] may not be ll[pos] the next time you look. So the point in using pos as a list index is lost on me.

About your error message: The message seems to have been generated by the gtk, not your code, so it seems likely that you've got a pointer wrong in your linked list code that has let you write into your executable space. It probably happens the second time the code is traversed because the code has been changed (overwritten) by your first run.

Last edited by PTrenholme; 09-11-2008 at 11:22 AM.
 
Old 09-11-2008, 11:58 AM   #3
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
Thanks for the reply.

1) Isn't the STL actually C++, otherwise point me in the right direction.
2) Not my field at all, new subject.
3) Same as 2.
4) Only adds a single pointer and count (int) to mix, but not really.
5) Once managed, then quick multipass can be achieved.
*** this list wasn't written for this project...

I'll have a revision of the gtk code and see if anythings amiss. I did wonder about using malloc within the list init function earlier.

Cheers.
 
Old 09-12-2008, 05:54 PM   #4
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
The stl is, as you note, C++. But it's all source code, and using the code as a template for C code is fairly straight forward.

From your code, it looks like you're trying to find all the "dictionary words" in all possible permutations of the letters of some input string. Perhaps you should consider using a "permutation generation" method to get your permutation.

For example, the "Adjacent Mark" method (see S. M. Johnson, Generation of Permutations by Adjacent Transposition in Mathematical Computation 17 (1963) 282-285) of generating all the permutations of a set of values by exchanging a pair of adjacent values at each step. Using that algorithm your "word search" space at each step would only need to consider strings that would be altered by the exchange performed.

Oh, if you're interested, here's a quick-and-dirty C code implementation of the algorithm:
PHP Code:
#include <stdlib.h>                        
#include <string.h>                        
#include <stdio.h>                         
#define debug 0                            
int main()                                 
{                                          
  
char test1[]="1234";                     
  
char test2[]="anagram";                  
  
int flag 1,                            
      
ret;                                 
  while ((
ret comb(test1flag)) != -1) {
    
printf("%3d - %s\n"rettest1);      
    
flag=0;                                
  }                                        
  
printf("\n");                            
  
flag=1;                                  
  while ((
ret comb(test2flag)) != -1) {
    
printf("%3d - %s\n"rettest2);      
    
flag=0;                                
  }                                        
  exit (
0);                                
}                                          
/*****************************************/
/*                                       */
/* Find the next permutation of a string */
/*                                       */
/*****************************************/
int comb(       // -1 If no more permutations,
                // length of string if returned string is unchanged,
                // otherwise index of character exchanged with next one
  
char string,// String whose characters are being permuted          
  
int new)      // Flag. 1 if string is a new string to be permuted, 0 otherwise                                                                    
{                                                                         
  static 
int n 0,                                                       
             
i,j,m,                                                       
             * 
0,                                                     
             * 
0,                                                     
             * 
0;                                                     
  
char c;                                                                 
  
int k;                                                                  
  
// Are we starting a new string?                                        
  
if (new) {                                                              
    
strlen(string);                                                   
    if (
2) {                                                          
      
// Rase error: Called with fewer than two characters in string      
      
return -1;                                                          
    }                                                                     
    
1;                                                            
    
malloc(sizeof(int));                                          
    
malloc(sizeof(int));                                          
    
malloc(sizeof(int));                                          
    if (!
|| !|| !) {                                                
      
// Raise error: Out of memory                                       
      
return -1;                                                          
    }                                                                     
    for (
0n; ++i) {                                             
      
d[i]=0;
      
e[i]=1;
      
a[i]=i+1;
    }
    
m;
    return 
n;
  }
// If here, not initalizing. Find the next permutation, if any
step2:
  
a[j] = a[j] - e[j];
  if ((
a[j] == 1) || (a[j]== 0)) {
    
e[j]=-e[j];
    
d[j]=d[j];
    
1;
// Are we done?
    
if (== 0) {
      
free(d);
      
free(e);
      
free(a);
      return -
1;
    }
    
goto step2;
  }
  
a[j];
  for (
1n; ++i) {
    
+= d[i];
  }
  
string[k];
  
string[k] = string[1];
  
string[1] = c;
  return 
1;

and here's the output:
Code:
$ gcc comb.c -o comb
$ ./comb
  4 - 1234                  
  2 - 1243                  
  1 - 1423                  
  0 - 4123                  
  2 - 4132                  
  1 - 4312                  
  2 - 4321                  

  7 - anagram
  5 - anagrma
  4 - anagmra
  3 - anamgra
  2 - anmagra
  1 - amnagra
  0 - managra
  5 - managar
  4 - manaagr
  3 - manaagr
  2 - maanagr
  1 - maanagr
  5 - maanarg
  4 - maanrag
  3 - maarnag
  2 - maranag
  5 - maranga
  4 - maragna
  3 - margana
  5 - margaan
  4 - margaan
  5 - margana
 
Old 09-13-2008, 03:11 PM   #5
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
Thanks, i'll have a go through tomorrow, but I assume it's just the first part of the combinations (not all sizes).

Oh, the reason why I calculated the number of combinations was so I could pre-declare the array.

Being American do you know of 'Countdown' (A daily quiz show here in UK, with the ever so lovely Carol Vordaman)?



Here's a very weird first episode.
But i've not seen this one.


P.S. I think one of my first python versions worked by a similar method to the one you show. My final python one could take upto 50 seconds to work through though (on 9 letters).
 
Old 09-13-2008, 05:44 PM   #6
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
I suspect that you want all the (distinct) partitions of the permutations, unless, of course, you're searching for phrases rather than words. The point, if you're searching for words, is that you can't pre-allocate space for the words unless you don't care that many entries might be duplicates.

The solution, I believe, is to use a binary (perhaps hashed) tree to store the "words" and throw out any duplicates. (Or count them if you're interested.)

The point in the adjacent letter switch method is that you only need to look for partitions which contain the switched letters when you're storing the "words."

If I get time, perhaps I'll see if I can put together a package to build the "word" list.

By the way, the "raw" number of partitions of an n-letter string is 2**(n-1), not n!.
 
Old 09-13-2008, 06:17 PM   #7
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
Well, no, I don't actually watch much video programming except a little "American Football" in the Fall, so I've never seen "Countdown" nor, in fact, ever heard about it.

To return to you problem:

1) I suspect that you're interested in the partitions of each permutation, not the combinations of letters. The point being that the number of partitions of a n-character string is 2^(n-1), and n! is the number of permutations on things, so the "raw" number of "words" you can generate is (n!)(2^(n-1)). Thus the number of combinations is, perhaps, not too relevant to the problem.

2) In fact, unless you're looking for phrases rather than words in your string, you're probably more interested in the distinct words in the partitions of the permutations on the letters in the input work. That was the point in using the "adjacent letter" permutation method: you only need to look at partrtion containing the "switched" positions for new "words," and then only if the stitched letters are different from each other.

To expand on point 2: If my understanding of your objective is correct, than I believe that you best strategy would be to store the generated "words" in a hashed binary tree, using the first letter as your hash key, and a binary tree under that hash as your (dynamic) storage. So you initial allocation would be an array of binary tree bases, one for each (distinct) letter in you input string. Than store each (distinct) partition under it's hash, either ignoring or counting any duplicated strings.

If I have time, I'll see if I can throw something together.

P.S.: The "ugly" goto in the q&d code above can be eliminated by a while (1) {if ... else break construct. As I said, it was "quic and dirty."
 
Old 09-13-2008, 06:58 PM   #8
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
If I was allowed a dog, I'd buy 'it' one of these. [good site]

I'm not sure if i'll read 'Stranger in a Strange Land' by Heinlein, but Case likes the fact about the word 'cyberspace' here, and I learnt a new word, 'neologism'.



The maths is mainly reworked from quite a basic statistics book, developing from what I prised from the python examples, so those short cuts sound good (tomorrow i'll test).

The binary tree concept works by solving the thought of reiterating the list to remove duplicates, which saves the time which wouldn't really be saved (on a large search), (omg i'm lazy at times).

Cheers
 
Old 09-16-2008, 03:04 PM   #9
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
If you're still interested, here's a "all words made from letters in a input stream" solution which relies on Linux tools rather than lists.

First, here's the output (and command line) for "anagram:"
Code:
$ echo anagram | ./comb |sort -u|hunspell -G          
a                                                                         
agar                                                                      
am                                                                        
an                                                                        
anagram                                                                   
g                                                                         
gar                                                                       
gm                                                                        
gr                                                                        
gram                                                                      
m                                                                         
ma                                                                        
mag                                                                       
man                                                                       
mar                                                                       
mg                                                                        
mgr                                                                       
n                                                                         
nag                                                                       
r                                                                         
rag                                                                       
ram                                                                       
ran                                                                       
rang                                                                      
rm
and here's the source code:
PHP Code:
/* Find the next permutation of a string */                               
#include <stdlib.h>                                                       
#include <string.h>                                                       
#include <stdio.h>                                                        
#define debug 0                                                           
extern FILE stdin;                                                      
extern FILE stdout;                                                     
extern FILE stderr;                                                     
/**********************************************/                          
/*                                            "/                          
/* Partition a string into all its substrings */                          
/*                                            */                          
/**********************************************/                          
void partition(                 // No reurn value                         
    
const char * const string,  // String to be partitioned               
    
FILE out)                 // File where each partition is to be written                                                                       
{                                                                         
  
long int npart;               // Number of partitions                   
  
long int bits;                // Binary value holder                    
  
int n;                        // Length of input strng                  
  
register int pos;             // Character to be next printed           
  
register int k;               // Inner loop index                       
  
long int i;                   // Current partition number               
  
strlen(string);                                                     
  
npart = ((long int1) << (1);                                      
  for (
npart 1>= 0; --i) {                                      
    
bits i;                                                             
    
pos=0;                                                                
    while (
bits) {                                                        
      
fprintf(out,"%c",string[pos++]);                                    
      if (
bits 1fprintf(out,"\n");                                    
      
bits bits 2;                                                    
    }                                                                     
    if (
pos n) {                                                        
      for (;
pos<n;++posfprintf(out,"%c",string[pos]);                   
      
fprintf(out,"\n");                                                  
    }                                                                     
  }                                                                       
}                                                                         

int comb(       // -1 If no more permutations,
                // length of string if returned string is unchanged,
                // otherwise index of character exchanged with next one
  
char string,// String whose characters are being permuted          
  
int *new)     // Flag. 1 if string is a new string to be permuted, 0 otherwise                                                                    
{                                                                         
  static 
int n 0,                                                       
             
i,j,                                                         
             * 
0,                                                     
             * 
0,                                                     
             * 
0;                                                     
  
char c;                                                                 
  
int k;                                                                  
  
// Are we starting a new string?                                        
  
if (*new) {                                                             
    
strlen(string);                                                   
    
// Remove any terminating new line character                          
    
if (string[n-1]=='\n'string[--n]=0;                                 
    
// Do we have anything left?                                          
    
if (2) {                                                          
      
fprintf(stderr,"\"%s\" is too short to permute.\n"string);        
      return -
1;                                                          
    }                                                                     
    
malloc(sizeof(int));                                          
    
malloc(sizeof(int));                                          
    
malloc(sizeof(int));                                          
    if (!
|| !|| !) {                                                
      
fprintf(stderr,"comb: Insuffent dynamic memory.\n");                
      if (
dfree(d);                                                     
      if (
efree(e);                                                     
      if (
afree(a);                                                     
      return -
1;                                                          
    }                                                                     
    
// Initalize the tracking arrays                                      
    
for (0n; ++i) {                                             
      
d[i]=0;                                                             
      
e[i]=1;                                                             
      
a[i]=i+1;                                                           
    }                                                                     
    
// Start the exchage with the last character                          
    
n;                                                                
    
// Set the 'new string" flag off                                      
    
*new=0;                                                               
    return 
n;                                                             
  }                                                                       
// If here, not initalizing. Find the next permutation, if any            
  
while (1) {                                                             
    
a[j] = a[j] - e[j];                                                   
    if ((
a[j] == 1) || (a[j]== 0)) {                                  
      
e[j]=-e[j];                                                         
      
d[j]=d[j];                                                      
      
1;                                                          
// Are we done?                                                           
      
if (0) {                                                        
        
free(d);                                                          
        
free(e);                                                          
        
free(a);                                                          
        return -
1;                                                        
      }                                                                   
    }                                                                     
    else break;                                                           
  }                                                                       
  
a[j];                                                               
  for (
1n; ++i) {                                           
    
+= d[i];                                                            
  }                                                                       
  
string[k];                                                          
  
string[k] = string[1];                                              
  
string[1] = c;                                                      
  return 
1;                                                           
}                                                                         

int main(int argcchar **argv)
{
  
FILE in;        // Input file pointer
  
FILE out;       // Output file pointer
  
char word[256];   // Current word holder
  
int i;            // Temporary integers (loop indices, etc.)
  
in = (argc 1) ? fopen(argv[1],"r") : stdin;
  if (! 
in) {
    if (
argc 1)
      
fprintf(stderr"Could not open %s for input.\n"argv[1]);
    else
      
fprintf(stderr"Could not open stdin for input.\n");
    exit (
1);
  }
  
out = (argc 2) ? fopen(argv[2],"w") : stdout;
  if (! 
out) {
    if (
argc 2)
      
fprintf(stderr"Could not open %s for output.\n"argv[2]);
    else
      
fprintf(stderr"Could not open stdout for output.\n");
    exit (
1);
  }
  while (
fgets(word256in)) {
// Write all permutations of "word' to stdout
    
1;
    while (
comb(word,&i)>=0) {
      
partition(wordstdout);
    }
  }
  exit (
0);

 
Old 09-17-2008, 03:29 AM   #10
rubadub
Member
 
Registered: Jun 2004
Posts: 233

Original Poster
Rep: Reputation: 33
Yes i'm still interested, work caught up with me on Sunday, so i'll probably not have the time I want to dedicate to this until the weekend. But 'hunspell' is a new one on me, a quick perusal of it's man page looks interesting, thanks for the heads up!

Rob
 
Old 09-20-2008, 01:16 PM   #11
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
O.K., I found your problem interesting, so here's another take that works a little faster. Instead of linked lists, I used SQLite to sort and store the data.

I tried my last code on this string and aborted after an hour or so. This code finished in about 10 minutes.

First, here's the output:
Code:
$ echo averylongstring | ./comb2 | hunspell -G
an                                                                     
as                                                                     
at                                                                     
av                                                                     
ave                                                                    
aver                                                                   
avers                                                                  
avert                                                                  
avg                                                                    
ay                                                                     
ea                                                                     
en                                                                     
er                                                                     
erg                                                                    
err                                                                    
es                                                                     
gave                                                                   
gin                                                                    
gist                                                                   
go                                                                     
gong                                                                   
gongs                                                                  
gr                                                                     
grin                                                                   
gs                                                                     
gt                                                                     
in                                                                     
ion                                                                    
is                                                                     
it                                                                     
iv                                                                     
la                                                                     
lav                                                                    
lave                                                                   
lay                                                                    
lg                                                                     
lion                                                                   
lo                                                                     
log                                                                    
loin                                                                   
long                                                                   
longs                                                                  
lorn                                                                   
lot                                                                    
ls                                                                     
lyre                                                                   
naive                                                                  
naiver                                                                 
nave                                                                   
no                                                                     
non                                                                    
nylon                                                                  
oi                                                                     
on                                                                     
or                                                                     
over                                                                   
rat                                                                    
rave                                                                   
raver                                                                  
re                                                                     
rev                                                                    
rig                                                                    
ring
rs
rt
sag
save
saver
sit
so
son
song
st
stir
string
ta
ti
tn
to
ton
tong
tongs
tr
trig
try
ts
veg
very
vet
vi
vie
voe
vs
ya
ye
yer
yo
yr
And here's the source code. Note that I chose to use an "ephemeral" data base, but you could choose to save the information is a data base file and use it in other programs if you wished.
PHP Code:
#include <stdlib.h>                                                   
#include <string.h>                                                   
#include <stdio.h>                                                    
#include <sqlite3.h>                                                  
#define debug 0                                                       
extern FILE stdin;                                                  
extern FILE stdout;                                                 
extern FILE stderr;                                                 
/**********************************************/                      
/*                                            */                      
/* SQLite error report helper function        */                      
/*                                            */                      
/**********************************************/                      
int check_code(         // Return 0 is OK, 1 otherwise                
  
sqlite3 db,         // Data base information pointer              
  
sqlite3_stmt *stmt,   // Statement being checked                    
  
const int rc,         // Value to check                             
  
const char text,    // Text to print if check fails               
  
const int target)     // SQLite expected return code                
{                                                                     
  if (
rc != target) {                                                 
    
fprintf(stderr"%s: %s\n"textsqlite3_errmsg(db));            
    if (
stmtsqlite3_finalize(stmt);                                 
    return 
1;                                                         
  }                                                                   
  return 
0;                                                           
}                                                                     
/**********************************************/                      
/*                                            */                      
/* Partition a string into all its substrings */                      
/*                                            */                      
/**********************************************/                      
int partition(                  // Return 0 on success, 1 otherwise   
    
const char * const string,  // String to be partitioned           
    
sqlite3 db)               // Pointer to the SQLite data base to use for storaage                                                        
{                                                                      
  
long int npart;               // Number of partitions                
  
long int bits;                // Binary value holder                 
  
int n;                        // Length of input string              
  
register int pos;             // Character to be next printed        
  
register int k;               // Inner loop index                    
  
long int ij;                // Current partition number            
  
char str;                   // Word holder                         
  
sqlite3_stmt *stmt;           // Insert statement holder             
  
char errmsg;                                                       
  
int rc;                       // SQLite return code holder           
  
char insert[256];                                                    

  
strlen(string);
  
npart = ((long int1) << (1);

  
str = (char *) malloc(n*sizeof(char));
  if (!
str) {                           
    
fprintf(stderr,"partition: Could not allocate %d characters for \"str.\"\n"n);                                                          
    return 
1;                                                          
  }                                                                    

// Find the (next) partition and insert it into the data base if it's longer than 1 character                                                 
  
0;                                                               
  for (
npart 1>= 0; --i) {                                   
    
bits i;                                                          
    
pos=0;                                                             
    
0;                                                             
    while (
bits) {                                                     
      
str[k++] = string[pos++];                                        
      if (
bits 1) {                                                  
        
str[k] = (char0;                                             
// Add the word to the data base if it's long enough                   
        
if (1) {                                                   
          
sqlite3_snprintf(255insert"INSERT INTO WORDS (WORD) VALUES(%Q)"str);                                                          
          
rc sqlite3_exec(dbinsertNULLNULL, &errmsg);          
          if (
check_code(dbstmtrc"partition: Problem inserting WORD"SQLITE_OK)) {                                                     
            
sqlite3_free(errmsg);                                      
            
sqlite3_close(db);                                         
            exit (
1);                                                  
          }                                                            
        }                                                              
// And compute the next word . . .                                     
        
++j;                                                           
        
0;                                                         
      }                                                                
      
bits bits 2;                                                 
    }                                                                  
// Finished with the current value of j. Process any remaining characters.                                                                    
    
while (pos nstr[k++] = string[pos++];                          
    
str[k] = (char0;                                                 
    
pos 0;                                                           
// Add the last string if it's long enough                             
    
if (1) {                                                       
      
sqlite3_snprintf(255insert"INSERT INTO WORDS (WORD) VALUES(%Q)"str);                                                              
      
rc sqlite3_exec(dbinsertNULLNULL, &errmsg);              
      if (
check_code(dbstmtrc"partition: Problem inserting WORD"SQLITE_OK)) {                                                         
         
sqlite3_free(errmsg);                                         
         
sqlite3_close(db);                                            
         exit (
1);                                                     
      }                                                                
    }                                                                  
    
bits = --i;                                                        
    
0;                                                             
  }                                                                    
  return 
0;                                                            
}                                                                      

int comb(       // -1 If no more permutations,
                // length of string if returned string is unchanged,
                // otherwise index of character exchanged with next one
  
char string,// String whose characters are being permuted          
  
int *new)     // Flag. 1 if string is a new string to be permuted, 0 otherwise                                                              
{                                                                      
  static 
int n 0,                                                    
             
i,j,                                                      
             * 
0,                                                  
             * 
0,                                                  
             * 
0;                                                  
  
char c;                                                              
  
int k;                                                               
  
// Are we starting a new string?                                     
  
if (*new) {                                                          
    
strlen(string);                                                
    
// Remove any terminating new line character                       
    
if (string[n-1]=='\n'string[--n]=0;                              
    
// Do we have anything left?                                       
    
if (2) {                                                       
      
fprintf(stderr,"\"%s\" is too short to permute.\n"string);     
      return -
1;                                                       
    }                                                                  
    
malloc(sizeof(int));                                       
    
malloc(sizeof(int));                                       
    
malloc(sizeof(int));                                       
    if (!
|| !|| !) {                                             
      
fprintf(stderr,"comb: Insufficient dynamic memory.\n");          
      if (
dfree(d);                                                  
      if (
efree(e);                                                  
      if (
afree(a);                                                  
      return -
1;                                                       
    }                                                                  
    
// Initialize the tracking arrays                                  
    
for (0n; ++i) {                                          
      
d[i]=0;                                                          
      
e[i]=1;                                                          
      
a[i]=i+1;                                                        
    }                                                                  
    
// Start the exchange with the last character                      
    
1;                                                         
    
// Set the 'new string" flag off                                   
    
*new=0;                                                            
    return 
n;                                                          
  }                                                                    
// If here, not initializing. Find the next permutation, if any        
  
while (1) {                                                          
    
a[j] = a[j] - e[j];                                                
    if ((
a[j] == 1) || (a[j]== 0)) {                               
      
e[j]=-e[j];                                                      
      
d[j]=d[j];                                                   
      
1;                                                       
// Are we done?                                                        
      
if (== 0) {                                                    
        
free(d);                                                       
        
free(e);                                                       
        
free(a);                                                       
        return -
1;                                                     
      }                                                                
    }                                                                  
    else break;                                                        
  }                                                                    
  
a[j];                                                            
  for (
1n; ++i) {                                        
    
+= d[i];                                                         
  }                                                                    
  
string[k];                                                       
  
string[k] = string[1];                                           
  
string[1] = c;                                                   
  return 
1;                                                        
}                                                                      

int main(int argcchar **argv)
{                              
  
char word[256];       // Current word holder
  
char msg[256];        // Potential error message holder
  
int i;                                                 
  
register int j,k,l;   // Temporary integers (loop index, etc.)
// SQLite stuff                                                 
  
sqlite3 *db;                                                  
  
sqlite3_stmt *stmt 0;                                       
  
int rc;                                                       
  
char create[]="CREATE TABLE WORDS (WORD VARCHAR(255) PRIMARY KEY ON CONFLICT IGNORE)";                                                      
  
char select[]="SELECT WORD FROM WORDS ORDER BY WORD";                
  
char *errmsg = (char *) NULL;                                        
// End SQLite stuff                                                    

  
while (fgets(word256stdin))   {
    
// Create a temporary data base to hold the strings found
    
rc sqlite3_open_v2(NULL, &db0errmsg);              
    
sprintf(msg"%s: Could not open an ephemeral SQLite data base"argv[0]);                                                                
    if (
check_code(dbstmtrcmsgSQLITE_OK)) {                    
      
close(db);                                                       
      exit(
1);
    }
    
// Create the table to store the "words"
    
rc sqlite3_exec(dbcreateNULLNULL, &errmsg);
    
sprintf(msg"%s: Could not create table WORDS"argv[0]);
    if (
check_code(dbstmtrcmsgSQLITE_OK)) {
      
sqlite3_close(db);
      exit(
1);
    }
    
// Insert all permutations of "word' into the temporary data base
    
1;
    while (
comb(word, &i) >= 0) {
      if (
partition(worddb)) {
        
// If we get here we had a data base error. Abort.
        
sqlite3_close(db);
        exit (
1);
      }
    }
    
// Write the "words" stored in the data base to the output file
    
rc sqlite3_prepare_v2(dbselect, -1, &stmt0);
    if (
rc != SQLITE_OK) {
      
fprintf(stderr,"%s: Error preparing %s: %s\n"argv[0], selectsqlite3_errmsg(db));
      
sqlite3_finalize(stmt);
      exit(
1);
    }
    while ((
rc sqlite3_step(stmt)) == SQLITE_ROW) {
      
strncpy(word, (char *) sqlite3_column_text(stmt0), 255);
      
fprintf(stdout,"%s\n"word);
    }
    
sprintf(msg"%s: Error retrieving data from WORDS"argv[0]);
    
check_codedbstmtrcmsgSQLITE_DONE);
    
sqlite3_finalize(stmt);
    
sqlite3_close(db);
  }
  exit ((
rc==SQLITE_DONE) ? 1);

 
Old 09-21-2008, 01:21 PM   #12
PTrenholme
Senior Member
 
Registered: Dec 2004
Location: Olympia, WA, USA
Distribution: Fedora, (K)Ubuntu
Posts: 4,149

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
As a further improvement, here's a version that eliminates processing any partition where identical character are being exchanged, and eliminates any duplicates from the strings to be partitioned. Oh, a couple of other things:

1) Whilst writing this code, I inadvertently attempted to free memory which had not,in fact, been allocated. That produced the "double linked list" error message about which you originally asked. So I suspect that your code was somehow trying to free memory you'd not actually allocated.

2) The funny code in main is there because the compiler complained when I used process_sql in the sqlite_exec call. I don't understand why, and, in fact, when I finish this note I'm going to start a thread to see what other people think might be the explanation.

So, here's the revised code. The changes are mostly in main and the recursive call at the end of comb to skip swapping identical characters.
PHP Code:
/* Find the next permutation of a string */
#include <stdlib.h>                        
#include <string.h>                        
#include <stdio.h>                         
#include <sqlite3.h>                       
#define debug 0                            
extern FILE stdin;                       
extern FILE stdout;                      
extern FILE stderr;                      
/**********************************************/
/*                                            */
/* SQLite error report helper function        */
/*                                            */
/**********************************************/
int check_code(         // Return 0 is OK, 1 otherwise
  
sqlite3 db,         // Data base information pointer
  
sqlite3_stmt *stmt,   // Statement being checked      
  
const int rc,         // Value to check               
  
const char text,    // Text to print if check fails 
  
const int target)     // SQLite expected return code  
{                                                       
  if (
rc != target) {                                   
    
fprintf(stderr"%s: %s\n"textsqlite3_errmsg(db));
    if (
stmtsqlite3_finalize(stmt);                     
    return 
1;                                             
  }                                                       
  return 
0;                                               
}                                                         
/**********************************************/          
/*                                            */          
/* Partition a string into all its substrings */          
/*                                            */          
/**********************************************/          
int partition(                  // Return 0 on success, 1 otherwise
    
const char * const string,  // String to be partitioned        
    
sqlite3 db)               // Pointer to the SQLite data base to use for storage
{                                                                                     
  
long int npart;               // Number of partitions                               
  
long int bits;                // Binary value holder                                
  
int n;                        // Length of input string                             
  
register int pos;             // Character to be next printed                       
  
register int k;               // Inner loop index                                   
  
long int ij;                // Current partition number                           
  
char str;                   // Word holder                                        
  
sqlite3_stmt *stmt;           // Insert statement holder                            
  
char errmsg;                                                                      
  
int rc;                       // SQLite return code holder                          
  
char insert[256];                                                                   

  
strlen(string);
  
npart = ((long int1) << (1);

  
str = (char *) malloc(n*sizeof(char));
  if (!
str) {                           
    
fprintf(stderr,"partition: Could not allocate %d characters for \"str.\"\n"n);
    return 
1;                                                                       
  }                                                                                 

// Find the (next) partition and insert it into the data base if it's longer than 1 character
  
0;                                                                                     
  for (
npart 1>= 0; --i) {                                                         
    
bits i;                                                                                
    
pos=0;                                                                                   
    
0;                                                                                   
    while (
bits) {                                                                           
      
str[k++] = string[pos++];                                                              
      if (
bits 1) {                                                                        
        
str[k] = (char0;                                                                   
// Add the word to the data base if it's long enough                                         
        
if (1) {                                                                         
          
sqlite3_snprintf(255insert"INSERT INTO WORDS (WORD) VALUES(%Q)"str);         
          
rc sqlite3_exec(dbinsertNULLNULL, &errmsg);                                
          if (
check_code(dbstmtrc"partition: Problem inserting WORD"SQLITE_OK)) {    
            
sqlite3_free(errmsg);                                                            
            
sqlite3_close(db);                                                               
            exit (
1);                                                                        
          }                                                                                  
        }                                                                                    
// And compute the next word . . .                                                           
        
++j;                                                                                 
        
0;                                                                               
      }                                                                                      
      
bits bits 2;                                                                       
    }                                                                                        
// Finished with the current value of j. Process any remaining characters.                   
    
while (pos nstr[k++] = string[pos++];                                                
    
str[k] = (char0;                                                                       
    
pos 0;                                                                                 
// Add the last string if it's long enough                                                   
    
if (1) {                                                                             
      
sqlite3_snprintf(255insert"INSERT INTO WORDS (WORD) VALUES(%Q)"str);             
      
rc sqlite3_exec(dbinsertNULLNULL, &errmsg);                                    
      if (
check_code(dbstmtrc"partition: Problem inserting WORD"SQLITE_OK)) {        
         
sqlite3_free(errmsg);                                                               
         
sqlite3_close(db);                                                                  
         exit (
1);                                                                           
      }                                                                                      
    }                                                                                        
    
bits = --i;                                                                              
    
0;                                                                                   
  }                                                                                          
  return 
0;                                                                                  
}                                                                                            

int comb(       // -1 If no more permutations,
                // length of string if returned string is unchanged,
                // otherwise index of character exchanged with next one
  
char string,// String whose characters are being permuted          
  
int *new)     // Flag. 1 if string is a new string to be permuted, 0 otherwise
{                                                                               
  static 
int n 0,                                                             
             
i,j,                                                               
             * 
0,                                                           
             * 
0,                                                           
             * 
0;                                                           
  
char c;                                                                       
  
int k;                                                                        
  
// Are we starting a new string?                                              
  
if (*new) {                                                                   
    
strlen(string);                                                         
    
// Remove any terminating new line character                                
    
if (string[n-1]=='\n'string[--n]=0;                                       
    
// Do we have anything left?                                                
    
if (2) {                                                                
      
fprintf(stderr,"\"%s\" is too short to permute.\n"string);              
      return -
1;                                                                
    }                                                                           
    
malloc(sizeof(int));                                                
    
malloc(sizeof(int));                                                
    
malloc(sizeof(int));                                                
    if (!
|| !|| !) {                                                      
      
fprintf(stderr,"comb: Insufficient dynamic memory.\n");                   
      if (
dfree(d);                                                           
      if (
efree(e);                                                           
      if (
afree(a);                                                           
      return -
1;                                                                
    }                                                                           
    
// Initialize the tracking arrays                                           
    
for (0n; ++i) {                                                   
      
d[i]=0;                                                                   
      
e[i]=1;                                                                   
      
a[i]=i+1;                                                                 
    }                                                                           
    
// Start the exchange with the last character                               
    
1;                                                                  
    
// Set the 'new string" flag off                                            
    
*new=0;                                                                     
    return 
n;                                                                   
  }                                                                             
// If here, not initializing. Find the next permutation, if any                 
  
while (1) {                                                                   
    
a[j] = a[j] - e[j];                                                         
    if ((
a[j] == 1) || (a[j]== 0)) {                                        
      
e[j]=-e[j];                                                               
      
d[j]=d[j];                                                            
      
1;                                                                
// Are we done?                                                                 
      
if (== 0) {                                                             
        
free(d);                                                                
        
free(e);                                                                
        
free(a);                                                                
        return -
1;                                                              
      }                                                                         
    }                                                                           
    else break;                                                                 
  }                                                                             
  
a[j];                                                                     
  for (
1n; ++i) {                                                 
    
+= d[i];                                                                  
  }                                                                             
  if (
string[k-1] != string[k]) {                                               
    
string[k];                                                              
    
string[k] = string[1];                                                  
    
string[1] = c;                                                          
    return 
1;                                                               
  }                                                                             
  
// Recursive call to deal with exchange of duplicate characters               
  
return comb(string, new);                                                     
}                                                                               

/******************************************************/
/*                                                    */
/* Call-back function used by sqlite3_exec()          */
/*                                                    */
/******************************************************/
static int process_sql// Return 0 on success          
  
sqlite3 *db,          // Data base being processed    
  
int argc,             // Number of row values returned by query
  
char **argv,          // Data values returned                  
  
char **azColName)     // Name of the data columns returned     
{                                                                
  if (
argc 0) return 1;                                        
  if (
partition(argv[0], db)) {                                  
    
// If we get here we had a data base error. Abort.           
    
sqlite3_close(db);                                           
    exit (
1);                                                    
  }                                                              
  
// Partition the root word                                     
  
if (partition(argv[0], db)) {                                  
    
// If we get here we had a data base error. Abort.           
    
sqlite3_close(db);                                           
    exit (
1);                                                    
  }                                                              
  return 
0;                                                      
}                                                                

int main(int argcchar **argv)
{                              
  
char word[256];       // Current word holder
  
char msg[256];        // Potential error message holder
  
int i;                                                 
  
register int j,k,l;   // Temporary integers (loop index, etc.)
// SQLite stuff                                                 
  
sqlite3 *db;                                                  
  
sqlite3_stmt *stmt 0;                                       
  
sqlite3_stmt *root 0;                                       
  
int rc;                                                       
  
char create[]= "CREATE TABLE WORDS (WORD TEXT PRIMARY KEY ON CONFLICT IGNORE)";
  
char select[]= "SELECT WORD FROM WORDS ORDER BY WORD";                         
  
char roots[]=  "CREATE TABLE ROOTS (ROOT TEXT PRIMARY KEY ON CONFLICT IGNORE)";
  
char getroot[]="SELECT ROOT FROM ROOTS ORDER BY ROOT";                         
  
char command[256]; // Command string holder                                    
  
char *errmsg = (char *) NULL;                                                  

  
// Create a temporary data base to hold the strings found
  
rc sqlite3_open_v2(NULL, &db0errmsg);              
  
sprintf(msg"%s: Could not open an ephemeral SQLite data base"argv[0]);
  if (
check_code(dbstmtrcmsgSQLITE_OK)) {                           
    
close(db);                                                              
    exit(
1);                                                                
  }                                                                         
  
// Create the table to store the root "words"                             
  
rc sqlite3_exec(dbrootsNULLNULL, &errmsg);                        
  
sprintf(msg"%s: Could not create table ROOTS"argv[0]);                
  if (
check_code(dbstmtrcmsgSQLITE_OK)) {                           
    
sqlite3_close(db);                                                      
    exit(
1);                                                                
  }                                                                         
  
// Create the table to store the "words"                                  
  
rc sqlite3_exec(dbcreateNULLNULL, &errmsg);                       
  
sprintf(msg"%s: Could not create table WORDS"argv[0]);                
  if (
check_code(dbstmtrcmsgSQLITE_OK)) {                           
    
sqlite3_close(db);                                                      
    exit(
1);                                                                
  }                                                                         
// End SQLite stuff                                                         

// For each input string . ' '
  
while (fgets(word256stdin))   {
    
// Insert all permutations of "word' into the temporary data base
    
1;                                                           
    while (
comb(word, &i) >= 0) {                                    
      
sqlite3_snprintf(255command"INSERT INTO WORDS (WORD) VALUES(%Q)"word);
      
rc sqlite3_exec(dbcommandNULLNULL, &errmsg);
      
sprintf(msg"%s: Problem inserting WORD (\"%s\")"argv[0], word);
      if (
check_code(dbstmtrcmsgSQLITE_OK)) {
         
sqlite3_free(errmsg);
         
sqlite3_close(db);
         exit (
1);
      }
    }
  }
  
// O.K., now all the unique, permuted strings from the input are ready to be partitioned. Do it.
  //
  // Note: The processing is done in the call-back routine, "process_sql"
  //
  
rc sqlite3_exec(dbselect, (sqlite3_callbackprocess_sqldb, &errmsg);
  
sprintf(msg"%s: Problem creating WORDS"argv[0]);
  if (
check_code(dbstmtrcmsgSQLITE_OK)) {
    
sqlite3_free(errmsg);
    
sqlite3_close(db);
    exit(
1);
  }
  
// Write the "words" stored in the data base to the output file
  
rc sqlite3_prepare_v2(dbselect, -1, &stmt0);
  if (
rc != SQLITE_OK) {
    
fprintf(stderr,"%s: Error preparing %s: %s\n"argv[0], selectsqlite3_errmsg(db));
    
sqlite3_finalize(stmt);
    exit(
1);
  }
  while ((
rc sqlite3_step(stmt)) == SQLITE_ROW) {
    
strncpy(word, (char *) sqlite3_column_text(stmt0), 255);
    
fprintf(stdout,"%s\n"word);
  }
  
sprintf(msg"%s: Error retrieving data from WORDS"argv[0]);
  
check_codedbstmtrcmsgSQLITE_DONE);
  
sqlite3_finalize(stmt);
  
sqlite3_close(db);
  exit ((
rc==SQLITE_DONE) ? 1);


Last edited by PTrenholme; 09-30-2008 at 05:42 PM. Reason: Changed the sqlite3_exec call in main() to cast the callback to a sqlite3_callback pointer
 
  


Reply

Tags
sqlite, sqlite3


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
*** glibc detected *** malloc() / free()/ double RohanShrivastav Programming 12 10-01-2012 10:08 AM
*** glibc detected *** double free or corruption vvenugop Linux - General 0 02-19-2008 09:11 AM
*** glibc detected *** corrupted double-linked list: 0x084a25c0 *** Looooooka Slackware 2 03-06-2006 08:41 AM
What the heck is a corrupted double linked list??? The_Nerd Programming 18 02-10-2006 03:17 PM


All times are GMT -5. The time now is 09:49 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration