当前位置：网站首页>Guava ImmutableSet. Builder source code analysis, shift original code, complement code, reverse code review

Guava ImmutableSet. Builder source code analysis, shift original code, complement code, reverse code review

2022-07-04 11:43:00 【Brother Wang_】

The inheritance structure of the builder pattern

The builder mode is very cool for construction , I also like this way of writing , Look at the inheritance system handled here

Use ImmutableSet As an example

Each one has a static Member method of , Better unify the construction calls of all sets
Use ImmutableSet As an example

       
        public static <E> Builder<E> builder() {
        
    return new Builder<E>();
        
}
       
       
        1.
        2.
        3.

ImmutableSet Inside static Of Builder Class inheritance , Here inheritance can be constructed to meet the current ImmutableSet Structure , To construct build(). The method is embodied here .
ImmutableCollection.ArrayBasedBuilder, You can know from the name that this contains container related object[] coents= new object[defaultsize], The data in our construction set is placed here for processing . According to the single principle of classes , A class does only one thing , Well done , Well packaged , Be able to reuse code to the greatest extent .
Basically, the code is implemented by inheriting the methods of the parent class , What expansion , Add elements and so on , The template method is still used here , Let the parent class call the implementation of the child class .addAll(…)
I like this chain style of writing very much , It feels very good .

       
        /**
        
   * A builder for creating {@code ImmutableSet} instances
        
   *
        
   *   static final ImmutableSet<Color> GOOGLE_COLORS =
        
   *       ImmutableSet.<Color>builder()
        
   *           .addAll(WEBSAFE_COLORS)
        
   *           .add(new Color(0, 191, 255))
        
   *           .build();}</pre>
        
   */
        
  public static class Builder<E> 
        
    extends 
        
    ImmutableCollection.ArrayBasedBuilder<E> {
        
    /**
        
     * Creates a new builder. 
        
     *The returned builder is equivalent to the builder
        
     * generated by {@link ImmutableSet#builder}.
        
     * The following are methods that call the parent class 
        
     */
        
    public Builder() {
        
      this(DEFAULT_INITIAL_CAPACITY);//4
        
    }
        
    Builder(int capacity) {
        
      super(capacity);
        
    }
        
    @Override
        
    public Builder<E> add(E element) {
        
      super.add(element);
        
      return this;
        
    }
        
    @Override
        
    public Builder<E> add(E... elements) {
        
      super.add(elements);
        
      return this;
        
    }
        
    @Override
        
    public Builder<E> addAll(Iterable< ? extends E> elements) {
        
      super.addAll(elements);
        
      return this;
        
    }
        
    @Override
        
    public Builder<E> addAll(Iterator< ? extends E> elements) {
        
      super.addAll(elements);
        
      return this;
        
    }
        
    @Override
        
    Builder<E> combine(ArrayBasedBuilder<E> builder) {
        
      super.combine(builder);
        
      return this;
        
    }
        
    /**
        
     * Returns a newly-created  based on the contents of
        
     * the {@code Builder}.
        
     * construct Call the current class ImuutableSet Construction method of , Here we need to deal with the problem of weight removal 
        
     *  therefore size It's no use changing your feelings 
        
     */
        
    @Override
        
    public ImmutableSet<E> build() {
        
      ImmutableSet<E> result = construct(size, contents);
        
      // construct has the side effect of deduping contents, so we update size
        
      // accordingly.
        
      size = result.size();
        
      return result;
        
    }
        
  }
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.
        39.
        40.
        41.
        42.
        43.
        44.
        45.
        46.
        47.
        48.
        49.
        50.
        51.
        52.
        53.
        54.
        55.
        56.
        57.
        58.
        59.
        60.
        61.
        62.
        63.
        64.
        65.

