Microsoft KB Archive/123496

BUG: qsort() Sorts Huge String Arrays > 64K Incorrectly

Q123496

The information in this article applies to:

The C Run-Time (CRT), included with:
- Microsoft Visual C++, versions 1.5, 1.51

SYMPTOMS

Using the C Run-time function qsort() to sort a two-dimensional character array that is greater than 64K in size may generate incorrect results such as missing the first element in the result, or causing the computer to hang (stop responding). This happens if a two-dimensional character array is used in the huge memory model or if a huge pointer is used in the other memory models.

RESOLUTION

To correct the problem, use one of these workarounds:

Instead of using a two-dimensional character array, use an array of structure that contains a field of a character array. See the example below in the Sample Code section of this article.
If the string information is of a numerical type, you might try sorting the numbers as numbers. Then store them as strings if necessary.

STATUS

Microsoft has confirmed this to be a bug in the Microsoft products listed at the beginning of this article. We are researching this problem and will post new information here in the Microsoft Knowledge Base as it becomes available.

MORE INFORMATION

The sample code below reproduces the problem. To work around the problem, compile the code WITHOUT switch /D"_PROBLEM".

Sample Code

/* Compile options needed: /AH /D"COLUMN=36" /D"_PROBLEM"
*/ 
/* -- test.c -- */ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <search.h>
#define ROW ( (0xffff/COLUMN) + 1 )    /* ( 65535/COLUMN ) + 1 */ 
#ifdef _PROBLEM
char TestString[ROW][COLUMN];
#else
struct Test { char string[COLUMN]; } TestString[ROW];
#endif
int cmp( const void *c1, const void *c2 );
                                 /* User defined sort function */ 
void main()
{
   int i;
   for ( i=0; i<ROW; i++ )
   {
#ifdef _PROBLEM
     sprintf( TestString[i], "%6d\n", rand() );
#else
     sprintf( TestString[i].string, "%6d\n", rand() );
#endif
   }
#ifdef _PROBLEM
   qsort( (void*)TestString, (size_t)ROW, (size_t)COLUMN, cmp );
#else
   qsort( (void*)TestString, (size_t)ROW, sizeof(struct Test), cmp );
#endif
   for ( i=0; i<ROW; i++ )
   {
#ifdef _PROBLEM
     if ( TestString[i][0] == '\0' )
        printf("TestString[%d] is empty.\n", i );
     else
        printf("TestString[%d] = %s", i, TestString[i] );
#else
     if ( TestString[i].string[0] == '\0' )
        printf("TestString[%d] is empty.\n", i );
     else
        printf("TestString[%d] = %s", i, TestString[i].string );
#endif
   }
}
int cmp( const void *c1, const void *c2 )
{
#ifdef _PROBLEM
   return strcmp( c1, c2 );
#else
   return strcmp( ((struct Test*)c1)->string,
                  ((struct Test*)c2)->string
                );
#endif
}

Additional query words: 1.50 1.51 buglist1.50 buglist1.51

Keywords : kb16bitonly
Issue type :
Technology : kbVCsearch kbAudDeveloper kbCRT