JobHu

實(shí)現(xiàn)一個(gè)棧,使其push,pop,min(取得棧中的最小元素)均為O(1)

我的解

把一個(gè)二叉排序樹(也許不叫這個(gè))變?yōu)檫f增的雙向鏈表,不能夠生成額外的結(jié)點(diǎn).
eg 6
       / \
      4   8
     / \ / \
    3  5 7  9

3=4=5=6=7=8=9

我的解:

輸出:
b == c
127 == 0x7F
b == c
128 == 0x80
-128 == c
128 == (c&0xFF)

Here's a list of keywords in the Java programming language. You cannot use any of the following as identifiers in your programs. The keywords const and goto are reserved, even though they are not currently used. true, false, and null might seem like keywords, but they are actually literals; you cannot use them as identifiers in your programs.

abstract	continue	for	new	switch
assert***	default	goto*	package	synchronized
boolean	do	if	private	this
break	double	implements	protected	throw
byte	else	import	public	throws
case	enum****	instanceof	return	transient
catch	extends	int	short	try
char	final	interface	static	void
class	finally	long	strictfp**	volatile
const*	float	native	super	while

來看看ContainerBase的start方法：

 1public synchronized void start() throws LifecycleException {
 2
 3        //如果Container已經(jīng)處于start狀態(tài)，直接返回
 4        if (started) {
 5            if(log.isInfoEnabled())
 6                log.info(sm.getString("containerBase.alreadyStarted", logName()));
 7            return;
 8        }
 9        
10        // Notify our interested LifecycleListeners
11        lifecycle.fireLifecycleEvent(BEFORE_START_EVENT, null);
12
13        started = true;
14
15        // Start our subordinate components, if any
16        if ((loader != null) && (loader instanceof Lifecycle))
17            ((Lifecycle) loader).start();
18        logger = null;
19        getLogger();
20        if ((logger != null) && (logger instanceof Lifecycle))
21            ((Lifecycle) logger).start();
22    //用來管理session
23        if ((manager != null) && (manager instanceof Lifecycle))
24            ((Lifecycle) manager).start();
25    //看名字就知道是干什么的，不過研究集群的優(yōu)先級很低
26        if ((cluster != null) && (cluster instanceof Lifecycle))
27            ((Lifecycle) cluster).start();
28    //用來進(jìn)行訪問控制，或者權(quán)限控制的
29        if ((realm != null) && (realm instanceof Lifecycle))
30            ((Lifecycle) realm).start();
31    //和JNDI相關(guān)
32        if ((resources != null) && (resources instanceof Lifecycle))
33            ((Lifecycle) resources).start();
34
35        //啟動(dòng)所有子container
36        Container children[] = findChildren();
37        for (int i = 0; i < children.length; i++) {
38            if (children[i] instanceof Lifecycle)
39                ((Lifecycle) children[i]).start();
40        }
41
42        // 啟動(dòng)Container內(nèi)部持有的pipeline對象，Container對Pipeline接口的實(shí)現(xiàn)就是通過調(diào)用這個(gè)內(nèi)部持有的Pipeline對象
43        if (pipeline instanceof Lifecycle)
44            ((Lifecycle) pipeline).start();
45
46        // Notify our interested LifecycleListeners
47        lifecycle.fireLifecycleEvent(START_EVENT, null);
48
49        // 注釋說這個(gè)函數(shù)用來check session是否過期，但看的不是太懂
50        threadStart();
51
52        // Notify our interested LifecycleListeners
53        lifecycle.fireLifecycleEvent(AFTER_START_EVENT, null);
54
55}
56

 

所有和cluster、realm相關(guān)都放在最后來研究了，不管怎么樣先把tomcat如何處理request的整個(gè)過程串起來對現(xiàn)在的我來說是最重要的。另外還有Tomcat中的很多部件都用到了JMX API，即SNMP的Java實(shí)現(xiàn)來進(jìn)行性能檢測和管理，這個(gè)也會放在最后研究。

ContainerBase就看這么多了，下面來看看StandardEngine這個(gè)類。除去和cluster、realm、JMX相關(guān)的方法后，StanderdEngine剩下的方法就很很少了。

