qsort clobbering memory location

[William Buch]

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

MEMORY LOCATION OK HERE
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table[i])
{
printf("NULL Table call.\n");
return;
}
linkTable = table[i];
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);

printf("%x\n", list); NOT OK!!!!!!!!

//printf("%i\n", cmp);
qsort (table[i], ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[i][k] != table[i][j]) {
k = k + 1;
table[i][k] = table[i][j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[i][ptab[j]] = k;
}

printf("%x\n", list); NOT OK!!!!!!!!!!!!! !

printf("Compres sion Complete %i.\n", k);
table[i][k+1] = -1; /* End of table Marker */
sizeTab[i] = k+1;
entries += k+1;
printf("Before Blah\n");

printf("In use %x\n", list); NOT OK!!!!!!!!!!!!! !!!

printf("Blah\n" );
}
I tried list as static and "unstatic" but always global. Could that
be the problem? Any help would be greatly appreciated ASAP!

[Artie Gold]

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

MEMORY LOCATION OK HERE
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table[i])
{
printf("NULL Table call.\n");
return;
}
linkTable = table[i];
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);

printf("%x\n", list); NOT OK!!!!!!!!

//printf("%i\n", cmp);
qsort (table[i], ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[i][k] != table[i][j]) {
k = k + 1;
table[i][k] = table[i][j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[i][ptab[j]] = k;
}

printf("%x\n", list); NOT OK!!!!!!!!!!!!! !

printf("Compres sion Complete %i.\n", k);
table[i][k+1] = -1; /* End of table Marker */
sizeTab[i] = k+1;
entries += k+1;
printf("Before Blah\n");

printf("In use %x\n", list); NOT OK!!!!!!!!!!!!! !!!

printf("Blah\n" );
}
I tried list as static and "unstatic" but always global. Could that
be the problem? Any help would be greatly appreciated ASAP!

Well, obviously there's a bug in the program. How, may I ask, is
*anyone* supposed to know where the problem is without seeing the
relevant declarations?

Present code that can be compiled and run; it greatly enhances your
chance of receiving appropriate help.