ImmutableCollection.ArrayBasedBuilder This is a real implementation class
Inherited ImmutableCollection.Builder, There are many abstract methods here , And the method of capacity expansion is unified , I'll explain it slowly later
Object[] contents This is the point , Containers , A container for a set of data , Add data information to this container , Or merge the data information of the set , They all practice here , Information about different specific classes , How to construct immutable sets is their own business , We just need to put the current object Just pass the array , Task to complete .
The expansion check here haha , Prevent the array from exceeding the size , I feel pretty good ！

       
        abstract static class ArrayBasedBuilder<E>
        
     extends ImmutableCollection.Builder<E> {
        
    Object[] contents;// Container oh ！
        
    int size;// The size used by the current container ！
        
    ArrayBasedBuilder(int initialCapacity) {
        
      //CollectPreconditions  The detection in is not negative 
        
      checkNonnegative(initialCapacity, "initialCapacity");
        
      this.contents = new Object[initialCapacity];
        
      this.size = 0;
        
    }
        

        
    /**
        
     * Expand the absolute capacity of the builder 
        
     * so it can accept at least
        
     * the specified number of elements without being resized.
        
     *  Every time you add an element, check the size of the current container , Then we are expanding 
        
     * expandedCapacity It is the method of parent class expansion , I'll say later 
        
     * Arrays.copyOf Copy a data , Expand its length 
        
     */
        
    private void ensureCapacity(int minCapacity) {
        
      if (contents.length < minCapacity) {
        
        this.contents =
        
            Arrays.copyOf(
        
                this.contents, 
        
                expandedCapacity(contents.length, minCapacity)
        
                );
        
      }
        
    }
        
    /**
        
    * Here is just adding elements , For the bottom layer Set Data structure , It's up to them to do it 
        
    */
        
    @Override
        
    public ArrayBasedBuilder<E> add(E element) {
        
      checkNotNull(element);// Judge not empty 
        
      ensureCapacity(size + 1);// Capacity expansion 
        
      contents[size++] = element;// insert data 
        
      return this;
        
    }
        
   /*
        
    *static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 
        
    * Copies an array from the specified source array , Copy from the specified location , To the specified position of the target array . 
        
    */
        
    @Override
        
    public Builder<E> add(E... elements) {
        
      checkElementsNotNull(elements);
        
      ensureCapacity(size + elements.length);
        
      System.arraycopy(elements, 0, contents, size, elements.length);
        
      size += elements.length;
        
      return this;
        
    }
        
     /*
        
     *Iterable Proxies are basically Collection
        
     */
        
    @Override
        
    public Builder<E> addAll(Iterable<? extends E> elements) {
        
      if (elements instanceof Collection) {
        
        Collection<?> collection = (Collection<?>) elements;
        
        ensureCapacity(size + collection.size());
        
      }
        
      super.addAll(elements);
        
      return this;
        
    }
        
    // Two builder Merge 
        
    @CanIgnoreReturnValue
        
    ArrayBasedBuilder<E> combine(ArrayBasedBuilder<E> builder) {
        
      checkNotNull(builder);
        
      ensureCapacity(size + builder.size);
        
      System.arraycopy(builder.contents, 0, this.contents, size, builder.size);
        
      size += builder.size;
        
      return this;
        
    }
        
  }
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.
        39.
        40.
        41.
        42.
        43.
        44.
        45.
        46.
        47.
        48.
        49.
        50.
        51.
        52.
        53.
        54.
        55.
        56.
        57.
        58.
        59.
        60.
        61.
        62.
        63.
        64.
        65.
        66.
        67.
        68.
        69.
        70.
        71.
        72.
        73.

