[asterisk-dev] [Code Review]: RFC for proposed astobj2 API container enhancements
rmudgett
reviewboard at asterisk.org
Thu Mar 29 12:31:38 CDT 2012
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, line 725
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line725>
> >
> > I don't really like the term "container key item". I think that something like "search key" would be better.
done
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 933-935
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line933>
> >
> > Either change this to "duplicate-keyed objects" (added hyphen) or to "objects with duplicate keys". I prefer the second one.
done
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, line 904
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line904>
> >
> > "sense"
done
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 891-892
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line891>
> >
> > It's spelled "descending"
done
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 908-917
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line908>
> >
> > Having a flag evaluate to '0' doesn't work.
> >
> > Presumably, you're going to have some code that does something like
> >
> > if (flags & AO2_CONTAINER_ALLOC_OPT_INSERT_END) {
> > do_something();
> > }
> >
> > Having a 0-defined flag means that the if will never evaluate true.
> >
> > My guess here is that your intention is for this to be a "default" behavior, meaning that you will assume this behavior unless a conflicting option is specified. This is inherently risky though because someone may attempt to actually use this flag in other code, not realizing that a logical and will never evaluate true.
> >
> > I suggest either
> > 1) Remove the flag altogether and document default behavior in ao2_container_alloc()
> > 2) Keep the flag but make it non-zero. You can then document that if an ordering is not specified, then AO2_CONTAINER_ALLOC_OPT_INSERT_END is implied.
Removed. I originally had a sort enumeration value to indicate where to insert the object. However, I realized that the presence of the sort callback function already implied the container is sorted so I gave this flag a secondary meaning for duplicates.
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 929-932
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line929>
> >
> > (0 << 1) ?
> >
> > I'm going to assume again that this flag does not actually get evaluated anywhere and is provided to indicate default behavior unless a conflicting flag is set. My same advice for AO2_CONTAINER_ALLOC_OPT_INSERT_END applies here; either get rid of the flag altogether or make it evaluate to something other than 0.
Again, this is an enumeration option and the presence of the mask definition is needed. I have moved the mask definition to the beginning of the enumeration definitions.
> 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.
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.
> 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?
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.
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, line 953
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line953>
> >
> > This flag definition is haphazard because if someone sets AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, then the other two AO2_CONTAINER_ALLOC_OPT_DUPS flags evaluate true as well. Code can be written to handle this properly, but it's just done way too riskily here for my tastes.
> >
> > Don't be afraid to use more bits. We've got plenty of them :)
It is still an enumeration.
We only have 32 bits. Otherwise we need to use different coins. :)
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, lines 954-955
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line954>
> >
> > Why is this needed?
It is an enumeration option not bit flags.
> 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.
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".
> On March 29, 2012, 9:50 a.m., Mark Michelson wrote:
> > /trunk/include/asterisk/astobj2.h, line 1126
> > <https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line1126>
> >
> > Shouldn't a sort_fn be required for a red-black tree? Also, a red-black tree doesn't have "buckets".
Done. Cut-n-paste error from the hash definitions.
> 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?
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.
- rmudgett
-----------------------------------------------------------
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/e3de01d8/attachment-0001.htm>
More information about the asterisk-dev
mailing list