StandardEngine有一個(gè)Service類型的成員。Java doc中指出Service就是由很多共享同一個(gè)Container的Connector組成。一個(gè)Service對應(yīng)于一個(gè)Container，來自這個(gè)Service的任何一個(gè)Connector的request都會由其對應(yīng)的Container進(jìn)行處理。看到現(xiàn)在的感覺就是Connector對Container提供request對象，并接受Container返回的response對象。在Tomcat中有很多類別都被用來體現(xiàn)現(xiàn)request或者response，例如org.apache.catalina.connector .Request就是Coyote request的一個(gè)wrapper類，Coyote這個(gè)framework幫助封裝了底層的網(wǎng)絡(luò)復(fù)雜性，向上提供一個(gè)統(tǒng)一的接口。我想tomcat既能夠成為一個(gè)standalone的http、jsp/Servlet服務(wù)器，也能夠同apache http server集成，很可能就是依賴于Coyote提供的統(tǒng)一接口。

在構(gòu)造函數(shù)中會將StandardEngine這個(gè)Pipeline的最后一個(gè)Valve，即Basic設(shè)置為StandardEngineValve。來看看StandardEnginValue的invoke方法
 

可以看出在處理到StandardEngine這個(gè)Pipeline的最后一個(gè)Valve時(shí)，會根據(jù)當(dāng)前request所指定的Host，將當(dāng)前的request和response傳遞給該Host這個(gè)Pipeline的第一個(gè)Valve進(jìn)行處理。

我想Tomcat中的Engine、Host、Context、Wrapper處理request生成response的過程大概是這樣的：

Engine在收到request后在其Pipeline中的每一個(gè)Valve對request進(jìn)行處理，也可能會生成response的某些部分，在最后一個(gè)Valve中將request和response傳給下一級Container即Host的第一個(gè)Valve。Host重復(fù)同樣過程，繼續(xù)傳遞給Context，Context再傳遞給Wrapper。由于Wrapper代表的是Servlet對象，因此在Wrapper處所有的處理都結(jié)束了，response對象生成完畢。當(dāng)然了，如果在某一級中無法找到request要求的下一級對象，則整個(gè)處理過程也會立即結(jié)束。

ContainerBase對Pipeline接口的實(shí)現(xiàn)完全依賴于其內(nèi)部的一個(gè)Pipeline類型的成員pipeline（實(shí)現(xiàn)類為StandardPipeline）。
    在Tomcat的doc中這樣介紹Pipeline接口：該接口的invoke（）方法被調(diào)用時(shí)，將會引發(fā)一系列Value對象的序列調(diào)用。要求一個(gè)Pipeline中的存在一個(gè)Value對象（多為最后一個(gè)Value對象）完成對request的處理，并生成相應(yīng)的response，而不能試圖將Request繼續(xù)傳遞給其它Value對象（這個(gè)Value對象被稱為Basic）。通常，每個(gè)Container對象都持有一個(gè)Pipline類型(實(shí)際上為StandardPipeline)的成員。在Pipeline的doc中，方法getBasic，getFirst兩個(gè)方法的Method Summary完全一樣，Apache的牛人們也不能免俗啊。

StandardPipeline除實(shí)現(xiàn)Pipeline接口外，也實(shí)現(xiàn)了Lifecycle接口。這個(gè)類的start和stop方法，首先檢查是否已經(jīng)被start或stop，如果是則會拋出一個(gè)LifecycleException的異常，否則便fire和生命期改變的相關(guān)事件，并調(diào)用其內(nèi)部valve對象（如果該valve對象也實(shí)現(xiàn)了Lifecycle接口）的start和stop方法。addValve方法用來向StandardPipeline中加入Valve對象，新加入的Value對象被放在一個(gè)叫做Basic的特殊Valve（就是一個(gè)Pipeline的最后一個(gè)Valve）的前面，如果在添加Valve的時(shí)候該StandardPipeline已經(jīng)處于start狀態(tài)，則會進(jìn)行一些注冊（調(diào)用apache commons庫的一個(gè)類，完全沒有看懂這個(gè)地方是什么作用>_<）