ImmutableCollection.Builder This is an abstract class , It is the parent of all builder patterns , Here, capacity expansion detection is realized , Add collection , Add iterations and so on , Adding a single element is an abstraction , Use template method to process , The parent class calls the methods of the child class , Here, the processing of capacity expansion is realized , and JDK in anrrylist The treatment is a little similar .
The main implementation steps of capacity expansion
Expand the size of the current space 3 times +1
Compare with the current minimum space size
If you expand 3 Times smaller , Then use the current minimum incoming space , That is, the highest bit of the current array length that needs to be accommodated is filled with 1 After the value of

       
        /**
        
   * Abstract base class for builders of 
        
   * ImmutableCollectiontypes.
        
   */
        
  public abstract static class Builder<E> {
        
    static final int DEFAULT_INITIAL_CAPACITY = 4;
        
    // Default array size 
        
    // The following are the specific methods of capacity expansion , Very subtle , I'll analyze it later 
        
    //Integer.highestOneBit 
        
    static int expandedCapacity(int oldCapacity, int minCapacity) {
        
      if (minCapacity < 0) {
        
        throw new AssertionError("cannot store more than MAX_VALUE elements");
        
      }
        
      // careful of overflow!
        
      // Here is to expand the capacity 
        
      int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
        
      if (newCapacity < minCapacity) {
        
        //highestOneBit Take the highest value ,-1 That is, it is equivalent to moving one bit to the right 
        
        // such as  1101->1000(highestOneBit)->0111(-1)->1111(<<1)
        
        // The benefits of this treatment are minCapacity It is greater than 0 Of , In the current bit, it will not exceed 31 position 
        
        // In this way, all the current bits can be filled with 1, This is the maximum value .
        
        newCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
        
      }
        
      // The handling here feels unnecessary , It won't be overstepped 
        
      if (newCapacity < 0) {
        
        newCapacity = Integer.MAX_VALUE;
        
        // guaranteed to be >= newCapacity
        
      }
        
      return newCapacity;
        
    }
        

        
    Builder() {}
        
    // Template method , Leave it to subclasses to implement 
        
    public abstract Builder<E> add(E element);
        
    public Builder<E> add(E... elements) {
        
      for (E element : elements) {
        
        add(element);
        
      }
        
      return this;
        
    }
        
    public Builder<E> addAll(Iterable<? extends E> elements) {
        
      for (E element : elements) {
        
        add(element);
        
      }
        
      return this;
        
    }
        

        
    @CanIgnoreReturnValue
        
    public Builder<E> addAll(Iterator<? extends E> elements) {
        
      while (elements.hasNext()) {
        
        add(elements.next());
        
      }
        
      return this;
        
    }
        

        
    /**
        
     * The structure here is the last and most important department , Finally being ImmutableSet structure , You can go back and see the logic  ImmutableSet<E> result = construct(size, contents);
        
     * Returns a newly-created 
        
     *{@code ImmutableCollection} of the appropriate
        
     * type, containing the elements provided to this builder.
        
     *
        
     * <p>Note that each builder class covariantly returns the appropriate type
        
     * of {@code ImmutableCollection} from this method.
        
     */
        
    public abstract ImmutableCollection<E> build();
        
  }
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.
        16.
        17.
        18.
        19.
        20.
        21.
        22.
        23.
        24.
        25.
        26.
        27.
        28.
        29.
        30.
        31.
        32.
        33.
        34.
        35.
        36.
        37.
        38.
        39.
        40.
        41.
        42.
        43.
        44.
        45.
        46.
        47.
        48.
        49.
        50.
        51.
        52.
        53.
        54.
        55.
        56.
        57.
        58.
        59.
        60.
        61.
        62.
        63.
        64.
        65.
        66.

Integer.highestOneBit

Before we know this , I also want to know some simple knowledge about the principle of computer composition first, haha , Don't often use things that are easy to forget details , Take a look back. .

The original code complements the counter code

The positive original code is the same as the negative complement , Complement code （ Negative binary ）= Inverse code +1

Original code

The first digit on the left indicates the symbol （0 Being positive ,1 Negative ）, The rest of the bits represent values .
The conversion method of true value into original code ：
First of all ： Taking the absolute value of the true value 2 Hexadecimal said
second ： Add the symbol first on the left .
for example :
Consider the storage of a byte ,-127, The absolute value is 127 Of 2 The base number is represented by 0111 1111
Add symbols （1） by 1111 1111.
True value =0 When ,[+0] It could be expressed as 0000 0000, [-0] It could be expressed as 1000 0000.

