Channel Patch

[Peter Stuge]

On Tue, Aug 07, 2007 at 03:29:06PM -0400, Chris Rapier wrote:
> > The step optimization is really simple and still allows index
> > lookups. The step works just like a pointer in the linked list.
> 
> I'm going to betray my ignorance here and ask for a bit of
> clarification.

Sure!


> This isn't like a skip list but basically just a data element that
> points to the next active channel.

Well I interpreted it as a skip int that would be in the array.


> So instead of iterating through every element of the array I'd only
> go to active elements by doing something like
> 
> for (c = channels; c != NULL;  c = c->skip)
> {}

int i=0;
for(c=channels[i];c;i+=c->skip) {}


> When a channel is added or removed I would have to iterate through
> the entire array and update c->skip but that operation shouldn't
> happen all that often. Is this correct?

On add you need to find a free slot. How is not important. One way is
just iterating over the array from start until c->skip>1 and then
channels[i+1] will be free. Fill channels[i+1], then set
channels[i+1].skip=c->skip-1 and finally set c->skip=1.

Remove is cheaper, just do ++channels[i-1].skip;


> If so, this would preserve the index lookup and eliminate
> unnecessary looping, wouldn't it? In fact, its basically a
> linked list but superimposed on an array, right?

Yep. I envisioned using an index for skipping rather than a pointer
but the effect is exactly the same.


//Peter