001: /*
002:
003: Derby - Class org.apache.derby.impl.store.access.sort.NodeAllocator
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.store.access.sort;
023:
024: /**
025:
026: NodeAllocator manages an array of nodes which can be reused.
027:
028: **/
029:
030: final class NodeAllocator {
031: private static final int DEFAULT_INIT_SIZE = 128;
032: private static final int GROWTH_MULTIPLIER = 2;
033: private static final int DEFAULT_MAX_SIZE = 1024;
034:
035: private Node array[];
036: private int maxSize;
037: private int nAllocated;
038: private Node freeList = null;
039:
040: /**
041: Construct an empty allocator. The caller must call
042: init() before using it.
043: **/
044: public NodeAllocator() {
045: array = null;
046: nAllocated = 0;
047: maxSize = 0;
048: }
049:
050: public Node newNode() {
051: // Caller forgot to init?
052: if (array == null) {
053: if (init() == false)
054: return null;
055: }
056:
057: if (freeList != null) {
058: Node n = freeList;
059: freeList = n.rightLink;
060: n.rightLink = null;
061: return n;
062: }
063:
064: // Do we need to try reallocating the array?
065: if (nAllocated == array.length) {
066: // If the array is already the maximum size, then
067: // tell the caller that there are no more nodes
068: // available.
069: if (array.length >= maxSize)
070: return null;
071:
072: // Attempt to allocate a new array. If the allocation
073: // fails, tell the caller that there are no more
074: // nodes available.
075: Node[] newArray = new Node[array.length * GROWTH_MULTIPLIER];
076: if (newArray == null)
077: return null;
078:
079: // The new array was successfully allocated. Copy the
080: // nodes from the original array into it, and make the
081: // new array the allocator's array.
082: System.arraycopy(array, 0, newArray, 0, array.length);
083: array = newArray;
084: }
085:
086: // If this slot in the array hasn't had a node
087: // allocated for it yet, do so now.
088: if (array[nAllocated] == null)
089: array[nAllocated] = new Node(nAllocated);
090:
091: // Return the node and increase the allocated count.
092: return array[nAllocated++];
093: }
094:
095: /**
096: Return a node to the allocator.
097: **/
098: public void freeNode(Node n) {
099: n.reset();
100: n.rightLink = freeList;
101: freeList = n;
102: }
103:
104: /**
105: Initialize the allocator with default values for
106: initial and maximum size. Returns false if sufficient
107: memory could not be allocated.
108: **/
109: public boolean init() {
110: return init(DEFAULT_INIT_SIZE, DEFAULT_MAX_SIZE);
111: }
112:
113: /**
114: Initialize the allocator with default values for
115: initial size and the provided maximum size.
116: Returns false if sufficient memory could not be allocated.
117: **/
118: public boolean init(int maxSize) {
119: return init(DEFAULT_INIT_SIZE, maxSize);
120: }
121:
122: /**
123: Initialize the allocator with the given initial and
124: maximum sizes. This method does not check, but assumes
125: that the value of initSize is less than the value of
126: maxSize, and that they are both powers of two. Returns
127: false if sufficient memory could not be allocated.
128: **/
129: public boolean init(int initSize, int maxSize) {
130: this .maxSize = maxSize;
131: if (maxSize < initSize)
132: initSize = maxSize;
133: array = new Node[initSize];
134: if (array == null)
135: return false;
136: nAllocated = 0;
137: return true;
138: }
139:
140: /**
141: Expand the node allocator's capacity by certain percent.
142: **/
143: public void grow(int percent) {
144: if (percent > 0) // cannot shrink
145: maxSize = maxSize * (100 + percent) / 100;
146: }
147:
148: /**
149: Clear all nodes that this allocator has allocated.
150: The allocator must already have been initialized.
151: **/
152: public void reset() {
153: if (array == null)
154: return;
155: for (int i = 0; i < nAllocated; i++)
156: array[i].reset();
157: nAllocated = 0;
158: freeList = null;
159: }
160:
161: public void close() {
162: array = null;
163: nAllocated = 0;
164: maxSize = 0;
165: freeList = null;
166: }
167:
168: public int capacity() {
169: return maxSize;
170: }
171: }
|