Linked List

The Max t_linklist data structure is useful for maintaining ordered lists of items where you want to be able to insert and delete items efficiently. More...

Collaboration diagram for Linked List:

Data Structures
struct	t_llelem
	A linklist element. More...
struct	t_linklist
	The linklist object. More...

Functions
BEGIN_USING_C_LINKAGE t_linklist *	linklist_new (void)
	Create a new linklist object. More...
void	linklist_chuck (t_linklist *x)
	Free a linklist, but don't free the items it contains. More...
t_atom_long	linklist_getsize (t_linklist *x)
	Return the number of items in a linklist object. More...
void *	linklist_getindex (t_linklist *x, long index)
	Return the item stored in a linklist at a specified index. More...
t_atom_long	linklist_objptr2index (t_linklist *x, void *p)
	Return an item's index, given the item itself. More...
t_atom_long	linklist_append (t_linklist *x, void *o)
	Add an item to the end of the list. More...
t_atom_long	linklist_insertindex (t_linklist *x, void *o, long index)
	Insert an item into the list at the specified index. More...
long	linklist_insert_sorted (t_linklist *x, void *o, long cmpfn(void *, void *))
	Insert an item into the list, keeping the list sorted according to a specified comparison function. More...
t_llelem *	linklist_insertafterobjptr (t_linklist *x, void *o, void *objptr)
	Insert an item into the list after another specified item. More...
t_llelem *	linklist_insertbeforeobjptr (t_linklist *x, void *o, void *objptr)
	Insert an item into the list before another specified item. More...
t_llelem *	linklist_moveafterobjptr (t_linklist *x, void *o, void *objptr)
	Move an existing item in the list to a position after another specified item in the list. More...
t_llelem *	linklist_movebeforeobjptr (t_linklist *x, void *o, void *objptr)
	Move an existing item in the list to a position before another specified item in the list. More...
t_atom_long	linklist_deleteindex (t_linklist *x, long index)
	Remove the item from the list at the specified index and free it. More...
long	linklist_chuckindex (t_linklist *x, long index)
	Remove the item from the list at the specified index. More...
long	linklist_chuckobject (t_linklist *x, void *o)
	Remove the specified item from the list. More...
long	linklist_deleteobject (t_linklist *x, void *o)
	Delete the specified item from the list. More...
void	linklist_clear (t_linklist *x)
	Remove and free all items in the list. More...
t_atom_long	linklist_makearray (t_linklist *x, void **a, long max)
	Retrieve linklist items as an array of pointers. More...
void	linklist_reverse (t_linklist *x)
	Reverse the order of items in the linked-list. More...
void	linklist_rotate (t_linklist *x, long i)
	Rotate items in the linked list in circular fashion. More...
void	linklist_shuffle (t_linklist *x)
	Randomize the order of items in the linked-list. More...
void	linklist_swap (t_linklist *x, long a, long b)
	Swap the position of two items in the linked-list, specified by index. More...
t_atom_long	linklist_findfirst (t_linklist *x, void **o, long cmpfn(void *, void *), void *cmpdata)
	Search the linked list for the first item meeting defined criteria. More...
void	linklist_findall (t_linklist *x, t_linklist **out, long cmpfn(void *, void *), void *cmpdata)
	Search the linked list for all items meeting defined criteria. More...
void	linklist_methodall (t_linklist *x, t_symbol *s,...)
	Call the named message on every object in the linklist. More...
void *	linklist_methodindex (t_linklist *x, t_atom_long i, t_symbol *s,...)
	Call the named message on an object specified by index. More...
void	linklist_sort (t_linklist *x, long cmpfn(void *, void *))
	Sort the linked list. More...
void	linklist_funall (t_linklist *x, method fun, void *arg)
	Call the specified function for every item in the linklist. More...
t_atom_long	linklist_funall_break (t_linklist *x, method fun, void *arg)
	Call the specified function for every item in the linklist. More...
