About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Tue, 14 Nov 2006

Why trees are better than binary search.


For netchannels wildcard support I need to create set of non-crossing intervals which will be examined for each packet. It is possible to put them one-by-one and thus form an array of intervals which can be traversed using binary search, but there is a major problem when we will add new interval, which should be placed somewhere inside the existing array - that will force array reallocation and copy. This problem also applies to hash tables and actually all other table-based approaches, but does not exist in trees, although tree requres a bit more memory.
both have the same search speed about O(log2(N)), where N is number of intervals.

Rough code snippet (no return value checks and reference counters update), which splits intervals into non-crossing ranges:

	if (in->min < new->min) {
		netchannel_interval_split(in, in->min, new->min-1, GFP_KERNEL);
		if (in->max > new->max) {
			netchannel_interval_split(NULL, new->min, new->max, GFP_KERNEL);
			netchannel_interval_split(new, new->max+1, in->max, GFP_KERNEL);
		} else if (in->max < new->max) {
			netchannel_interval_split(NULL, new->min, in->max, GFP_KERNEL);
			netchannel_interval_split(new, in->max+1, new->max, GFP_KERNEL);
		} else {
			netchannel_interval_split(new, new->min, in->max, GFP_KERNEL);
		}
	} else if (in->min > new->min) {
		netchannel_interval_split(in, new->min, in->min-1, GFP_KERNEL);
		if (in->max > new->max) {
			netchannel_interval_split(NULL, in->min, new->max, GFP_KERNEL);
			netchannel_interval_split(new, new->max+1, in->max, GFP_KERNEL);
		} else if (in->max < new->max) {
			netchannel_interval_split(NULL, in->min, in->max, GFP_KERNEL);
			netchannel_interval_split(new, in->max+1, new->max, GFP_KERNEL);
		} else {
			netchannel_interval_split(new, in->min, new->max, GFP_KERNEL);
		}
	} else {
		if (in->max > new->max) {
			netchannel_interval_split(in, in->min, new->max, GFP_KERNEL);
			netchannel_interval_split(new, new->max+1, in->max, GFP_KERNEL);
		} else if (in->max < new->max) {
			netchannel_interval_split(in, in->min, in->max, GFP_KERNEL);
			netchannel_interval_split(new, in->max+1, new->max, GFP_KERNEL);
		} else {
			netchannel_interval_split(in, in->min, in->max, GFP_KERNEL);
		}
	}

/devel/networking :: Link / Comments ()