From 78f74e193fcc871be406d5cde191818224b8e249 Mon Sep 17 00:00:00 2001 From: megacz Date: Fri, 30 Jan 2004 06:45:12 +0000 Subject: [PATCH] 2002/03/21 01:19:34 darcs-hash:20040130064512-2ba56-3e7969ce72964e71e58e82328d466121a0d50d1c.gz --- src/org/xwt/util/DirtyList.java | 179 ++++++++++++++++++++++++++++++++++++ src/org/xwt/util/Hash.java | 154 +++++++++++++++++++++++++++++++ src/org/xwt/util/JSObject.java | 194 +++++++++++++++++++++++++++++++++++++++ src/org/xwt/util/Log.java | 52 +++++++++++ src/org/xwt/util/Queue.java | 81 ++++++++++++++++ src/org/xwt/util/Semaphore.java | 31 +++++++ src/org/xwt/util/Vec.java | 102 ++++++++++++++++++++ src/org/xwt/util/package.html | 2 + 8 files changed, 795 insertions(+) create mode 100644 src/org/xwt/util/DirtyList.java create mode 100644 src/org/xwt/util/Hash.java create mode 100644 src/org/xwt/util/JSObject.java create mode 100644 src/org/xwt/util/Log.java create mode 100644 src/org/xwt/util/Queue.java create mode 100644 src/org/xwt/util/Semaphore.java create mode 100644 src/org/xwt/util/Vec.java create mode 100644 src/org/xwt/util/package.html diff --git a/src/org/xwt/util/DirtyList.java b/src/org/xwt/util/DirtyList.java new file mode 100644 index 0000000..0368ef8 --- /dev/null +++ b/src/org/xwt/util/DirtyList.java @@ -0,0 +1,179 @@ +// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL] +package org.xwt.util; + +import java.util.*; + +/** + * A general-purpose data structure for holding a list of rectangular + * regions that need to be repainted, with intelligent coalescing. + * + * DirtyList will unify two regions A and B if the smallest rectangle + * enclosing both A and B occupies no more than epsilon + Area_A + + * Area_B. Failing this, if two corners of A fall within B, A will be + * shrunk to exclude the union of A and B. + */ +public class DirtyList { + + public DirtyList() { } + + /** The dirty regions (each one is an int[4]). */ + private int[][] dirties = new int[10][]; + + /** The number of dirty regions */ + private int numdirties = 0; + + /** See class comment */ + private static final int epsilon = 50 * 50; + + public int num() { return numdirties; } + + /** grows the array */ + private void grow() { + int[][] newdirties = new int[dirties.length * 2][]; + System.arraycopy(dirties, 0, newdirties, 0, numdirties); + dirties = newdirties; + } + + /** Add a new rectangle to the dirty list; returns false if the + * region fell completely within an existing rectangle or set of + * rectangles (ie did not expand the dirty area) + */ + public synchronized boolean dirty(int x, int y, int w, int h) { + if (numdirties == dirties.length) grow(); + + // we attempt the "lossless" combinations first + for(int i=0; i= cur[0] && y >= cur[1] && x + w <= cur[0] + cur[2] && y + h <= cur[1] + cur[3]) { + return false; + + // existing region falls completely within new region + } else if (x <= cur[0] && y <= cur[1] && x + w >= cur[0] + cur[2] && y + h >= cur[1] + cur[3]) { + dirties[i][2] = 0; + dirties[i][3] = 0; + + // left end of new region falls within existing region + } else if (x >= cur[0] && x < cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) { + w = x + w - (cur[0] + cur[2]); + x = cur[0] + cur[2]; + i = -1; continue; + + // right end of new region falls within existing region + } else if (x + w > cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y + h <= cur[1] + cur[3]) { + w = cur[0] - x; + i = -1; continue; + + // top end of new region falls within existing region + } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y >= cur[1] && y < cur[1] + cur[3]) { + h = y + h - (cur[1] + cur[3]); + y = cur[1] + cur[3]; + i = -1; continue; + + // bottom end of new region falls within existing region + } else if (x >= cur[0] && x + w <= cur[0] + cur[2] && y + h > cur[1] && y + h <= cur[1] + cur[3]) { + h = cur[1] - y; + i = -1; continue; + + // left end of existing region falls within new region + } else if (dirties[i][0] >= x && dirties[i][0] < x + w && dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) { + dirties[i][2] = dirties[i][2] - (x + w - dirties[i][0]); + dirties[i][0] = x + w; + i = -1; continue; + + // right end of existing region falls within new region + } else if (dirties[i][0] + dirties[i][2] > x && dirties[i][0] + dirties[i][2] <= x + w && + dirties[i][1] >= y && dirties[i][1] + dirties[i][3] <= y + h) { + dirties[i][2] = x - dirties[i][0]; + i = -1; continue; + + // top end of existing region falls within new region + } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && dirties[i][1] >= y && dirties[i][1] < y + h) { + dirties[i][3] = dirties[i][3] - (y + h - dirties[i][1]); + dirties[i][1] = y + h; + i = -1; continue; + + // bottom end of existing region falls within new region + } else if (dirties[i][0] >= x && dirties[i][0] + dirties[i][2] <= x + w && + dirties[i][1] + dirties[i][3] > y && dirties[i][1] + dirties[i][3] <= y + h) { + dirties[i][3] = y - dirties[i][1]; + i = -1; continue; + } + + } + + // then we attempt the "lossy" combinations + for(int i=0; i 0 && h > 0 && cur[2] > 0 && cur[3] > 0 && + ((max(x + w, cur[0] + cur[2]) - min(x, cur[0])) * + (max(y + h, cur[1] + cur[3]) - min(y, cur[1])) < + w * h + cur[2] * cur[3] + epsilon)) { + int a = min(cur[0], x); + int b = min(cur[1], y); + int c = max(x + w, cur[0] + cur[2]) - min(cur[0], x); + int d = max(y + h, cur[1] + cur[3]) - min(cur[1], y); + dirties[i][2] = 0; + dirties[i][3] = 0; + return dirty(a, b, c, d); + } + } + + dirties[numdirties++] = new int[] { x, y, w, h }; + return true; + } + + /** Returns true if there are no regions that need repainting */ + public boolean empty() { return (numdirties == 0); } + + /** + * Atomically returns the list of dirty rectangles as an array of + * four-int arrays and clears the internal dirty-rectangle + * list. Note that some of the regions returned may be null, or + * may have zero height or zero width, and do not need to be + * repainted. + */ + public synchronized int[][] flush() { + if (numdirties == 0) return null; + int[][] ret = dirties; + for(int i=numdirties; ib) return a; + else return b; + } + + /** included here so that it can be inlined */ + private static final int min(int a, int b, int c) { + if (a<=b && a<=c) return a; + else if (b<=c && b<=a) return b; + else return c; + } + + /** included here so that it can be inlined */ + private static final int max(int a, int b, int c) { + if (a>=b && a>=c) return a; + else if (b>=c && b>=a) return b; + else return c; + } + + /** included here so that it can be inlined */ + private static final int bound(int a, int b, int c) { + if (a > b) return a; + if (c < b) return c; + return b; + } + +} diff --git a/src/org/xwt/util/Hash.java b/src/org/xwt/util/Hash.java new file mode 100644 index 0000000..2d73b10 --- /dev/null +++ b/src/org/xwt/util/Hash.java @@ -0,0 +1,154 @@ +// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL] +package org.xwt.util; + +import java.util.*; + +/** Implementation of an unsynchronized hash table, with one or two + * keys, using Radke's quadradic residue linear probing instead of + * buckets to minimize object count (less allocations, faster GC). + * See C. Radke, Communications of the ACM, 1970, 103-105 + */ +public class Hash { + + /** this object is inserted as key in a slot when the + * corresponding value is removed -- this ensures that the + * probing sequence for any given key remains the same even if + * other keys are removed. + */ + private static Object placeholder = new Object(); + + /** the number of entries with at least one non-null key */ + private int usedslots = 0; + + /** the number of entries with non-null values */ + private int size = 0; + + /** when num_slots < loadFactor * size, rehash into a bigger table */ + private final int loadFactor; + + /** primary keys */ + private Object[] keys1 = null; + + /** secondary keys; null if no secondary key has ever been added */ + private Object[] keys2 = null; + + /** the values for the table */ + private Object[] vals = null; + + /** the number of entries with a non-null value */ + public int size() { return size; } + + /** empties the table */ + public void clear() { + size = 0; + usedslots = 0; + for(int i=0; i vals.length) rehash(); + int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode()); + int dest = Math.abs(hash) % vals.length; + int odest = dest; + boolean plus = true; + int tries = 1; + while (true) { + Object hk1 = keys1[dest]; + Object hk2 = keys2 == null ? null : keys2[dest]; + if (hk1 == null && hk2 == null) { // empty slot + if (v == null) return; + size++; + usedslots++; + break; + } + + if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) && // replacing former entry + (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) { + + // we don't actually remove things from the table; rather, we insert a placeholder + if (v == null) { + k1 = placeholder; + k2 = null; + size--; + } + break; + } + + dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length); + if (plus) tries++; + plus = !plus; + } + + keys1[dest] = k1; + if (k2 != null && keys2 == null) keys2 = new Object[keys1.length]; + if (keys2 != null) keys2[dest] = k2; + vals[dest] = v; + } + +} + + diff --git a/src/org/xwt/util/JSObject.java b/src/org/xwt/util/JSObject.java new file mode 100644 index 0000000..81f36ea --- /dev/null +++ b/src/org/xwt/util/JSObject.java @@ -0,0 +1,194 @@ +// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL] +package org.xwt.util; + +import org.mozilla.javascript.*; +import java.net.*; +import java.io.*; +import java.util.*; +import org.xwt.*; + +/** Simple implementation of a JavaScript host object. + * + * If privateVars is set, then any "var" declaration issued on this + * scope will create a variable visible only to scripts from the same + * directory (package) as the script that made the declaration. + * + * This is implemented by making JSObject.Top the ultimate + * parentScope of all privateVars-style JSObjects. Puts to JSObjects + * which are var-decls will not climb the scope chain, and will be + * put directly to the JSObject. Puts which are not var-decls + * will climb the scope chain and will be put to Top, which will then + * re-put the value to the JSObject as a global. + */ +public class JSObject implements Scriptable { + + // Static Data /////////////////////////////////////////////////////////////////////// + + /** helper; retrieves the 'source code filename' (usually the nodeName) of the currently-executing function in this thread */ + public static String getCurrentFunctionSourceName() { + Function cf = Context.getCurrentContext().currentFunction; + if (cf == null) return null; + return (cf instanceof InterpretedFunction) ? + ((InterpretedFunction)cf).getSourceName() : ((InterpretedScript)cf).getSourceName(); + } + + /** cache for nodeNameToPackageName(); prevents creation of zillions of String objects */ + private static Hash nodeNameToPackageNameHash = new Hash(1000, 2); + + /** converts a nodeName (source code filename) into the 'package name' (resource name of its directory) */ + private static String nodeNameToPackageName(String nodeName) { + if (nodeName == null) return null; + String ret = (String)nodeNameToPackageNameHash.get(nodeName); + if (ret != null) return ret; + ret = nodeName; + for(int i=0; iname associated with nodeName */ + public Object getPrivately(String name, String nodeName) { + return properties == null ? null : properties.get(name, nodeNameToPackageName(nodeName)); + } + + /** puts a property as a private variable, accessible only to scripts in the source code file nodeName */ + public void putPrivately(String name, Object value, String nodeName) { + if (!privateVars) { + putGlobally(name, null, value); + return; + } + if (properties == null) properties = new Hash(); + + // we use NOT_FOUND to mark a variable which exists as a script-local, yet has a value of null + if (value == null) value = NOT_FOUND; + properties.put(name, nodeNameToPackageName(nodeName), value); + } + + /** forces a property to be put globally -- accessible to all scripts */ + public void putGlobally(String name, Scriptable start, Object value) { + if (name == null || name.equals("")) return; + if (properties == null) properties = new Hash(); + properties.put(name, null, value); + } + + /** if a put is made directly to us (rather than cascading up to Top), it must be a var-declaration */ + public void put(String name, Scriptable start, Object value) { + if (sealed) return; + if (name == null || name.equals("")) return; + putPrivately(name, value, getCurrentFunctionSourceName()); + } + + /** if privateVars is enabled, we always return false, to see if the put propagates up to Top */ + public boolean has(String name, Scriptable start) { + if (!privateVars) return properties != null && properties.get(name) != null; + Top.lastByThread.put(Thread.currentThread(), this); + return false; + } + + public Object[] getIds() { + if (properties == null) return new Object[] { }; + else return properties.keys(); + } + + /** Parent scope of all JSObjects; we use the has(String) method on this object to determine if a put represents a var-declaration or a plain 'ol put */ + private static class Top implements Scriptable { + + /** Last JSObject to perform a has(), keyed by thread. + * Assumes that every Top.has() is immediately preceded by a JSObject.has() in the same thread + */ + public static Hash lastByThread = new Hash(); + + public static Top singleton = new Top(); + private Top() { } + + public boolean has(String name, Scriptable start) { return true; } + public void put(String name, Scriptable start, Object value) { + JSObject last = (JSObject)lastByThread.get(Thread.currentThread()); + if (last.properties != null && last.properties.get(name, nodeNameToPackageName(getCurrentFunctionSourceName())) != null) + last.put(name, start, value); + else last.putGlobally(name, start, value); + } + + public Object get(String name, Scriptable start) { + + // hack since Rhino needs to be able to grab these functions to create new objects + if (name.equals("Object")) return JSObject.defaultObjects.get("Object", null); + if (name.equals("Array")) return JSObject.defaultObjects.get("Array", null); + if (name.equals("Function")) return JSObject.defaultObjects.get("Function", null); + if (name.equals("TypeError")) return JSObject.defaultObjects.get("TypeError", null); + return ((JSObject)lastByThread.get(Thread.currentThread())).get(name, start); + } + + // Trivial methods + public String getClassName() { return "Top"; } + public Scriptable construct(Context cx, Scriptable scope, java.lang.Object[] args) { return null; } + public void delete(String name) { } + public Scriptable getParentScope() { return null; } + public void setParentScope(Scriptable p) { } + public boolean hasInstance(Scriptable value) { return false; } + public Scriptable getPrototype() { return null; } + public void setPrototype(Scriptable p) { } + public void delete(int i) { } + public Object getDefaultValue(Class hint) { return "Top"; } + public void put(int i, Scriptable start, Object value) { } + public Object get(int i, Scriptable start) { return null; } + public boolean has(int i, Scriptable start) { return false; } + public Object[] getIds() { return new Object[] { }; } + + } + + + // Trivial Methods /////////////////////////////////////////////////////////// + + public void setSeal(boolean doseal) { sealed = doseal; } + public void flush() { if (properties != null) properties.clear(); } + public void delete(String name) { if (Log.on) Log.log(this, "JSObject.delete() should not be reachable"); } + public void delete(int i) { if (Log.on) Log.log(this, "JSObject.delete() should not be reachable"); } + public Scriptable getParentScope() { return privateVars ? Top.singleton : null; } + public void setParentScope(Scriptable p) { } + public boolean hasInstance(Scriptable value) { return false; } + public Scriptable getPrototype() { return null; } + public void setPrototype(Scriptable p) { } + public String getClassName() { return this.getClass().getName(); } + public Object getDefaultValue(Class hint) { return toString(); } + public void put(int i, Scriptable start, Object value) { } + public Object get(int i, Scriptable start) { return null; } + public boolean has(int i, Scriptable start) { return false; } + +} + diff --git a/src/org/xwt/util/Log.java b/src/org/xwt/util/Log.java new file mode 100644 index 0000000..81f89e1 --- /dev/null +++ b/src/org/xwt/util/Log.java @@ -0,0 +1,52 @@ +// Copyright 2002 Adam Megacz, see the COPYING file for licensing [LGPL] +package org.xwt.util; +import java.io.*; + +/** easy to use logger */ +public class Log { + + public static boolean on = true; + public static boolean verbose = false; + + /** true iff nothing has yet been logged */ + public static boolean firstMessage = true; + + /** message can be a String or a Throwable */ + public static synchronized void log(Object o, Object message) { + + if (firstMessage) { + firstMessage = false; + System.err.println("==========================================================================="); + log(Log.class, "Logging enabled at " + new java.util.Date()); + } + + String classname; + if (o instanceof Class) classname = ((Class)o).getName(); + else if (o instanceof String) classname = (String)o; + else classname = o.getClass().getName(); + + if (classname.indexOf('.') != -1) classname = classname.substring(classname.lastIndexOf('.') + 1); + if (classname.length() > 20) classname = classname.substring(0, 20); + while (classname.length() < 20) classname = " " + classname; + classname = classname + ": "; + + if (!(message instanceof Throwable)) System.err.println(classname + message); + else { + ByteArrayOutputStream baos = new ByteArrayOutputStream(); + ((Throwable)message).printStackTrace(new PrintStream(baos)); + byte[] b = baos.toByteArray(); + BufferedReader br = new BufferedReader(new InputStreamReader(new ByteArrayInputStream(b))); + String s = null; + try { + while((s = br.readLine()) != null) { + System.err.print(classname); + for(int i=0; i vec.length) { + System.arraycopy(vec, first, newvec, 0, vec.length - first); + System.arraycopy(vec, 0, newvec, vec.length - first, size - (vec.length - first)); + } else { + System.arraycopy(vec, first, newvec, 0, size); + } + first = 0; + vec = newvec; + } + + /** The number of elements in the queue */ + public int size() { return size; } + + /** Empties the queue */ + public synchronized void flush() { + first = 0; + size = 0; + for(int i=0; i= vec.length) vec[first + size - vec.length] = o; + else vec[first + size] = o; + size++; + if (size == 1) notify(); + } + + /** Remove and return and element from the queue, blocking if empty. */ + public Object remove() { return remove(true); } + + /** Remove and return an element from the queue, blocking if + block is true and the queue is empty. */ + public synchronized Object remove(boolean block) { + + while (size == 0) { + if (!block) return null; + try { + wait(); + } catch (InterruptedException e) { + } catch (Exception e) { + if (Log.on) Log.log(this, "exception in Queue.wait(); this should never happen"); + if (Log.on) Log.log(this, e); + } + } + + Object ret = vec[first]; + first++; + size--; + if (first >= vec.length) first = 0; + return ret; + } + + /** Returns the top element in the queue without removing it */ + public synchronized Object peek() { + if (size == 0) return null; + return vec[first]; + } + +} diff --git a/src/org/xwt/util/Semaphore.java b/src/org/xwt/util/Semaphore.java new file mode 100644 index 0000000..278e0e6 --- /dev/null +++ b/src/org/xwt/util/Semaphore.java @@ -0,0 +1,31 @@ +// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL] +package org.xwt.util; + +/** Simple implementation of a blocking, counting semaphore. */ +public class Semaphore { + + private int val = 0; + + public Semaphore() { }; + + /** Decrement the counter, blocking if zero. */ + public synchronized void block() { + while(val == 0) { + try { + wait(); + } catch (InterruptedException e) { + } catch (Throwable e) { + if (Log.on) Log.log(this, "Exception in Semaphore.block(); this should never happen"); + if (Log.on) Log.log(this, e); + } + } + val--; + } + + /** Incremenet the counter. */ + public synchronized void release() { + val++; + notify(); + } + +} diff --git a/src/org/xwt/util/Vec.java b/src/org/xwt/util/Vec.java new file mode 100644 index 0000000..ac8b149 --- /dev/null +++ b/src/org/xwt/util/Vec.java @@ -0,0 +1,102 @@ +// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL] +package org.xwt.util; + +import java.util.*; +import java.io.*; + +/** + * An unsynchronized Vector implementation; same semantics as + * java.util.Vector. Useful for JDK1.1 platforms that don't have + * java.util.ArrayList. + * @see java.util.Vector + */ +public class Vec implements Serializable { + + private Object[] store; + private int size = 0; + + public Vec() { this(10); } + public Vec(int i) { store = new Object[i]; } + + private void grow() { grow(store.length * 2); } + private void grow(int newsize) { + Object[] newstore = new Object[newsize]; + System.arraycopy(store, 0, newstore, 0, size); + store = newstore; + } + + public void removeAllElements() { + for(int i=0; i= store.length) grow(); + store[size++] = o; + } + + public Object elementAt(int i) { + return store[i]; + } + + public Object lastElement() { + if (size == 0) return null; + return store[size - 1]; + } + + public int size() { return size; } + + public void setSize(int newSize) { + if (newSize < 0) throw new RuntimeException("tried to set size to negative value"); + if (newSize > size) grow(newSize * 2); + if (newSize < size) + for(int i=newSize; i= size || i < 0) throw new RuntimeException("tried to remove an element outside the vector's limits"); + for(int j=i; j= size) setSize(i); + store[i] = o; + } + + public void removeElement(Object o) { + for(int i=0; iat; i--) + store[i] = store[i-1]; + store[at] = o; + size++; + } + +} diff --git a/src/org/xwt/util/package.html b/src/org/xwt/util/package.html new file mode 100644 index 0000000..fa3334b --- /dev/null +++ b/src/org/xwt/util/package.html @@ -0,0 +1,2 @@ + +An assortment of useful utility classes. -- 1.7.10.4