void *	linklist_funindex (t_linklist *x, long i, method fun, void *arg)
	Call the specified function for an item specified by index. More...
void *	linklist_substitute (t_linklist *x, void *p, void *newp)
	Given an item in the list, replace it with a different value. More...
void *	linklist_next (t_linklist *x, void *p, void **next)
	Given an item in the list, find the next item. More...
void *	linklist_prev (t_linklist *x, void *p, void **prev)
	Given an item in the list, find the previous item. More...
void *	linklist_last (t_linklist *x, void **item)
	Return the last item (the tail) in the linked-list. More...
void	linklist_readonly (t_linklist *x, long readonly)
	Set the linklist's readonly bit. More...
void	linklist_flags (t_linklist *x, long flags)
	Set the linklist's datastore flags. More...
t_atom_long	linklist_getflags (t_linklist *x)
	Get the linklist's datastore flags. More...
long	linklist_match (void *a, void *b)
	A linklist comparison method that determines if two item pointers are equal. More...

Detailed Description

The Max t_linklist data structure is useful for maintaining ordered lists of items where you want to be able to insert and delete items efficiently.

Random access of individual items, however, gets appreciably slower as the list grows in size. The t_linklist is thread-safe by default, but thread safety can be turned off for performance benefits in single-threaded applications. However, ensure that your use of the linked list is truly single-threaded (based on an understanding of Max's Threading model) before turning off the thread safety features.

By default, the t_linklist holds pointers to Max objects. However, you can treat what the linklist holds as data rather than objects to be freed by using the linklist_flags() function.

Here is a simple example of the use of t_linklist. The code below stores five symbols, sorts them, searches for a specific item, deletes an item, prints all items, and then frees the entire structure. Since symbols in Max are never freed, linklist_flags() is used to specify that data, rather than object pointers, are being stored.

void mylistfun()
{
    t_linklist *list;

    list = (t_linklist *)linklist_new();
    linklist_flags(list, OBJ_FLAG_DATA);

    // add some data
    linklist_append(list, gensym("one"));
    linklist_append(list, gensym("two"));
    linklist_append(list, gensym("three"));
    linklist_append(list, gensym("four"));
    linklist_append(list, gensym("five"));

    // sort
    linklist_sort(list, (t_cmpfn)mysortfun);

    // search
    index = linklist_findfirst(list, &found, mysearchfun, gensym("four"));  // find the "four" symbol
    if (index != -1)    // found
        linklist_chuckindex(list, index);

    // iterate
    linklist_funall(list, myprintfun, NULL);

    // delete
    linklist_chuck(list);
}

The sorting function compares two items in the list and returns non-zero if the first one should go before the second one.

long mysortfun(void *a, void *b)
{
    t_symbol *sa = (t_symbol *)a;
    t_symbol *sb = (t_symbol *)b;

    return strcmp(sa->s_name, sb->s_name) > 0;
}

The search function is passed the final argument to linklist_findfirst() and, in this case, just returns the symbol that matches, which is just testing for pointer equivalence since all Max symbols are unique. You could do more sophisticated searching if you store more complex data in a linklist.

long mysearchfun(t_symbol *elem, t_symbol *match)
{
    return elem == match;
}

The iteration function takes some action on all items in the list. The third argument to linklist_funall() is passed as the second argument to your iteration function. In this example, we don't do anything with it.

void myprintfun(t_symbol *item, void *dummy)
{
    post("%s",item->s_name);
}

See also

http://en.wikipedia.org/wiki/Linked_list

Function Documentation

t_atom_long linklist_append	(	t_linklist *	x,
		void *	o
	)

Add an item to the end of the list.

Parameters

x	The linklist instance.
o	The item pointer to append to the linked-list.

Returns

The updated size of the linklist after appending the new item, or -1 if the append failed.

Referenced by jit_linklist_append().

void linklist_chuck

(

t_linklist *

x

)

Free a linklist, but don't free the items it contains.

The linklist can contain a variety of different types of data. By default, the linklist assumes that all items are max objects with a valid t_object header.

You can alter the linklist's notion of what it contains by using the linklist_flags() method.

When you free the linklist by calling object_free() it then tries to free all of the items it contains. If the linklist is storing a custom type of data, or should otherwise not free the data it contains, then call linklist_chuck() to free the object instead of object_free().

Parameters

x	The linklist object to be freed.

See also

object_free

Referenced by jit_linklist_chuck(), and jit_linklist_findcount().

long linklist_chuckindex	(	t_linklist *	x,
		long	index
	)

Remove the item from the list at the specified index.

You are responsible for freeing any memory associated with the item that is removed from the linklist.

Parameters

x	The linklist instance.
index	The index of the item to remove.

Returns

Returns MAX_ERR_NONE on successful removal, otherwise returns MAX_ERR_GENERIC

See also

linklist_deleteindex

linklist_chuckobject

Referenced by jit_linklist_chuckindex().

long linklist_chuckobject	(	t_linklist *	x,
		void *	o
	)

Remove the specified item from the list.

You are responsible for freeing any memory associated with the item that is removed from the linklist.

Parameters

x	The linklist instance.
o	The pointer to the item to remove.

See also

linklist_deleteindex

linklist_chuckindex

linklist_deleteobject

void linklist_clear

(

t_linklist *

x

)

Remove and free all items in the list.

Freeing items in the list is subject to the same rules as linklist_deleteindex(). You can alter the linklist's notion of what it contains, and thus how items are freed, by using the linklist_flags() method.

Parameters

x	The linklist instance.

Referenced by jit_linklist_clear(), and jit_linklist_free().

t_atom_long linklist_deleteindex	(	t_linklist *	x,
		long	index
	)

Remove the item from the list at the specified index and free it.

The linklist can contain a variety of different types of data. By default, the linklist assumes that all items are max objects with a valid t_object header. Thus by default, it frees items by calling object_free() on them.

You can alter the linklist's notion of what it contains by using the linklist_flags() method.

If you wish to remove an item from the linklist and free it yourself, then you should use linklist_chuckptr().

Parameters

x	The linklist instance.
index	The index of the item to delete.

Returns

Returns the index number of the item delted, or -1 if the operation failed.

See also

linklist_chuckindex

linklist_chuckobject

Referenced by jit_linklist_deleteindex().

long linklist_deleteobject	(	t_linklist *	x,
		void *	o
	)

Delete the specified item from the list.

The object is removed from the list and deleted. The deletion is done with respect to any flags passed to linklist_flags.

Parameters

x	The linklist instance.
o	The pointer to the item to delete.

See also

linklist_deleteindex

linklist_chuckindex

linklist_chuckobject

void linklist_findall	(	t_linklist *	x,
		t_linklist **	out,
		long	cmpfnvoid *, void *,
		void *	cmpdata
	)

Search the linked list for all items meeting defined criteria.

The items in the list are traversed, calling a specified comparison function on each, and returning the matches in another linklist.

Parameters

x	The linklist instance.
out	The address to a t_linklist pointer. You should initialize the pointer to NULL before calling linklist_findall(). A new linklist will be created internally by linklist_findall() and returned here.
cmpfn	The function used to determine a match in the list.
cmpdata	An argument to be passed to the t_cmpfn. This will be passed as the second of the two args to the t_cmpfn. The first arg will be the linklist item at each iteration in the list.

Remarks

The following example assumes you have a linklist called myLinkList, and t_cmpfn called myCmpFunction, and some sort of data to match in someCriteria.

t_linklist *results = NULL;

linklist_findall(myLinkList, &results, myCmpFunction, (void *)someCriteria);
// do something here with the 'results' linklist
// then free the results linklist
linklist_chuck(results);

See also

linklist_match

t_cmpfn

linklist_findfirst

Referenced by jit_linklist_findall(), and jit_linklist_findcount().

t_atom_long linklist_findfirst	(	t_linklist *	x,
		void **	o,
		long	cmpfnvoid *, void *,
		void *	cmpdata
	)

Search the linked list for the first item meeting defined criteria.

The items in the list are traversed, calling a specified comparison function on each until the comparison function returns true.

Parameters

x	The linklist instance.
o	The address to pointer that will be set with the matching item.
cmpfn	The function used to determine a match in the list.
cmpdata	An argument to be passed to the t_cmpfn. This will be passed as the second of the two args to the t_cmpfn. The first arg will be the linklist item at each iteration in the list.

Returns

The index of the matching item, or -1 if no match is found.

Remarks

The following shows how to manually do what linklist_chuckobject() does.

void *obj;
long index;

index = linklist_findfirst(x, &obj, #linklist_match, o);
if(index != -1)
   linklist_chuckindex(x, index);

See also

linklist_match

t_cmpfn

linklist_findall

Referenced by jit_linklist_findfirst().

void linklist_flags	(	t_linklist *	x,
		long	flags
	)

Set the linklist's datastore flags.

The available flags are enumerated in e_max_datastore_flags. These flags control the behavior of the linklist, particularly when removing items from the list using functions such as linklist_clear(), linklist_deleteindex(), or when freeing the linklist itself.

Parameters

x	The linklist instance.
flags	A valid value from the e_max_datastore_flags. The default is OBJ_FLAG_OBJ.

void linklist_funall	(	t_linklist *	x,
		method	fun,
		void *	arg
	)

Call the specified function for every item in the linklist.

Parameters

x	The linklist instance.
fun	The function to call, specified as function pointer cast to a Max method.
arg	An argument that you would like to pass to the function being called.

Remarks

The linklist_funall() method will call your function for every item in the list. It will pass both a pointer to the item in the list, and any argument that you provide. The following example shows a function that could be called by linklist_funall().

void myFun(t_object *myObj, void *myArg)
{
   // do something with myObj and myArg here
   // myObj is the item in the linklist
}

t_atom_long linklist_funall_break	(	t_linklist *	x,
		method	fun,
		void *	arg
	)

Call the specified function for every item in the linklist.

The iteration through the list will halt if the function returns a non-zero value.

Parameters

x	The linklist instance.
fun	The function to call, specified as function pointer cast to a Max method.
arg	An argument that you would like to pass to the function being called.

Remarks

The linklist_funall() method will call your function for every item in the list. It will pass both a pointer to the item in the list, and any argument that you provide. The following example shows a function that could be called by linklist_funall().

long myFun(t_symbol *myListItemSymbol, void *myArg)
{
   // this function is called by a linklist that contains symbols for its items
   if(myListItemSymbol == gensym("")){
       error("empty symbol -- aborting linklist traversal")
       return 1;           
   }
   else{
       // do something with the symbol
       return 0;
   }
}

void* linklist_funindex	(	t_linklist *	x,
		long	i,
		method	fun,
		void *	arg
	)

Call the specified function for an item specified by index.

Parameters

x	The linklist instance.
i	The index of the item to which to send the message.
fun	The function to call, specified as function pointer cast to a Max method.
arg	An argument that you would like to pass to the function being called.

Remarks

The linklist_funindex() method will call your function for an item in the list. It will pass both a pointer to the item in the list, and any argument that you provide. The following example shows a function that could be called by linklist_funindex().

void myFun(t_object *myObj, void *myArg)
{
   // do something with myObj and myArg here
   // myObj is the item in the linklist
}

t_atom_long linklist_getflags

(

t_linklist *

x

)

Get the linklist's datastore flags.

Parameters

x	The linklist instance.

Returns

The current state of the linklist flags as enumerated in e_max_datastore_flags.

void* linklist_getindex	(	t_linklist *	x,
		long	index
	)

Return the item stored in a linklist at a specified index.

Parameters

x	The linklist instance.
index	The index in the linklist to fetch. Indices are zero-based.

Returns

The item from the linklist stored at index. If there is no item at the index, NULL is returned

Referenced by jit_linklist_getindex().

t_atom_long linklist_getsize

(

t_linklist *

x

)

Return the number of items in a linklist object.

Parameters

x	The linklist instance.

Returns

The number of items in the linklist object.

Referenced by jit_linklist_findcount(), and jit_linklist_getsize().

long linklist_insert_sorted	(	t_linklist *	x,
		void *	o,
		long	cmpfnvoid *, void *
	)

Insert an item into the list, keeping the list sorted according to a specified comparison function.

Parameters

x	The linklist instance.
o	The item pointer to insert.
cmpfn	A comparison function by which the list should be sorted.

Returns

The index of the new item in the linklist, or -1 if the insert failed.

t_llelem* linklist_insertafterobjptr	(	t_linklist *	x,
		void *	o,
		void *	objptr
	)

Insert an item into the list after another specified item.

Parameters

x	The linklist instance.
o	The item pointer to insert.
objptr	The item pointer after which to insert in the list.

Returns

An opaque linklist element.

t_llelem* linklist_insertbeforeobjptr	(	t_linklist *	x,
		void *	o,
		void *	objptr
	)

Insert an item into the list before another specified item.

Parameters

x	The linklist instance.
o	The item pointer to insert.
objptr	The item pointer before which to insert in the list.

Returns

An opaque linklist element.

t_atom_long linklist_insertindex	(	t_linklist *	x,
		void *	o,
		long	index
	)

Insert an item into the list at the specified index.

Parameters

x	The linklist instance.
o	The item pointer to insert.
index	The index at which to insert. Index 0 is the head of the list.

Returns

The index of the item in the linklist, or -1 if the insert failed.

Referenced by jit_linklist_insertindex().

void* linklist_last	(	t_linklist *	x,
		void **	item
	)

Return the last item (the tail) in the linked-list.

Parameters

x	The linklist instance.
item	The address of pointer in which to store the last item in the linked-list.

Returns

always returns NULL

t_atom_long linklist_makearray	(	t_linklist *	x,
		void **	a,
		long	max
	)

Retrieve linklist items as an array of pointers.

Parameters

x	The linklist instance.
a	The address of the first pointer in the array to fill.
max	The number of pointers in the array.

Returns

The number of items from the list actually returned in the array.

Referenced by jit_linklist_makearray().

long linklist_match	(	void *	a,
		void *	b
	)

A linklist comparison method that determines if two item pointers are equal.

Parameters

a	The first item to compare.
b	The second item to compare.

Returns

Returns 1 if the items are equal, otherwise 0.

See also

t_cmpfn

void linklist_methodall	(	t_linklist *	x,
		t_symbol *	s,
			...
	)

Call the named message on every object in the linklist.

The linklist_methodall() function requires that all items in the linklist are object instances with a valid t_object header.

Parameters

x	The linklist instance.
s	The name of the message to send to the objects.
...	Any arguments to be sent with the message.

Remarks

Internally, this function uses object_method(), meaning that no errors will be posted if the message name does not exist for the object. It also means that messages sent methods with A_GIMME definitions will need to be given a symbol argument prior to the argc and argv array information.

Referenced by jit_linklist_methodall().

void* linklist_methodindex	(	t_linklist *	x,
		t_atom_long	i,
		t_symbol *	s,
			...
	)

Call the named message on an object specified by index.

The item must be an object instance with a valid t_object header.

Parameters

x	The linklist instance.
i	The index of the item to which to send the message.
s	The name of the message to send to the objects.
...	Any arguments to be sent with the message.

Remarks

Internally, this function uses object_method(), meaning that no errors will be posted if the message name does not exist for the object. It also means that messages sent methods with A_GIMME definitions will need to be given a symbol argument prior to the argc and argv array information.

Referenced by jit_linklist_methodindex().

t_llelem* linklist_moveafterobjptr	(	t_linklist *	x,
		void *	o,
		void *	objptr
	)

Move an existing item in the list to a position after another specified item in the list.

Parameters

x	The linklist instance.
o	The item pointer to insert.
objptr	The item pointer after which to move o in the list.

Returns

An opaque linklist element.

t_llelem* linklist_movebeforeobjptr	(	t_linklist *	x,
		void *	o,
		void *	objptr
	)

Move an existing item in the list to a position before another specified item in the list.

Parameters

x	The linklist instance.
o	The item pointer to insert.
objptr	The item pointer before which to move o in the list.

Returns

An opaque linklist element.

BEGIN_USING_C_LINKAGE t_linklist* linklist_new

(

void

)

Create a new linklist object.

You can free the linklist by calling object_free() on the linklist's pointer, or by using linklist_chuck().

Returns

Pointer to the new linklist object.

See also

object_free()

linklist_chuck()

Referenced by jit_linklist_new().

void* linklist_next	(	t_linklist *	x,
		void *	p,
		void **	next
	)

Given an item in the list, find the next item.

This provides an means for walking the list.

Parameters

x	The linklist instance.
p	An item in the list.
next	The address of a pointer to set with the next item in the list.

t_atom_long linklist_objptr2index	(	t_linklist *	x,
		void *	p
	)

Return an item's index, given the item itself.

Parameters

x	The linklist instance.
p	The item pointer to search for in the linklist.

Returns

The index of the item given in the linklist. If the item is not in the linklist MAX_ERR_GENERIC is returned.

Referenced by jit_linklist_objptr2index().

void* linklist_prev	(	t_linklist *	x,
		void *	p,
		void **	prev
	)

Given an item in the list, find the previous item.

This provides an means for walking the list.

Parameters

x	The linklist instance.
p	An item in the list.
prev	The address of a pointer to set with the previous item in the list.

void linklist_readonly	(	t_linklist *	x,
		long	readonly
	)

Set the linklist's readonly bit.

By default the readonly bit is 0, indicating that it is threadsafe for both reading and writing. Setting the readonly bit to 1 will disable the linklist's theadsafety mechanism, increasing performance but at the expense of threadsafe operation. Unless you can guarantee the threading context for a linklist's use, you should leave this set to 0.

Parameters

x	The linklist instance.
readonly	A 1 or 0 for setting the readonly bit.

void linklist_reverse

(

t_linklist *

x

)

Reverse the order of items in the linked-list.

Parameters

x	The linklist instance.

Referenced by jit_linklist_reverse().

void linklist_rotate	(	t_linklist *	x,
		long	i
	)

Rotate items in the linked list in circular fashion.

Parameters

x	The linklist instance.
i	The number of positions in the list to shift items.

Referenced by jit_linklist_rotate().

void linklist_shuffle

(

t_linklist *

x

)

Randomize the order of items in the linked-list.

Parameters

x	The linklist instance.

Referenced by jit_linklist_shuffle().

void linklist_sort	(	t_linklist *	x,
		long	cmpfnvoid *, void *
	)

Sort the linked list.

The items in the list are ordered using a t_cmpfn function that is passed in as an argument.

Parameters

x	The linklist instance.
cmpfn	The function used to sort the list.

Remarks

The following is example is a real-world example of sorting a linklist of symbols alphabetically by first letter only. First the cmpfn is defined, then it is used in a different function by linklist_sort().

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);
}

Referenced by jit_linklist_sort().

void* linklist_substitute	(	t_linklist *	x,
		void *	p,
		void *	newp
	)

Given an item in the list, replace it with a different value.

Parameters

x	The linklist instance.
p	An item in the list.
newp	The new value.

Returns

Always returns NULL.

void linklist_swap	(	t_linklist *	x,
		long	a,
		long	b
	)

Swap the position of two items in the linked-list, specified by index.

Parameters

x	The linklist instance.
a	The index of the first item to swap.
b	The index of the second item to swap.

Referenced by jit_linklist_swap().