/*
    * Copyright 2012 The Netty Project
    *
    * The Netty Project licenses this file to you under the Apache License,
    * version 2.0 (the "License"); you may not use this file except in compliance
    * with the License. You may obtain a copy of the License at:
    *
    *   https://www.apache.org/licenses/LICENSE-2.0
    *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
   * License for the specific language governing permissions and limitations
   * under the License.
   */
  
  package io.netty.buffer;
  
  import static io.netty.buffer.PoolChunk.RUN_OFFSET_SHIFT;
  import static io.netty.buffer.PoolChunk.SIZE_SHIFT;
  import static io.netty.buffer.PoolChunk.IS_USED_SHIFT;
  import static io.netty.buffer.PoolChunk.IS_SUBPAGE_SHIFT;
  import static io.netty.buffer.SizeClasses.LOG2_QUANTUM;
  
  final class PoolSubpage<T> implements PoolSubpageMetric {
  
      final PoolChunk<T> chunk;
      final int elemSize;
      private final int pageShifts;
      private final int runOffset;
      private final int runSize;
      private final long[] bitmap;
  
      PoolSubpage<T> prev;
      PoolSubpage<T> next;
  
      boolean doNotDestroy;
      private int maxNumElems;
      private int bitmapLength;
      private int nextAvail;
      private int numAvail;
  
      // TODO: Test if adding padding helps under contention
      //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
  
      /** Special constructor that creates a linked list head */
      PoolSubpage() {
          chunk = null;
          pageShifts = -1;
          runOffset = -1;
          elemSize = -1;
          runSize = -1;
          bitmap = null;
      }
  
      PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int pageShifts, int runOffset, int runSize, int elemSize) {
          this.chunk = chunk;
          this.pageShifts = pageShifts;
          this.runOffset = runOffset;
          this.runSize = runSize;
          this.elemSize = elemSize;
          bitmap = new long[runSize >>> 6 + LOG2_QUANTUM]; // runSize / 64 / QUANTUM
  
          doNotDestroy = true;
          if (elemSize != 0) {
              maxNumElems = numAvail = runSize / elemSize;
              nextAvail = 0;
              bitmapLength = maxNumElems >>> 6;
              if ((maxNumElems & 63) != 0) {
                  bitmapLength ++;
              }
  
              for (int i = 0; i < bitmapLength; i ++) {
                  bitmap[i] = 0;
              }
          }
          addToPool(head);
      }
  
      /**
       * Returns the bitmap index of the subpage allocation.
       */
      long allocate() {
          if (numAvail == 0 || !doNotDestroy) {
              return -1;
          }
  
          final int bitmapIdx = getNextAvail();
          int q = bitmapIdx >>> 6;
          int r = bitmapIdx & 63;
          assert (bitmap[q] >>> r & 1) == 0;
          bitmap[q] |= 1L << r;
  
          if (-- numAvail == 0) {
              removeFromPool();
          }
  
          return toHandle(bitmapIdx);
      }
 
     /**
      * @return {@code true} if this subpage is in use.
      *         {@code false} if this subpage is not used by its chunk and thus it's OK to be released.
      */
     boolean free(PoolSubpage<T> head, int bitmapIdx) {
         if (elemSize == 0) {
             return true;
         }
         int q = bitmapIdx >>> 6;
         int r = bitmapIdx & 63;
         assert (bitmap[q] >>> r & 1) != 0;
         bitmap[q] ^= 1L << r;
 
         setNextAvail(bitmapIdx);
 
         if (numAvail ++ == 0) {
             addToPool(head);
             /* When maxNumElems == 1, the maximum numAvail is also 1.
              * Each of these PoolSubpages will go in here when they do free operation.
              * If they return true directly from here, then the rest of the code will be unreachable
              * and they will not actually be recycled. So return true only on maxNumElems > 1. */
             if (maxNumElems > 1) {
                 return true;
             }
         }
 
         if (numAvail != maxNumElems) {
             return true;
         } else {
             // Subpage not in use (numAvail == maxNumElems)
             if (prev == next) {
                 // Do not remove if this subpage is the only one left in the pool.
                 return true;
             }
 
             // Remove this subpage from the pool if there are other subpages left in the pool.
             doNotDestroy = false;
             removeFromPool();
             return false;
         }
     }
 
     private void addToPool(PoolSubpage<T> head) {
         assert prev == null && next == null;
         prev = head;
         next = head.next;
         next.prev = this;
         head.next = this;
     }
 
     private void removeFromPool() {
         assert prev != null && next != null;
         prev.next = next;
         next.prev = prev;
         next = null;
         prev = null;
     }
 
     private void setNextAvail(int bitmapIdx) {
         nextAvail = bitmapIdx;
     }
 
     private int getNextAvail() {
         int nextAvail = this.nextAvail;
         if (nextAvail >= 0) {
             this.nextAvail = -1;
             return nextAvail;
         }
         return findNextAvail();
     }
 
     private int findNextAvail() {
         final long[] bitmap = this.bitmap;
         final int bitmapLength = this.bitmapLength;
         for (int i = 0; i < bitmapLength; i ++) {
             long bits = bitmap[i];
             if (~bits != 0) {
                 return findNextAvail0(i, bits);
             }
         }
         return -1;
     }
 
     private int findNextAvail0(int i, long bits) {
         final int maxNumElems = this.maxNumElems;
         final int baseVal = i << 6;
 
         for (int j = 0; j < 64; j ++) {
             if ((bits & 1) == 0) {
                 int val = baseVal | j;
                 if (val < maxNumElems) {
                     return val;
                 } else {
                     break;
                 }
             }
             bits >>>= 1;
         }
         return -1;
     }
 
     private long toHandle(int bitmapIdx) {
         int pages = runSize >> pageShifts;
         return (long) runOffset << RUN_OFFSET_SHIFT
                | (long) pages << SIZE_SHIFT
                | 1L << IS_USED_SHIFT
                | 1L << IS_SUBPAGE_SHIFT
                | bitmapIdx;
     }
 
     @Override
     public String toString() {
         final boolean doNotDestroy;
         final int maxNumElems;
         final int numAvail;
         final int elemSize;
         if (chunk == null) {
             // This is the head so there is no need to synchronize at all as these never change.
             doNotDestroy = true;
             maxNumElems = 0;
             numAvail = 0;
             elemSize = -1;
         } else {
             synchronized (chunk.arena) {
                 if (!this.doNotDestroy) {
                     doNotDestroy = false;
                     // Not used for creating the String.
                     maxNumElems = numAvail = elemSize = -1;
                 } else {
                     doNotDestroy = true;
                     maxNumElems = this.maxNumElems;
                     numAvail = this.numAvail;
                     elemSize = this.elemSize;
                 }
             }
         }
 
         if (!doNotDestroy) {
             return "(" + runOffset + ": not in use)";
         }
 
         return "(" + runOffset + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +
                 ", offset: " + runOffset + ", length: " + runSize + ", elemSize: " + elemSize + ')';
     }
 
     @Override
     public int maxNumElements() {
         if (chunk == null) {
             // It's the head.
             return 0;
         }
 
         synchronized (chunk.arena) {
             return maxNumElems;
         }
     }
 
     @Override
     public int numAvailable() {
         if (chunk == null) {
             // It's the head.
             return 0;
         }
 
         synchronized (chunk.arena) {
             return numAvail;
         }
     }
 
     @Override
     public int elementSize() {
         if (chunk == null) {
             // It's the head.
             return -1;
         }
 
         synchronized (chunk.arena) {
             return elemSize;
         }
     }
 
     @Override
     public int pageSize() {
         return 1 << pageShifts;
     }
 
     void destroy() {
         if (chunk != null) {
             chunk.destroy();
         }
     }
 }