linklist_sort() help

Jun 23, 2009 at 7:48pm

linklist_sort() help

I am very new to C programming and even newer to the Max SDK.
Could someone explain the linklist_sort() to me?

long myAlphabeticalCmpfn(void *a, void *b)
    {
        t_symbol *s1 = (t_symbol *)a;
        t_symbol *s2 = (t_symbol *)b;

        if(s1->s_name[0] < s2->s_name[0])
            return true;
        else
            return false;
    }

    void mySortMethod(t_myobj *x)
    {
        // the linklist was already created and filled with items previously
        linklist_sort(x->myLinkList, myAlphabeticalCmpfn);
    }

My first problem is that there doesn’t seem to be a function that walks through the linked list. I pass the linked list to the myAlphabeticalCmpfn but there seems to be no equivalent to x->next. So how does it iterate through the whole list?

The myAlphabeticalCmpfn only returns a true or false and doesn’t do any sorting. Where does the sorting take place? What kind of sort is it, swap-sort?

I believe t_symbol is a struct. Is there an equivalent for float (ultimately I want to sort floats).

Sorry if this is all obvious, but I am at a roadblock here. Any input is very much appreciated.

#44518
Jun 24, 2009 at 4:22pm

hello,

here an exemple ; as i learn C/SDK too, don’t trust me too much ! Wink

typedef struct _flop {
	t_object	ob ;
	t_linklist	*f_list ;
	void        *m_out1 ;
	} t_flop ;

void *flop_new (t_symbol *s, long argc, t_atom *argv)
{
      t_flop *x = NULL;
      if (x = (t_flop *)object_alloc(flop_class))
          {
              x->f_list = linklist_new () ;
              linklist_flags (x->f_list, OBJ_FLAG_MEMORY) ;
              x->m_out1 = listout ((t_object *)x) ;
          }
      return (x) ;
}

void flop_free (t_flop *x)
{
     object_free (x->f_list) ;
}	

void flop_float (t_flop *x, double f)
{
      long ac ;
      char alloc ;
      t_atom *ptr = NULL ;
      atom_alloc (&ac, &ptr, &alloc) ;
      if (alloc)
          {
              atom_setfloat (ptr, (float)f) ;
              linklist_append (x->f_list, ptr) ;
          }
}

void flop_bang (t_flop *x)
{
      long i ;
      long size = (short)linklist_getsize (x->f_list) ;
      t_atom *p ;
      t_atom result_list[size] ;
      linklist_sort (x->f_list, (t_cmpfn)howto) ;
      for (i = 0 ; if_list, i) ;
               result_list[i] = *p ;
          }
      outlet_list (x->m_out1, NULL, (short)size, result_list) ;
      linklist_clear (x->f_list) ;
}

long howto (t_atom *ptr1, t_atom *ptr2)
{
      float a, b ;
      a = atom_getfloat (ptr1) ;
      b = atom_getfloat (ptr2) ;
      if (a

Take floats in ; bang sort all and out in a list (complete file ziped).

thanks for guru feedback !

#160088
Jun 24, 2009 at 5:10pm

thanks for the reply.
I will have a look at your code later today and report back. thanks again.

#160089
Jun 24, 2009 at 5:46pm

Just had a quick look (will dig into it more a little later), but just a question regarding t_linklist. In the doc it says:
“This struct is provided for debugging convenience, but should be considered opaque and is subject to change without notice.”
The same goes for t_llelem.
Does this mean that I really should define my own struct?

My struct is going to look something like this:

struct Data{
	int id;
	int depth;
	struct Coord coord1;
	struct Coord coord2;
	float angle;
	float maxDist;
	struct Data *next;
} ;

struct Coord{
	float x_coord;
	float y_coord;
};

And ultimately I would want to try and sort according to coord1.x_coord

#160090
Jun 24, 2009 at 8:03pm
MIB wrote on Wed, 24 June 2009 19:46
In the doc it says:
“This struct is provided for debugging convenience, but should be considered opaque and is subject to change without notice.”
The same goes for t_llelem.
Does this mean that I really should define my own struct?

No, it means you should use t_linklist but you !!MUST!!NOT!! access the struct members directly. Instead use API functions linklist_new() and the other linklist_xxx() functions. linklist_sort() will not work if you use a custom struct. It will probably crash and burn.

#160091
Jun 24, 2009 at 9:28pm

Just a bit more information. There are a number of things you’re confused about

MIB wrote on Tue, 23 June 2009 21:48
My first problem is that there doesn’t seem to be a function that walks through the linked list. I pass the linked list to the myAlphabeticalCmpfn but there seems to be no equivalent to x->next. So how does it iterate through the whole list?

You don’t need to walk the list to sort it, and you don’t “pass the list” to myAlphabetCmpfn().

linklist_sort() sorts the list. It takes two parameters. The first parameter is your linked list. So far so good. But linklist_sort() doesn’t know what your sort criteria are. That’s what the second parameter is for. The 2nd parameter is a pointer to a function that takes two list elements and returns TRUE if the first is “before” the second according to whatever your criteria are. The myAlphabetCmpfn() code is simply an example of one way to do that. It works on the assumption that your list elements are t_symbols and that you want a (very primitive) ASCII sort. You will need to adapt it to your particular circumstances.

Quote:
Where does the sorting take place?

see above.

Quote:
What kind of sort is it, swap-sort?

Probably some version of qsort(), but you don’t really care.

Quote:
I believe t_symbol is a struct.

Don’t guess: look it up.

Quote:
Is there an equivalent for float (ultimately I want to sort floats).

List items are typically Max objects. They are, in any case, pointers. You could possibly typecast your (32-bit) floats to (void*), although that seems like Truly Vile Idea. It would be cleaner to define your own data type, even if it’s only:

struct myType { float myFloat; };

and work with that. That is basically what Béchamel’s code is doing.


Edited to clarify usage of 2nd param to linklist_sort(). Also corrected an annoying typo

#160092
Jun 25, 2009 at 6:12am

hello,

just a question about A_FLOAT and t_atom, i did :

atom_setfloat (ptr, (float)f) ;

is it usefull to cast f (who is double), or not ?

thanks.

EDIT : oops, it seems not.

#160093
Jun 26, 2009 at 10:38am

Take a look at the prototype for atom_setfloat().

No, the typecast isn’t necessary and, in this case, is probably counter-productive.

There was a lot of explicit typecasting in C for the orig. K&R spec, but that’s almost all superfluous since about 1990.

#160094
Jun 26, 2009 at 12:57pm

hello peter,

thanks ; it seems my C learning book is very old ! Smile

#160095

You must be logged in to reply to this topic.