/* * Licensed to the Apache Software Foundation (ASF) under one * or more contributor license agreements. See the NOTICE file * distributed with this work for additional information * regarding copyright ownership. The ASF licenses this file * to you under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ /* * $Id: CoroutineManager.java 468653 2006-10-28 07:07:05Z minchau $ */ package org.apache.xml.dtm.ref; import java.util.BitSet; import org.apache.xml.res.XMLErrorResources; import org.apache.xml.res.XMLMessages; /** *
Support the coroutine design pattern.
* *A coroutine set is a very simple cooperative non-preemptive * multitasking model, where the switch from one task to another is * performed via an explicit request. Coroutines interact according to * the following rules:
* *Coroutines can be thought of as falling somewhere between pipes and * subroutines. Like call/return, there is an explicit flow of control * from one coroutine to another. Like pipes, neither coroutine is * actually "in charge", and neither must exit in order to transfer * control to the other.
* *One classic application of coroutines is in compilers, where both * the parser and the lexer are maintaining complex state * information. The parser resumes the lexer to process incoming * characters into lexical tokens, and the lexer resumes the parser * when it has reached a point at which it has a reliably interpreted * set of tokens available for semantic processing. Structuring this * as call-and-return would require saving and restoring a * considerable amount of state each time. Structuring it as two tasks * connected by a queue may involve higher overhead (in systems which * can optimize the coroutine metaphor), isn't necessarily as clear in * intent, may have trouble handling cases where data flows in both * directions, and may not handle some of the more complex cases where * more than two coroutines are involved.
* *Most coroutine systems also provide a way to pass data between the * source and target of a resume operation; this is sometimes referred * to as "yielding" a value. Others rely on the fact that, since only * one member of a coroutine set is running at a time and does not * lose control until it chooses to do so, data structures may be * directly shared between them with only minimal precautions.
* *"Note: This should not be taken to mean that producer/consumer * problems should be always be done with coroutines." Queueing is * often a better solution when only two threads of execution are * involved and full two-way handshaking is not required. It's a bit * difficult to find short pedagogical examples that require * coroutines for a clear solution.
* *The fact that only one of a group of coroutines is running at a * time, and the control transfer between them is explicit, simplifies * their possible interactions, and in some implementations permits * them to be implemented more efficiently than general multitasking. * In some situations, coroutines can be compiled out entirely; * in others, they may only require a few instructions more than a * simple function call.
* *This version is built on top of standard Java threading, since * that's all we have available right now. It's been encapsulated for * code clarity and possible future optimization.
* *(Two possible approaches: wait-notify based and queue-based. Some * folks think that a one-item queue is a cleaner solution because it's * more abstract -- but since coroutine _is_ an abstraction I'm not really * worried about that; folks should be able to switch this code without * concern.)
* *%TBD% THIS SHOULD BE AN INTERFACE, to facilitate building other * implementations... perhaps including a true coroutine system * someday, rather than controlled threading. Arguably Coroutine * itself should be an interface much like Runnable, but I think that * can be built on top of this.
* */ public class CoroutineManager { /** "Is this coroutine ID number already in use" lookup table. * Currently implemented as a bitset as a compromise between * compactness and speed of access, but obviously other solutions * could be applied. * */ BitSet m_activeIDs=new BitSet(); /** Limit on the coroutine ID numbers accepted. I didn't want the * in-use table to grow without bound. If we switch to a more efficient * sparse-array mechanism, it may be possible to raise or eliminate * this boundary. * @xsl.usage internal */ static final int m_unreasonableId=1024; /** Internal field used to hold the data being explicitly passed * from one coroutine to another during a co_resume() operation. * (Of course implicit data sharing may also occur; one of the reasons * for using coroutines is that you're guaranteed that none of the * other coroutines in your set are using shared structures at the time * you access them.) * * %REVIEW% It's been proposed that we be able to pass types of data * other than Object -- more specific object types, or * lighter-weight primitives. This would seem to create a potential * explosion of "pass x recieve y back" methods (or require * fracturing resume into two calls, resume-other and * wait-to-be-resumed), and the weight issue could be managed by * reusing a mutable buffer object to contain the primitive * (remember that only one coroutine runs at a time, so once the * buffer's set it won't be walked on). Typechecking objects is * interesting from a code-robustness point of view, but it's * unclear whether it makes sense to encapsulate that in the * coroutine code or let the callers do it, since it depends on RTTI * either way. Restricting the parameters to objects implementing a * specific CoroutineParameter interface does _not_ seem to be a net * win; applications can do so if they want via front-end code, but * there seem to be too many use cases involving passing an existing * object type that you may not have the freedom to alter and may * not want to spend time wrapping another object around. * */ Object m_yield=null; // Expose??? final static int NOBODY=-1; final static int ANYBODY=-1; /** Internal field used to confirm that the coroutine now waking up is * in fact the one we intended to resume. Some such selection mechanism * is needed when more that two coroutines are operating within the same * group. */ int m_nextCoroutine=NOBODY; /**Each coroutine in the set managed by a single * CoroutineManager is identified by a small positive integer. This * brings up the question of how to manage those integers to avoid * reuse... since if two coroutines use the same ID number, resuming * that ID could resume either. I can see arguments for either * allowing applications to select their own numbers (they may want * to declare mnemonics via manefest constants) or generating * numbers on demand. This routine's intended to support both * approaches.
* *%REVIEW% We could use an object as the identifier. Not sure * it's a net gain, though it would allow the thread to be its own * ID. Ponder.
* * @param coroutineID If >=0, requests that we reserve this number. * If <0, requests that we find, reserve, and return an available ID * number. * * @return If >=0, the ID number to be used by this coroutine. If <0, * an error occurred -- the ID requested was already in use, or we * couldn't assign one without going over the "unreasonable value" mark * */ public synchronized int co_joinCoroutineSet(int coroutineID) { if(coroutineID>=0) { if(coroutineID>=m_unreasonableId || m_activeIDs.get(coroutineID)) return -1; } else { // What I want is "Find first clear bit". That doesn't exist. // JDK1.2 added "find last set bit", but that doesn't help now. coroutineID=0; while(coroutineID