//以前寫在blogger上的一篇老文了
曾經(jīng)很好奇線程池是怎么實(shí)現(xiàn)的，.net中有現(xiàn)成的線程池可以使用，但是java中沒有。還有就是Servlet的service方法是怎么樣為每一個(gè) Request在不同的線程中獨(dú)立服務(wù)的，由于Servlet接口沒有繼承自Runnable接口，因此無法直接由一個(gè)Servlet對象生成多個(gè)線程。后來在網(wǎng)上找到了一個(gè)java版本的線程池的例子（http://www.informit.com/articles/article.asp?p= 30483&seqNum=1&rl=1）在該例子的基礎(chǔ)上簡化得到了下面這個(gè)版本的java線程池，記錄在這里。

包org.apache.catalina主要由接口組成。我們可以把這些接口分為幾個(gè)大類。

第一類接口主要是對web application及其各個(gè)組成部分的抽象。這些接口以Container為父接口，分別為Context，Engine，Host，Wrapper。

Engine代表的是整個(gè)Catalina Servlet引擎。

Host代表的是Catalina Servlet引擎中的一個(gè)虛擬主機(jī)。

Context

Wrapper代表的是某一個(gè)具體的servlet

下面我從Container的抽象實(shí)現(xiàn)ContainerBase來切入Container，Context，Engine，Host，Wrapper的實(shí)現(xiàn)。

由于Container接口是web application中各部分的抽象的公共部分，因此其實(shí)現(xiàn)類ContrainerBase是一個(gè)抽象類。對于Container接口的各個(gè)子接口的實(shí)現(xiàn)類，則通過繼承ContainerBase來實(shí)現(xiàn)接口Container接口。例如Engine接口繼承Container接口，Engine的實(shí)現(xiàn)類StandardEnginer繼承ContainerBase類。

ContainerBase實(shí)現(xiàn)得接口有Container，Lifecycle，MBeanRegistration, Pipeline，Serializable。其中Lifecycle，Pipeline和Container屬于同一個(gè)包。

Lifecycle接口定義了一個(gè)具有生命期屬性的組件所必須提供的方法：start（啟動(dòng)一個(gè)組件），stop（停止一個(gè)組件）；除此之外該接口還定義了與具有生命期屬性的組件的Listener相關(guān)的3個(gè)方法，用來添加、刪除、查找對該組件的生命期階段變化感興趣的Listener。

Pipeline在Tomcat中是一個(gè)或者多個(gè)Value的組合，Value用來對Request進(jìn)行處理，生成Response或者將Request和Response傳給下一個(gè)Value進(jìn)行處理。Tomcat并沒有象通常一樣將Pipeline和Value作為同一個(gè)接口，即使用Composite模式，而是Pipeline和Value分別作為集合和元素，Pipeline只能加入Value而不能加入Pipeline，Value則不能包含任何子Value。

ContainerBase對lifecycle接口的實(shí)現(xiàn)分為兩類，addLifecycleListener、findLifecycleListener、removeLifecycleListener都是通過調(diào)用ContainerBase的一個(gè)LifecycleSupport成員實(shí)現(xiàn)；start和stop方法則為ContainerBase自己實(shí)現(xiàn)。我一開始以為LifecycleSupport也實(shí)現(xiàn)了lifecycle接口，但實(shí)際上并不是這樣，原因是start和stop方法與具體的組件密切相關(guān)。此外LifecycleSupport中還包括一個(gè)名為fireLifecycleEvent的方法，該方法遍歷所有的LifeCycleListener，并觸發(fā)Lifecycle事件?？傮w上看LifecycleSupport實(shí)現(xiàn)了所有實(shí)現(xiàn)Lifecycle接口的組件的公共部分，維護(hù)一個(gè)LifecycleListener的數(shù)組，提供了添加、修改、獲取LifecycleListener和觸發(fā)各個(gè)Listener的方法。一個(gè)有趣的情況是，LifecycleSupport是一個(gè)final類，無法被繼承，利用java的語言性質(zhì)強(qiáng)制執(zhí)行了面向?qū)ο笾薪M合優(yōu)于繼承的思想。