[One thing to look for is `off-by-one' errors -- one variety of which is
writing past the end of an array.]

HTH,
--ag

--
Artie Gold -- Austin, Texas

[Jack Klein]

On 26 Jan 2004 14:46:47 -0800, wl****@earthlin k.net (William Buch)
wrote in comp.lang.c:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

MEMORY LOCATION OK HERE
for (i = 0; i < list->in_use; i++) {
[snip]
printf("%x\n", list); NOT OK!!!!!!!!
[snip]
printf("%x\n", list); NOT OK!!!!!!!!!!!!! !
[snip]
printf("In use %x\n", list); NOT OK!!!!!!!!!!!!! !!!

Unless the first line of your snippet above has a serious error,
'list' is a pointer to a structure or union type. Passing it to
printf() with a %x conversion specifier produces undefined behavior.

This is not likely to be the cause of your problem, it is probably in
the code you didn't post.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[pete]

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program.

Since you can only run the program four times, once,
(then it becomes the fifth time and the sixth time, etc.)
what do you mean by "ALWAYS the fourth time running the program"?

--
pete

[Michel Bardiaux]

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)

if(item1<=item2 )
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

HTH,
--
Michel Bardiaux
Peaktime Belgium S.A. Bd. du Souverain, 191 B-1160 Bruxelles
Tel : [phone]

[pete]

Michel Bardiaux wrote:

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)

if(item1<=item2 )
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

--
pete

[William Buch]

pete <pf*****@mindsp ring.com> wrote in message news:<40******* ****@mindspring .com>...

Michel Bardiaux wrote:

William Buch wrote:

I have a strange problem. The code isn't written by me, but uses the
qsort function in stdlib. ALWAYS, the fourth time through, the memory
location of variable list (i.e. mem location = 41813698) becomes 11,
then the program crashes. It is obviously qsort that may me
overwritten the used memory location. The weird thing is that it is
ALWAYS the fourth time running the program. Below is the code

[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2 )
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:
static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));
table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));
sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list[i], phone_from_id (j));
table[i][j] = phone_to_id (triphoneStr, FALSE);
if (table[i][j] >= 0)
triphoneContext ++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[i][j] < 0) {
sprintf (triphoneStr, list->list[i], "SIL");
table[i][j] = phone_to_id (triphoneStr, FALSE);
if (table[i][j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[i][j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list[i]);
p = strchr (stmp, '(');
*p = '\0';
table[i][j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[i][j] = hmm_pid2sid(pho ne_map(table[i][j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table[i])
{
printf("NULL Table call.\n");
return;
}
linkTable = table[i];
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table[i], ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[i][k] != table[i][j]) {
k = k + 1;
table[i][k] = table[i][j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[i][ptab[j]] = k;
}
printf("%x\n", list);
printf("Compres sion Complete %i.\n", k);
table[i][k+1] = -1; /* End of table Marker */
sizeTab[i] = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n" );
}
//printf("\t%6d triphones\n\t%6 d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext , silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory? Could
it be possible that something is not being freed, thus qsort (or my
program) is allocating more and more memory and eventually overwrites
the variable in question? I am a little out of my league when it
comes to debugging problems like these.

[pete]

William Buch wrote:

static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

The difference between two signed integers is unsuitable
for a compar of random array elements.
The result can overflow.

--
pete

[Rob Thorpe]

wl****@earthlin k.net (William Buch) wrote in message news:<47******* *************** ****@posting.go ogle.com>...

pete <pf*****@mindsp ring.com> wrote in message news:<40******* ****@mindspring .com>...

Michel Bardiaux wrote:

William Buch wrote:

> I have a strange problem. The code isn't written by me, but uses the
> qsort function in stdlib. ALWAYS, the fourth time through, the memory
> location of variable list (i.e. mem location = 41813698) becomes 11,
> then the program crashes. It is obviously qsort that may me
> overwritten the used memory location. The weird thing is that it is
> ALWAYS the fourth time running the program. Below is the code
[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2 )
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:
static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));
table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));
sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list[i], phone_from_id (j));
table[i][j] = phone_to_id (triphoneStr, FALSE);
if (table[i][j] >= 0)
triphoneContext ++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[i][j] < 0) {
sprintf (triphoneStr, list->list[i], "SIL");
table[i][j] = phone_to_id (triphoneStr, FALSE);
if (table[i][j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[i][j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list[i]);
p = strchr (stmp, '(');
*p = '\0';
table[i][j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[i][j] = hmm_pid2sid(pho ne_map(table[i][j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table[i])
{
printf("NULL Table call.\n");
return;
}
linkTable = table[i];
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table[i], ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[i][k] != table[i][j]) {
k = k + 1;
table[i][k] = table[i][j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[i][ptab[j]] = k;
}
printf("%x\n", list);
printf("Compres sion Complete %i.\n", k);
table[i][k+1] = -1; /* End of table Marker */
sizeTab[i] = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n" );
}
//printf("\t%6d triphones\n\t%6 d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext , silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory? Could
it be possible that something is not being freed, thus qsort (or my
program) is allocating more and more memory and eventually overwrites
the variable in question? I am a little out of my league when it
comes to debugging problems like these.

I can't understand your program, I doubt many people can. Avoid
things like "int32 ***" if you can (I understand you have inherited
this). Consider rewriting this function.
I can help you with one thing: it is very unlikely to be a bug in
qsort, qsort is used very frequently on every platform. Also it
probably uses stack memory not heap (even if it's not recursive).

There is definitely something very wrong going on:

this line

qsort (ptab, ciCount, sizeof(int32), cmpPT);

sorts the array ptab, which contains all integers from 0 to ciCount.
It's not erm, normal to sort a sequence.

but it sorts it with this:

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

Call me pathetic, but it's a brave man who sorts an array based not on
the information in it, but information somewhere else entirely.

[pete]

William Buch wrote:

pete <pf*****@mindsp ring.com> wrote in message news:<40******* ****@mindspring .com>...

Michel Bardiaux wrote:

William Buch wrote:

> I have a strange problem. The code isn't written by me, but uses the
> qsort function in stdlib. ALWAYS, the fourth time through, the memory
> location of variable list (i.e. mem location = 41813698) becomes 11,
> then the program crashes. It is obviously qsort that may me
> overwritten the used memory location. The weird thing is that it is
> ALWAYS the fourth time running the program. Below is the code
[snip]

Some (if not all) implementations of qsort *assume* the comparison
function is consistent in time, i.e. will always return equivalent
results when confronted with the same pair. A common mistake is to write
a comparison function like (pseudocode!)
http://alpha.searchlimo.com/
if(item1<=item2 )
return -1;
else
return 1;

because comparing (X,Y) and (Y,X) return contradictory values when X
'equals' Y. But since you didn't post your comparison function...

qsort assumes that compar will return 0 for equal.

My apologies for not including the comparison functions. They are as
follows:

static int
cmp (void const *a, void const *b)
{
return (*(int32 const *)a - *(int32 const *)b);
}

int32 *linkTable;

static int
cmpPT (void const *a, void const *b)
{
return (linkTable[*(int32 const *)a] - linkTable[*(int32 const
*)b]);
}

And again here is the snippet:

static void
buildExitTable (list_t *list, int32 ***table_p, int32 ***permuTab_p,
int32 **sizeTab_p)
{
int32 ciCount = phoneCiCount();
int32 i, j, k;
char triphoneStr[128];
int32 silContext = 0;
int32 triphoneContext = 0;
int32 noContext = 0;
int32 entries = 0;
int32 **table;
int32 **permuTab;
int32 *sizeTab;
int32 ptab[128];

*table_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1, sizeof
(int32 *));
table = *table_p;
*permuTab_p = (int32 **) CM_2dcalloc (list->in_use, ciCount+1,
sizeof (int32 *));
permuTab = *permuTab_p;
*sizeTab_p = (int32 *) CM_calloc (list->in_use, sizeof (int32 *));
sizeTab = *sizeTab_p;

//printf("Exit Context table contains\n\t%6d entries\n",
list->in_use);
E_INFO("\t%6d possible cross word triphones.\n", list->in_use *
ciCount);

printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {

for (j = 0; j < ciCount; j++) {
/*
* Look for the triphone
*/
sprintf (triphoneStr, list->list[i], phone_from_id (j));
table[i][j] = phone_to_id (triphoneStr, FALSE);
if (table[i][j] >= 0)
triphoneContext ++;
/*
* If we can't find the desired context use "SIL"
*/
if (table[i][j] < 0) {
sprintf (triphoneStr, list->list[i], "SIL");
table[i][j] = phone_to_id (triphoneStr, FALSE);
if (table[i][j] >= 0)
silContext++;
}
/*
* If we can't find "SIL" use context indepedent
*/
if (table[i][j] < 0) {
char stmp[32];
char *p;
strcpy (stmp, list->list[i]);
p = strchr (stmp, '(');
*p = '\0';
table[i][j] = phone_to_id (stmp, TRUE);
noContext++;
}
table[i][j] = hmm_pid2sid(pho ne_map(table[i][j]));
}
}
//printf("About to compress the table.\n");
/*
* Now compress the table to eliminate duplicate entries.
*/
printf("%x\n", list);
for (i = 0; i < list->in_use; i++) {
/*
* Set up the permutation table
*/
for (k = 0; k < ciCount; k++) {
ptab[k] = k;
}
if(!table[i])
{
printf("NULL Table call.\n");
return;
}
linkTable = table[i];
//printf("%x\n", linkTable);
//printf("%i\n", cmpPT);
//_quicksort (ptab, ciCount, sizeof(int32), cmpPT);
qsort (ptab, ciCount, sizeof(int32), cmpPT);
printf("%x\n", list);
//printf("%i\n", cmp);
qsort (table[i], ciCount, sizeof(int32), cmp);
for (k = 0, j = 0; j < ciCount; j++) {
if (table[i][k] != table[i][j]) {
k = k + 1;
table[i][k] = table[i][j];
}
/*
* Mirror the compression in the permutation table
*/
permuTab[i][ptab[j]] = k;
}
printf("%x\n", list);
printf("Compres sion Complete %i.\n", k);
table[i][k+1] = -1; /* End of table Marker */
sizeTab[i] = k+1;
entries += k+1;
printf("Before Blah\n");
printf("In use %x\n", list);
printf("Blah\n" );
}
//printf("\t%6d triphones\n\t%6 d pseudo diphones\n\t%6d
uniphones\n",
//triphoneContext , silContext, noContext);
E_INFO("\t%6d right context entries\n", entries);
E_INFO("\t%6d ave entries per exit context\n",
((list->in_use == 0) ? 0 : entries/list->in_use));
}

I run this program in a loop, with each iteration after some input.
The first three times the program functions properly. One the fourth
time of initializing the system, when running the qsort program,
everything bombs. My question is how qsort allocates memory?

qsort is not allowed to fail if the arguments to qsort are valid.

--
pete