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