001    package com.thaiopensource.relaxng.impl;
002    
003    
004    final class PatternInterner {
005      private static final int INIT_SIZE = 256;
006      private static final float LOAD_FACTOR = 0.3f;
007      private Pattern[] table;
008      private int used;
009      private int usedLimit;
010    
011      PatternInterner() {
012        table = null;
013        used = 0;
014        usedLimit = 0;
015      }
016    
017      PatternInterner(PatternInterner parent) {
018        table = parent.table;
019        if (table != null)
020          table = (Pattern[])table.clone();
021        used = parent.used;
022        usedLimit = parent.usedLimit;
023      }
024    
025      Pattern intern(Pattern p) {
026        int h;
027    
028        if (table == null) {
029          table = new Pattern[INIT_SIZE];
030          usedLimit = (int)(INIT_SIZE * LOAD_FACTOR);
031          h = firstIndex(p);
032        }
033        else {
034          for (h = firstIndex(p); table[h] != null; h = nextIndex(h)) {
035            if (p.samePattern(table[h]))
036              return table[h];
037          }
038        }
039        if (used >= usedLimit) {
040          // rehash
041          Pattern[] oldTable = table;
042          table = new Pattern[table.length << 1];
043          for (int i = oldTable.length; i > 0;) {
044            --i;
045            if (oldTable[i] != null) {
046              int j;
047              for (j = firstIndex(oldTable[i]); table[j] != null; j = nextIndex(j))
048                ;
049              table[j] = oldTable[i];
050            }
051          }
052          for (h = firstIndex(p); table[h] != null; h = nextIndex(h))
053            ;
054          usedLimit = (int)(table.length * LOAD_FACTOR);
055        }
056        used++;
057        table[h] = p;
058        return p;
059      }
060    
061      private int firstIndex(Pattern p) {
062        return p.patternHashCode() & (table.length - 1);
063      }
064    
065      private int nextIndex(int i) {
066        return i == 0 ? table.length - 1 : i - 1;
067      }
068    }