1/* 2 * reserved comment block 3 * DO NOT REMOVE OR ALTER! 4 */ 5/* 6 * Licensed to the Apache Software Foundation (ASF) under one or more 7 * contributor license agreements. See the NOTICE file distributed with 8 * this work for additional information regarding copyright ownership. 9 * The ASF licenses this file to You under the Apache License, Version 2.0 10 * (the "License"); you may not use this file except in compliance with 11 * the License. You may obtain a copy of the License at 12 * 13 * http://www.apache.org/licenses/LICENSE-2.0 14 * 15 * Unless required by applicable law or agreed to in writing, software 16 * distributed under the License is distributed on an "AS IS" BASIS, 17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 18 * See the License for the specific language governing permissions and 19 * limitations under the License. 20 */ 21 22package com.sun.org.apache.xerces.internal.impl.xpath.regex; 23 24/** 25 */ 26 27final class CaseInsensitiveMap { 28 29 private static final int CHUNK_SHIFT = 10; /* 2^10 = 1k */ 30 private static final int CHUNK_SIZE = (1<<CHUNK_SHIFT); 31 private static final int CHUNK_MASK = (CHUNK_SIZE-1); 32 private static final int INITIAL_CHUNK_COUNT = 64; /* up to 0xFFFF */ 33 34 private static int[][][] caseInsensitiveMap; 35 36 private static final int LOWER_CASE_MATCH = 1; 37 private static final int UPPER_CASE_MATCH = 2; 38 39 static { 40 buildCaseInsensitiveMap(); 41 } 42 43 /** 44 * Return a list of code point characters (not including the input value) 45 * that can be substituted in a case insensitive match 46 */ 47 static public int[] get(int codePoint) { 48 return (codePoint < 0x10000) ? getMapping(codePoint) : null; 49 } 50 51 private static int[] getMapping(int codePoint) { 52 int chunk = codePoint >>> CHUNK_SHIFT; 53 int offset = codePoint & CHUNK_MASK; 54 55 return caseInsensitiveMap[chunk][offset]; 56 } 57 58 private static void buildCaseInsensitiveMap() { 59 caseInsensitiveMap = new int[INITIAL_CHUNK_COUNT][CHUNK_SIZE][]; 60 int lc, uc; 61 for (int i=0; i<0x10000; i++) { 62 lc = Character.toLowerCase(i); 63 uc = Character.toUpperCase(i); 64 65 // lower/upper case value is not the same as code point 66 if (lc != uc || lc != i) { 67 int[] map = new int[2]; 68 int index = 0; 69 70 if (lc != i) { 71 map[index++] = lc; 72 map[index++] = LOWER_CASE_MATCH; 73 int[] lcMap = getMapping(lc); 74 if (lcMap != null) { 75 map = updateMap(i, map, lc, lcMap, LOWER_CASE_MATCH); 76 } 77 } 78 79 if (uc != i) { 80 if (index == map.length) { 81 map = expandMap(map, 2); 82 } 83 map[index++] = uc; 84 map[index++] = UPPER_CASE_MATCH; 85 int[] ucMap = getMapping(uc); 86 if (ucMap != null) { 87 map = updateMap(i, map, uc, ucMap, UPPER_CASE_MATCH); 88 } 89 } 90 91 set(i, map); 92 } 93 } 94 } 95 96 private static int[] expandMap(int[] srcMap, int expandBy) { 97 final int oldLen = srcMap.length; 98 int[] newMap = new int[oldLen + expandBy]; 99 100 System.arraycopy(srcMap, 0, newMap, 0, oldLen); 101 return newMap; 102 } 103 104 private static void set(int codePoint, int[] map) { 105 int chunk = codePoint >>> CHUNK_SHIFT; 106 int offset = codePoint & CHUNK_MASK; 107 108 caseInsensitiveMap[chunk][offset] = map; 109 } 110 111 private static int[] updateMap(int codePoint, int[] codePointMap, 112 int ciCodePoint, int[] ciCodePointMap, int matchType) { 113 for (int i=0; i<ciCodePointMap.length; i+=2) { 114 int c = ciCodePointMap[i]; 115 int[] cMap = getMapping(c); 116 if (cMap != null) { 117 if (contains(cMap, ciCodePoint, matchType)) { 118 if (!contains(cMap, codePoint)) { 119 cMap = expandAndAdd(cMap, codePoint, matchType); 120 set(c, cMap); 121 } 122 if (!contains(codePointMap, c)) { 123 codePointMap = expandAndAdd(codePointMap, c,matchType); 124 } 125 } 126 } 127 } 128 129 if (!contains(ciCodePointMap, codePoint)) { 130 ciCodePointMap = expandAndAdd(ciCodePointMap, codePoint, matchType); 131 set(ciCodePoint, ciCodePointMap); 132 } 133 134 return codePointMap; 135 } 136 137 private static boolean contains(int[] map, int codePoint) { 138 for (int i=0; i<map.length; i += 2) { 139 if (map[i] == codePoint) { 140 return true; 141 } 142 } 143 return false; 144 } 145 146 private static boolean contains(int[] map, int codePoint, int matchType) { 147 for (int i=0; i<map.length; i += 2) { 148 if (map[i] == codePoint && map[i+1] == matchType) { 149 return true; 150 } 151 } 152 return false; 153 } 154 155 private static int[] expandAndAdd(int[] srcMap, int codePoint, int matchType) { 156 final int oldLen = srcMap.length; 157 int[] newMap = new int[oldLen + 2]; 158 159 System.arraycopy(srcMap, 0, newMap, 0, oldLen); 160 newMap[oldLen] = codePoint; 161 newMap[oldLen+1] = matchType; 162 return newMap; 163 } 164} 165