[asterisk-dev] [Code Review]: RFC for proposed astobj2 API container enhancements

[Mark Michelson]

> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 938-946
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line938>
> >
> >     How do you plan to detect a duplicate object?
> 
> rmudgett wrote:
>     Duplicate objects are easily detectable in sorted containers.  Unsorted containers must be searched.  I will note that the duplicate option is only applicable to sorted containers.

To clarify my question more, how do you differentiate between duplicate objects and objects with duplicate keys?

I suppose that my definition of what a duplicate key is may be different from yours. For instance, if you have an object type foo, and it has a field bar within it like:

struct foo {
    char *bar;
};

Then it is reasonable to assume that we might compare foos by using the comparison function:

int cmp_foo(void *obj, void *arg, int flags)
{
    struct foo *foo1 = obj;
    struct foo *foo2 = arg;
    return !strcmp(foo1->bar, foo2->bar) ? CMP_MATCH : 0;
}

Similarly, we may choose to hash foos using the hash function

int hash_foo(const void *obj, int flags)
{
    struct foo *foo = obj;
    return ast_str_hash(foo->bar);
}

Now, how do we determine if two foos are duplicates? Is it because cmp_foo() returns CMP_MATCH? Doesn't that just mean the objects have duplicate keys? Or would two foos be considered to have duplicate keys if hash_foo() returns the same value for two foos? If the latter, then what does it mean for an object to have duplicate keys if it is not in a hash container?


> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, line 1064
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line1064>
> >
> >     A couple of things:
> >     
> >     1) Does providing a sort_fn imply that the container is sorted? In other words, will every object linked into the container undergo sorting so that it is inserted in the proper spot? Based on the fact there appears to be no ao2_sort() function or anything similar, I'm assuming so. Would there be value to providing a sort_fn but not having the container be automatically sorted? I'm thinking of a case where the order of elements in a container typically does not matter but for the output of a CLI or AMI command, we want to list objects in a particular order.
> >     
> >     2) What does it mean to sort a hash table? Does the sort_fn only apply to items with duplicate keys (i.e. in the same bucket)? The phrase "buckets not sorted" is ambiguous in your parenthetical note.
> 
> rmudgett wrote:
>     The presence of the sort_fn implies that the container is sorted in some manner.  For hash containers this means that the hash buckets are sorted.  Traversing over a hash container still does not give a sorted output of all contents in the container.  Hashing works against sorting.
>     
>     Your normal use case of a container as unsorted but the CLI or AMI output being sorted is the reason for the ao2_container_dup() function.  You duplicate a hash container into a sorted container.  Problems will arise if the contained objects change their search key values when in more than one container.
>     
>     A "sorted" hash container is only useful if you want to use the duplicate object handling options.  However, the degenerate hash container (only one bucket) is a list which has more uses for the sorted property.
>     
>     The same could be said for traversal order over a hash container.  The degenerate hash container has more use for traversal order since it is a list.
>     
>     How is "NULL if buckets not sorted" ambiguous in that context?  I changed the wording to "NULL to not sort the buckets".

The ambiguity of "buckets not sorted" is that I don't know if you mean that the contents within a single bucket is not sorted or if the buckets themselves (somehow) are not sorted. You've answered this with your clarifying comments here indicating that you mean the contents of the individual buckets.


> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 1596-1600
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line1596>
> >
> >     In a hash table, does this mean that the items within a bucket are traversed in descending order AND that the buckets themselves are traversed in descending order?
> >     
> >     Also, again, the word is "descending".
> >     
> >     As a final note, you provide preorder and postorder traversal options for ao2_callback(). Shouldn't the same options be available for iterators?
> 
> rmudgett wrote:
>     Yes the traversal order is as you stated: descending buckets and descending items within the bucket.  It doesn't make much difference for a hash container unless it is a degenerate hash container (i.e. a list).
>     
>     The pre-order and post-order traversal options do not make sense for iterators since those orders require the container structure to remain the same over the traversal.  Iterators just about guarantee that is not going to happen because the container is allowed to change during the traversal.

Okay, I would add some sort of comment here indicating why the pre-order and post-order traversals are not present then. That way it's more clear that their omission was intentional and not an oversight.


> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 893-896
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line893>
> >
> >     What effect would these flags have on a non-tree? No effect? Emit a warning under dev-mode? Assert under dev-mode?
> >     
> >     Defining OBJ_ORDER_POST as you have here is dangerous since if it is set then OBJ_ORDER_DESCENDING and OBJ_ORDER_PRE also evaluate true. You can code around this, but it's too risky for my tastes. You're basically mandating that
> >     1) All OBJ_ORDER flags have to be evaluated to know for sure which order is being requested.
> >     2) OBJ_ORDER flags have to be evaluated in a specific order to know for sure which order is being requested.
> >     
> >     Just use separate bits for each flag.
> 
> rmudgett wrote:
>     You seem to be assuming the OBJ_ORDER_xxx values are stand alone flags.  The OBJ_ORDER_xxx is an enumeration field so only one value is allowed.  Breaking the search orders into stand alone flags is rather silly since many of those resulting combinations would be invalid.  The default field value is ascending so if it is not explicitly stated, the traversal order is ascending.
>     
>     I moved the enumeration mask define to the beginning of the order enumeration defines.
>     
>     I added notes to the PRE and POST ordering to indicate what non-tree containers would do.

Okay, I get it now. I had been thinking of using purely bitwise logic to to determine if a flag had been set. You're thinking more along the lines of doing something like:

if ((flags & OBJ_ORDER_MASK) == OBJ_ORDER_POST) {
    /* Do stuff */
}

This also suddenly makes the 0-value flag make sense because

if ((flags & OBJ_ORDER_MASK) == OBJ_ORDER_ASCENDING) {
}

can actually evaluate true now. Cool cool. I take back this and any other similar comments I've made on flags such as these.


- Mark


-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviewboard.asterisk.org/r/1835/#review5906
-----------------------------------------------------------


On March 28, 2012, 10:51 a.m., rmudgett wrote:
> 
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviewboard.asterisk.org/r/1835/
> -----------------------------------------------------------
> 
> (Updated March 28, 2012, 10:51 a.m.)
> 
> 
> Review request for Asterisk Developers, Mark Michelson and Matt Jordan.
> 
> 
> Summary
> -------
> 
> RFC to add proposed API enhancements for containers.
> 
> API allows for sorted containers, insertion options, duplicate handling options, and traversal order options.
> 
> Also has several documentation corrections.
> 
> 
> Diffs
> -----
> 
>   /trunk/include/asterisk/astobj2.h 360708 
> 
> Diff: https://reviewboard.asterisk.org/r/1835/diff
> 
> 
> Testing
> -------
> 
> It compiles but doesn't link.  This is a RFC.  :)
> 
> 
> Thanks,
> 
> rmudgett
> 
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.digium.com/pipermail/asterisk-dev/attachments/20120329/cbe61b99/attachment-0001.htm>