[asterisk-dev] [Code Review] Implement ast_channel_search_locked to expensive per-notify channel walk in chan_sip

[Tim Panton]

On 6 Nov 2008, at 17:40, Steve Murphy wrote:

> On Wed, 2008-11-05 at 10:44 +0000, Tim Panton wrote:
>> On 4 Nov 2008, at 23:54, Brian Degenhardt wrote:
>>>
>>> That's what I was thinking, but I was wondering if Murf and Russell
>>> could comment on if that approach is adequate, or if we want to
>>> maintain
>>> a hashtab of channels keyed on linkedid, and insert/remove them from
>>> there.
>>>
>>> I'm sorta partial to your way, above.  While it's slower, we don't
>>> have
>>> to worry about maintaining the separate data structure which has the
>>> potential to get out of sync.  Especially since this code only  
>>> runs if
>>> you care about LINKEDID_END events.
>>
>> I've been so long out of the C world I'm not sure this helps, but we
>> had a similar problem _years_ ago and I ended up solving it with a  
>> weird
>> dual purpose data structure. It was (originally) a linked list the
>> sequence
>> mattered and in some cases it needed to be walked in order.
>> The most frequent access was a name based lookup that was independent
>> of sequence for which we really wanted a hashtable.
>>
>> What we did was to replace the 'malloc/free' code in the linked list
>> insert/delete.
>> It allocated a slot in a hash table (based on a hash of the name).  
>> All
>> the
>> list walk stuff worked exactly as before, but we added a fast
>> find_by_name()
>> that used the hashtable. It gave us a huge speedup. The only problem
>> was when
>> the names changed. - we had to implement that as a delete/add.
>>
>> Tim.
>
> Tim--
>
> Using multiple structures to provide different access methods to the
> same
> set of items is definitely an option. As usual, there are speed/size
> compromises to make, where size is both code and memory.
>
> murf
>

Sure, but what was nice about this one was that there was only 1  
datastructure,
the hashtable, but we added pointers in each entry that allowed you to  
walk
through it like a list  when needed.

Tim.