Inverse code

The representation of the inverse code is :

1. If it's a positive number , The reverse code is the same as the original code .

2. If it's a negative number , Inverse code is the sign bit unchanged , The remaining bits of the original code are reversed .

3. Example ：

[+127] primary =0111 1111,

[+127] back =0111 1111,

[-127] primary =1111 1111,

[-127] back =1000 0000.

Complement representation ：

If it's a positive number , The complement is the same as the original .
If it's a negative number , On the basis of irony +1.
Complement code （ Negative binary ）= Inverse code +1
Example ：
[+127] primary =0111 1111,
[+127] back =0111 1111,
[+127] repair =0111 1111
[-127] primary =1111 1111,
[-127] back =1000 0000,
[-127] repair =1000 0001

Unsigned displacement (>>>、<<<) Signed displacement (>>、<<)

Shift summary

When the sign is shifted left, the low complement 0
When the sign moves to the right , If the symbol is regular high complement 0, On the contrary 1;

The unsigned shift right operator complements both positive and negative in the high order 0.
Example ： 15

15 Binary system
00000000 00000000 00000000 00001111
-15 Binary system
11111111 11111111 11111111 11110001
The calculation process ： Complement code （ Negative binary ）= Inverse code +1
Original code ：10000000 00000000 00000000 00001111
Inverse code ：11111111 11111111 11111111 11110000
Complement code （ The add 1）：11111111 11111111 11111111 11110001
That is to say -15 Binary system

Positive shift

Unsigned displacement 15>>>2
Binary system ：00000000 00000000 00000000 00001111
After moving ：00000000 00000000 00000000 00000011 （11 Abandon ） Four times smaller
Signed displacement 15>>2
Binary system :00000000 00000000 00000000 00001111
After moving ：00000000 00000000 00000000 00000011 （11 Abandon ) Same as （>>>）

Negative shift

Unsigned displacement -15>>>2
Binary system ：11111111 11111111 11111111 11110001
After moving ：00111111 11111111 11111111 11111100 （01 Abandon ）
* The unsigned shift right operator complements both positive and negative in the high order 0
Signed bit shift -15>>2
Binary system ：11111111 11111111 11111111 11110001
After moving ：11111111 11111111 11111111 11111100 （01 Abandon ）
When the sign moves to the right , If the symbol is regular high complement 0, On the contrary 1;
Find the value after the move ：
Complement code （ Negative binary ）= Inverse code +1
Complement 11111111 11111111 11111111 11111100
First reduction 1：11111111 11111111 11111111 11111011 Inverse code result
Original code : 10000000 00000000 00000000 00000100 （ The result is -4)
Negative inverse code to original code ： The symbol is unchanged , Other reverse

Integer.highestOneBit Source code

effect ： Put an integer （ Binary system ） Set the highest bit to 1, The others are 0, Then return the changed value , If this integer is 0 return 0

The subtlety of the shift operation , Take your time , Signed and unsigned are different ！

       
        public static int highestOneBit(int i) {
        
    //  for example 1000
        
    i |= (i >>  1); 
        
    //  Before making 2 A into 1, amount to i = i | (i >> 1); 
        
    //i = 1000 | 0100 = 1100
        
    i |= (i >>  2); 
        
    //  Before making 4 A into 1, Because the last step ensures that the first two are 1,\
        
    // So this time move two digits ,1111
        
    i |= (i >>  4); //  Before making 8 A into 1,1111
        
    i |= (i >>  8); //  Before making 16 A into 1,1111
        
    i |= (i >> 16); //  Before making 32 A into 1,1111
        
    return i - (i >>> 1); 
        
    // i >>> 1  unsigned right shift , Make the highest position 0, The rest are 1
        
    // Subtract to get the result ,1111 - 0111 = 1000 
        
}
       
       
        1.
        2.
        3.
        4.
        5.
        6.
        7.
        8.
        9.
        10.
        11.
        12.
        13.
        14.
        15.