lucene中的PackedInts源码解读(3)-PACKED格式

继续回到最开始的获得mutable的代码那里去

public static Mutable getMutable(int valueCount,   int bitsPerValue, PackedInts.Format format) {
    assert valueCount >= 0;
    switch (format) {
      case PACKED_SINGLE_BLOCK:
        return Packed64SingleBlock.create(valueCount, bitsPerValue);//这个已经说完了，
      case PACKED://这篇文章说明这个
        switch (bitsPerValue) {
          case 8:
            return new Direct8(valueCount);
          case 16:
            return new Direct16(valueCount);
          case 32:
            return new Direct32(valueCount);
          case 64:
            return new Direct64(valueCount);
          case 24:
            if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) {
              return new Packed8ThreeBlocks(valueCount);
            }
            break;
          case 48:
            if (valueCount <= Packed16ThreeBlocks.MAX_SIZE) {
              return new Packed16ThreeBlocks(valueCount);
            }
            break;
        }
        return new Packed64(valueCount, bitsPerValue);//如果没有上面的bitPerValue的，则使用这个。
      default:
        throw new AssertionError();
    }
  }

 之前说完了Packed64SingleBlock的原理，他多少是浪费空间的，虽然很小。这次要说的PACKED格式的Mutable是完全不浪费空间的，其中Direct8、Direct16、Direct32、Direct64都是一个block保存一个数字，比如Direct8，他里面就是使用了byte[]，一个block就是一个byte，所以这样不会造成一点的浪费。同理，Direct16是使用了short[]，Direct32是使用了int[]，Direct64是使用了long[]。他们要比原来的Packed64SingleBlock的思路更简单，而且在保存和查找的时候代码也更简单。我们那Direct32的代码做例子吧。看看他的保存（即set）方法和读取（即get）方法。

 

 

public int set(int index, long[] arr, int off, int len) {
    assert len > 0 : "len must be > 0 (got " + len + ")";
    assert index >= 0 && index < valueCount;
    assert off + len <= arr.length;

    final int sets = Math.min(valueCount - index, len);
    for (int i = index, o = off, end = index + sets; i < end; ++i, ++o) {
      values[i] = (int) arr[o];//直接用原来的值即可，不过要变为int。
    }
    return sets;
}
public int get(int index, long[] arr, int off, int len) {
    assert len > 0 : "len must be > 0 (got " + len + ")";
    assert index >= 0 && index < valueCount;
    assert off + len <= arr.length;

    final int gets = Math.min(valueCount - index, len);
    for (int i = index, o = off, end = index + gets; i < end; ++i, ++o) {
      arr[o] = values[i] & 0xFFFFFFFFL;//直接读取，不过要变为一个int
    }
    return gets;
}

 

 

这样就很简单的看完了Directx系列，再看一下Packed8ThreeBlocks和Packed16ThreeBlocks，这俩的思路也很简单，Packed8ThreeBlocks处理bitPerValue是24的情况，他内部使用了一个byte[]，所以使用3个byte来保存一个数字，而他创建的byte[]的最大程度是int.max_value，所以最多存储的数字的数量是Integer.max_value/3个，所以就有了上面的if (valueCount <= Packed8ThreeBlocks.MAX_SIZE) 的判断，Packed16ThreeBlocks的思路类似，这里直接略过。

 

上面的Directx系列和Packed8ThreeBlocks、Packed16ThreeBlocks系列都是存储的8的整数倍大小的bitPerValue，如果不是8的整数倍呢，就要使用上面的Packed64了。它使用long[]来保存数字，但是他不会浪费空间，（类似Packed64SingleBlock，但是他是连续的，即一个数字可能会保存在两个block，即两个long数字里面）.【注：Format只要是packed类型的，则一定不会浪费空间】

 

public Packed64(int valueCount, int bitsPerValue) { 
    super(valueCount, bitsPerValue);//他的父类是MutableImpl，里面仅仅保存了数字的数量和每个数字的bitPerValue。 
    final PackedInts.Format format = PackedInts.Format.PACKED; 
    final int longCount = format.longCount(PackedInts.VERSION_CURRENT, valueCount, bitsPerValue);//计算使用的long的数量  
    this.blocks = new long[longCount];//最终使用的数字 
    maskRight = ~0L << (BLOCK_SIZE-bitsPerValue) >>> (BLOCK_SIZE-bitsPerValue);//先左移，把高位的去掉，再无符号右移，把高位全部用0填充，这样就把超过bitPerValue的位数上的变为0.其他位上全是1. 
    bpvMinusBlockSize = bitsPerValue - BLOCK_SIZE;//相当于是64-bitPerValue的负数。 
}

 看看他的set方法

