Summary:ASTERISK-04154: [patch] macros for simple list navigation
Reporter:Luigi Rizzo (rizzo)Labels:
Date Opened:2005-05-13 02:24:07Date Closed:2005-05-14 22:40:51
Versions:Frequency of
Environment:Attachments:( 0) list.patch
Description:(disclaimer on file)
Many times we have simple lists that we navigate keeping one
pointer (scanning for content) or prev-cur pointers (scanning
preparing for an insert or a delete).
The attached patch supplies two macros to navigate the list, and
provides a small example of use - a lot more will come if there is
interest and this patch is committed.
The resulting code is a lot more readable and will make life a lot
easier if/when we should decide to move to alternative data structures
such hash tables to store these info.

Affected files:
       include/asterisk/linkedlist.h (definitions)
       pbx.c           (example of use)
Comments:By: Olle Johansson (oej) 2005-05-13 10:09:41

Please explain what the difference between this concept and ASTOBJ is? Curious.

By: Luigi Rizzo (rizzo) 2005-05-13 12:33:40

Difference #1: my ignorance of the existence of ASTOBJ (also known as
  "Not Invented Here"...).
  To tell the truth i don't believe I am alone in this:

     > grep -l ASTOBJ *c */*c

  I.e. they are basically used only in one file, which is probably
  the reason i and others did not realize of their existence.

Difference #2: the two (2) simple macros I suggest are a lot simpler to learn
  and use (probably a lot less powerful, too) than the thirtynine (39)  
  different macros defined in astobj.h, and fit the only data structure
  (head-lists) that seems to be used in *

My goal was only to provide standard methods for navigating these lists
in their existing form. Surely some of these lists
should be changed to TAILQ or hash tables to improve
efficiency, at which point we could add appropriate methods if needed.
I doubt that at that stage the ugliness of macros will improve
performance significantly. Let's face it, if we want C++ we better use C++
and not reinvent something very complex based on macros.
Unfortunately, the similarly issue exists (different language or libraries) for string manipulation, which * seems to require a lot e.g. in doing signalling.

By: Olle Johansson (oej) 2005-05-13 13:01:50

...so we need kpflemings input on this as well, as he's the architect behind ASTOBJ. It's still being hashed out a bit, so that's why it's not implemented on all possible parts of the code, but it seems to have stabilized over the last weeks.

By: Kevin P. Fleming (kpfleming) 2005-05-14 20:31:33

OK, first off: ASTOBJ is not the cure-all for everything in Asterisk :-) It will not be used in places where reference counts are not required, where entries being moved between containers (or existing in multiple containers) are not required, etc. There will always be a need for simple linked lists.

That said, I don't think these macros belong in linkedlists.h, because they don't operate on the type of lists all the other macros in that file do. In fact, I think a better solution would be to convert the places that you used these new macros to instead _use_ the macros from linkedlists.h for their lists, since we already have traversal macros in place there. We even have "safe traversal", which could be useful in a few of the places that you modified in pbx.c.

By: Kevin P. Fleming (kpfleming) 2005-05-14 22:40:09

I have modified AST_LIST_TRAVERSE_SAFE_BEGIN to add a "prev" pointer, and added AST_LIST_REMOVE_CURRENT which uses it to quickly remove a list entry from a list during traversal. I have also added a AST_LIST_HEAD_STATIC macro for defining single-instance lists. With these changes, the improvements proposed here should be possible using the existing macros, not new ones.

By: Kevin P. Fleming (kpfleming) 2005-05-14 22:40:43

Won't apply this patch as it stands, but you are welcome to improve pbx.c by using the existing macros :-)