001: package org.zilonis.util;
002:
003: /**
004: * Copyright (c) 2005 Elie Levy <elie.levy@zilonis.org>
005: * All rights reserved
006: *
007: * This License governs use of the accompanying Software, and your use of the
008: * Software constitutes acceptance of this license.
009: *
010: * You may use this Software for any non-commercial purpose, subject to the
011: * restrictions in this license. Some purposes which can be non-commercial are
012: * teaching, academic research, and personal experimentation. You may also
013: * distribute this Software with books or other teaching materials, or publish
014: * the Software on websites, that are intended to teach the use of the
015: * Software.
016: *
017: *
018: * You may not use or distribute this Software or any derivative works in any
019: * form for commercial purposes. Examples of commercial purposes would be
020: * running business operations, licensing, leasing, or selling the Software, or
021: * distributing the Software for use with commercial products.
022: *
023: * You may modify this Software and distribute the modified Software for
024: * non-commercial purposes, however, you may not grant rights to the Software
025: * or derivative works that are broader than those provided by this License.
026: * For example, you may not distribute modifications of the Software under
027: * terms that would permit commercial use, or under terms that purport to
028: * require the Software or derivative works to be sublicensed to others.
029: *
030: * You may use any information in intangible form that you remember after
031: * accessing the Software. However, this right does not grant you a license to
032: * any of the copyrights or patents for anything you might create using such
033: * information.
034: *
035: * In return, we simply require that you agree:
036: *
037: * Not to remove any copyright or other notices from the Software.
038: *
039: *
040: * That if you distribute the Software in source or object form, you will
041: * include a verbatim copy of this license.
042: *
043: *
044: * That if you distribute derivative works of the Software in source code form
045: * you do so only under a license that includes all of the provisions of this
046: * License, and if you distribute derivative works of the Software solely in
047: * object form you do so only under a license that complies with this License.
048: *
049: *
050: * That if you have modified the Software or created derivative works, and
051: * distribute such modifications or derivative works, you will cause the
052: * modified files to carry prominent notices so that recipients know that they
053: * are not receiving the original Software. Such notices must state: (i) that
054: * you have changed the Software; and (ii) the date of any changes.
055: *
056: *
057: * THAT THE SOFTWARE COMES "AS IS", WITH NO WARRANTIES. THIS MEANS NO EXPRESS,
058: * IMPLIED OR STATUTORY WARRANTY, INCLUDING WITHOUT LIMITATION, WARRANTIES OF
059: * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE OR ANY WARRANTY OF TITLE
060: * OR NON-INFRINGEMENT. ALSO, YOU MUST PASS THIS DISCLAIMER ON WHENEVER YOU
061: * DISTRIBUTE THE SOFTWARE OR DERIVATIVE WORKS.
062: *
063: *
064: * THAT NEITHER ZILONIS NOR THE AUTHOR WILL BE LIABLE FOR ANY DAMAGES RELATED
065: * TO THE SOFTWARE OR THIS LICENSE, INCLUDING DIRECT, INDIRECT, SPECIAL,
066: * CONSEQUENTIAL OR INCIDENTAL DAMAGES, TO THE MAXIMUM EXTENT THE LAW PERMITS,
067: * NO MATTER WHAT LEGAL THEORY IT IS BASED ON. ALSO, YOU MUST PASS THIS
068: * LIMITATION OF LIABILITY ON WHENEVER YOU DISTRIBUTE THE SOFTWARE OR
069: * DERIVATIVE WORKS.
070: *
071: *
072: * That if you sue anyone over patents that you think may apply to the Software
073: * or anyone's use of the Software, your license to the Software ends
074: * automatically.
075: *
076: *
077: * That your rights under the License end automatically if you breach it in any
078: * way.
079: *
080: *
081: * Elie Levy reserves all rights not expressly granted to you in this
082: * license.
083: *
084: */
085:
086: import java.util.concurrent.locks.ReentrantLock;
087:
088: public abstract class Index<Type extends IMultiListElement> implements
089: NextHolder {
090:
091: private static final int LOG2_INDEX_SIZE = 13;
092:
093: private static final int INDEX_SIZE = (((int) 1) << LOG2_INDEX_SIZE);
094:
095: private static final int INDEX_MASK = (INDEX_SIZE - 1);
096:
097: private static final int LOG2_SEGMENT_SIZE = 5;
098:
099: private static final int SEGMENT_SIZE = (((int) 1) << LOG2_SEGMENT_SIZE);
100:
101: private static final int SEGMENT_MASK = (SEGMENT_SIZE - 1);
102:
103: final ReentrantLock segment[];
104:
105: final IMultiListElement index[];
106:
107: int list;
108:
109: public Index(int list) {
110: this .list = list;
111: index = new IMultiListElement[INDEX_SIZE];
112: segment = new ReentrantLock[SEGMENT_SIZE];
113: for (int i = 0; i < SEGMENT_SIZE; ++i)
114: segment[i] = new ReentrantLock();
115: }
116:
117: public Type get(int hashCode) {
118: return (Type) index[hashCode & INDEX_MASK];
119: }
120:
121: public ReentrantLock getSegment(int position) {
122: position = position & SEGMENT_MASK;
123: return segment[position];
124: }
125:
126: public void lock(int list, IMultiListElement element) {
127: int position = getHashCode((Type) element);
128: getSegment(position).lock();
129: }
130:
131: public void unlock(int list, IMultiListElement element) {
132: int position = getHashCode((Type) element);
133: getSegment(position).unlock();
134: }
135:
136: public abstract int getHashCode(Type element);
137:
138: /*
139: * { return element.hashCode(); }
140: */
141:
142: public void setNext(int list, IMultiListElement element) {
143: validateList(list);
144: int position = getHashCode((Type) element) & INDEX_MASK;
145: index[position] = element;
146: }
147:
148: public void removeLast(int list, IMultiListElement element) {
149: validateList(list);
150: int position = getHashCode((Type) element) & INDEX_MASK;
151: index[position] = null;
152: }
153:
154: public void add(Type element) {
155: int position = getHashCode((Type) element) & INDEX_MASK;
156: lock(list, element);
157: element.lock(list, null);
158: if (index[position] != null) {
159: index[position].lock(list, null);
160: }
161: try {
162: element.setNext(list, index[position]);
163: if (index[position] != null)
164: index[position].setPrev(list, (NextHolder) element);
165: index[position] = element;
166: } finally {
167: if (element.getNext(list) != null)
168: element.getNext(list).unlock(list, null);
169: element.unlock(list, null);
170: unlock(list, element);
171: }
172: }
173:
174: public void add(int list, Type element) {
175: validateList(list);
176: add(element);
177: }
178:
179: public void validateList(int list) {
180: if (list != this .list)
181: throw new IllegalArgumentException("The list received:"
182: + list + " does not match the expected:"
183: + this.list);
184: }
185:
186: }
|