public int set(int index, long[] arr, int off, int len) {
    assert len > 0 : "len must be > 0 (got " + len + ")";
    assert index >= 0 && index < valueCount;
    len = Math.min(len, valueCount - index);
    assert off + len <= arr.length;

    final int originalIndex = index;
    final PackedInts.Encoder encoder = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);

    // go to the next block where the value does not span across two blocks  这一块的逻辑和前面的Packed64SingleBlcok中的是一样的，
    final int offsetInBlocks = index % encoder.longValueCount();//是不是bulk set的一个块的开始，因为下面的bulk set要在一个块的开始才可以。encoder.longValueCount表示一个块中long的数量
    if (offsetInBlocks != 0) {//如果不满足一个快的开始，就单独的调用set。
      for (int i = offsetInBlocks; i < encoder.longValueCount() && len > 0; ++i) {
        set(index++, arr[off++]);
        --len;
      }
      if (len == 0) {
        return index - originalIndex;
      }
    }

    // bulk set  此时存放一定是一个块的开始，块的开始一定是从一个long开始
    assert index % encoder.longValueCount() == 0;
    int blockIndex = (int) (((long) index * bitsPerValue) >>> BLOCK_BITS);//从第几个long开始放
    assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
    final int iterations = len / encoder.longValueCount();//放多少次，因为对于bulk set来说，一放就是一个块，块的大小（能存放的int的数量）是encoder.longValueCount。
    encoder.encode(arr, off, blocks, blockIndex, iterations);//单独拿出来了下面有
    final int setValues = iterations * encoder.longValueCount();
    index += setValues;
    len -= setValues;
    assert len >= 0;

    if (index > originalIndex) {
      // stay at the block boundary
      return index - originalIndex;
    } else {//这种情况是可能发生的，比如offsetInBlock正好是0，但是要保存的数字的数量不够encoder.longValueCount，就会发生这种情况。此时就要调用父类的方法，挨个调用set方法
      // no progress so far => already at a block boundary but no full block to get
      assert index == originalIndex;
      return super.set(index, arr, off, len);
    }
}

 里面有单独的set方法，即一个一个设置的方法，如下：

public void set(final int index, final long value) {
    // The abstract index in a contiguous bit stream
    final long majorBitPos = (long)index * bitsPerValue;
    // The index in the backing long-array
    final int elementPos = (int)(majorBitPos >>> BLOCK_BITS); // BLOCK_SIZE  除以64求商，也就是计算是第几个long数字
    // The number of value-bits in the second long
    final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;//结束为止，计算方式为：求余数（在某个long中的开始位置），然后加上长度（bitPerValue）再减去block_size。如果小于0，说明在一个long里面。

    if (endBits <= 0) {// Single block  如果没有跨long，则-endBits就是这个数字结束后还剩多少位， 先计算&，表示把这个数字要在的多个位置全部变为0（也就是清空），然后再|，表示将这个字段
        blocks[elementPos] = blocks[elementPos] &  ~(maskRight << -endBits) | (value << -endBits);//maskRight<<   从这里看出，是从高位到低位存的。
        return;
    }
    
    // Two blocks    此时，endBits就是在第二个long中的结束位置了。~(maskRight >>> endBits)表示将第一个long上的最后几位清空，然后|(value >>> endBits)，表示保存数据
    blocks[elementPos] = blocks[elementPos] &  ~(maskRight >>> endBits) | (value >>> endBits);
    blocks[elementPos+1] = blocks[elementPos+1] &  (~0L >>> endBits) | (value << (BLOCK_SIZE - endBits));//保存第二部分。
}

 从上面可以看出来，单独的set方法是由高位到低位的，这一点和Packed64SingleBlock是不同的，后者是从低位到高位。里面的encoder还没有看，使用的是org.apache.lucene.util.packed.BulkOperation.packedBulkOps这个数组里面的对象，根据bitPerValue来获得的。数组里面的都是继承自BulkOperationPacked，只是传入的bitPerValue不一样。我们看下这个类的encode方法（encode方法就是一下子操作一个块，这里的iteration是经过计算后传入的，要么一个块全部填完，要么一个都不填）

public void encode(long[] values, int valuesOffset, long[] blocks, int blocksOffset, int iterations) {
	long nextBlock = 0;
	int bitsLeft = 64;
	for (int i = 0; i < longValueCount * iterations; ++i) {//longValueCount即一个块能存放数字的数量，
		bitsLeft -= bitsPerValue;
		if (bitsLeft > 0) {//当前的long的位数有剩余
			nextBlock |= values[valuesOffset++] << bitsLeft;//由高位到低位
		} else if (bitsLeft == 0) {//当前的long全部使用完了，则不需要位移动了
			nextBlock |= values[valuesOffset++];
			blocks[blocksOffset++] = nextBlock;
			nextBlock = 0;
			bitsLeft = 64;
		} else { // bitsLeft < 0
			nextBlock |= values[valuesOffset] >>> -bitsLeft;//保存这个数字的高位（bitPerValue-bitsLeft位）
			blocks[blocksOffset++] = nextBlock;
			nextBlock = (values[valuesOffset++] & ((1L << -bitsLeft) - 1)) << (64 + bitsLeft);//将当前数字的后bitsLeft位保存起来。
			bitsLeft += 64;
		}
	}
}

