1: //========================================================================================
     2: //  TickerQueue.java
     3: //    en:Sort of a simple task scheduler
     4: //    ja:簡易タスクスケジューラのようなもの
     5: //  Copyright (C) 2003-2026 Makoto Kamada
     6: //
     7: //  This file is part of the XEiJ (X68000 Emulator in Java).
     8: //  You can use, modify and redistribute the XEiJ if the conditions are met.
     9: //  Read the XEiJ License for more details.
    10: //  https://stdkmd.net/xeij/
    11: //========================================================================================
    12: 
    13: package xeij;
    14: 
    15: public class TickerQueue {
    16: 
    17:   //class Ticker
    18:   //  ティッカー
    19:   public static abstract class Ticker {
    20:     Ticker () {
    21:       time = Long.MAX_VALUE;  //キューにない
    22:     }
    23:     long time;  //実行時刻。キューにないときLong.MAX_VALUE
    24:     //  tickが呼び出された時点でthisはキューから削除されている
    25:     //  tickの中でtkqAddを呼び出してthisまたは他のティッカーをキューに追加できる
    26:     //  tickの中でtkqRemoveを呼び出して他のティッカーをキューから削除できる
    27:     //  tickの中でtkqRunを呼び出してはならない
    28:     abstract void tick ();
    29:   }  //class Ticker
    30: 
    31:   //キュー
    32:   //  キューに近いソート済み集合
    33:   static final int TKQ_S = 256;  //容量。2の累乗
    34:   static final Ticker[] tkqArray = new Ticker[TKQ_S];  //配列。未使用領域は不定
    35:   //  w-r       使用量
    36:   //  r==w      空
    37:   //  s-(w-r)   空き容量
    38:   //  (w-r)==s  満杯
    39:   //  w&(s-1)   末尾+1のインデックス
    40:   //  r&(s-1)   先頭のインデックス
    41:   static int tkqR;  //先頭。読み出した回数の下位32bit
    42:   static int tkqW;  //末尾+1。書き込んだ回数の下位32bit
    43: 
    44:   static final boolean TKQ_NULL = true;  //true=未使用領域をnullにする
    45: 
    46:   //tkqInit ()
    47:   //  初期化
    48:   public static void tkqInit () {
    49:     //tkqArray = new Ticker[TKQ_S];
    50:     tkqR = 0;
    51:     tkqW = 0;
    52:     if (false) {
    53:       tkqTest ();
    54:     }
    55:   }  //tkqInit
    56: 
    57:   //tkqRun (time)
    58:   //  実行
    59:   //  指定された時刻までの実行時刻を持つティッカーをキューから削除して実行する
    60:   public static void tkqRun (long time) {
    61:     Ticker ticker;
    62:     while (tkqR != tkqW &&  //キューが空でなくて
    63:            (ticker = tkqArray[tkqR & (TKQ_S - 1)]).time <= time) {  //先頭のティッカーが実行時刻になっている
    64:       ticker.time = Long.MAX_VALUE;  //キューから削除する
    65:       if (TKQ_NULL) {
    66:         tkqArray[tkqR & (TKQ_S - 1)] = null;  //未使用領域をnullにする
    67:       }
    68:       tkqR++;  //先頭を進める
    69:       ticker.tick ();  //実行する。ここでtkqRやtkqWが動く場合があることに注意
    70:     }
    71:   }  //tkqRun
    72: 
    73:   //tkqAdd (ticker, time)
    74:   //  追加
    75:   //  指定されたティッカーに指定された時刻を持たせてキューに追加する
    76:   public static void tkqAdd (Ticker ticker, long time) {
    77:     tkqRemove (ticker);  //キューにあれば削除する
    78:     if ((tkqW - tkqR) == TKQ_S) {  //キューが満杯
    79:       throw new Error ("tkqAdd: overflow");
    80:     }
    81:     ticker.time = time;  //キューに追加する
    82:     int w = tkqW;  //後ろから
    83:     Ticker t;
    84:     while (tkqR < w &&
    85:            time < (t = tkqArray[(w - 1) & (TKQ_S - 1)]).time) {  //探す
    86:       tkqArray[w & (TKQ_S - 1)] = t;  //後ろを後ろにずらす
    87:       w--;
    88:     }
    89:     tkqArray[w & (TKQ_S - 1)] = ticker;
    90:     tkqW++;  //末尾を進める
    91:   }  //tkqAdd
    92: 
    93:   //tkqRemove (ticker)
    94:   //  削除
    95:   //  指定されたティッカーがキューにあればキューから削除する。なければ何もしない
    96:   public static void tkqRemove (Ticker ticker) {
    97:     if (ticker.time == Long.MAX_VALUE) {  //キューにない
    98:       return;
    99:     }
   100:     ticker.time = Long.MAX_VALUE;  //削除する
   101:     int r = tkqR;  //先頭から
   102:     while (tkqArray[r & (TKQ_S - 1)] != ticker) {  //探す。必ずある
   103:       r++;
   104:     }
   105:     while (tkqR < r) {
   106:       tkqArray[r & (TKQ_S - 1)] = tkqArray[(r - 1) & (TKQ_S - 1)];  //手前を後ろにずらす
   107:       r--;
   108:     }
   109:     if (TKQ_NULL) {
   110:       tkqArray[r & (TKQ_S - 1)] = null;  //未使用領域をnullにする
   111:     }
   112:     tkqR++;  //先頭を進める
   113:   }  //tkqRemove
   114: 
   115:   //tkqTest ()
   116:   //  テスト
   117:   static void tkqTest () {
   118:     //準備
   119:     int n = 200;
   120:     Ticker[] a = new Ticker[n];
   121:     for (int i = 0; i < n; i++) {
   122:       a[i] = new Ticker () {
   123:         @Override void tick () {
   124:         }
   125:       };
   126:     }
   127:     //昇順書き込み
   128:     for (int i = 0; i < n; i++) {
   129:       tkqAdd (a[i], i);
   130:     }
   131:     if (tkqW - tkqR != n) {
   132:       System.out.println ("tkqTest: error 1");
   133:       return;
   134:     }
   135:     for (int i = 0; i < n; i++) {
   136:       if (tkqArray[(tkqR + i) & (TKQ_S - 1)] != a[i]) {
   137:         System.out.println ("tkqTest: error 2");
   138:         return;
   139:       }
   140:     }
   141:     //昇順削除
   142:     for (int i = 0; i < n; i++) {
   143:       tkqRemove (a[i]);
   144:     }
   145:     if (tkqW - tkqR != 0) {
   146:       System.out.println ("tkqTest: error 3");
   147:       return;
   148:     }
   149:     //昇順書き込み
   150:     for (int i = 0; i < n; i++) {
   151:       tkqAdd (a[i], i);
   152:     }
   153:     if (tkqW - tkqR != n) {
   154:       System.out.println ("tkqTest: error 4");
   155:       return;
   156:     }
   157:     for (int i = 0; i < n; i++) {
   158:       if (tkqArray[(tkqR + i) & (TKQ_S - 1)] != a[i]) {
   159:         System.out.println ("tkqTest: error 5");
   160:         return;
   161:       }
   162:     }
   163:     //降順削除
   164:     for (int i = 0; i < n; i++) {
   165:       tkqRemove (a[n - 1 - i]);
   166:     }
   167:     if (tkqW - tkqR != 0) {
   168:       System.out.println ("tkqTest: error 6");
   169:       return;
   170:     }
   171:     //降順書き込み
   172:     for (int i = 0; i < n; i++) {
   173:       tkqAdd (a[n - 1 - i], n - 1 - i);
   174:     }
   175:     if (tkqW - tkqR != n) {
   176:       System.out.println ("tkqTest: error 7");
   177:       return;
   178:     }
   179:     for (int i = 0; i < n; i++) {
   180:       if (tkqArray[(tkqR + i) & (TKQ_S - 1)] != a[i]) {
   181:         System.out.println ("tkqTest: error 8");
   182:         return;
   183:       }
   184:     }
   185:     //昇順削除
   186:     for (int i = 0; i < n; i++) {
   187:       tkqRemove (a[i]);
   188:     }
   189:     if (tkqW - tkqR != 0) {
   190:       System.out.println ("tkqTest: error 9");
   191:       return;
   192:     }
   193:     //降順書き込み
   194:     for (int i = 0; i < n; i++) {
   195:       tkqAdd (a[n - 1 - i], n - 1 - i);
   196:     }
   197:     if (tkqW - tkqR != n) {
   198:       System.out.println ("tkqTest: error 10");
   199:       return;
   200:     }
   201:     for (int i = 0; i < n; i++) {
   202:       if (tkqArray[(tkqR + i) & (TKQ_S - 1)] != a[i]) {
   203:         System.out.println ("tkqTest: error 11");
   204:         return;
   205:       }
   206:     }
   207:     //降順削除
   208:     for (int i = 0; i < n; i++) {
   209:       tkqRemove (a[n - 1 - i]);
   210:     }
   211:     if (tkqW - tkqR != 0) {
   212:       System.out.println ("tkqTest: error 12");
   213:       return;
   214:     }
   215:   }  //tkqTest
   216: 
   217: }  //class TickerQueue