1 /*
   2  * Copyright (c) 2015, 2015, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 package sun.jvm.hotspot.utilities;
  26 
  27 import java.util.*;
  28 import sun.jvm.hotspot.debugger.*;
  29 import sun.jvm.hotspot.oops.*;
  30 import sun.jvm.hotspot.types.*;
  31 import sun.jvm.hotspot.runtime.*;
  32 import sun.jvm.hotspot.utilities.*;
  33 
  34 public class CompactHashTable extends VMObject {
  35   static {
  36     VM.registerVMInitializedObserver(new Observer() {
  37       public void update(Observable o, Object data) {
  38         initialize(VM.getVM().getTypeDataBase());
  39       }
  40     });
  41   }
  42 
  43   private static synchronized void initialize(TypeDataBase db) throws WrongTypeException {
  44     Type type = db.lookupType("SymbolCompactHashTable");
  45     baseAddressField = type.getAddressField("_base_address");
  46     bucketCountField = type.getCIntegerField("_bucket_count");
  47     tableEndOffsetField = type.getCIntegerField("_table_end_offset");
  48     bucketsField = type.getAddressField("_buckets");
  49     uintSize = db.lookupType("juint").getSize();
  50   }
  51 
  52   // Fields
  53   private static CIntegerField bucketCountField;
  54   private static CIntegerField tableEndOffsetField;
  55   private static AddressField  baseAddressField;
  56   private static AddressField  bucketsField;
  57   private static long uintSize;
  58   private static long uintxSize;
  59 
  60   private static int BUCKET_OFFSET_MASK = 0x3FFFFFFF;
  61   private static int BUCKET_TYPE_SHIFT = 30;
  62   private static int COMPACT_BUCKET_TYPE = 1;
  63 
  64   public CompactHashTable(Address addr) {
  65     super(addr);
  66   }
  67 
  68   private int bucketCount() {
  69     return (int)bucketCountField.getValue(addr);
  70   }
  71 
  72   private int tableEndOffset() {
  73     return (int)tableEndOffsetField.getValue(addr);
  74   }
  75 
  76   private boolean isCompactBucket(int bucket_info) {
  77     return (bucket_info >> BUCKET_TYPE_SHIFT) == COMPACT_BUCKET_TYPE;
  78   }
  79 
  80   private int bucketOffset(int bucket_info) {
  81     return bucket_info & BUCKET_OFFSET_MASK;
  82   }
  83 
  84   public Symbol probe(byte[] name, long hash) {
  85     long    symOffset;
  86     Symbol  sym;
  87     Address baseAddress = baseAddressField.getValue(addr);
  88     Address bucket = bucketsField.getValue(addr);
  89     Address bucketEnd = bucket;
  90     long index = hash % bucketCount();
  91     int bucketInfo = (int)bucket.getCIntegerAt(index * uintSize, uintSize, true);
  92     int bucketOffset = bucketOffset(bucketInfo);
  93     int nextBucketInfo = (int)bucket.getCIntegerAt((index+1) * uintSize, uintSize, true);
  94     int nextBucketOffset = bucketOffset(nextBucketInfo);
  95     
  96     bucket = bucket.addOffsetTo(bucketOffset * uintSize);
  97     
  98     if (isCompactBucket(bucketInfo)) {
  99       symOffset = bucket.getCIntegerAt(0, uintSize, true);
 100       sym = Symbol.create(baseAddress.addOffsetTo(symOffset));
 101       if (sym.equals(name)) {
 102         return sym;
 103       }
 104     } else {
 105       bucketEnd = bucket.addOffsetTo(nextBucketOffset * uintSize);
 106       while (bucket.lessThan(bucketEnd)) {
 107         long symHash = bucket.getCIntegerAt(0, uintSize, true);
 108         if (symHash == hash) {
 109           symOffset = bucket.getCIntegerAt(uintSize, uintSize, true);
 110           Address symAddr = baseAddress.addOffsetTo(symOffset);
 111           sym = Symbol.create(symAddr);
 112           if (sym.equals(name)) {
 113             return sym;
 114           }
 115         }
 116         bucket = bucket.addOffsetTo(2 * uintSize);
 117       }
 118     }
 119     return null;
 120   }
 121 }