KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > events > NodeIDMap


1 /*******************************************************************************
2  * Copyright (c) 2000, 2005 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11 package org.eclipse.core.internal.events;
12
13 import org.eclipse.core.runtime.IPath;
14
15 /**
16  * A specialized map that maps Node IDs to their old and new paths.
17  * Used for calculating moves during resource change notification.
18  */
19 public class NodeIDMap {
20     //using prime table sizes improves our hash function
21 private static final int[] SIZES = new int[] {13, 29, 71, 173, 349, 733, 1511, 3079, 6133, 16381, 32653, 65543, 131111, 262139, 524287, 1051601};
22     private static final double LOAD_FACTOR = 0.75;
23     //2^32 * golden ratio
24 private static final long LARGE_NUMBER = 2654435761L;
25
26     int sizeOffset = 0;
27     protected int elementCount = 0;
28     protected long[] ids;
29     protected IPath[] oldPaths;
30     protected IPath[] newPaths;
31
32     /**
33      * Creates a new node ID map of default capacity.
34      */
35     public NodeIDMap() {
36         this.sizeOffset = 0;
37         this.ids = new long[SIZES[sizeOffset]];
38         this.oldPaths = new IPath[SIZES[sizeOffset]];
39         this.newPaths = new IPath[SIZES[sizeOffset]];
40     }
41
42     /**
43      * The array isn't large enough so double its size and rehash
44      * all its current values.
45      */
46     protected void expand() {
47         int newLength;
48         try {
49             newLength = SIZES[++sizeOffset];
50         } catch (ArrayIndexOutOfBoundsException JavaDoc e) {
51             //will only occur if there are > 1 million elements in delta
52 newLength = ids.length * 2;
53         }
54         long[] grownIds = new long[newLength];
55         IPath[] grownOldPaths = new IPath[newLength];
56         IPath[] grownNewPaths = new IPath[newLength];
57         int maxArrayIndex = newLength - 1;
58         for (int i = 0; i < ids.length; i++) {
59             long id = ids[i];
60             if (id != 0) {
61                 int hash = hashFor(id, newLength);
62                 while (grownIds[hash] != 0) {
63                     hash++;
64                     if (hash > maxArrayIndex)
65                         hash = 0;
66                 }
67                 grownIds[hash] = id;
68                 grownOldPaths[hash] = oldPaths[i];
69                 grownNewPaths[hash] = newPaths[i];
70             }
71         }
72         ids = grownIds;
73         oldPaths = grownOldPaths;
74         newPaths = grownNewPaths;
75     }
76
77     /**
78      * Returns the index of the given element in the map. If not
79      * found, returns -1.
80      */
81     private int getIndex(long searchID) {
82         final int len = ids.length;
83         int hash = hashFor(searchID, len);
84
85         // search the last half of the array
86 for (int i = hash; i < len; i++) {
87             if (ids[i] == searchID)
88                 return i;
89             // marker info not found so return -1
90 if (ids[i] == 0)
91                 return -1;
92         }
93
94         // search the beginning of the array
95 for (int i = 0; i < hash - 1; i++) {
96             if (ids[i] == searchID)
97                 return i;
98             // marker info not found so return -1
99 if (ids[i] == 0)
100                 return -1;
101         }
102         // marker info not found so return -1
103 return -1;
104     }
105
106     /**
107      * Returns the new path location for the given ID, or null
108      * if no new path is available.
109      */
110     public IPath getNewPath(long nodeID) {
111         int index = getIndex(nodeID);
112         if (index == -1)
113             return null;
114         return newPaths[index];
115     }
116
117     /**
118      * Returns the old path location for the given ID, or null
119      * if no old path is available.
120      */
121     public IPath getOldPath(long nodeID) {
122         int index = getIndex(nodeID);
123         if (index == -1)
124             return null;
125         return oldPaths[index];
126     }
127
128     private int hashFor(long id, int size) {
129         //Knuth's hash function from Art of Computer Programming section 6.4
130 return (int) Math.abs((id * LARGE_NUMBER) % size);
131     }
132
133     /**
134      * Returns true if there are no elements in the map, and
135      * false otherwise.
136      */
137     public boolean isEmpty() {
138         return elementCount == 0;
139     }
140
141     /**
142      * Adds the given path mappings to the map. If either oldPath
143      * or newPath is null, they are ignored (old map values are not overwritten).
144      */
145     private void put(long id, IPath oldPath, IPath newPath) {
146         if (oldPath == null && newPath == null)
147             return;
148         int hash = hashFor(id, ids.length);
149
150         // search for an empty slot at the end of the array
151 for (int i = hash; i < ids.length; i++) {
152             if (ids[i] == id) {
153                 //replace value for existing entry
154 if (oldPath != null)
155                     oldPaths[i] = oldPath;
156                 if (newPath != null)
157                     newPaths[i] = newPath;
158                 return;
159             }
160             if (ids[i] == 0) {
161                 //add a new entry to the map
162 ids[i] = id;
163                 if (oldPath != null)
164                     oldPaths[i] = oldPath;
165                 if (newPath != null)
166                     newPaths[i] = newPath;
167                 elementCount++;
168                 // grow if necessary
169 if (shouldGrow())
170                     expand();
171                 return;
172             }
173         }
174
175         // search for an empty slot at the beginning of the array
176 for (int i = 0; i < hash - 1; i++) {
177             if (ids[i] == id) {
178                 //replace value for existing entry
179 if (oldPath != null)
180                     oldPaths[i] = oldPath;
181                 if (newPath != null)
182                     newPaths[i] = newPath;
183                 return;
184             }
185             if (ids[i] == 0) {
186                 //add a new entry to the map
187 ids[i] = id;
188                 if (oldPath != null)
189                     oldPaths[i] = oldPath;
190                 if (newPath != null)
191                     newPaths[i] = newPath;
192                 elementCount++;
193                 // grow if necessary
194 if (shouldGrow())
195                     expand();
196                 return;
197             }
198         }
199         // if we didn't find a free slot, then try again with the expanded set
200 expand();
201         put(id, oldPath, newPath);
202     }
203
204     /**
205      * Adds an entry for a node's old path
206      */
207     public void putOldPath(long id, IPath path) {
208         put(id, path, null);
209     }
210
211     /**
212      * Adds an entry for a node's old path
213      */
214     public void putNewPath(long id, IPath path) {
215         put(id, null, path);
216     }
217
218     private boolean shouldGrow() {
219         return elementCount > ids.length * LOAD_FACTOR;
220     }
221 }
222
Popular Tags