1/*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2002,2008 Oracle. All rights reserved. 5 * 6 * $Id: VisitedObjects.java,v 1.1 2008/02/07 17:12:27 mark Exp $ 7 */ 8 9package 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 */ 19class VisitedObjects { 20 21 /* 22 * Offset to indicate that the visited object is stored in the primary key 23 * byte array. 24 */ 25 static final int PRI_KEY_VISITED_OFFSET = Integer.MAX_VALUE - 1; 26 27 /* Used by RecordOutput to prevent illegal nested references. */ 28 static final int PROHIBIT_REF_OFFSET = Integer.MAX_VALUE - 2; 29 30 /* Used by RecordInput to prevent illegal nested references. */ 31 static final Object PROHIBIT_REF_OBJECT = new Object(); 32 33 static final String PROHIBIT_NESTED_REF_MSG = 34 "Cannot embed a reference to a proxied object in the proxy; for " + 35 "example, a collection may not be an element of the collection " + 36 "because collections are proxied"; 37 38 private static final int INIT_LEN = 50; 39 40 private Object[] objects; 41 private int[] offsets; 42 private int nextIndex; 43 44 /** 45 * Creates an empty set. 46 */ 47 VisitedObjects() { 48 objects = new Object[INIT_LEN]; 49 offsets = new int[INIT_LEN]; 50 nextIndex = 0; 51 } 52 53 /** 54 * Adds a visited object and offset, growing the visited arrays as needed. 55 * @return the index of the new slot. 56 */ 57 int add(Object o, int offset) { 58 59 int i = nextIndex; 60 nextIndex += 1; 61 if (nextIndex > objects.length) { 62 growVisitedArrays(); 63 } 64 objects[i] = o; 65 offsets[i] = offset; 66 return i; 67 } 68 69 /** 70 * Sets the object for an existing slot index. 71 */ 72 void setObject(int index, Object o) { 73 objects[index] = o; 74 } 75 76 /** 77 * Sets the offset for an existing slot index. 78 */ 79 void setOffset(int index, int offset) { 80 offsets[index] = offset; 81 } 82 83 /** 84 * Returns the offset for a visited object, or -1 if never visited. 85 */ 86 int getOffset(Object o) { 87 for (int i = 0; i < nextIndex; i += 1) { 88 if (objects[i] == o) { 89 return offsets[i]; 90 } 91 } 92 return -1; 93 } 94 95 /** 96 * Returns the visited object for a given offset, or null if never visited. 97 */ 98 Object getObject(int offset) { 99 for (int i = 0; i < nextIndex; i += 1) { 100 if (offsets[i] == offset) { 101 return objects[i]; 102 } 103 } 104 return null; 105 } 106 107 /** 108 * Replaces a given object in the list. Used when an object is converted 109 * after adding it to the list. 110 */ 111 void replaceObject(Object existing, Object replacement) { 112 for (int i = nextIndex - 1; i >= 0; i -= 1) { 113 if (objects[i] == existing) { 114 objects[i] = replacement; 115 return; 116 } 117 } 118 assert false; 119 } 120 121 /** 122 * Doubles the size of the visited arrays. 123 */ 124 private void growVisitedArrays() { 125 126 int oldLen = objects.length; 127 int newLen = oldLen * 2; 128 129 Object[] newObjects = new Object[newLen]; 130 int[] newOffsets = new int[newLen]; 131 132 System.arraycopy(objects, 0, newObjects, 0, oldLen); 133 System.arraycopy(offsets, 0, newOffsets, 0, oldLen); 134 135 objects = newObjects; 136 offsets = newOffsets; 137 } 138} 139