|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg Khovayko [SPAM trap - don't re 2:5020/400 25 Jul 2003 06:26:43
To : Sergiy Kanilo
Subject : Re: Круговой стек
--------------------------------------------------------------------------------
Sergiy Kanilo wrote:
>> AG> Своего рода кольцевой стек.
Да, эта штука в народе так и зовется - кольцевой буфер.
Делается так: Заводится сам буфер, два указателя (put & get),
и счетчик свободных элементов.
Потом делается примерно так:
#define buf_mask 017 // must be 2^n - 1
void Init() {
put = get = 0;
cnt = buf_mask + 1;
}
bool Put(int x) {
if(cnt <= 0) return false; // queue full
mas[put++] = x;
put &= buf_mask;
cnt--;
return true;
}
int Get() {
if(cnt == buf_mask + 1) return Q_EMPTY;
int rc = mas[get++];
get &= buf_mask;
cnt++;
return rc;
}
Теперь самое главное, ради чего я пишу данной послание:
Если Вы делаете встроеную систему, и имеете возможность выровнять
буфер по некоей границе памяти, такой чтобы адрес буфера содержал
битовые нули в младших разрядах, в которых крутится счетчик,
то возможно еще более эффективное решение - накладывание масок
непосредственно на указатели. В этом случае put & get являются
не индексами в массиве, а непосредственными указателями на массив,
в котором организована кольцевая очередь.
При этом вышеприведенные процедуры начинают выглядеть след. образом:
#define buf_mask 020 // must be 2^n
int mas[buf_mask]; // Выровнян по памяти, и находится с
// адреса, скажем, 01000
void Init() {
put = get = mas; // for example, 01000
cnt = buf_mask;
}
bool Put(int x) {
if(cnt <= 0) return false; // queue full
*put++ = x;
put &= ~(buf_mask << 2);// предполагается, что int 4-х байтовый
cnt--;
return true;
}
int Get() {
if(cnt == buf_mask) return Q_EMPTY;
int rc = *get++;
get &= ~(buf_mask << 2);// предполагается, что int 4-х байтовый
cnt++;
return rc;
}
В примере выше накладывание маски на указатель будеи приводить к тому,
что когда указатель достигает значения 01100, в нем сбрасывается
единственный бит 0100, и он опять указывает на 01000, то есть на mas[0].
PS: Я ознакомился с таким вариантом реализации кольцевого буфера,
реассемблируя в свое время программу периферийной машины ПК УК-HЦ.
Мне тогда сильно понравилось...
PS2: Я этот код написал только что, и не проверял. Возможны ошибки.
--
#include <best/regards>
Oleg Khovayko http://olegh.spedia.net
PS/ATTN: Reply to reverted address net.comcast@olegh
--- ifmail v.2.15dev5
* Origin: http://www.ftc.gov/opa/2001/04/spam.htm (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
