View Javadoc
1   /*
2    * Copyright 2020 The Netty Project
3    *
4    * The Netty Project licenses this file to you under the Apache License,
5    * version 2.0 (the "License"); you may not use this file except in compliance
6    * with the License. You may obtain a copy of the License at:
7    *
8    *   https://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations
14   * under the License.
15   */
16  package io.netty.buffer;
17  
18  import java.util.Arrays;
19  
20  /**
21   * Internal primitive priority queue, used by {@link PoolChunk}.
22   * The implementation is based on the binary heap, as described in Algorithms by Sedgewick and Wayne.
23   */
24  final class IntPriorityQueue {
25      public static final int NO_VALUE = -1;
26      private int[] array = new int[9];
27      private int size;
28  
29      public void offer(int handle) {
30          if (handle == NO_VALUE) {
31              throw new IllegalArgumentException("The NO_VALUE (" + NO_VALUE + ") cannot be added to the queue.");
32          }
33          size++;
34          if (size == array.length) {
35              // Grow queue capacity.
36              array = Arrays.copyOf(array, 1 + (array.length - 1) * 2);
37          }
38          array[size] = handle;
39          lift(size);
40      }
41  
42      public void remove(int value) {
43          for (int i = 1; i <= size; i++) {
44              if (array[i] == value) {
45                  array[i] = array[size--];
46                  lift(i);
47                  sink(i);
48                  return;
49              }
50          }
51      }
52  
53      public int peek() {
54          if (size == 0) {
55              return NO_VALUE;
56          }
57          return array[1];
58      }
59  
60      public int poll() {
61          if (size == 0) {
62              return NO_VALUE;
63          }
64          int val = array[1];
65          array[1] = array[size];
66          array[size] = 0;
67          size--;
68          sink(1);
69          return val;
70      }
71  
72      public boolean isEmpty() {
73          return size == 0;
74      }
75  
76      private void lift(int index) {
77          int parentIndex;
78          while (index > 1 && subord(parentIndex = index >> 1, index)) {
79              swap(index, parentIndex);
80              index = parentIndex;
81          }
82      }
83  
84      private void sink(int index) {
85          int child;
86          while ((child = index << 1) <= size) {
87              if (child < size && subord(child, child + 1)) {
88                  child++;
89              }
90              if (!subord(index, child)) {
91                  break;
92              }
93              swap(index, child);
94              index = child;
95          }
96      }
97  
98      private boolean subord(int a, int b) {
99          return array[a] > array[b];
100     }
101 
102     private void swap(int a, int b) {
103         int value = array[a];
104         array[a] = array[b];
105         array[b] = value;
106     }
107 }