LinuxQuestions.org
Go Job Hunting at the LQ Job Marketplace
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-23-2005, 11:57 AM   #1
Adelsm
LQ Newbie
 
Registered: Sep 2005
Posts: 7

Rep: Reputation: 0
qsort() on linux produce the wrong sort


I am using qsort() to sort an array of structure (not array of pointers), about 145 structures but I it does not sort correctly. This is used in a
C++ code

This code compile and produce the right results in Solaris 2.6 & windows2000 but not in linux redhat 9

here is part of my code:

struct FullTableInfo
{
int a;
char s;
CElement *owner; // owner is a pointer to a class object CElement.
};



main()
{
struct FullTableInfo *FullTable = new struct FullTableInfo[145];

// I fill the array with data and the owner pointer pointing to different
// CElement some of the FullTable[] are pointing to the same CElement

// Sort it....
qsort (FullTable, 145, sizeof(struct FullTableInfo), sortIt);

// the results does not look that it is sorted right?
// if we are sorting owner1, owner2, owner3.....etc
// i get ownere 1 and then owner2 and then back to owner1

any ideas. could it be a bug in qsort() or the g++ compiler i am using??

Thanks

}

static int sortIt (const void *thisone, const void *theotherone)
{
// I am sorting of the address of owner

struct FullTableStruct *theOne = (struct FullTableStruct *)thisone;
struct FullTableStruct *theOther = (struct FullTableStruct *)theotherone;

return (theOne->owner-theOther->owner);
}

Last edited by Adelsm; 09-25-2005 at 06:56 AM.
 
Old 09-24-2005, 12:08 PM   #2
XavierP
Moderator
 
Registered: Nov 2002
Location: Kent, England
Distribution: Lubuntu
Posts: 19,176
Blog Entries: 4

Rep: Reputation: 430Reputation: 430Reputation: 430Reputation: 430Reputation: 430
Moved: This thread is more suitable in Programming and has been moved accordingly to help your thread/question get the exposure it deserves.
 
Old 09-26-2005, 10:03 AM   #3
Adelsm
LQ Newbie
 
Registered: Sep 2005
Posts: 7

Original Poster
Rep: Reputation: 0
I found out if I do the following in my compare routine, the sorting seems to work

cast the address to (int)

return ( (int)theOne->owner - (int)theOther->owner);

Any Comments??

Thanks
 
Old 09-26-2005, 10:34 AM   #4
zeropash
Member
 
Registered: Apr 2003
Location: Bangalore,India
Distribution: FC2, RHES, RH9, FC3, FC1, Slackware 3.0
Posts: 208

Rep: Reputation: 30
when you are doing a
theOne->owner-theOther->owner
you are just subtracting the pointers. are you sure this is what you want to do? do you want to sort the list according the address of the owner or is it according to some content?
 
Old 09-26-2005, 10:44 AM   #5
Adelsm
LQ Newbie
 
Registered: Sep 2005
Posts: 7

Original Poster
Rep: Reputation: 0
Hello zeropash,

Thanks for you reply. I need to sort it by the address of the owner so all the owners
with the same address should be grouped together. Some how when I casted the address
to (int) the sorting works??
 
Old 09-26-2005, 11:57 AM   #6
addy86
Member
 
Registered: Nov 2004
Location: Germany
Distribution: Debian Testing
Posts: 332

Rep: Reputation: 31
Sounds strange. Have you tried looking at the produced assembly code (if you speak i386 )?
 
Old 09-26-2005, 12:54 PM   #7
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 369Reputation: 369Reputation: 369Reputation: 369
This is just a guess, but say the second pointer is larger than the first: 0x12345678 - 0xFF000000

After the operation, the result is supposed to be negative, but what exactly is a negative pointer? There's no such thing as a negative memory address, and I have no clue how the compiler would interpret it. Would it scale the pointer operation? Say sizeof(struct FullTableInfo) equals 16 bytes. Would the subtraction be equivalent to 0x12345678 - ( 0xFF000000 * 16)?

Even though the return result is declared as an int, I doubt the pointer values are altered to ints during the evaluation. What I'm getting at is say you have "float = int * float". The int is promoted to float before the expression is evaluated. Here, you have "int = pointer - pointer". I don't know that the compiler would do any data type conversion until after the subtraction was finished.

Anyway, if you're in the experimentation mood, I would suggest trying this code:
Code:
if( theOne->owner == theOther->owner )
  return 0;
else if( theOne->owner > theOther->owner )
  return 1;
else
  return -1;
In my opinion, it's a little more clear what's going on (though it could be better).
 
Old 09-26-2005, 01:06 PM   #8
Adelsm
LQ Newbie
 
Registered: Sep 2005
Posts: 7

