VisitedObjects


1   /*-
2    * See the file LICENSE for redistribution information.
3    *
4    * Copyright (c) 2002,2006 Oracle.  All rights reserved.
5    *
6    * $Id: VisitedObjects.java,v 1.9 2006/10/30 21:14:32 bostic Exp $
7    */
8   
9   package com.sleepycat.persist.impl;
10  
11  /**
12   * Keeps track of a set of visited objects and their corresponding offset in a
13   * byte array.  This uses a resizable int array for speed and simplicity.  If
14   * in the future the array resizing or linear search are performance issues, we
15   * could try using an IdentityHashMap instead.
16   *
17   * @author Mark Hayes
18   */
19  class VisitedObjects {
20  
21      private static final int INIT_LEN = 50;
22  
23      private Object  [] objects;
24      private int[] offsets;
25      private int nextIndex;
26  
27      /**
28       * Creates an empty set.
29       */
30      VisitedObjects() {
31          objects = new Object  [INIT_LEN];
32          offsets = new int[INIT_LEN];
33          nextIndex = 0;
34      }
35  
36      /**
37       * Adds a visited object and offset, growing the visited arrays as needed.
38       */
39      void add(Object   o, int offset) {
40  
41          int i = nextIndex;
42          nextIndex += 1;
43          if (nextIndex > objects.length) {
44              growVisitedArrays();
45          }
46          objects[i] = o;
47          offsets[i] = offset;
48      }
49  
50      /**
51       * Returns the offset for a visited object, or -1 if never visited.
52       */
53      int getOffset(Object   o) {
54          for (int i = 0; i < nextIndex; i += 1) {
55              if (objects[i] == o) {
56                  return offsets[i];
57              }
58          }
59          return -1;
60      }
61  
62      /**
63       * Returns the visited object for a given offset, or null if never visited.
64       */
65      Object   getObject(int offset) {
66          for (int i = 0; i < nextIndex; i += 1) {
67              if (offsets[i] == offset) {
68                  return objects[i];
69              }
70          }
71          return null;
72      }
73  
74      /**
75       * Replaces a given object in the list.  Used when an object is converted
76       * after adding it to the list.
77       */
78      void replaceObject(Object   existing, Object   replacement) {
79          for (int i = nextIndex - 1; i >= 0; i -= 1) {
80              if (objects[i] == existing) {
81                  objects[i] = replacement;
82                  return;
83              }
84          }
85          assert false;
86      }
87  
88      /**
89       * Doubles the size of the visited arrays.
90       */
91      private void growVisitedArrays() {
92  
93          int oldLen = objects.length;
94          int newLen = oldLen * 2;
95  
96          Object  [] newObjects = new Object  [newLen];
97          int[] newOffsets = new int[newLen];
98  
99          System.arraycopy(objects, 0, newObjects, 0, oldLen);
100         System.arraycopy(offsets, 0, newOffsets, 0, oldLen);
101 
102         objects = newObjects;
103         offsets = newOffsets;
104     }
105 }
106
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags