Re: Сортировка "наобо рот"

From

Andrew Ezhguroff ()

To

Andrew Ezhguroff

Date

2002-10-13T16:08:17Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Andrew Ezhguroff" <eandr@com2com.ru>  сообщил(а):

Вот такой набросок алгоритма на псевдокоде:

type _List_Msg := record
                    Next_Msg: ^_List_Msg;
                    Val_Msg :  _Message ;
                  end record;

type _Queue := record
                 Prev_Queue:  integer  ;
                 Next_Queue:  integer  ;
                 Time_Msg  :  long     ;
                 Beg_Msg   : ^_List_Msg;
                 End_Msg   : ^_List_Msg;
               end record;

var Tab_Queue: array [0..0xFF] of _Queue;
    Cur_Queue: integer(-1);

// Параллельный процесс - выдача сообщений устройствам
task Put_Msg;
  var Delta_Time:  long     ;
      Tmp_Msg   : ^_List_Msg;
begin
  loop
    wait while Cur_Queue==(-1); // Приостанавливаем, пока список пуст
    Delta_Time:=Min_Time-(Get_Time()-Tab_Queue[Cur_Queue].Time_Msg);
    if Delta_Time>0 then // Приостанавливаем, пока не истекло время
      wait time(Delta_Time);
    end if;

    // Собственно отправка сообщения
    Tmp_Msg:=Tab_Queue[Cur_Queue].Beg_Msg;
    send_message(Cur_Queue, Tmp_Msg^.Val_Msg);
    Tab_Queue[Cur_Queue].Time_Msg:=Get_Time();

    critical
      // Удаляем сообщение из очереди
      Tab_Queue[Cur_Queue].Beg_Msg:=Tmp_Msg^.Next_Msg;
      delete Tmp_Msg;

      if Tab_Queue[Cur_Queue].Beg_Msg!=NULL then
        // Если очередь не пуста, переходим к следующей очереди
        Cur_Queue:=Tab_Queue[Cur_Queue].Next_Queue;
      elsif Cur_Queue!=Tab_Queue[Cur_Queue].Next_Queue then
        // Если в списке более одной очереди,
        // удаляем пустую очередь из списка
        Tab_Queue[Tab_Queue[Cur_Queue].Next_Queue].Prev_Queue:=
          Tab_Queue[Cur_Queue].Prev_Queue;
        Tab_Queue[Tab_Queue[Cur_Queue].Prev_Queue].Next_Queue:=
          Tab_Queue[Cur_Queue].Next_Queue;
        Cur_Queue:=Tab_Queue[Cur_Queue].Next_Queue;
      else
        // Если непустых очередей нет, обнуляем список
        Cur_Queue:=(-1);
      end if;
    end ctitical;
  end loop;
end task;

// Интерфейс - занесение сообщения в очередь
interface Out_Msg(Device: integer, Msg: Message);
  var Tmp_Msg : ^_List_Msg;
begin
  critical
    // Добавляем сообщение к очереди
    Tmp_Msg :=new _List_Msg(Message);
    if Tab_Tab_Queue[Device].Beg_Msg!=NULL then
      // Если очередь не пуста
      Tab_Tab_Queue[Device].End_Msg^.Next_Msg:=Tmp_Msg;
    else
      // Если очередь пуста
      Tab_Tab_Queue[Device].Beg_Msg:=Tmp_Msg;
      if Cur_Queue==(-1) then
        // Добавляем очередь в пустой кольцевой список
        Cur_Queue:=Device;
        Tab_Queue[Device].Prev_Queue:=Device;
        Tab_Queue[Device].Next_Queue:=Device;
      else
        // Добавляем очередь в непустой кольцевой список
        // Это простейший вариант, желательно его немного усложнить,
        // чтобы добавлять не в "конец", а по времени отправки
        // последнего сообщения
        Tab_Queue[Device].Next_Queue:=Cur_Queue;
        Tab_Queue[Device].Prev_Queue:=Tab_Queue[Cur_Queue].Prev_Queue;
        Tab_Queue[Tab_Queue[Cur_Queue].Prev_Queue].Next_Queue:=Device;
        Tab_Queue[Cur_Queue].Prev_Queue:=Device;
      end if;
    end if;
    Tab_Tab_Queue[Device].End_Msg:=Tmp_Msg;
  end critical;
end interface;

С уважением, Андрей.


-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)