forgot to check length()
[idea/community.git] / platform / analysis-impl / src / com / intellij / codeInsight / daemon / UsedColors.java
1 /*
2  * Copyright 2000-2016 JetBrains s.r.o.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.intellij.codeInsight.daemon;
17
18 import com.intellij.codeHighlighting.RainbowHighlighter;
19 import com.intellij.openapi.util.Key;
20 import com.intellij.openapi.util.UserDataHolderEx;
21 import com.intellij.openapi.util.text.StringHash;
22 import com.intellij.util.ArrayUtil;
23 import org.jetbrains.annotations.NotNull;
24
25 import java.util.concurrent.atomic.AtomicInteger;
26
27 class UsedColors {
28   private static final Key<Object/*UsedColor or UsedColor[]*/> USED_COLOR = Key.create("USED_COLOR");
29
30   public static final AtomicInteger counter = new AtomicInteger();
31   private static class UsedColor {
32     @NotNull final String name;
33     final int index;
34
35     UsedColor(@NotNull String name, int index) {
36       this.name = name;
37       this.index = index;
38       counter.incrementAndGet();
39     }
40   }
41
42   static int getOrAddColorIndex(@NotNull final UserDataHolderEx context,
43                                 @NotNull final String name,
44                                 @NotNull RainbowHighlighter rainbowHighlighter) {
45     int colorsCount = rainbowHighlighter.getColorsCount();
46     Object data = context.getUserData(USED_COLOR);
47
48     int colorIndex;
49     while (true) {
50       Object newColors;
51       if (data == null) {
52         colorIndex = hashColor(name, colorsCount);
53         newColors = new UsedColor(name, colorIndex); // put an object instead of array to save space
54       }
55       else if (data instanceof UsedColor) {
56         UsedColor usedColor = (UsedColor)data;
57         if (usedColor.name.equals(name)) {
58           colorIndex = usedColor.index;
59           newColors = null; // found, no need to create new
60         }
61         else {
62           int hashedIndex = hashColor(name, colorsCount);
63           if (hashedIndex == usedColor.index) hashedIndex = (hashedIndex + 1) % colorsCount;
64           colorIndex = hashedIndex;
65           UsedColor newColor = new UsedColor(name, colorIndex);
66           newColors = new UsedColor[]{usedColor, newColor};
67         }
68       }
69       else {
70         colorIndex = -1;
71         int hashedIndex = hashColor(name, colorsCount);
72         int[] index2usage = new int[colorsCount];
73         UsedColor[] usedColors = (UsedColor[])data;
74         for (UsedColor usedColor : usedColors) {
75           int index = usedColor.index;
76           index2usage[index]++;
77           if (usedColor.name.equals(name)) {
78             colorIndex = index;
79             break;
80           }
81         }
82         if (colorIndex == -1) {
83           int minIndex1 = indexOfMin(index2usage, hashedIndex, colorsCount);
84           int minIndex2 = indexOfMin(index2usage, 0, hashedIndex);
85           colorIndex = index2usage[minIndex1] <= index2usage[minIndex2] ? minIndex1 : minIndex2;
86           UsedColor newColor = new UsedColor(name, colorIndex);
87           newColors = ArrayUtil.append(usedColors, newColor);
88         }
89         else {
90           newColors = null;
91         }
92       }
93       if (newColors == null || context.replace(USED_COLOR, data, newColors)) {
94         break;
95       }
96     }
97
98     return colorIndex;
99   }
100
101   private static int hashColor(@NotNull String name, int colorsCount) {
102     return Math.abs(StringHash.murmur(name, 0x55AA)) % colorsCount;
103   }
104
105   private static int indexOfMin(@NotNull int[] values, int start, int end) {
106     int min = Integer.MAX_VALUE;
107     int minIndex = start;
108     for (int i = start; i < end; i++) {
109       int value = values[i];
110       if (value < min) {
111         min = value;
112         minIndex = i;
113       }
114     }
115     return minIndex;
116   }
117 }