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

[Tim Panton]

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.