上面中和单独的set方法也是一样的，都是从高位到低位。

 

 

看完了保存的方法，再看一下get方法，先看packed64的批量的get方法：

public int get(int index, long[] arr, int off, int len) {
    assert len > 0 : "len must be > 0 (got " + len + ")";
    assert index >= 0 && index < valueCount;
    len = Math.min(len, valueCount - index);
    assert off + len <= arr.length;

    final int originalIndex = index;
    final PackedInts.Decoder decoder = BulkOperation.of(PackedInts.Format.PACKED, bitsPerValue);//找到decoder

    // go to the next block where the value does not span across two blocks
    final int offsetInBlocks = index % decoder.longValueCount();//和encoder的逻辑一样，都是为了凑够一个块的数量。longValueCount表示一个块的数字的数量
    if (offsetInBlocks != 0) {//如果不是合适的数字（即不是一个bulk set的块的开始），则调用单独的get方法
      for (int i = offsetInBlocks; i < decoder.longValueCount() && len > 0; ++i) {
        arr[off++] = get(index++);//单个的get方法
        --len;
      }
      if (len == 0) {
        return index - originalIndex;
      }
    }

    // bulk get 前提是一个新的bulk set的块，也一定是一个新的long
    assert index % decoder.longValueCount() == 0;
    int blockIndex = (int) (((long) index * bitsPerValue) >>> BLOCK_BITS);//从第几个long开始
    assert (((long)index * bitsPerValue) & MOD_MASK) == 0;
    final int iterations = len / decoder.longValueCount();//需要多少个块（说的是bulk set的块）
    decoder.decode(blocks, blockIndex, arr, off, iterations);//解码指定的块，代码在下面。
    final int gotValues = iterations * decoder.longValueCount();
    index += gotValues;
    len -= gotValues;
    assert len >= 0;

    if (index > originalIndex) {
      // stay at the block boundary
      return index - originalIndex;
    } else {
      // no progress so far => already at a block boundary but no full block to get
      assert index == originalIndex;
      return super.get(index, arr, off, len);
    }
}

  单个的get方法如下：

public long get(final int index) {
    // The abstract index in a bit stream
    final long majorBitPos = (long)index * bitsPerValue;
    // The index in the backing long-array 	
    final int elementPos = (int)(majorBitPos >>> BLOCK_BITS);//开始位置在哪个long上
    // The number of value-bits in the second long
    final long endBits = (majorBitPos & MOD_MASK) + bpvMinusBlockSize;//(majorBitPos & MOD_MASK)表示在指定的long上的开始位置，加上bitPerValue，减去block_size。

    if (endBits <= 0) {// Single block 此时 -endBits表示离这个logn的最后还剩几位，右移blocks[elementPos]的目的是要和maskRight做&，和maskRigh做%的目的是将其变为一个
      return (blocks[elementPos] >>> -endBits) & maskRight;
    }
    // Two blocks
    return ((blocks[elementPos] << endBits) /*第一个long中的内容左移指定的位数，因为他后面的几位已经在第二个long中了*/  | (blocks[elementPos+1] >>> (BLOCK_SIZE - endBits)))  & maskRight;
}

最后看下decoder类，因为对不不同的bitPerValue，所以有 很多个类（和上面的encoder一样，都是org.apache.lucene.util.packed.BulkOperation.packedBulkOps这个数组）,但是我不明白的是他们竟然有很多都覆写了org.apache.lucene.util.packed.BulkOperationPacked.decode(long[], int, long[], int, int)方法，我个人觉得直接使用org.apache.lucene.util.packed.BulkOperationPacked.decode(long[], int, long[], int, int)就可以啊，没有必要再覆写，尤其是在我看到了BulkOperationPacked1和BulkOperationPacked2的方法后，我更是这么认为，因为他们覆写后的方法和没有覆写是一样的，在我看了BulkOperationPacked3之后，  我想到了一小点就是效率会高一点，如果网友有更好的理解，请联系我（qq:1308567317），这里我就只看org.apache.lucene.util.packed.BulkOperationPacked.decode(long[], int, long[], int, int)方法了

public void decode(long[] blocks, int blocksOffset, long[] values, int valuesOffset, int iterations) {
	int bitsLeft = 64;
	for (int i = 0; i < longValueCount * iterations; ++i) {
		bitsLeft -= bitsPerValue;
		if (bitsLeft < 0) {
			values[valuesOffset++] = ((blocks[blocksOffset++]
					& ((1L << (bitsPerValue + bitsLeft)) - 1)) << -bitsLeft)
					| (blocks[blocksOffset] >>> (64 + bitsLeft));
			bitsLeft += 64;
		} else {
			values[valuesOffset++] = (blocks[blocksOffset] >>> bitsLeft) & mask;
		}
	}
}

 上面的方法很简单就能看懂了。

 

好了，很简单就看懂了所有的PackedInts的源码。如果有人觉得我写的有问题，可以联系我（qq:1308567317）