<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 solid;">
<tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://reviewboard.asterisk.org/r/1835/">https://reviewboard.asterisk.org/r/1835/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<p style="margin-top: 0;">On March 29th, 2012, 9:50 a.m., <b>Mark Michelson</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<table width="100%" border="0" bgcolor="white" style="border: 1px solid #C0C0C0; border-collapse: collapse; margin: 2px padding: 2px;">
<thead>
<tr>
<th colspan="4" bgcolor="#F0F0F0" style="border-bottom: 1px solid #C0C0C0; font-size: 9pt; padding: 4px 8px; text-align: left;">
<a href="https://reviewboard.asterisk.org/r/1835/diff/1/?file=26924#file26924line1064" style="color: black; font-weight: bold; text-decoration: underline;">/trunk/include/asterisk/astobj2.h</a>
<span style="font-weight: normal;">
(Diff revision 1)
</span>
</th>
</tr>
</thead>
<tbody style="background-color: #e4d9cb; padding: 4px 8px; text-align: center;">
<tr>
<td colspan="4"><pre style="font-size: 8pt; line-height: 140%; margin: 0; ">struct ao2_container;</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" align="right"><font size="2"></font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "></pre></td>
<th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; border-right: 1px solid #C0C0C0;" align="right"><font size="2">1036</font></th>
<td bgcolor="#c5ffc4" width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; "><span class="cm"> * \param sort_fn Pointer to a sort function. (NULL if buckets not sorted.)</span></pre></td>
</tr>
</tbody>
</table>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre>
</blockquote>
<p>On March 29th, 2012, 12:19 p.m., <b>rmudgett</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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".</pre>
</blockquote>
<p>On March 29th, 2012, 2:05 p.m., <b>Mark Michelson</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre>
</blockquote>
<p>On March 30th, 2012, 5:53 a.m., <b>schmidts</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">i dont know if this will still brake something but i had once the idea of adding the "move to front" algorithm for objects in a bucket but this had broke some thing in the code. When you are doing a sort order in a bucket it should also be possible to add this move to front method also, right?
Cause this could improve the access speed of objects in a bucket.</pre>
</blockquote>
</blockquote>
<pre style="margin-left: 1em; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">I had seriously considered adding a move-to-front option because you had attempted to add that feature.
I rejected it for several reasons:
1) It is incompatible with rwlocks. Every read would modify the container and thus require the write lock to be obtained.
2) It would still break iterators. I came up with a way around the problem but the overhead needed did not seem worth it and iterators could not get the benefit.
3) It is a specialized list optimization.
When I get a chance to implement the red-black tree container, we might get an overall speed improvement from the channels container because a partial channel name search would not have to search the whole container.
One thing you might want to look at is the hashing algorithm used for the channels container and the number of buckets. It might be suffering from too many hash collisions, a non-prime number of buckets, or just too few buckets. Hash containers are supposed to have O(1) access. However, if you have too many collisions, you then have to consider the access time of the buckets. In this case a linked list which is O(n)/2.</pre>
<br />
<p>- rmudgett</p>
<br />
<p>On March 29th, 2012, 5:06 p.m., rmudgett wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" style="background-image: url('https://reviewboard.asterisk.org/media/rb/images/review_request_box_top_bg.png'); background-position: left top; background-repeat: repeat-x; border: 1px black solid;">
<tr>
<td>
<div>Review request for Asterisk Developers, Mark Michelson and Matt Jordan.</div>
<div>By rmudgett.</div>
<p style="color: grey;"><i>Updated March 29, 2012, 5:06 p.m.</i></p>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">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.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: 1px solid #b8b5a0">
<tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">It compiles but doesn't link. This is a RFC. :)</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>/trunk/include/asterisk/astobj2.h <span style="color: grey">(360828)</span></li>
</ul>
<p><a href="https://reviewboard.asterisk.org/r/1835/diff/" style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>