Original Poster
Rep: Reputation: 0
You are right there is no such a thing as negative memory address but just returning
a negative number or positive number will tell qsort() to do the sorting assending or descending
and that's what qsort needs to know. I tried to return 1, -1, 0 but that still gave me the wrong
sorting.
 
Old 09-26-2005, 01:19 PM   #9
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 369Reputation: 369Reputation: 369Reputation: 369
Well, what I'm getting at is this: if there is no data type upgrade when the expression is evaluated, the compiler needs to make a decision on what to do. It has a negative value that it's supposed to interpret as a pointer. It has to interpret it as a pointer before the value can be cast to an int. So what does it do with it? Take the absolute value? "Wrap" the memory space?

The sortIt() function makes the assumption that you can use pointers as ordinary ints. I'm saying that assumption might be incorrect. If pointers behaved the same way as ints (or more appropriately unsigned ints), then why would there be separate data types?
 
Old 09-26-2005, 01:27 PM   #10
Adelsm
LQ Newbie
 
Registered: Sep 2005
Posts: 7

Original Poster
Rep: Reputation: 0
So what do you think I should do? I tried your suggestion by returning 1, -1, 0
and that did not work. Do you think if I cast the pointer to their original data types
that will work ?

return ( (CElement *)theOne - (CElement *)theOther);
 
Old 09-26-2005, 01:57 PM   #11
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 369Reputation: 369Reputation: 369Reputation: 369
All I'm suggesting is to avoid using a pointer in mathematical operations. If you must use them that way, then typecast them, or assign them to temporary variables of the appropriate type:
Code:
static int sortIt (const void *thisone, const void *theotherone)
{
  // I am sorting of the address of owner
  int theOne_owner_address;
  int theOther_owner_address;

  struct FullTableStruct *theOne = (struct FullTableStruct *)thisone;
  struct FullTableStruct *theOther = (struct FullTableStruct *)theotherone;

  theOne_owner_address = (int)theOne->owner;
  theOther_owner_address = (int)theOther->owner;

  return( theOne_owner_address - theOther_owner_address);
}
EDIT: removed bad example... not comparing apples to apples...

Last edited by Dark_Helmet; 09-26-2005 at 01:59 PM.
 
Old 09-27-2005, 01:51 AM   #12
addy86
Member
 
Registered: Nov 2004
Location: Germany
Distribution: Debian Testing
Posts: 332

Rep: Reputation: 31
When you subtract two pointers, it will return the difference divided by the size of the dereferenced pointer. For example:
int a;
int b;
&a - &b
is equivalent to (on a 32-bit machine)
(( int )&a - ( int )&b) / sizeof( int )

You can easily test this with arrays:
int a[10];
int d1 = &a[5] - &a[3];
int d2 = &a[5] - &a[8];
printf("%d, %d\n", d1, d2 );

This will print 2, -3 (regardless whether it is int a[], char a[] or any other type).
 
Old 09-27-2005, 02:12 AM   #13
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 369Reputation: 369Reputation: 369Reputation: 369
That makes sense... It tells how many objects are between the two addresses (assuming a contiguous array). Given that, I can't think of a reason why the sortIt() function failed when using pointer subtraction, but worked as expected when typecasting the pointers to ints.

I'm at a loss...

Last edited by Dark_Helmet; 09-27-2005 at 02:14 AM.
 
Old 09-27-2005, 04:15 AM   #14
addy86
Member
 
Registered: Nov 2004
Location: Germany
Distribution: Debian Testing
Posts: 332

Rep: Reputation: 31
It's really strange. What compiler flags did you use?
 
Old 09-27-2005, 07:15 AM   #15
Adelsm
LQ Newbie
 
Registered: Sep 2005
Posts: 7

Original Poster
Rep: Reputation: 0
I am using g++ compiler with -g for the debug version and -O3 for the optimize version.
Also I am using the -Wno-deprecated

One thing is worth to mention that bsearch() (binary search) did not work for me either
in linux (red hat 9) but again, the same source code did work on Solaris, Windows, HP

As you can see I port the same source code on different platforms.

I started to believe it could be a compiler issue (flags needs to be set) since I don't
think qsort() & bsearch() will fail and they are popular functions.

Note: My code is a C++ code.
 
  


Reply


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
linux clustering - sort of msound Linux - Networking 1 09-23-2005 08:07 AM
In C, using qsort for dynamically allocated array ntmsz Programming 7 08-23-2005 10:33 AM
qsort in C questions trutnev Programming 4 06-10-2005 08:49 AM
Webalizer not producing reports Braytac Linux - Networking 1 04-22-2005 04:04 PM
Audio apps for producing libranikki General 12 02-16-2005 02:13 PM


All times are GMT -5. The time now is 06:19 PM.

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