Re: быстрая вставка в очередь

From

Oleg I. Khovayko ()

To

Dmitri Khanevski ()

Date

2003-03-07T00:07:46Z

Area

RU.ALGORITHMS

From: "Oleg I. Khovayko" <olegh@ncbi.nlm.nih.gov>


Dmitri Khanevski wrote:
> 
> Количество элементов поpядка нескольких сотен.
> 

Допустим, у тебе к таймеру стоит не одна очередь,
а 32 паралельных очереди. В очереди "0" хранятся
заявки на события, которые должны быть выполнены
в нулевой, 32-й, 64-й и т.д. тик. 
В первой очереди - события, которые должны быть 
выполнены в первый, 33-й, 65-й тик, и так далее.

Процессор таймера имеет список из 32-х голов очередей,
и бегает по кругу. То есть, обслужив элемент 
из очереди 0, он не ждет времени срабатывания 
след. элемента из той же очереди, а переходит 
к элементу 1, и т.д.

Тогда вставка в коротенькие очереди-списки
не будет отнимать много времени.
А получение номера очереди, и зацикливание счетчика 
списков можно сделать просто битовыми масками.

Конечно, есть нюансы реализации.
Но сделать все же можно, и получится не 
особо сложно.

P.S:
Если пишешь embedded систему, где ты сам можешь
выбрать место под массив из 32-х слов-указателей
на головы очередей, можно применить такой трюк:

Поместить массив голов (считаем, что одна голова - 4 слова) 
с адреса, где младшие 8 битов равны нулю.

cur_ptr = your_addr;

loop:
	PROCESS cur_ptr
	cur_ptr += 4; Go to next word
	cur_ptr &= ~0200 ; cбросили бит, зациклив тем самым pointer
	goto	loop

Таким образом, в цикл вводится не счетчик, который
потом каждый раз прибавляется к адресу массива, а сам указатель.

-- 
#include <best/regards.hpp>
Oleg I. KHOVAYKO  
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
 * Origin: National Center for Biotechnology Information (2:5020/400)