/*
    * Copyright 2021 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.netty5.buffer.api.pool;
  
  import java.util.concurrent.ConcurrentHashMap;
  
  /**
   * SizeClasses requires {@code pageShifts} to be defined prior to inclusion,
   * and it in turn defines:
   * <p>
   *   LOG2_SIZE_CLASS_GROUP: Log of size class count for each size doubling.
   *   LOG2_MAX_LOOKUP_SIZE: Log of max size class in the lookup table.
   *   sizeClasses: Complete table of [index, log2Group, log2Delta, nDelta, isMultiPageSize,
   *                 isSubPage, log2DeltaLookup] tuples.
   *     index: Size class index.
   *     log2Group: Log of group base size (no deltas added).
   *     log2Delta: Log of delta to previous size class.
   *     nDelta: Delta multiplier.
   *     isMultiPageSize: 'yes' if a multiple of the page size, 'no' otherwise.
   *     isSubPage: 'yes' if a subpage size class, 'no' otherwise.
   *     log2DeltaLookup: Same as log2Delta if a lookup table size class, 'no'
   *                      otherwise.
   * <p>
   *   nSubpages: Number of subpages size classes.
   *   nSizes: Number of size classes.
   *   nPSizes: Number of size classes that are multiples of pageSize.
   *
   *   smallMaxSizeIdx: Maximum small size class index.
   *
   *   lookupMaxclass: Maximum size class included in lookup table.
   *   log2NormalMinClass: Log of minimum normal size class.
   * <p>
   *   The first size class and spacing are 1 << LOG2_QUANTUM.
   *   Each group has 1 << LOG2_SIZE_CLASS_GROUP of size classes.
   *
   *   size = 1 << log2Group + nDelta * (1 << log2Delta)
   *
   *   The first size class has an unusual encoding, because the size has to be
   *   split between group and delta*nDelta.
   *
   *   If pageShift = 13, sizeClasses looks like this:
   *
   *   (index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup)
   * <p>
   *   ( 0,     4,        4,         0,       no,             yes,        4)
   *   ( 1,     4,        4,         1,       no,             yes,        4)
   *   ( 2,     4,        4,         2,       no,             yes,        4)
   *   ( 3,     4,        4,         3,       no,             yes,        4)
   * <p>
   *   ( 4,     6,        4,         1,       no,             yes,        4)
   *   ( 5,     6,        4,         2,       no,             yes,        4)
   *   ( 6,     6,        4,         3,       no,             yes,        4)
   *   ( 7,     6,        4,         4,       no,             yes,        4)
   * <p>
   *   ( 8,     7,        5,         1,       no,             yes,        5)
   *   ( 9,     7,        5,         2,       no,             yes,        5)
   *   ( 10,    7,        5,         3,       no,             yes,        5)
   *   ( 11,    7,        5,         4,       no,             yes,        5)
   *   ...
   *   ...
   *   ( 72,    23,       21,        1,       yes,            no,        no)
   *   ( 73,    23,       21,        2,       yes,            no,        no)
   *   ( 74,    23,       21,        3,       yes,            no,        no)
   *   ( 75,    23,       21,        4,       yes,            no,        no)
   * <p>
   *   ( 76,    24,       22,        1,       yes,            no,        no)
   */
  abstract class SizeClasses implements SizeClassesMetric {
      private static final ConcurrentHashMap<SizeClassKey, SizeClassValue> CACHE =
              new ConcurrentHashMap<>();
  
      static final int LOG2_QUANTUM = 4;
  
      private static final int LOG2_SIZE_CLASS_GROUP = 2;
      private static final int LOG2_MAX_LOOKUP_SIZE = 12;
  
      private static final int LOG2GROUP_IDX = 1;
      private static final int LOG2DELTA_IDX = 2;
      private static final int NDELTA_IDX = 3;
      private static final int PAGESIZE_IDX = 4;
      private static final int SUBPAGE_IDX = 5;
      private static final int LOG2_DELTA_LOOKUP_IDX = 6;
  
      private static final byte no = 0, yes = 1;
  
      protected SizeClasses(int pageSize, int pageShifts, int chunkSize, int directMemoryCacheAlignment) {
         this.pageSize = pageSize;
         this.pageShifts = pageShifts;
         this.chunkSize = chunkSize;
         this.directMemoryCacheAlignment = directMemoryCacheAlignment;
 
         SizeClassValue value = CACHE.computeIfAbsent(
                 new SizeClassKey(pageSize, pageShifts, chunkSize, directMemoryCacheAlignment),
                 key -> new SizeClassValue(key, directMemoryCacheAlignment));
         nSizes = value.nSizes;
         nSubpages = value.nSubpages;
         nPSizes = value.nPSizes;
         smallMaxSizeIdx = value.smallMaxSizeIdx;
         lookupMaxSize = value.lookupMaxSize;
         pageIdx2sizeTab = value.pageIdx2sizeTab;
         sizeIdx2sizeTab = value.sizeIdx2sizeTab;
         size2idxTab = value.size2idxTab;
     }
 
     protected final int pageSize;
     protected final int pageShifts;
     protected final int chunkSize;
     protected final int directMemoryCacheAlignment;
 
     final int nSizes;
     final int nSubpages;
     final int nPSizes;
     final int smallMaxSizeIdx;
 
     private final int lookupMaxSize;
     private final int[] pageIdx2sizeTab;
 
     // lookup table for sizeIdx <= smallMaxSizeIdx
     private final int[] sizeIdx2sizeTab;
 
     // lookup table used for size <= lookupMaxclass
     // spacing is 1 << LOG2_QUANTUM, so the size of array is lookupMaxclass >> LOG2_QUANTUM
     private final int[] size2idxTab;
 
     @Override
     public int sizeIdx2size(int sizeIdx) {
         return sizeIdx2sizeTab[sizeIdx];
     }
 
     @Override
     public int sizeIdx2sizeCompute(int sizeIdx) {
         int group = sizeIdx >> LOG2_SIZE_CLASS_GROUP;
         int mod = sizeIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
 
         int groupSize = group == 0? 0 :
                 1 << LOG2_QUANTUM + LOG2_SIZE_CLASS_GROUP - 1 << group;
 
         int shift = group == 0? 1 : group;
         int lgDelta = shift + LOG2_QUANTUM - 1;
         int modSize = mod + 1 << lgDelta;
 
         return groupSize + modSize;
     }
 
     @Override
     public long pageIdx2size(int pageIdx) {
         return pageIdx2sizeTab[pageIdx];
     }
 
     @Override
     public long pageIdx2sizeCompute(int pageIdx) {
         int group = pageIdx >> LOG2_SIZE_CLASS_GROUP;
         int mod = pageIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
 
         long groupSize = group == 0? 0 :
                 1L << pageShifts + LOG2_SIZE_CLASS_GROUP - 1 << group;
 
         int shift = group == 0? 1 : group;
         int log2Delta = shift + pageShifts - 1;
         int modSize = mod + 1 << log2Delta;
 
         return groupSize + modSize;
     }
 
     @Override
     public int size2SizeIdx(int size) {
         if (size == 0) {
             return 0;
         }
         if (size > chunkSize) {
             return nSizes;
         }
 
         size = alignSizeIfNeeded(size, directMemoryCacheAlignment);
 
         if (size <= lookupMaxSize) {
             //size-1 / MIN_TINY
             return size2idxTab[size - 1 >> LOG2_QUANTUM];
         }
 
         int x = PoolThreadCache.log2((size << 1) - 1);
         int shift = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
                 ? 0 : x - (LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM);
 
         int group = shift << LOG2_SIZE_CLASS_GROUP;
 
         int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
                 ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
 
         int deltaInverseMask = -1 << log2Delta;
         int mod = (size - 1 & deltaInverseMask) >> log2Delta &
                   (1 << LOG2_SIZE_CLASS_GROUP) - 1;
 
         return group + mod;
     }
 
     @Override
     public int pages2pageIdx(int pages) {
         return pages2pageIdxCompute(pages, false);
     }
 
     @Override
     public int pages2pageIdxFloor(int pages) {
         return pages2pageIdxCompute(pages, true);
     }
 
     private int pages2pageIdxCompute(int pages, boolean floor) {
         int pageSize = pages << pageShifts;
         if (pageSize > chunkSize) {
             return nPSizes;
         }
 
         int x = PoolThreadCache.log2((pageSize << 1) - 1);
 
         int shift = x < LOG2_SIZE_CLASS_GROUP + pageShifts
                 ? 0 : x - (LOG2_SIZE_CLASS_GROUP + pageShifts);
 
         int group = shift << LOG2_SIZE_CLASS_GROUP;
 
         int log2Delta = x < LOG2_SIZE_CLASS_GROUP + pageShifts + 1?
                 pageShifts : x - LOG2_SIZE_CLASS_GROUP - 1;
 
         int deltaInverseMask = -1 << log2Delta;
         int mod = (pageSize - 1 & deltaInverseMask) >> log2Delta &
                   (1 << LOG2_SIZE_CLASS_GROUP) - 1;
 
         int pageIdx = group + mod;
 
         if (floor && pageIdx2sizeTab[pageIdx] > pages << pageShifts) {
             pageIdx--;
         }
 
         return pageIdx;
     }
 
     // Round size up to the nearest multiple of alignment.
     private static int alignSizeIfNeeded(int size, int alignment) {
         if (alignment <= 0) {
             return size;
         }
         int delta = size & alignment - 1;
         return delta == 0? size : size + alignment - delta;
     }
 
     @Override
     public int normalizeSize(int size) {
         if (size == 0) {
             return sizeIdx2sizeTab[0];
         }
         size = alignSizeIfNeeded(size, directMemoryCacheAlignment);
 
         if (size <= lookupMaxSize) {
             int ret = sizeIdx2sizeTab[size2idxTab[size - 1 >> LOG2_QUANTUM]];
             assert ret == normalizeSizeCompute(size);
             return ret;
         }
         return normalizeSizeCompute(size);
     }
 
     private static int normalizeSizeCompute(int size) {
         int x = PoolThreadCache.log2((size << 1) - 1);
         int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
                 ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
         int delta = 1 << log2Delta;
         int delta_mask = delta - 1;
         return size + delta_mask & ~delta_mask;
     }
 
     private static final class SizeClassKey {
         final int pageSize;
         final int pageShifts;
         final int chunkSize;
         final int directMemoryCacheAlignment;
 
         private SizeClassKey(int pageSize, int pageShifts, int chunkSize, int directMemoryCacheAlignment) {
             this.pageSize = pageSize;
             this.pageShifts = pageShifts;
             this.chunkSize = chunkSize;
             this.directMemoryCacheAlignment = directMemoryCacheAlignment;
         }
 
         @Override
         public boolean equals(Object o) {
             if (this == o) {
                 return true;
             }
             if (o == null || getClass() != o.getClass()) {
                 return false;
             }
 
             SizeClassKey that = (SizeClassKey) o;
 
             if (pageSize != that.pageSize) {
                 return false;
             }
             if (pageShifts != that.pageShifts) {
                 return false;
             }
             if (chunkSize != that.chunkSize) {
                 return false;
             }
             return directMemoryCacheAlignment == that.directMemoryCacheAlignment;
         }
 
         @Override
         public int hashCode() {
             int result = pageSize;
             result = 31 * result + pageShifts;
             result = 31 * result + chunkSize;
             result = 31 * result + directMemoryCacheAlignment;
             return result;
         }
     }
 
     private static final class SizeClassValue {
         final SizeClassKey key;
         final int nSizes;
         final int nSubpages;
         final int nPSizes;
         final int smallMaxSizeIdx;
         final int lookupMaxSize;
         final int[] pageIdx2sizeTab;
         final int[] sizeIdx2sizeTab;
         final int[] size2idxTab;
 
         SizeClassValue(SizeClassKey key, int directMemoryCacheAlignment) {
             this.key = key;
             int group = PoolThreadCache.log2(key.chunkSize) + 1 - LOG2_QUANTUM;
 
             //generate size classes
             //[index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup]
             short[][] sizeClasses = new short[group << LOG2_SIZE_CLASS_GROUP][7];
 
             int normalMaxSize = -1;
             int nSizes = 0;
             int size = 0;
 
             int log2Group = LOG2_QUANTUM;
             int log2Delta = LOG2_QUANTUM;
             int ndeltaLimit = 1 << LOG2_SIZE_CLASS_GROUP;
 
             //First small group, nDelta start at 0.
             //first size class is 1 << LOG2_QUANTUM
             for (int nDelta = 0; nDelta < ndeltaLimit; nDelta++, nSizes++) {
                 short[] sizeClass = newSizeClass(nSizes, log2Group, log2Delta, nDelta, key);
                 sizeClasses[nSizes] = sizeClass;
                 size = sizeOf(sizeClass, directMemoryCacheAlignment);
             }
 
             log2Group += LOG2_SIZE_CLASS_GROUP;
 
             //All remaining groups, nDelta start at 1.
             for (; size < key.chunkSize; log2Group++, log2Delta++) {
                 for (int nDelta = 1; nDelta <= ndeltaLimit && size < key.chunkSize; nDelta++, nSizes++) {
                     short[] sizeClass = newSizeClass(nSizes, log2Group, log2Delta, nDelta, key);
                     sizeClasses[nSizes] = sizeClass;
                     size = normalMaxSize = sizeOf(sizeClass, directMemoryCacheAlignment);
                 }
             }
 
             //chunkSize must be normalMaxSize
             assert key.chunkSize == normalMaxSize;
 
             int smallMaxSizeIdx = 0;
             int lookupMaxSize = 0;
             int nPSizes = 0;
             int nSubpages = 0;
             for (int idx = 0; idx < nSizes; idx++) {
                 short[] sz = sizeClasses[idx];
                 if (sz[PAGESIZE_IDX] == yes) {
                     nPSizes++;
                 }
                 if (sz[SUBPAGE_IDX] == yes) {
                     nSubpages++;
                     smallMaxSizeIdx = idx;
                 }
                 if (sz[LOG2_DELTA_LOOKUP_IDX] != no) {
                     lookupMaxSize = sizeOf(sz, directMemoryCacheAlignment);
                 }
             }
             this.smallMaxSizeIdx = smallMaxSizeIdx;
             this.lookupMaxSize = lookupMaxSize;
             this.nPSizes = nPSizes;
             this.nSubpages = nSubpages;
             this.nSizes = nSizes;
 
             //generate lookup table
             sizeIdx2sizeTab = newIdx2SizeTab(sizeClasses, nSizes, directMemoryCacheAlignment);
             pageIdx2sizeTab = newPageIdx2sizeTab(sizeClasses, nSizes, nPSizes, directMemoryCacheAlignment);
             size2idxTab = newSize2idxTab(lookupMaxSize, sizeClasses);
         }
 
         //calculate size class
         private static short[] newSizeClass(int index, int log2Group, int log2Delta, int nDelta, SizeClassKey key) {
             short isMultiPageSize;
             if (log2Delta >= key.pageShifts) {
                 isMultiPageSize = yes;
             } else {
                 int pageSize = 1 << key.pageShifts;
                 int size = (1 << log2Group) + (1 << log2Delta) * nDelta;
 
                 isMultiPageSize = size == size / pageSize * pageSize? yes : no;
             }
 
             int log2Ndelta = nDelta == 0? 0 : PoolThreadCache.log2(nDelta);
 
             byte remove = 1 << log2Ndelta < nDelta? yes : no;
 
             int log2Size = log2Delta + log2Ndelta == log2Group? log2Group + 1 : log2Group;
             if (log2Size == log2Group) {
                 remove = yes;
             }
 
             short isSubpage = log2Size < key.pageShifts + LOG2_SIZE_CLASS_GROUP? yes : no;
 
             int log2DeltaLookup = log2Size < LOG2_MAX_LOOKUP_SIZE ||
                     log2Size == LOG2_MAX_LOOKUP_SIZE && remove == no
                     ? log2Delta : no;
 
             return new short[] {
                     (short) index, (short) log2Group, (short) log2Delta,
                     (short) nDelta, isMultiPageSize, isSubpage, (short) log2DeltaLookup
             };
         }
 
         private static int[] newIdx2SizeTab(short[][] sizeClasses, int nSizes, int directMemoryCacheAlignment) {
             int[] sizeIdx2sizeTab = new int[nSizes];
 
             for (int i = 0; i < nSizes; i++) {
                 short[] sizeClass = sizeClasses[i];
                 sizeIdx2sizeTab[i] = sizeOf(sizeClass, directMemoryCacheAlignment);
             }
             return sizeIdx2sizeTab;
         }
 
         private static int calculateSize(int log2Group, int nDelta, int log2Delta) {
             return (1 << log2Group) + (nDelta << log2Delta);
         }
 
         private static int sizeOf(short[] sizeClass, int directMemoryCacheAlignment) {
             int log2Group = sizeClass[LOG2GROUP_IDX];
             int log2Delta = sizeClass[LOG2DELTA_IDX];
             int nDelta = sizeClass[NDELTA_IDX];
 
             int size = calculateSize(log2Group, nDelta, log2Delta);
 
             return alignSizeIfNeeded(size, directMemoryCacheAlignment);
         }
 
         private static int[] newPageIdx2sizeTab(short[][] sizeClasses, int nSizes, int nPSizes,
                                                 int directMemoryCacheAlignment) {
             int[] pageIdx2sizeTab = new int[nPSizes];
             int pageIdx = 0;
             for (int i = 0; i < nSizes; i++) {
                 short[] sizeClass = sizeClasses[i];
                 if (sizeClass[PAGESIZE_IDX] == yes) {
                     pageIdx2sizeTab[pageIdx++] = sizeOf(sizeClass, directMemoryCacheAlignment);
                 }
             }
             return pageIdx2sizeTab;
         }
 
         private static int[] newSize2idxTab(int lookupMaxSize, short[][] sizeClasses) {
             int[] size2idxTab = new int[lookupMaxSize >> LOG2_QUANTUM];
             int idx = 0;
             int size = 0;
 
             for (int i = 0; size <= lookupMaxSize; i++) {
                 int log2Delta = sizeClasses[i][LOG2DELTA_IDX];
                 int times = 1 << log2Delta - LOG2_QUANTUM;
 
                 while (size <= lookupMaxSize && times-- > 0) {
                     size2idxTab[idx++] = i;
                     size = idx + 1 << LOG2_QUANTUM;
                 }
             }
             return size2idxTab;
         }
     }
 }