ByteQueue.java
     1: //========================================================================================
     2: //  ByteQueue.java
     3: //    en:Byte queue
     4: //    ja:バイトキュー
     5: //  Copyright (C) 2003-2025 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 ByteQueue {
    16: 
    17:   private static final class Block {
    18:     private volatile Block p = null;  //前のブロック。先頭のブロックの方向のリンク。null=先頭のブロック
    19:     private volatile Block n = null;  //後のブロック。末尾のブロックの方向のリンク。null=末尾のブロック
    20:     
    21:     private static final int s = 1 << 16;  //配列のバイト数。2の累乗
    22:     private static final byte[] a = new byte[s];  //配列
    23:     private volatile long w = 0;  //書き込んだバイト数
    24:     private volatile long r = w;  //読み出したバイト数
    25:     //  a[(int)w&(s-1)]  書き込む位置
    26:     //  a[(int)r&(s-1)]  読み出す位置
    27:     //  r+s-w            書き込めるバイト数
    28:     //  w-r              読み出せるバイト数
    29:     //  w==r+s           満
    30:     //  r==w             空
    31:     //  0<=w-r<=s
    32:     //  r<=w<=r+s
    33: 
    34:     //length = clear ()
    35:     //  空にする。読み飛ばしたバイト数を返す
    36:     private int clear () {
    37:       return skip (used ());
    38:     }  //clear
    39: 
    40:     //data = read ()
    41:     //  1バイト読み出して0x00~0xffの範囲で返す。-1=空
    42:     private int read () {
    43:       return r != w ? a[(int) (r++) & (s - 1)] & 0xff : -1;
    44:     }  //read
    45: 
    46:     //length = read (array, offset, length)
    47:     //  配列へ読み出す。読み出せたバイト数を返す
    48:     private int read (byte[] array, int offset, int length) {
    49:       length = Math.min (length, (int) (w - r));  //読み出せるバイト数
    50:       int offset0 = offset;
    51:       for (;;) {
    52:         int k = Math.min (length, s - ((int) r & (s - 1)));  //読み出す位置から末尾までのバイト数
    53:         if (k == 0) {
    54:           return offset - offset0;
    55:         }
    56:         System.arraycopy (a, (int) r & (s - 1),
    57:                           array, offset,
    58:                           k);
    59:         r += k;
    60:         offset += k;
    61:         length -= k;
    62:       }
    63:     }  //read
    64: 
    65:     //length = skip (length)
    66:     //  読み飛ばす。読み飛ばせた長さを返す
    67:     private int skip (int length) {
    68:       length = Math.min (length, (int) (w - r));  //読み飛ばせるバイト数
    69:       r += length;
    70:       return length;
    71:     }  //skip
    72: 
    73:     //length = unused ()
    74:     //  書き込めるバイト数を返す。0=満
    75:     private int unused () {
    76:       return (int) (r + s - w);
    77:     }  //unused
    78: 
    79:     //length = used ()
    80:     //  読み出せるバイト数を返す。0=空
    81:     private int used () {
    82:       return (int) (w - r);
    83:     }  //used
    84: 
    85:     //write (data)
    86:     //  1バイト書き込む。書き込めたバイト数を返す
    87:     private int write (int data) {
    88:       if (w == r + s) {
    89:         return 0;
    90:       }
    91:       a[(int) (w++) & (s - 1)] = (byte) data;
    92:       return 1;
    93:     }  //write
    94: 
    95:     //length = write (array, offset, length)
    96:     //  配列から書き込む。書き込めたバイト数を返す
    97:     private int write (byte[] array, int offset, int length) {
    98:       length = Math.min (length, (int) (r + s - w));  //書き込めるバイト数
    99:       int offset0 = offset;
   100:       for (;;) {
   101:         int k = Math.min (length, s - ((int) w & (s - 1)));  //書き込む位置から末尾までのバイト数
   102:         if (k == 0) {
   103:           return offset - offset0;
   104:         }
   105:         System.arraycopy (array, offset,
   106:                           a, (int) w & (s - 1),
   107:                           k);
   108:         w += k;
   109:         offset += k;
   110:         length -= k;
   111:       }
   112:     }  //write
   113: 
   114:   }  //class Block
   115: 
   116:   private volatile Block h = new Block ();  //先頭のブロック。次に読み出すブロック。h.p==null
   117:   private volatile Block t = h;  //末尾のブロック。次に書き込むブロック。t.n==null
   118: 
   119:   private static final int s = 0x7fffffff;  //上限のバイト数
   120:   private volatile long w = 0;  //書き込んだバイト数
   121:   private volatile long r = w;  //読み出したバイト数
   122:   //  r+s-w            書き込めるバイト数
   123:   //  w-r              読み出せるバイト数
   124:   //  w==r+s           満
   125:   //  r==w             空
   126:   //  0<=w-r<=s
   127:   //  r<=w<=r+s
   128: 
   129:   //length = clear ()
   130:   //  空にする。読み飛ばしたバイト数を返す
   131:   protected int clear () {
   132:     return skip (used ());
   133:   }  //clear
   134: 
   135:   //data = read ()
   136:   //  1バイト読み出して0x00~0xffの範囲で返す。-1=空
   137:   protected int read () {
   138:     int data = h.read ();
   139:     if (data < 0) {
   140:       if (h == t) {
   141:         return data;
   142:       }
   143:       Block n = h.n;
   144:       n.p = null;
   145:       h.n = null;
   146:       h = n;
   147:       data = h.read ();
   148:     }
   149:     r++;
   150:     return data;
   151:   }  //read
   152: 
   153:   //length = read (array, offset, length)
   154:   //  配列へ読み出す。読み出せたバイト数を返す
   155:   protected int read (byte[] array, int offset, int length) {
   156:     if (length == 0) {
   157:       return 0;
   158:     }
   159:     //length = Math.min (length, (int) (w - r));  //読み出せるバイト数
   160:     long r0 = r;
   161:     int k = h.read (array, offset, length);
   162:     r += k;
   163:     offset += k;
   164:     length -= k;
   165:     while (length != 0) {
   166:       if (h == t) {
   167:         return (int) (r - r0);
   168:       }
   169:       Block n = h.n;
   170:       n.p = null;
   171:       h.n = null;
   172:       h = n;
   173:       k = h.read (array, offset, length);
   174:       r += k;
   175:       offset += k;
   176:       length -= k;
   177:     }
   178:     return (int) (r - r0);
   179:   }  //read
   180: 
   181:   //length = skip (length)
   182:   //  読み飛ばす。読み飛ばせた長さを返す
   183:   protected int skip (int length) {
   184:     if (length == 0) {
   185:       return 0;
   186:     }
   187:     //length = Math.min (length, (int) (w - r));  //読み出せるバイト数
   188:     long r0 = r;
   189:     int k = h.skip (length);
   190:     r += k;
   191:     length -= k;
   192:     while (length != 0) {
   193:       if (h == t) {
   194:         return (int) (r - r0);
   195:       }
   196:       Block n = h.n;
   197:       n.p = null;
   198:       h.n = null;
   199:       h = n;
   200:       k = h.skip (length);
   201:       r += k;
   202:       length -= k;
   203:     }
   204:     return (int) (r - r0);
   205:   }  //skip
   206: 
   207:   //length = unused ()
   208:   //  書き込めるバイト数を返す。0=満
   209:   protected int unused () {
   210:     return (int) (r + s - w);
   211:   }  //unused
   212: 
   213:   //length = used ()
   214:   //  読み出せるバイト数を返す。0=空
   215:   protected int used () {
   216:     return (int) (w - r);
   217:   }  //used
   218: 
   219:   //length = write (data)
   220:   //  1バイト書き込む。書き込めたバイト数を返す
   221:   protected int write (int data) {
   222:     if (w == r + s) {
   223:       return 0;
   224:     }
   225:     if (t.write (data) == 0) {
   226:       Block n = new Block ();
   227:       n.p = t;
   228:       t.n = n;
   229:       t = n;
   230:       t.write (data);
   231:     }
   232:     w++;
   233:     Thread wt = waitThread;  //待機中のスレッドが
   234:     if (wt != null) {  //あれば
   235:       wt.interrupt ();  //割り込む
   236:     }
   237:     return 1;
   238:   }  //write
   239: 
   240:   //length = write (array, offset, length)
   241:   //  配列から書き込む。書き込めたバイト数を返す
   242:   protected int write (byte[] array, int offset, int length) {
   243:     if (length == 0) {
   244:       return 0;
   245:     }
   246:     length = Math.min (length, (int) (r + s - w));  //書き込めるバイト数
   247:     long w0 = w;
   248:     int k = t.write (array, offset, length);
   249:     w += k;
   250:     offset += k;
   251:     length -= k;
   252:     while (length != 0) {
   253:       Block n = new Block ();
   254:       n.p = t;
   255:       t.n = n;
   256:       t = n;
   257:       k = t.write (array, offset, length);
   258:       w += k;
   259:       offset += k;
   260:       length -= k;
   261:     }
   262:     Thread wt = waitThread;  //待機中のスレッドが
   263:     if (wt != null) {  //あれば
   264:       wt.interrupt ();  //割り込む
   265:     }
   266:     return (int) (w - w0);
   267:   }  //write
   268: 
   269: 
   270:   private volatile Thread waitThread = null;  //waitAndReadで待機中のスレッド。null=ない
   271:   private volatile int waitNumber;  //waitAndReadの呼び出し番号。waitAndReadが書き込む
   272:   private volatile int cancelNumber;  //waitAndReadのキャンセル番号。cancelが書き込む
   273: 
   274:   //cancel ()
   275:   //  waitAndReadをキャンセルする
   276:   protected void cancel () {
   277:     Thread wt = waitThread;  //待機中のスレッドが
   278:     if (wt != null) {  //あれば
   279:       cancelNumber = waitNumber;  //キャンセルして
   280:       wt.interrupt ();  //割り込む
   281:     }
   282:   }  //cancel
   283: 
   284:   //data = waitAndRead ()
   285:   //  1バイト読み出して0x00~0xffの範囲で返す
   286:   //  1バイト読み出せるまでブロックする
   287:   //  キャンセルされたとき-1を返す
   288:   //  readと同じスレッドで呼び出すこと
   289:   protected int waitAndRead () {
   290:     int data = -1;
   291:     waitThread = Thread.currentThread ();  //待機中のスレッドは現在のスレッド
   292:     waitNumber++;
   293:     while (waitNumber != cancelNumber) {  //キャンセルされていなければ繰り返す
   294:       data = read ();  //データを読み出す。なければ-1
   295:       if (0 <= data || waitNumber == cancelNumber) {  //データがあるかキャンセルされたら
   296:         break;  //終わり
   297:       }
   298:       try {
   299:         //while (true) {  //割り込まれなくても3億年経つと起きてしまうが条件が揃わなければ二度寝するだけなので以下略
   300:         Thread.sleep (Long.MAX_VALUE);  //割り込みを待つ
   301:         //}
   302:       } catch (InterruptedException ie) {
   303:       }
   304:     }
   305:     waitThread = null;  //待機中のスレッドはない
   306:     return data;  //データを返す
   307:   }  //waitAndRead
   308: 
   309:   //length = waitAndRead (array, offset, length)
   310:   //  配列へ読み出す。読み出せたバイト数を返す
   311:   //  少なくとも1バイト読み出せるまでブロックする
   312:   //  キャンセルされたとき-1を返す
   313:   //  readと同じスレッドで呼び出すこと
   314:   protected int waitAndRead (byte[] array, int offset, int length) {
   315:     if (length == 0) {
   316:       return 0;
   317:     }
   318:     int data = waitAndRead ();  //1バイト読み出す
   319:     if (data < 0) {  //キャンセルされた
   320:       return -1;
   321:     }
   322:     array[offset] = (byte) data;  //1バイト目
   323:     return 1 + read (array, offset + 1, Math.min (length - 1, used ()));  //2バイト目以降
   324:   }  //waitAndRead
   325: 
   326: 
   327: }  //class ByteQueue