java/src/main/com/google/appengine/api/labs/datastore/overlay/IdAllocationPolicy.java

   1 // Copyright 2013 Google Inc. All Rights Reserved.
   2 package com.google.appengine.api.labs.datastore.overlay;
   3
   4 /**
   5  * The set of id allocation policies available.
   6  * The map of (counter value, id policy) to valid ids is one-to-one.
   7  */
   8 enum IdAllocationPolicy implements IdAllocationPolicyInterface {
   9
  10   /** The default sequential allocation policy. */
  11   SEQUENTIAL(newSequentialPolicy(0)),
  12   /** The default scattered allocation policy. */
  13   SCATTERED(newScatteredPolicy(0)),
  14   /** The sequential allocation policy for an overlay Datastore. */
  15   OVERLAY_SEQUENTIAL(newSequentialPolicy(1)),
  16   /** The scattered allocation policy for an overlay Datastore. */
  17   OVERLAY_SCATTERED(newScatteredPolicy(1));
  18
  19   /**
  20    * Maps an ID assigned from a default policy into the corresponding overlay ID space.
  21    *
  22    * @param id an ID from the {@code DEFAULT_SEQUENTIAL} or {@code DEFAULT_SCATTERED} ranges
  23    * @return an ID representing the same counter value in the {@code OVERLAY_SEQUENTIAL} or
  24    *         {@code OVERLAY_SCATTERED} range.
  25    * @throws IllegalArgumentException if the ID is not from the {@code DEFAULT_SEQUENTIAL} or
  26    *         {@code DEFAULT_SCATTERED} ranges
  27    */
  28   public static long overlayIdFromDefaultId(long id) {
  29     if (SEQUENTIAL.containsId(id)) {
  30       return OVERLAY_SEQUENTIAL.counterToId(SEQUENTIAL.idToCounter(id));
  31     } else if (SCATTERED.containsId(id)) {
  32       return OVERLAY_SCATTERED.counterToId(SCATTERED.idToCounter(id));
  33     } else {
  34       throw new IllegalArgumentException(
  35           "ID does not conform to a known default allocation policy: " + Long.toHexString(id));
  36     }
  37   }
  38
  39   private final IdAllocationPolicyInterface policy;
  40
  41   private IdAllocationPolicy(IdAllocationPolicyInterface policy) {
  42     this.policy = policy;
  43   }
  44
  45   @Override
  46   public boolean containsId(long id) {
  47     return policy.containsId(id);
  48   }
  49
  50   @Override
  51   public long getMaximumCounterValue() {
  52     return policy.getMaximumCounterValue();
  53   }
  54
  55   @Override
  56   public long counterToId(long counter) {
  57     return policy.counterToId(counter);
  58   }
  59
  60   @Override
  61   public long idToCounter(long id) {
  62     return policy.idToCounter(id);
  63   }
  64
  65   private static IdAllocationPolicyInterface newSequentialPolicy(int depth) {
  66     final long minId = minSequentialId(depth);
  67     final long maxCounterValue = (1L << maxSequentialBit(depth)) - 1;
  68     final long maxId = minId + maxCounterValue;
  69
  70     return new IdAllocationPolicyInterface() {
  71       @Override
  72       public boolean containsId(long id) {
  73         return (id >= minId && id <= maxId);
  74       }
  75
  76       @Override
  77       public long getMaximumCounterValue() {
  78         return maxCounterValue;
  79       }
  80
  81       @Override
  82       public long counterToId(long counter) {
  83         checkCounterBounds(this, counter);
  84         return minId + counter;
  85       }
  86
  87       @Override
  88       public long idToCounter(long id) {
  89         checkIdBounds(this, id);
  90         return id - minId;
  91       }
  92     };
  93
  94   }
  95
  96   private static IdAllocationPolicyInterface newScatteredPolicy(int depth) {
  97     final long maxBit = maxScatteredBit(depth);
  98     final long maxCounterValue = (1L << maxBit) - 1;
  99     final long minId = minScatteredId(depth);
 100     final long maxId = minId + maxCounterValue;
 101     final long scatterShift = 64 - maxBit;
 102     return new IdAllocationPolicyInterface() {
 103
 104       @Override
 105       public boolean containsId(long id) {
 106         return (id >= minId && id <= maxId);
 107       }
 108
 109       @Override
 110       public long getMaximumCounterValue() {
 111         return maxCounterValue;
 112       }
 113
 114       @Override
 115       public long counterToId(long counter) {
 116         checkCounterBounds(this, counter);
 117         return minId + Long.reverse(counter << scatterShift);
 118       }
 119
 120       @Override
 121       public long idToCounter(long id) {
 122         checkIdBounds(this, id);
 123         return Long.reverse(id) >>> scatterShift;
 124       }
 125     };
 126   }
 127
 128   private static int maxSequentialBit(int depth) {
 129     return 52 - (3 * depth);
 130   }
 131
 132   private static long minSequentialId(int depth) {
 133     long prefix = 0;
 134     for (int i = 0; i < depth; i++) {
 135       prefix = (prefix << 3) + 6;
 136     }
 137     return prefix << (maxSequentialBit(depth) + 1);
 138   }
 139
 140   private static int maxScatteredBit(int depth) {
 141     return maxSequentialBit(depth) - 1;
 142   }
 143
 144   private static long minScatteredId(int depth) {
 145     return minSequentialId(depth) + (1L << maxSequentialBit(depth));
 146   }
 147
 148   private static void checkCounterBounds(IdAllocationPolicyInterface policy, long counter) {
 149     if (counter < 1) {
 150       throw new IllegalArgumentException(
 151           "Counter " + Long.toHexString(counter) + " is non-positive.");
 152     }
 153     if (counter > policy.getMaximumCounterValue()) {
 154       throw new IllegalArgumentException("Counter " + Long.toHexString(counter)
 155           + " exceeds maximum counter value " + Long.toHexString(policy.getMaximumCounterValue())
 156           + ".");
 157     }
 158   }
 159
 160   private static void checkIdBounds(IdAllocationPolicyInterface policy, long id) {
 161     if (!policy.containsId(id)) {
 162       throw new IllegalArgumentException("ID does not conform to allocation policy "
 163           + policy.getClass().getName() + ": " + Long.toHexString(id));
 164     }
 165   }
 166 }