19066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/* 29066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Copyright (C) 2007 The Android Open Source Project 39066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 49066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Licensed under the Apache License, Version 2.0 (the "License"); 59066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * you may not use this file except in compliance with the License. 69066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * You may obtain a copy of the License at 79066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 89066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 99066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * 109066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Unless required by applicable law or agreed to in writing, software 119066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 129066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 139066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * See the License for the specific language governing permissions and 149066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * limitations under the License. 159066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 169066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 179066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectpackage android.sax; 189066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 199066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project/** 209066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Contains element children. Using this class instead of HashMap results in 219066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * measurably better performance. 229066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 239066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Projectclass Children { 249066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 259066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Child[] children = new Child[16]; 269066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 279066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 289066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Looks up a child by name and creates a new one if necessary. 299066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 309066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Element getOrCreate(Element parent, String uri, String localName) { 319066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int hash = uri.hashCode() * 31 + localName.hashCode(); 329066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int index = hash & 15; 339066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 349066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Child current = children[index]; 359066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (current == null) { 369066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // We have no children in this bucket yet. 379066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project current = new Child(parent, uri, localName, parent.depth + 1, hash); 389066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project children[index] = current; 399066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return current; 409066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 419066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Search this bucket. 429066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Child previous; 439066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project do { 449066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (current.hash == hash 459066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && current.uri.compareTo(uri) == 0 469066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && current.localName.compareTo(localName) == 0) { 479066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // We already have a child with that name. 489066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return current; 499066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 509066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 519066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project previous = current; 529066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project current = current.next; 539066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } while (current != null); 549066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 559066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project // Add a new child to the bucket. 569066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project current = new Child(parent, uri, localName, parent.depth + 1, hash); 579066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project previous.next = current; 589066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return current; 599066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 609066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 619066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 629066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project /** 639066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project * Looks up a child by name. 649066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project */ 659066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Element get(String uri, String localName) { 669066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int hash = uri.hashCode() * 31 + localName.hashCode(); 679066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int index = hash & 15; 689066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 699066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Child current = children[index]; 709066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (current == null) { 719066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return null; 729066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } else { 739066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project do { 749066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project if (current.hash == hash 759066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && current.uri.compareTo(uri) == 0 769066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project && current.localName.compareTo(localName) == 0) { 779066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return current; 789066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 799066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project current = current.next; 809066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } while (current != null); 819066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 829066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project return null; 839066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 849066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 859066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 869066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project static class Child extends Element { 879066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 889066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project final int hash; 899066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Child next; 909066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project 919066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project Child(Element parent, String uri, String localName, int depth, 929066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project int hash) { 939066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project super(parent, uri, localName, depth); 949066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project this.hash = hash; 959066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 969066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project } 979066cfe9886ac131c34d59ed0e2d287b0e3c0087The Android Open Source Project} 98