Channel Patch

[Damien Miller]

On Tue, 7 Aug 2007, Chris Rapier wrote:

> Peter Stuge wrote:
> > On Tue, Aug 07, 2007 at 12:51:46PM -0400, Chris Rapier wrote:
> >>> If you wanted to be tricky, you could add a precomputed skip step
> >>> to the channels array that would point to the next allocated
> >>> channel, allowing the loop to skip past unused channels.
> >> One thing I'm not is tricky. I always end up confusing myself.
> >> Mostly I  just write this stuff as research projects in the hope
> >> that it interests someone else enough to actual code things
> >> properly :)
> > 
> > The step optimization is really simple and still allows index
> > lookups. The step works just like a pointer in the linked list.
> > 
> > As long as individual channel entries do not need to be atomically
> > inserted or removed it'll work great!
> 
> I'm going to betray my ignorance here and ask for a bit of 
> clarification. This isn't like a skip list but basically just a data 
> element that points to the next active channel. 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)
> {}

I think it would be more like:

for (i = channel_firstused; i < channels_alloc; i = c->skip)
	...

You would need to track the lowest allocated channel number, or
skip past any initial NULLs. It would be rare that channel 0 would
not be in use, but it is possible when connection multiplexing is in use.

> 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?

You would need to update the next lowest channel's c->skip to point to
the new channel you allocated, or to the next highest allocated allocated
channel on deletion. Something like this:

/* adding channel */

if (channel_first > 0) {
	/* Space exists at the beginning of the array */;
	id = 0
	next_channel = channel_firstused;
	channel_firstused = 0;
} else {
	for (i = channel_first; i < channels_alloc; i = channels[id]->skip) {
		if (channels[i]->skip == i + 1)
			continue;
		/* Found a gap in the array */
		id = i + 1;
		next_channel = channels[i]->skip;
		channels[i]->skip = id;
		break;
	}
	/* No space in array, grow it, etc. */
	...
}

channels[id] = xcalloc(1, sizeof(**channels));
channels[id]->skip = next_channel;

I guess you could optimise this further by keeping a channel_minfree
that is updated when the channels array is grown or when entries are
deleted, but I'm not sure that channel addition/deletion is worth
optimising so much because these operations are relatively infrequent.

> 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?

That's a reasonable analogy.

-d