0

I have this comparator function for my qsort in C, but I seem to be getting a segmentation fault no matter what I try...

int textCompare ( const void * a, const void * b ){
    const char **x =(const char**)a;
    const char **y =(const char**)b;
    return strcmp(*x, *y);
}

Here is my qsort call: where message** mList = malloc(INITIAL_CAPACITY * sizeof(message)); and count is an integer keeping track of the last element. message is just a typedef struct that contains an int and a pointer to a char. I'm 67% sure that I am calling qsort correctly, can anyone point me in the right direction?

qsort (*mList, count, sizeof(message), textCompare);

[EDIT] The reason I declare message*** instead of message* is because I'm trying to initialize an "array" of pointers to structures; unless I'm going about this the wrong way?

Improve this question
2
  • Since messages are not self-evidently pointers to char pointers, perhaps the trouble is that your comparator should be comparing message structures instead of pointers to character strings. Also, your memory allocation either has one too many stars on the LHS or the wrong size on the RHS. Or, perhaps, mList is a parameter to your function, but then the allocation line is misleading; you'd be doing *mList = malloc(INITIAL_CAPACITY * sizeof(message));. Commented Mar 8, 2011 at 5:56
  • The reason I declare message*** instead of message* is because I'm trying to initialize an "array" of pointers to structures; unless I'm going about this the wrong way? Commented Mar 8, 2011 at 6:33

3 Answers 3

Reset to default
6

If you do actually want to sort an array of pointers to message structs, then you would need to use this

message **mlist = (message **)malloc(INITIAL_CAPACITY * sizeof(message *));

Then you have to allocate memory for each message being pointed to by the pointers in the array.

for(int i=0; i<INITIAL_CAPACITY; i++) {
  mlist[i] = (message *)malloc(sizeof(message));
  /*  initialize the members here  */
  mlist[i]->int = get_int();
  mlist[i]->char = get_char();  
  count++
  if(count >= NUM_TO_FILL_RIGHT_NOW)
   break;   
}

now you can sort the array of pointers instead of the structures themselves.

int textCompare( const void *a, const void *b ) {
  message *m1 = *(message **)a;
  message *m2 = *(message **)b;
  return strcmp(m1->char, m2->char);
}

Now call qsort on the array of pointers

qsort( mlist, count, sizeof(message *), textCompare );

with this method, the pointers are in contiguous memory(theoretically), but the structures themselves are malloced individually as needed. Also, sorting pointers is usually faster than sorting structures because of the size of the object being copied. Pointers are 8 bytes on a 64 bit machine, and 4 bytes on a 32 bit machine, and your structure may actually be smaller than that, but a typical structure will be larger than a pointer.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

I'm not sure if you call to malloc() is allocating the right type of memory for what you're wanting to work with. You are declaring an array of pointers that are then in-turn pointing to some (possible) array of pointers, but it seems as though you are reserving memory for the actual size of the structures themselves, i.e., you are reserving memory for an array of messages, not an array of pointers to messages. For instance, if you dereference mlist, what is that resulting pointer pointing to? Is it suppose to be pointing to an individual message structure, or an array of message structures (i.e. you have some two-dimensional array of message structures where mlist[0] to mlist[n] each represent a pointer pointing to an array of messages on the heap that are some arbitrary length in size)? If it's not suppose to be pointing to anything, but rather should be an actual message structure, then your call should look more like:

message* mlist = malloc(INITIAL_CAPACITY * sizeof(message));

rather than mlist being of type message**.

Hope this helps.

Improve this answer

Comments

1

@Jason and @Tim both gave correct answers. Here is a correct, working program that demonstrates their answers. 

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

typedef struct message {
  int i;
  char *p;
} message;

int textCompare(const void *a, const void *b) {
  const message *ma = a;
  const message *mb = b;
  return strcmp(ma->p, mb->p);
}

int main()
{
  int i;
  message* mList = malloc(10 * sizeof(message));
  mList[0].i = 0; mList[0].p = "zero";
  mList[1].i = 1; mList[1].p = "one";
  mList[2].i = 2; mList[2].p = "two";

  qsort(mList, 3, sizeof(message), textCompare);

  for(i = 0; i < 3; i++) {
    printf("%d %s\n", mList[i].i, mList[i].p);
  }
  return 0;
}

Note the pattern of the malloc call. To allocate an array of type T:

T* var = malloc(array_size * sizeof(T));

See how there is only one * in the declaration, and the sizeof() operator takes one less star than that. Some people prefer this form: 

T* var = malloc(array_size * sizeof *var);

That way you only have to specify the type once. This is particularly useful for complicated types.

Also, note that there is no cast on the result of malloc.

Also, notice how the type of the first arg to qsort() matches the type of the converted parameters in the compare function. In this specific case, they are each message*.

You might find this qsort invocation easier to understand and maintain:

qsort(mList, 3, sizeof(*mList), textCompare);
Improve this answer

1 Comment

OP wanted to sort an array of pointers, not an array of structures. See accepted answer for correct response.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.