Data Structures

Linked Lists

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

There are many more functions for operating on linked lists you can read about by exploring the Linked List function reference.

Hash Tables

A hash table is a data structure that associates some data with a unique key. If you know the key, you can get back the data much more quickly than with a linked list, particularly as the number of items stored grows larger. The Max hash table t_hashtab is optimized to work with symbol pointers as keys, but you can use any pointer or number, as long as it is unique.

To create a t_hashtab, you use hashtab_new(). To add items, use hashtab_store(). To find items that have been added, use hashtab_lookup().

By contrast with linked lists and arrays, hash tables do not have a strong sense of ordering. You can iterate through all items using hashtab_funall(), but the exact order is not under your control as items are added and removed. There is also no way to "sort" a hash table.

Example:

The following example creates a hashtab, shows how to add some data (in this case, just a number), look it up, and delete the hashtab.

   t_hashtab *tab = (t_hashtab *)hashtab_new(0);
   long result, value;

   hashtab_store(tab, gensym("a great number"), (t_object *)74);

   result = hashtab_lookup(tab, gensym("a great number"), (t_object **)value);

   if (!result)
      post("found the value and it is %ld",value);
   else
      post("did not find the value");

   hashtab_chuck(tab);

Note that the Max t_dictionary used for managing patcher data is implemented as a t_hashtab.