効果的な省スペースXMLパーシング
複数のXML文字列を解析するためのシステムおよび方法である。前記方法に従って、入力文字列は、複数の連結リストノード構造に変形される。前記入力文字列の前記シンタックスは、検証される。複数の属性を備える前記複数の連結リストノード構造を用いて、複数の連結リスト属性構造が生成される。前記複数の連結リストノード構造の前記複数の予約ポインタを用いて、前記入力文字列内の複数のデータセグメントが得られる。前記複数の連結リストノード構造および属性構造は解放される。前記複数の連結リストノード構造および複数の属性構造を解放することは、前記複数の連結リストノードおよび属性構造内で定義される、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、広くインターネット技術に関する。より具体的には、本発明は、XML(拡張可能マークアップ言語)パーシングのためのシステムおよび方法に関する。
【発明の開示】
【0002】
拡張ワイヤレスPC(パーソナルコンピュータ)、ディジタルホーム、およびディジタルオフィスの複数の先駆けは、全てXML(拡張可能マークアップ言語)を活用する複数の標準プロトコルに基づく。複数の伝統的なXMLパーサは、複雑であり、複数の組み込み型デバイスにそれほど適していない。多くのデバイスベンダは、XMLパーシングの複雑さおよびオーバーヘッドのため、これら複数の標準プロトコルを彼らの複数のデバイスの中に実装することの困難さを有している。例えば、現在のパーサは、DOM(ドキュメントオブジェクトモデル)およびSAX(Simple API(アプリケーションプログラミングインターフェース) for XML)の2つのカテゴリに分類される。
【0003】
複数のDOMパーサは、XML文字列を解析し、複数のXML要素のまとまりを返すことで動作する。それぞれの要素は、XMLドキュメントの中の特定の要素に関する情報を有する。これを可能にするには、情報の全ては、返される構造にコピーされなければならない。これは、多くのメモリオーバーヘッドをもたらす。
【0004】
複数のSAXパーサは、設計において、とてもよりシンプルである。それらは、複数のステートレスフォワードパーサである。つまり、パーサを用いるアプリケーションは、状態を維持するために、ロジックを有さなければならず、アプリケーションに渡される任意のデータは、アプリケーションのメモリバッファにコピーされなければならない。SAXパーサは、DOMパーサよりもとてもシンプルな設計であるが、SAXパーサは、それでも多くのメモリオーバーヘッドを要求する。
【0005】
したがって、必要とされることは、多くのメモリオーバーヘッドを要求しないXMLを解析するためのシステムおよび方法である。同様に必要とされることは、設計においてシンプルであり、その上、省スペースを要求するXMLを解析するためのシステムおよび方法である。さらに必要とされることは、設計においてシンプルであり、少しのオーバーヘッド要求し、それにより複数のデバイスベンダがXMLパーシングを彼らの複数のデバイスに組み込むことを可能にするXMLを解析するためのシステムおよび方法である。
【図面の簡単な説明】
【0006】
ここに盛り込まれ、明細書の部分を構成する添付の複数の図面は、本発明の複数の実施形態を説明し、その説明と共に、さらに本発明の複数の原理を説明し、ならびに当業者が本発明を生産するおよび使用することを可能にすることに役立つ。複数の図面で、同様の複数の参照番号は、同一の、機能上同様な、および/または構造上同様な複数の要素を広く示す。要素が最初に現れる図面は、対応する参照番号内の左端の(複数の)桁により示される。
【0007】
【図1】本発明の一実施形態に従って複数のXML文字列を解析するための一例のシステムを説明するブロック図である。
【0008】
【図2A】本発明の一実施形態に従って複数のXML文字列を解析するための一例の方法を説明するフロー図である。
【0009】
【図2B】本発明の一実施形態に係る一例の連結リストノード構造を説明する。
【0010】
【図2C】本発明の一実施形態に係る一例の連結リスト属性構造を説明する。
【0011】
【図3A】一例のXML文字列を説明する。
【0012】
【図3B】本発明の一実施形態に従ってソースXMLをトークン化するための方法を説明する一例のフロー図である。
【0013】
【図3C】本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図である。
【図3D】本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図である。
【0014】
【図3E】本発明の一実施形態に係る図3Aに図示される一例のXML文字列のための一例の連結リストノード構造を説明する。
【0015】
【図4】本発明の一実施形態に従ってXML文字列が有効かどうかを判断する一例の方法を説明するフロー図である。
【0016】
【図5A】本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成する一例の方法を説明するフロー図である。
【図5B】本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成する一例の方法を説明するフロー図である。
【0017】
【図5C】図3Aの一例のXML文字列のための本発明の一実施形態に係る一例の連結リスト属性構造を説明する。
【0018】
【図6A】本発明の一実施形態に従って開始および終了連結リストノード構造からデータを得るための一例の方法を説明するフロー図である。
【0019】
【図6B】本発明の一実施形態に従って図3Aの一例のXML文字列から抽出されるデータを説明する。
【発明の詳細な説明】
【0020】
本発明は、ここで特定の複数のアプリケーションのための説明に役立つ複数の実施形態への参照を伴い説明されるが、本発明がそれに制限されないことは、理解されるべきである。ここで提供される複数の内容が入手可能な当業者は、その範囲内の付加的な複数の修正、複数の応用、および複数の実施形態および本発明の複数の実施形態が非常に役立つ付加的な複数の領域を認識するだろう。
【0021】
本発明の明細書中の"1つの実施形態"、"一実施形態"または"他の実施形態"への参照は、実施形態に関連して説明される特定の特徴、構造または特性は、本発明の少なくとも1つの実施形態に含まれることを意味する。したがって、明細書を通してさまざまな場所に現れる複数のフレーズの複数の出現"1つの実施形態において"または"一実施形態において"は、必ずしも同じ実施形態を参照している全てではない。
【0022】
本発明の複数の実施形態は、大量のメモリオーバーヘッドを要求しないXMLを解析するためのシステムおよび方法に向けられる。本発明は、複数のゼロメモリコピーをを用いることでこれを果たし、これにより、省スペースでとても効果的なパーサを生み出す。本発明の複数の実施形態は、XMLに関して説明されるが、複数のマークアップ言語の他の複数のタイプも同様に応用可能である。
【0023】
図1は、XMLを解析するためのシステム100を説明する一例のブロック図である。システム100は、ゼロコピー文字列パーサモジュール102およびパーサロジックモジュール104を備える。ゼロコピー文字列パーサモジュール102は、パーサロジックモジュール104に結合される。
【0024】
ゼロコピー文字列パーサモジュール102は、任意のデータをコピーすることなく複数のXML文字列を解析することに対して責任がある。ゼロコピー文字列パーサモジュール102は、シングルパスパーサであり、したがって、アプリケーションから受信される入力文字列は一度だけ読み込まれる。
【0025】
図1に示されるように、パーサロジックモジュール104は、ゼロコピー文字列パーサモジュール102の上部に構築される。パーサロジックモジュール104は、XML実体を解析するために要求されるロジックを備える。したがって、パーサロジックモジュール104は、XML文字列をメモリにコピーせざる得ないことなく、複数のXML文字列を解析するために、ゼロコピー文字列パーサモジュール102と対話する。
【0026】
ゼロコピー文字列パーサモジュール102は、解析すべき入力文字列および入力文字列の長さをアプリケーションから受信する。パーシングロジックモジュール104は、ゼロコピー文字列パーサモジュール102に、解析するための区切り文字を提供し、それにより、ゼロコピー文字列パーサモジュール102が文字列をトークン化することを可能にする。それぞれのトークンは、ソースXML文字列(すなわち入力文字列)へのインデックスを有し、その値、および値の長さを表す特性を表す。文字列が一旦トークン化されると、複数の連結リストノード構造は、複数のトークンを用いて構築され、複数の連結リスト属性構造は、複数の連結リストノード構造を用いて構築される。複数のノードおよび属性構造は、ソースXML文字列への複数のポインタを有する。複数の連結リストノードおよび属性構造は、ソースXML文字列に関連する複数のポインタを維持する間、メモリから解放される。複数の構造を削除しながら複数のポインタを維持することは、XML文字列がコピーされなくてはならないことを防ぎ、これにより、メモリオーバーヘッドを最小にする。
【0027】
文字列のトークン化の後、ゼロコピー文字列パーサモジュール102は、それぞれのトークンをパーシングロジックモジュール104へ複数の連結リストノード構造を作成するために送る。パーシングロジックモジュール104は、複数のトークンを受信すると、トークンの長さおよび区切り文字と共に、ゼロコピー文字列パーサモジュール102へ、1回に1つのトークンを返す。ゼロコピー文字列パーサモジュール102は、その後、連結リストノード構造のための複数のポインタを得るために、その区切り文字を用いてトークンを解析するこのプロセスは、全てのトークンが適切に解析されるまで続く。複数の連結リストノード構造が一旦作成されると、複数の連結リストノード構造は、XML文字列に含まれる複数の属性への複数のポインタを提供するための複数の連結リスト属性構造を作成するために使用される。同様に、XML文字列内のデータは、複数のポインタを用いて、複数の連結リストノード構造から抽出される。
【0028】
XML文字列を解析するために、少なくとも5つの区切り文字が使用される。複数の区切り文字は、開括弧"<"、スペース" "、コロン":"、等号"="、および閉括弧">"を含むが、これに制限されない。ロジックパーサモジュール104は、複数のトークンを解析し、それぞれのトークンを解析するために、ゼロコピー文字列パーサモジュール102へ適切な区切り文字を提供する。複数のXML文字列を解析するプロセスは、これから図2Aを参照して説明される。
【0029】
図2Aは、本発明の一実施形態に従って複数のXML文字列を解析するための一例の方法を説明するフロー図200である。本発明は、フロー図200に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック202で始まり、直ちにブロック204へ進む。
【0030】
ブロック204では、アプリケーションからゼロコピー文字列パーサモジュール102への入力であるXML文字列が、複数の連結リストノード構造に変形される。XML文字列内のそれぞれの要素は、開始タグのための1つのノード構造およびエンドタグのための1つのノード構造の2つのノード構造に変形される。
【0031】
図2Bは、本発明の一実施形態に係る一例のノード構造220を説明する。ノード構造220は、名称領域222、名称長領域224,名称空間領域226、名称空間長領域228、開始タグ領域230、空タグ領域232、予約領域234、次領域236、親領域238、ピア領域240、および終了タグ領域242を備える。
【0032】
名称領域222は、要素タグの名称を表す。名称長領域224は、要素タグの名称の長さを表す。名称空間領域226は、要素タグに関連する任意の接頭辞の名称を表す。名称空間長領域228は、要素タグに関連する任意の接頭辞の長さを表す。
【0033】
開始タグ領域230は、セットされた場合、要素タグが開始タグであることを示すフラグを表す。開始タグ領域230が消去された場合、タグは終了タグである。空タグ領域232は、セットされた場合、要素タグが空タグであることを示すフラグを表す。空タグは、それ自身のそばにあるタグである。言い換えれば、空タグは、どの内容をも囲まない。空タグは、閉括弧(すなわち、">")の代わりに、スラッシュおよび閉括弧(すなわち、"/>")で終わる。
【0034】
予約領域234は、タグが開始タグの場合、次の閉括弧(すなわち、">")の位置を表す。予約領域234は、タグが終了タグの場合、最初の開括弧(すなわち、"<")の位置を表す。次領域236は、次のノード構造へのポインタを表す。
【0035】
親領域238は、親要素の開要素へのポインタを表す。親要素は、ネスト化された要素を囲む要素である。ピア領域240は、ピア要素の開要素へのポインタを表す。ピア要素は、別の要素と同一の場所に配置される要素である。言い換えれば、複数のピア要素は、同じレベルである。例えば、同じ親要素を有する複数の子要素は複数のピア要素である。終了タグ領域242は、要素タグの閉要素へのポインタを表す。
【0036】
図2のブロック204に戻って、ノード構造220内の特定の複数の領域は、最初に満たされる。これら複数の領域は、名称領域222、名称長領域224、名称空間領域226、名称空間長領域228、開始タグ領域230、空タグ領域232、予約領域234、および次領域236を含む。名称、名称空間、予約、および次は、ソースXML文字列への複数のポインタである。XML文字列から連結リストノード構造を決定する方法は、図3B−図3Dを参照して以下においてさらに説明される。
【0037】
ブロック206において、XML入力文字列のシンタックスは、入力文字列が有効かどうかを判断するために検証される。これは、それぞれの要素が正しく開けられるおよび閉じられるかどうかを検証することで果たされる。複数のXMLドキュメントのための制約は、それらが適格であることである。特定の複数のルールは、XMLドキュメントが適格かどうかを判断する。1つのこのようなルールは、全ての開始タグは終了タグを有し、終了タグは、開始タグと同じ名称、同じ名称空間等を含まなければならないことである。例えば、<A:ElementTag>と名付けられた開始タグは、</A:ElementTag>と名付けられた終了タグで終わらなければならない。同様に、全てのタグは完全にネスト化されなければならない。例えば、1つは、<ElementTag> … <InnerTag> … </InnerTag> … </ElementTag>を有し、<ElementTag> … <InnerTag> … </ElementTag> … </InnerTag>ではない。
【0038】
XML文字列が検証されている間、連結リストノード構造の残りの複数の領域が満たされる。これら複数の領域は、親領域238、ピア領域240および終了タグ領域242を含む。XML文字列のシンタックスを検証するための方法は、図4を参照して以下で説明される。
【0039】
ブロック208において、複数の属性構造の連結リストは、連結リストノード構造から作成される。一例の連結リスト属性構造250は、図2Cで説明される。連結リスト属性構造250は、属性名称領域252、属性名称長領域254、属性値領域260、接頭辞名称領域256、接頭辞名称長領域258、属性値長領域262、および次属性領域264を備える。
【0040】
属性名称領域252は、属性の名称を表す。属性名称長領域254は、属性名称の長さを表す。接頭辞名称領域256は、接頭辞の名称を表す。接頭辞名称長領域258は、接頭辞名称の長さを表す。属性値領域260は、属性の値を表す。属性値長領域262は、属性値の長さを表す。次属性領域264は、幾つか存在する場合、次の属性へのポインタを表す。連結リスト属性構造を作成するための方法は、図5Aおよび図5Bを参照して、以下で説明される。
【0041】
図2Aに戻って、ブロック210において、与えられるノード構造からのデータセグメントが得られる。1つの実施形態では、与えられる要素のデータは、単純な文字列である。1つの実施形態では、与えられる要素のデータは、XMLサブツリーである。データセグメントの決定は、図6Aを参照して、以下に説明される。
【0042】
ブロック212において、複数のノード構造連結リストおよび複数の属性構造連結リストは、消去または解放され、元のXML文字列への複数のポインタのみを残す。
【0043】
連結リストノード構造および連結リスト属性構造を作成するための複数の方法を説明するに先立って、これら複数の方法を説明する時に参照される一例のXML文字列が説明される。図3Aは、一例のXML文字列302を説明する。XML文字列302は、"u:ElementTag"と名付けられた開始タグ304、"id"と名付けられた属性306、"TestValue"と名付けられた属性値308、"InnerTag"と名付けられた開始タグ310、"SampleValue"と名付けられたテキストデータ312、"InnerTag"と名付けられた終了タグ314、および"u:ElementTag"と名付けられた終了タグ316を備える。それぞれの開始タグ304および310は、適合している終了タグ316および314をそれぞれ有する。したがって、それぞれの開始タグは、開括弧"<"により識別され、各終了タグは、スラッシュが続く開括弧"</"により識別される。
【0044】
図3Bは、本発明の一実施形態に従ってソースXMLをトークン化するための方法を説明する一例のフロー図320である。本発明は、フロー図320に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック322で始まり、プロセスは、直ちに、ブロック324へ進む。
【0045】
ブロック324において、アプリケーションからのXML文字列およびパーシングロジック104からの開括弧("<")区切り文字は、ゼロコピー文字列パーサモジュール102への入力である。ゼロコピー文字列パーサモジュール102は、複数のトークンのリストを得るために、開括弧区切り文字を用いてXML文字列を解析する(ブロック326)。複数のトークンのリストは、XML入力文字列内のそれぞれのタグの開始を表す。図3Aからの一例のXML文字列302を用いて、以下の複数のトークンのリストが返される。(1)u:ElementTag;(2)InnerTag;(3)/InnerTag;および(4)/u:ElementTagそれぞれのトークンは、ソースXML文字列へのインデックスを代表し、その値、および値の長さを表す特性を表す。
【0046】
ブロック328において、複数のトークンのリストは、パーサロジックモジュール104へ返される。複数のトークンのリストからのそれぞれのトークンは、別個の連結リストノード構造を作成するために使用され、それは、図3Cおよび図3Dを参照してさらに説明される。
【0047】
図3Cおよび図3Dは、本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図204である。本発明は、フロー図204に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、図3Cのブロック330で始まり、プロセスは、直ちにブロック332へ進む。
【0048】
ブロック332において、トークンおよびスペース区切り文字(すなわち、" ")は、パーサロジックモジュール104からゼロコピー文字列パーサモジュール102への入力である。
【0049】
ブロック334において、トークンは、構造のためのタグ名称を識別するために、スペース(すなわち、" ")区切り文字を用いて解析される。例えば、トークンu:ElementTag id="TestValue"を用いて、ゼロコピー文字列パーサモジュール102は、スペース区切り文字を用いて解析し、トークンの2つの部分をパーサロジックモジュール104に返す。すなわち、一番目の部分は、u:ElementTagであり、二番目の部分は、id="TestValue"である。トークンの一番目の部分、u:ElementTagは、常にタグ名称を備える。トークンの二番目の部分、id="TestValue"は、(複数の)属性を備える。スペースを含まない複数のトークンに対して、ゼロコピー文字列パーサモジュール102は、トークンをそのままで返す。この場合、返されるトークンは、一番目のトークンなので、それは、タグ名称を備える。
【0050】
ブロック336において、パーサロジックモジュール104は、タグ名称を備える一番目の部分をコロン文字(すなわち、":")区切り文字と共にゼロコピー文字列パーサ102へ送る。コロン区切り文字は、タグのローカル名称から名称空間を抽出するために使用される。
【0051】
判断ブロック338において、タグ名称を備えるトークンの一番目の文字が"/"で始まるかが判断される。タグ名称を備えるトークンの一番目の文字が"/"で始まる場合、タグは、終了タグである。この場合、開始タグは、消去され(ブロック340)、一番目の開括弧("<")は、予約ポインタとしてセットされる(342)。プロセスは、その後ブロック348へ進む。
【0052】
判断ブロック338に戻り、タグ名称を備えるトークンの一番目の文字が"/"で始まらない場合、タグは、開始タグである。この場合、開始タグは、セットされ(ブロック344)、次の閉括弧(">")の位置は、予約ポインタとしてセットされる(ブロック346)。プロセスは、その後ブロック348へ進む。
【0053】
ブロック348において、タグ名称を備えるトークンは、コロン区切り文字を用いて解析される。
【0054】
図3Dの判断ブロック350において、タグ名称を備えるトークン内でコロン区切り文字が見つかるかが判断される。トークン内にコロン区切り文字が見つかる場合、コロンの左の全ての文字は、名称空間としてセットされ、コロンの右の全ての文字は、要素のローカル名称またはタグ名称としてセットされる(ブロック352)。例えば、解析された場合、開始タグu:ElementTagは、"u"を名称空間接頭辞としておよび"ElementTag"をローカルタグ名称として示す。トークン内にコロン区切り文字が見つからない場合、トークン内の全ての文字は、タグ名称を表す(ブロック354)。
【0055】
ブロック356において、タグ名称の長さおよび、存在する場合、名称空間の長さが決定される。
【0056】
ブロック358において、タグ名称および名称空間は、存在する場合、パーサロジックモジュール104に返される。ブロック360において、トークンの二番目の部分は、ゼロコピー文字列パーサ102へ渡される。
【0057】
判断ブロック362において、トークンの二番目の部分の一番目の文字が"/"かどうかが判断される。一番目のトークンの二番目の部分の一番目の文字が"/"であると判断される場合、タグは、空タグであり、プロセスは、ブロック364へ進む。
【0058】
ブロック364において、空タグ領域232は、セットされる。プロセスは、その後ブロック368へ進む。
【0059】
判断ブロック362へ戻って、一番目のトークンの二番目の部分の一番目の文字が"/"でないと判断される場合、プロセスは、ブロック366へ進む。
【0060】
ブロック366において、空タグ領域232は、消去され、プロセスは、ブロック368へ進む。
【0061】
ブロック368において、次領域236は、次のタグの開始へのポインタとしてセットされる。例えば、一例のXML文字列302において、開始タグu:ElementTagのための次領域236は、InnerTagへのポインタである。
【0062】
図3Eは、図3Aに示される一例のXML文字列302のための本発明の一実施形態に係る複数の一例の連結リストノード構造を説明する。XML文字列302内のそれぞれの開始タグおよび終了タグのための連結リストノード構造が示される。複数の連結リストノード構造の複数の領域からの複数の矢印は、実際のXML文字列への複数のポインタを示す。
【0063】
一番目の連結リストノード構造370は、開始タグu:ElementTagを代表する。タグ名称は、ElementTagである。ElementTagは、名称長領域224に示されるように、長さにおいて10文字である。名称空間接頭辞は、uであり、名称空間長領域228に示されるように、長さにおいて1文字である。開始タグは、セットされる。空タグは消去される。予約領域234は、開始タグu:ElementTagの閉括弧を指し示す。次領域236は、InnerTagである次のタグを指し示す。終了タグ領域242は、/u:ElementTagであるu:ElementTagの終了タグを指し示す。
【0064】
二番目の連結リストノード構造372は、開始タグInnerTagを代表する。タグ名称は、InnerTagである。InnerTagは、領域224に示されるように、長さにおいて8文字である。InnerTagは、名称空間を有さない(それは、InnerTag内のコロン文字の欠如によりしめされる)。したがって、名称空間長は、領域228に示されるようにゼロ(0)である。開始タグは、セットされる。空タグは、消去される。予約領域234は、開始タグInnerTagの閉括弧を指し示す。次領域236は、/InnerTagである次のタグを指し示す。InnerTagの親は、u:ElementTagである。終了タグ領域242は、/InnerTagであるInnerTagの終了タグを指し示す。
【0065】
三番目の連結リストノード構造374は、終了タグ/InnerTagを代表する。タグ名称は、InnerTagであり、長さは8文字である。前に示したように、InnerTagは、名称空間を有さず、したがって、名称空間長はゼロである。開始タグは、消去される。空タグは、消去される。予約領域234は、終了タグ/InnerTagの開括弧を指し示す。次領域236は、/u:ElementTagである次のタグを指し示す。ノード構造374は、終了タグを表すので、残りの複数の領域238、240、および242は、空である。
【0066】
四番目の連結リストノード構造376は、終了タグ/u:ElementTagを代表する。タグ名称は、ElementTagであり、長さは10文字である。名称空間は、uであり、長さは1文字である。開始タグは、消去される。空タグは、消去される。予約領域234は、終了タグu:ElementTagの開括弧を指し示す。ノード構造376は、終了タグを表し、XML文字列302内の最後のタグなので、次領域236、親領域238、ピア領域240および終了タグ領域242は、空である。
【0067】
図4は、本発明の一実施形態に従ってXML文字列が有効かどうかを判断するための方法を説明する一例のフロー図206である。本発明は、フロー図206に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック402で始まり、プロセスは、直ちにブロック404へ進む。
【0068】
ブロック404において、スタックは、初期化される。これは、スタックを消去することで果たされる。
【0069】
ブロック406において、連結リストノード構造は、受け取られる。判断ブロック408において、連結リストノード構造が開始タグを表すかどうかが判断される。連結リストノード構造が開始タグを表すと判断される場合、プロセスは、判断ブロック410へ進む。
【0070】
判断ブロック410において、開始タグがすでにスタック内に存在するかどうかが判断される。開始タグがスタック内にすでに存在する場合、親領域238は、スタックの上部の現在のアイテムへのポインタで満たされる(ブロック412)。例えば、図3A内のXML文字列302を用いて、ElementTagは、InnerTagの親である。これは、図3Eの連結リストノード構造372においても同様に示される。プロセスは、その後ブロック414へ進む。
【0071】
ブロック410へ戻り、開始タグはスタック内に存在しないと判断される場合(すなわち、スタックは、空である)、プロセスは、ブロック414へ進む。
【0072】
ブロック414において、現在の連結リストノード構造の開始タグは、スタック上に置かれる。プロセスは、次の連結リンクノード構造を受信するために、ブロック406へ戻る。
【0073】
ブロック408へ戻り、連結リストノード構造が終了タグであると判断される場合、プロセスは、ブロック416へ進む。ブロック416において、スタックの上部の開始タグは、スタックからポップオフされる。
【0074】
ブロック418において、ポップされた開始タグのピア領域240は、現在の終了タグの次領域ポインタ236で満たされる。次のXML構造は、ピアを説明する。
<u:ElementTag id=""TestValue">
<InnerTag>SampleValue</InnerTag>
<AnotherTag>AnotherValue</AnotherTag>
</u:ElementTag>
上の例において、InnerTagおよびAnotherTagは複数のピアである。InnerTagおよびAnotherTagは、同様に両方とも、u:ElementTagの子供たちである。プロセスは、判断ブロック420へ進む。
【0075】
判断ブロック420において、ポップオフされた開始タグが現在の終了タグに適合するかどうかが判断される。ポップオフされた開始タグが現在の終了タグと適合する場合、XML文字列は、有効な文字列であるとみなされる(ブロック422)。言い換えれば、XML文字列のシンタックスは、この時点では、正しい。終了タグ領域242は、現在の終了タグで満たされる(ブロック424)。
【0076】
判断ブロック426において、現在の連結リストノード構造が現在のXML文字列のための最後の構造かどうかが判断される。現在の連結リストノード構造が現在のXML文字列のための最後の構造ではないと判断される場合、プロセスは、次の連結リストノード構造を受信するためにブロック406へ戻る。
【0077】
判断ブロック426へ戻り、現在の連結リストノード構造が現在のXML文字列のための最後の構造であると判断される場合、プロセスはブロック430へ進み、プロセスは終了する。
【0078】
判断ブロック420へ戻り、ポップオフされた開始タグが現在の終了タグに適合しないと判断される場合、XML文字列は無効な文字列とみなされる(ブロック428)。プロセスは、ブロック430へ進み、プロセスは、直ちに終了する。
【0079】
アプリケーションが与えられる要素内に含まれる複数の属性へのアクセスを望む場合、アプリケーションは、ゼロコピー文字列パーサ102に連結リストノード構造を与えてよい。ゼロコピー文字列パーサ102は、複数の属性を解析するために、要素の複数の予約ポインタを使用する。ゼロコピー文字列パーサ102は、複数の属性構造の連結リストを返し、複数の値の長さを表す複数の特性と同様に属性名および属性値を表すために、これは、元の文字列への複数のポインタを有する。属性解析がアプリケーションにより要求されないので、複数の属性を解析するためにこの方法を使用することは、大多数のケースにとって、より少ないオーバーヘッドをもたらす。同様に、複数の属性が解析される場合、メモリコピーが無く、これは、旧来の複数の解析方法と比べて、より高い性能およびより少ないリソースの使用をもたらす。
【0080】
図5Aおよび図5Bは、本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成するための一例の方法を説明するフロー図208である。本発明は、フロー図208に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、図5Aのブロック502で始まり、プロセスは、直ちにブロック504へ進む。
【0081】
ブロック504において、開始タグのための連結リストノードは、ゼロコピー文字列パーサ102への入力である。
【0082】
ブロック506において、連結リストノード構造からの予約ポインタの位置を用いて、予約ポインタは、XML文字列内に開括弧が見つかるまで、減らされる。開括弧文字から予約ポインタの間の情報は、属性文字列を定義する。
【0083】
ブロック508において、属性文字列は、スペース文字を用いて複数のトークンへ解析される。前に示されたように、一番目のトークンは、タグ名称である。残りのトークンまたは複数のトークンは、幾らかでもあれば、実際の複数の属性である。ブロック510において、一番目のトークンは、属性ではないので廃棄される。
【0084】
ブロック512において、残りのトークンまたは複数のトークンは、属性名称を属性値から分離させるために、等号文字を用いて解析される。属性名称は、等号の左の複数の文字の全てに等しく、また、属性値は、等号の右の複数の文字の全てに等しい(ブロック514)。
【0085】
ブロック516において、属性名称は、存在するならば接頭辞を得るために、コロン記号(すなわち、":")を用いて解析される。図5Bの判断ブロック518において、属性名称内にコロン文字が見つかるかどうかが判断される。コロン文字が見つかる場合、コロンの左の全ては、接頭辞名称としてセットされ、コロンの右の全ては、属性名称としてセットされる(ブロック520)。属性名称内にコロン文字が存在しないと判断される場合、ブロック522において、全体のトークンが属性名称としてセットされる。
【0086】
ブロック524において、属性名称、属性値、および接頭辞名称の長さが決定される。接頭辞名称が存在しない場合、接頭辞名称の長さは、ゼロにセットされる。
【0087】
ブロック526において、XML文字列内に別の属性が存在する場合、次属性領域264は、次の属性へのポインタとしてセットされる。
【0088】
図5Cは、図3Aの一例のXML文字列302のための本発明の一実施形態に係る一例の連結リスト属性構造530を説明する。図5Cに示されるように、唯一の属性、すなわち、id="TestValue"は、XML文字列302に含まれる。連結リスト属性構造530内の複数のポインタは、XML文字列302内の位置を指し示す複数の矢印を用いて示される。残りの複数の領域254,258,および262は、それぞれ、属性名称、接頭辞名称、および属性値の長さを示す。XML文字列302は、1つの属性のみを有するので、次属性領域264は、XML文字列302内の位置へのポインタを含まない。
【0089】
アプリケーションが要素内に含まれるデータへのアクセスを望む場合、一つの実施形態では、アプリケーションは、開始連結リストノード構造をゼロコピー文字列パーサモジュール102へ与える。開始連結リストノード構造内の複数のポインタを用いて、ゼロコピー文字列パーサモジュール102は、終了タグを配置する。他の実施形態では、アプリケーションは、開始および終了連結リストノード構造をゼロコピー文字列パーサモジュール102へ与える。ゼロコピー文字列パーサモジュール102は、データセグメントを決定するために、パーサ102に渡される複数の構造のための開始および終了タグの複数の予約ポインタを使用し、データセグメントをアプリケーションへ返す。
【0090】
図6Aは、本発明の一実施形態に従って開始および終了連結リストノード構造からデータセグメントを得るための一例の方法を説明するフロー図210である。本発明は、フロー図210に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック602で始まり、プロセスは、直ちにブロック604へ進む。
【0091】
ブロック604において、対応する開始および終了タグのための両方の連結リストノード構造が受け取られる。
【0092】
ブロック606において、開始および終了タグの複数の予約ポインタを用いて、データセグメントは、決定される。開始タグのための予約ポインタは、閉括弧を指し示し、終了タグのための予約ポインタは、開括弧を指し示す。したがって、データセグメントは、これら2つの予約ポインタの間の全てである。図6Bは、本発明の一実施形態に従って図3Aの一例のXML文字列から抽出されるデータを説明する。InnerTagの開始タグのための予約ポインタ610は、InnerTagの閉括弧を指し示しており、さらに、/InnerTagの終了タグのための予約ポインタ612は、/InnerTagの開または開始括弧を指し示している。したがって、SampleValue614は、複数の予約ポインタ610および612それぞれの間に位置するので、データセグメントである。
【0093】
ブロック608において、データセグメントは、アプリケーションへ返される。
【0094】
本発明の複数の実施形態の特定の複数の側面は、ハードウェア、ソフトウェア、またはその組み合わせを用いて実装され、1つ以上のコンピュータシステムまたは他の複数のプロセッシングシステム内に実装される。実際、1つの実施形態において、複数の方法は、複数の携帯できるまたは固定されたコンピュータ、複数のパーソナルディジタルアシスタント(PDA)、複数のセットトップボックス、複数の携帯電話および複数のページャ、ならびにそれぞれがプロセッサ、プロセッサにより読み込み可能な記憶媒体(揮発性および不揮発性メモリおよび/または複数の記憶要素を含む)、少なくとも1つの入力デバイス、および1つ以上の出力デバイスを備える他の複数の電子デバイスなどの複数のプログラム可能マシン上で実行している複数のプログラムで実装される説明された複数の機能を実行するためにおよび出力情報を生成するために、プログラムコードは、入力デバイスを用いて入力されるデータに適用される。出力情報は、1つ以上の出力デバイスに適用される。当業者であれば、本発明の複数の実施形態は、複数のマルチプロセッサシステム、複数のミニコンピュータ、複数のメインフレームコンピュータ、および同様なものを含むさまざまなコンピュータシステム構成で実行されることを理解するだろう。本発明の複数の実施形態は、同様に、複数の分散コンピューティング環境で実行され、複数のタスクは、コミュニケーションネットワークを介してリンクされる複数のリモートプロセッシングデバイスにより実行される。
【0095】
それぞれのプログラムは、プロセッシングシステムと通信するために、高水準手続き型またはオブジェクト指向プログラミング言語で実装される。しかしながら、所望されれば、複数のプログラムは、アセンブリまたは機械言語で実装される。どんな場合でも、言語は、コンパイルまたは解釈される。
【0096】
複数のプログラム命令は、複数の命令でプログラムされる汎用または特定用途プロセッシングシステムにここで説明された複数の方法を実行させるために使用される。あるいは、複数の方法は、複数の方法を実行するためのハードウェアロジックを備える特定の複数のハードウェアコンポーネントにより、または複数のプログラムされたコンピュータコンポーネントおよび複数のカスタムハードウェアコンポーネントの任意の組み合わせにより実行される。ここで説明される複数の方法は、プロセッサシステムまたは他の電子デバイスが本複数の方法を実行するようにプログラムするために使用される複数の命令がそこに記憶される機械可読媒体を含むコンピュータプログラム製品として提供される。ここで用いられる用語"機械可読媒体"または"機械アクセス可能媒体"は、機械による実行のために複数の命令の列を記憶またはエンコードでき、機械にここで説明される複数の方法の任意の一つを実行させる任意の媒体を含む。複数の用語"機械可読媒体"および"機械アクセス可能媒体"は、それ故に、複数の半導体メモリ、複数の光学および磁気ディスク、およびデータ信号をエンコードする搬送波を含むが、制限はされない。その上、どのような形(例えば、プログラム、プロシージャ、プロセス、アプリケーション、モジュール、ロジック等)にせよ、動作を起こすまたは結果をもたらすように技術的にソフトウェアについて言及することは、一般的である。このような複数の表現は、単に、プロセッサに行為を遂行させるまたは結果を生成させるプロセッシングシステムによるソフトウェアの実行を述べる簡単な方法である。
【0097】
上記において、本発明のさまざまな実施形態が説明されたが、それらは、ほんの例として示され、制限ではないことは、理解されるべきである。添付の複数の請求項に定義される本発明の精神および範囲から逸脱することなく、形式および詳細のさまざまな変更がそこになされることは、当業者には理解されるだろう。したがって、本発明の広さおよび範囲は、上記において説明された例の複数の実施形態のいずれかにより制限されるべきではなく、複数の請求項およびそれらの複数の均等物に従って定義されるべきである。
【技術分野】
【0001】
本発明は、広くインターネット技術に関する。より具体的には、本発明は、XML(拡張可能マークアップ言語)パーシングのためのシステムおよび方法に関する。
【発明の開示】
【0002】
拡張ワイヤレスPC(パーソナルコンピュータ)、ディジタルホーム、およびディジタルオフィスの複数の先駆けは、全てXML(拡張可能マークアップ言語)を活用する複数の標準プロトコルに基づく。複数の伝統的なXMLパーサは、複雑であり、複数の組み込み型デバイスにそれほど適していない。多くのデバイスベンダは、XMLパーシングの複雑さおよびオーバーヘッドのため、これら複数の標準プロトコルを彼らの複数のデバイスの中に実装することの困難さを有している。例えば、現在のパーサは、DOM(ドキュメントオブジェクトモデル)およびSAX(Simple API(アプリケーションプログラミングインターフェース) for XML)の2つのカテゴリに分類される。
【0003】
複数のDOMパーサは、XML文字列を解析し、複数のXML要素のまとまりを返すことで動作する。それぞれの要素は、XMLドキュメントの中の特定の要素に関する情報を有する。これを可能にするには、情報の全ては、返される構造にコピーされなければならない。これは、多くのメモリオーバーヘッドをもたらす。
【0004】
複数のSAXパーサは、設計において、とてもよりシンプルである。それらは、複数のステートレスフォワードパーサである。つまり、パーサを用いるアプリケーションは、状態を維持するために、ロジックを有さなければならず、アプリケーションに渡される任意のデータは、アプリケーションのメモリバッファにコピーされなければならない。SAXパーサは、DOMパーサよりもとてもシンプルな設計であるが、SAXパーサは、それでも多くのメモリオーバーヘッドを要求する。
【0005】
したがって、必要とされることは、多くのメモリオーバーヘッドを要求しないXMLを解析するためのシステムおよび方法である。同様に必要とされることは、設計においてシンプルであり、その上、省スペースを要求するXMLを解析するためのシステムおよび方法である。さらに必要とされることは、設計においてシンプルであり、少しのオーバーヘッド要求し、それにより複数のデバイスベンダがXMLパーシングを彼らの複数のデバイスに組み込むことを可能にするXMLを解析するためのシステムおよび方法である。
【図面の簡単な説明】
【0006】
ここに盛り込まれ、明細書の部分を構成する添付の複数の図面は、本発明の複数の実施形態を説明し、その説明と共に、さらに本発明の複数の原理を説明し、ならびに当業者が本発明を生産するおよび使用することを可能にすることに役立つ。複数の図面で、同様の複数の参照番号は、同一の、機能上同様な、および/または構造上同様な複数の要素を広く示す。要素が最初に現れる図面は、対応する参照番号内の左端の(複数の)桁により示される。
【0007】
【図1】本発明の一実施形態に従って複数のXML文字列を解析するための一例のシステムを説明するブロック図である。
【0008】
【図2A】本発明の一実施形態に従って複数のXML文字列を解析するための一例の方法を説明するフロー図である。
【0009】
【図2B】本発明の一実施形態に係る一例の連結リストノード構造を説明する。
【0010】
【図2C】本発明の一実施形態に係る一例の連結リスト属性構造を説明する。
【0011】
【図3A】一例のXML文字列を説明する。
【0012】
【図3B】本発明の一実施形態に従ってソースXMLをトークン化するための方法を説明する一例のフロー図である。
【0013】
【図3C】本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図である。
【図3D】本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図である。
【0014】
【図3E】本発明の一実施形態に係る図3Aに図示される一例のXML文字列のための一例の連結リストノード構造を説明する。
【0015】
【図4】本発明の一実施形態に従ってXML文字列が有効かどうかを判断する一例の方法を説明するフロー図である。
【0016】
【図5A】本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成する一例の方法を説明するフロー図である。
【図5B】本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成する一例の方法を説明するフロー図である。
【0017】
【図5C】図3Aの一例のXML文字列のための本発明の一実施形態に係る一例の連結リスト属性構造を説明する。
【0018】
【図6A】本発明の一実施形態に従って開始および終了連結リストノード構造からデータを得るための一例の方法を説明するフロー図である。
【0019】
【図6B】本発明の一実施形態に従って図3Aの一例のXML文字列から抽出されるデータを説明する。
【発明の詳細な説明】
【0020】
本発明は、ここで特定の複数のアプリケーションのための説明に役立つ複数の実施形態への参照を伴い説明されるが、本発明がそれに制限されないことは、理解されるべきである。ここで提供される複数の内容が入手可能な当業者は、その範囲内の付加的な複数の修正、複数の応用、および複数の実施形態および本発明の複数の実施形態が非常に役立つ付加的な複数の領域を認識するだろう。
【0021】
本発明の明細書中の"1つの実施形態"、"一実施形態"または"他の実施形態"への参照は、実施形態に関連して説明される特定の特徴、構造または特性は、本発明の少なくとも1つの実施形態に含まれることを意味する。したがって、明細書を通してさまざまな場所に現れる複数のフレーズの複数の出現"1つの実施形態において"または"一実施形態において"は、必ずしも同じ実施形態を参照している全てではない。
【0022】
本発明の複数の実施形態は、大量のメモリオーバーヘッドを要求しないXMLを解析するためのシステムおよび方法に向けられる。本発明は、複数のゼロメモリコピーをを用いることでこれを果たし、これにより、省スペースでとても効果的なパーサを生み出す。本発明の複数の実施形態は、XMLに関して説明されるが、複数のマークアップ言語の他の複数のタイプも同様に応用可能である。
【0023】
図1は、XMLを解析するためのシステム100を説明する一例のブロック図である。システム100は、ゼロコピー文字列パーサモジュール102およびパーサロジックモジュール104を備える。ゼロコピー文字列パーサモジュール102は、パーサロジックモジュール104に結合される。
【0024】
ゼロコピー文字列パーサモジュール102は、任意のデータをコピーすることなく複数のXML文字列を解析することに対して責任がある。ゼロコピー文字列パーサモジュール102は、シングルパスパーサであり、したがって、アプリケーションから受信される入力文字列は一度だけ読み込まれる。
【0025】
図1に示されるように、パーサロジックモジュール104は、ゼロコピー文字列パーサモジュール102の上部に構築される。パーサロジックモジュール104は、XML実体を解析するために要求されるロジックを備える。したがって、パーサロジックモジュール104は、XML文字列をメモリにコピーせざる得ないことなく、複数のXML文字列を解析するために、ゼロコピー文字列パーサモジュール102と対話する。
【0026】
ゼロコピー文字列パーサモジュール102は、解析すべき入力文字列および入力文字列の長さをアプリケーションから受信する。パーシングロジックモジュール104は、ゼロコピー文字列パーサモジュール102に、解析するための区切り文字を提供し、それにより、ゼロコピー文字列パーサモジュール102が文字列をトークン化することを可能にする。それぞれのトークンは、ソースXML文字列(すなわち入力文字列)へのインデックスを有し、その値、および値の長さを表す特性を表す。文字列が一旦トークン化されると、複数の連結リストノード構造は、複数のトークンを用いて構築され、複数の連結リスト属性構造は、複数の連結リストノード構造を用いて構築される。複数のノードおよび属性構造は、ソースXML文字列への複数のポインタを有する。複数の連結リストノードおよび属性構造は、ソースXML文字列に関連する複数のポインタを維持する間、メモリから解放される。複数の構造を削除しながら複数のポインタを維持することは、XML文字列がコピーされなくてはならないことを防ぎ、これにより、メモリオーバーヘッドを最小にする。
【0027】
文字列のトークン化の後、ゼロコピー文字列パーサモジュール102は、それぞれのトークンをパーシングロジックモジュール104へ複数の連結リストノード構造を作成するために送る。パーシングロジックモジュール104は、複数のトークンを受信すると、トークンの長さおよび区切り文字と共に、ゼロコピー文字列パーサモジュール102へ、1回に1つのトークンを返す。ゼロコピー文字列パーサモジュール102は、その後、連結リストノード構造のための複数のポインタを得るために、その区切り文字を用いてトークンを解析するこのプロセスは、全てのトークンが適切に解析されるまで続く。複数の連結リストノード構造が一旦作成されると、複数の連結リストノード構造は、XML文字列に含まれる複数の属性への複数のポインタを提供するための複数の連結リスト属性構造を作成するために使用される。同様に、XML文字列内のデータは、複数のポインタを用いて、複数の連結リストノード構造から抽出される。
【0028】
XML文字列を解析するために、少なくとも5つの区切り文字が使用される。複数の区切り文字は、開括弧"<"、スペース" "、コロン":"、等号"="、および閉括弧">"を含むが、これに制限されない。ロジックパーサモジュール104は、複数のトークンを解析し、それぞれのトークンを解析するために、ゼロコピー文字列パーサモジュール102へ適切な区切り文字を提供する。複数のXML文字列を解析するプロセスは、これから図2Aを参照して説明される。
【0029】
図2Aは、本発明の一実施形態に従って複数のXML文字列を解析するための一例の方法を説明するフロー図200である。本発明は、フロー図200に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック202で始まり、直ちにブロック204へ進む。
【0030】
ブロック204では、アプリケーションからゼロコピー文字列パーサモジュール102への入力であるXML文字列が、複数の連結リストノード構造に変形される。XML文字列内のそれぞれの要素は、開始タグのための1つのノード構造およびエンドタグのための1つのノード構造の2つのノード構造に変形される。
【0031】
図2Bは、本発明の一実施形態に係る一例のノード構造220を説明する。ノード構造220は、名称領域222、名称長領域224,名称空間領域226、名称空間長領域228、開始タグ領域230、空タグ領域232、予約領域234、次領域236、親領域238、ピア領域240、および終了タグ領域242を備える。
【0032】
名称領域222は、要素タグの名称を表す。名称長領域224は、要素タグの名称の長さを表す。名称空間領域226は、要素タグに関連する任意の接頭辞の名称を表す。名称空間長領域228は、要素タグに関連する任意の接頭辞の長さを表す。
【0033】
開始タグ領域230は、セットされた場合、要素タグが開始タグであることを示すフラグを表す。開始タグ領域230が消去された場合、タグは終了タグである。空タグ領域232は、セットされた場合、要素タグが空タグであることを示すフラグを表す。空タグは、それ自身のそばにあるタグである。言い換えれば、空タグは、どの内容をも囲まない。空タグは、閉括弧(すなわち、">")の代わりに、スラッシュおよび閉括弧(すなわち、"/>")で終わる。
【0034】
予約領域234は、タグが開始タグの場合、次の閉括弧(すなわち、">")の位置を表す。予約領域234は、タグが終了タグの場合、最初の開括弧(すなわち、"<")の位置を表す。次領域236は、次のノード構造へのポインタを表す。
【0035】
親領域238は、親要素の開要素へのポインタを表す。親要素は、ネスト化された要素を囲む要素である。ピア領域240は、ピア要素の開要素へのポインタを表す。ピア要素は、別の要素と同一の場所に配置される要素である。言い換えれば、複数のピア要素は、同じレベルである。例えば、同じ親要素を有する複数の子要素は複数のピア要素である。終了タグ領域242は、要素タグの閉要素へのポインタを表す。
【0036】
図2のブロック204に戻って、ノード構造220内の特定の複数の領域は、最初に満たされる。これら複数の領域は、名称領域222、名称長領域224、名称空間領域226、名称空間長領域228、開始タグ領域230、空タグ領域232、予約領域234、および次領域236を含む。名称、名称空間、予約、および次は、ソースXML文字列への複数のポインタである。XML文字列から連結リストノード構造を決定する方法は、図3B−図3Dを参照して以下においてさらに説明される。
【0037】
ブロック206において、XML入力文字列のシンタックスは、入力文字列が有効かどうかを判断するために検証される。これは、それぞれの要素が正しく開けられるおよび閉じられるかどうかを検証することで果たされる。複数のXMLドキュメントのための制約は、それらが適格であることである。特定の複数のルールは、XMLドキュメントが適格かどうかを判断する。1つのこのようなルールは、全ての開始タグは終了タグを有し、終了タグは、開始タグと同じ名称、同じ名称空間等を含まなければならないことである。例えば、<A:ElementTag>と名付けられた開始タグは、</A:ElementTag>と名付けられた終了タグで終わらなければならない。同様に、全てのタグは完全にネスト化されなければならない。例えば、1つは、<ElementTag> … <InnerTag> … </InnerTag> … </ElementTag>を有し、<ElementTag> … <InnerTag> … </ElementTag> … </InnerTag>ではない。
【0038】
XML文字列が検証されている間、連結リストノード構造の残りの複数の領域が満たされる。これら複数の領域は、親領域238、ピア領域240および終了タグ領域242を含む。XML文字列のシンタックスを検証するための方法は、図4を参照して以下で説明される。
【0039】
ブロック208において、複数の属性構造の連結リストは、連結リストノード構造から作成される。一例の連結リスト属性構造250は、図2Cで説明される。連結リスト属性構造250は、属性名称領域252、属性名称長領域254、属性値領域260、接頭辞名称領域256、接頭辞名称長領域258、属性値長領域262、および次属性領域264を備える。
【0040】
属性名称領域252は、属性の名称を表す。属性名称長領域254は、属性名称の長さを表す。接頭辞名称領域256は、接頭辞の名称を表す。接頭辞名称長領域258は、接頭辞名称の長さを表す。属性値領域260は、属性の値を表す。属性値長領域262は、属性値の長さを表す。次属性領域264は、幾つか存在する場合、次の属性へのポインタを表す。連結リスト属性構造を作成するための方法は、図5Aおよび図5Bを参照して、以下で説明される。
【0041】
図2Aに戻って、ブロック210において、与えられるノード構造からのデータセグメントが得られる。1つの実施形態では、与えられる要素のデータは、単純な文字列である。1つの実施形態では、与えられる要素のデータは、XMLサブツリーである。データセグメントの決定は、図6Aを参照して、以下に説明される。
【0042】
ブロック212において、複数のノード構造連結リストおよび複数の属性構造連結リストは、消去または解放され、元のXML文字列への複数のポインタのみを残す。
【0043】
連結リストノード構造および連結リスト属性構造を作成するための複数の方法を説明するに先立って、これら複数の方法を説明する時に参照される一例のXML文字列が説明される。図3Aは、一例のXML文字列302を説明する。XML文字列302は、"u:ElementTag"と名付けられた開始タグ304、"id"と名付けられた属性306、"TestValue"と名付けられた属性値308、"InnerTag"と名付けられた開始タグ310、"SampleValue"と名付けられたテキストデータ312、"InnerTag"と名付けられた終了タグ314、および"u:ElementTag"と名付けられた終了タグ316を備える。それぞれの開始タグ304および310は、適合している終了タグ316および314をそれぞれ有する。したがって、それぞれの開始タグは、開括弧"<"により識別され、各終了タグは、スラッシュが続く開括弧"</"により識別される。
【0044】
図3Bは、本発明の一実施形態に従ってソースXMLをトークン化するための方法を説明する一例のフロー図320である。本発明は、フロー図320に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック322で始まり、プロセスは、直ちに、ブロック324へ進む。
【0045】
ブロック324において、アプリケーションからのXML文字列およびパーシングロジック104からの開括弧("<")区切り文字は、ゼロコピー文字列パーサモジュール102への入力である。ゼロコピー文字列パーサモジュール102は、複数のトークンのリストを得るために、開括弧区切り文字を用いてXML文字列を解析する(ブロック326)。複数のトークンのリストは、XML入力文字列内のそれぞれのタグの開始を表す。図3Aからの一例のXML文字列302を用いて、以下の複数のトークンのリストが返される。(1)u:ElementTag;(2)InnerTag;(3)/InnerTag;および(4)/u:ElementTagそれぞれのトークンは、ソースXML文字列へのインデックスを代表し、その値、および値の長さを表す特性を表す。
【0046】
ブロック328において、複数のトークンのリストは、パーサロジックモジュール104へ返される。複数のトークンのリストからのそれぞれのトークンは、別個の連結リストノード構造を作成するために使用され、それは、図3Cおよび図3Dを参照してさらに説明される。
【0047】
図3Cおよび図3Dは、本発明の一実施形態に従って連結リストノード構造を生成するための一例の方法を説明するフロー図204である。本発明は、フロー図204に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、図3Cのブロック330で始まり、プロセスは、直ちにブロック332へ進む。
【0048】
ブロック332において、トークンおよびスペース区切り文字(すなわち、" ")は、パーサロジックモジュール104からゼロコピー文字列パーサモジュール102への入力である。
【0049】
ブロック334において、トークンは、構造のためのタグ名称を識別するために、スペース(すなわち、" ")区切り文字を用いて解析される。例えば、トークンu:ElementTag id="TestValue"を用いて、ゼロコピー文字列パーサモジュール102は、スペース区切り文字を用いて解析し、トークンの2つの部分をパーサロジックモジュール104に返す。すなわち、一番目の部分は、u:ElementTagであり、二番目の部分は、id="TestValue"である。トークンの一番目の部分、u:ElementTagは、常にタグ名称を備える。トークンの二番目の部分、id="TestValue"は、(複数の)属性を備える。スペースを含まない複数のトークンに対して、ゼロコピー文字列パーサモジュール102は、トークンをそのままで返す。この場合、返されるトークンは、一番目のトークンなので、それは、タグ名称を備える。
【0050】
ブロック336において、パーサロジックモジュール104は、タグ名称を備える一番目の部分をコロン文字(すなわち、":")区切り文字と共にゼロコピー文字列パーサ102へ送る。コロン区切り文字は、タグのローカル名称から名称空間を抽出するために使用される。
【0051】
判断ブロック338において、タグ名称を備えるトークンの一番目の文字が"/"で始まるかが判断される。タグ名称を備えるトークンの一番目の文字が"/"で始まる場合、タグは、終了タグである。この場合、開始タグは、消去され(ブロック340)、一番目の開括弧("<")は、予約ポインタとしてセットされる(342)。プロセスは、その後ブロック348へ進む。
【0052】
判断ブロック338に戻り、タグ名称を備えるトークンの一番目の文字が"/"で始まらない場合、タグは、開始タグである。この場合、開始タグは、セットされ(ブロック344)、次の閉括弧(">")の位置は、予約ポインタとしてセットされる(ブロック346)。プロセスは、その後ブロック348へ進む。
【0053】
ブロック348において、タグ名称を備えるトークンは、コロン区切り文字を用いて解析される。
【0054】
図3Dの判断ブロック350において、タグ名称を備えるトークン内でコロン区切り文字が見つかるかが判断される。トークン内にコロン区切り文字が見つかる場合、コロンの左の全ての文字は、名称空間としてセットされ、コロンの右の全ての文字は、要素のローカル名称またはタグ名称としてセットされる(ブロック352)。例えば、解析された場合、開始タグu:ElementTagは、"u"を名称空間接頭辞としておよび"ElementTag"をローカルタグ名称として示す。トークン内にコロン区切り文字が見つからない場合、トークン内の全ての文字は、タグ名称を表す(ブロック354)。
【0055】
ブロック356において、タグ名称の長さおよび、存在する場合、名称空間の長さが決定される。
【0056】
ブロック358において、タグ名称および名称空間は、存在する場合、パーサロジックモジュール104に返される。ブロック360において、トークンの二番目の部分は、ゼロコピー文字列パーサ102へ渡される。
【0057】
判断ブロック362において、トークンの二番目の部分の一番目の文字が"/"かどうかが判断される。一番目のトークンの二番目の部分の一番目の文字が"/"であると判断される場合、タグは、空タグであり、プロセスは、ブロック364へ進む。
【0058】
ブロック364において、空タグ領域232は、セットされる。プロセスは、その後ブロック368へ進む。
【0059】
判断ブロック362へ戻って、一番目のトークンの二番目の部分の一番目の文字が"/"でないと判断される場合、プロセスは、ブロック366へ進む。
【0060】
ブロック366において、空タグ領域232は、消去され、プロセスは、ブロック368へ進む。
【0061】
ブロック368において、次領域236は、次のタグの開始へのポインタとしてセットされる。例えば、一例のXML文字列302において、開始タグu:ElementTagのための次領域236は、InnerTagへのポインタである。
【0062】
図3Eは、図3Aに示される一例のXML文字列302のための本発明の一実施形態に係る複数の一例の連結リストノード構造を説明する。XML文字列302内のそれぞれの開始タグおよび終了タグのための連結リストノード構造が示される。複数の連結リストノード構造の複数の領域からの複数の矢印は、実際のXML文字列への複数のポインタを示す。
【0063】
一番目の連結リストノード構造370は、開始タグu:ElementTagを代表する。タグ名称は、ElementTagである。ElementTagは、名称長領域224に示されるように、長さにおいて10文字である。名称空間接頭辞は、uであり、名称空間長領域228に示されるように、長さにおいて1文字である。開始タグは、セットされる。空タグは消去される。予約領域234は、開始タグu:ElementTagの閉括弧を指し示す。次領域236は、InnerTagである次のタグを指し示す。終了タグ領域242は、/u:ElementTagであるu:ElementTagの終了タグを指し示す。
【0064】
二番目の連結リストノード構造372は、開始タグInnerTagを代表する。タグ名称は、InnerTagである。InnerTagは、領域224に示されるように、長さにおいて8文字である。InnerTagは、名称空間を有さない(それは、InnerTag内のコロン文字の欠如によりしめされる)。したがって、名称空間長は、領域228に示されるようにゼロ(0)である。開始タグは、セットされる。空タグは、消去される。予約領域234は、開始タグInnerTagの閉括弧を指し示す。次領域236は、/InnerTagである次のタグを指し示す。InnerTagの親は、u:ElementTagである。終了タグ領域242は、/InnerTagであるInnerTagの終了タグを指し示す。
【0065】
三番目の連結リストノード構造374は、終了タグ/InnerTagを代表する。タグ名称は、InnerTagであり、長さは8文字である。前に示したように、InnerTagは、名称空間を有さず、したがって、名称空間長はゼロである。開始タグは、消去される。空タグは、消去される。予約領域234は、終了タグ/InnerTagの開括弧を指し示す。次領域236は、/u:ElementTagである次のタグを指し示す。ノード構造374は、終了タグを表すので、残りの複数の領域238、240、および242は、空である。
【0066】
四番目の連結リストノード構造376は、終了タグ/u:ElementTagを代表する。タグ名称は、ElementTagであり、長さは10文字である。名称空間は、uであり、長さは1文字である。開始タグは、消去される。空タグは、消去される。予約領域234は、終了タグu:ElementTagの開括弧を指し示す。ノード構造376は、終了タグを表し、XML文字列302内の最後のタグなので、次領域236、親領域238、ピア領域240および終了タグ領域242は、空である。
【0067】
図4は、本発明の一実施形態に従ってXML文字列が有効かどうかを判断するための方法を説明する一例のフロー図206である。本発明は、フロー図206に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック402で始まり、プロセスは、直ちにブロック404へ進む。
【0068】
ブロック404において、スタックは、初期化される。これは、スタックを消去することで果たされる。
【0069】
ブロック406において、連結リストノード構造は、受け取られる。判断ブロック408において、連結リストノード構造が開始タグを表すかどうかが判断される。連結リストノード構造が開始タグを表すと判断される場合、プロセスは、判断ブロック410へ進む。
【0070】
判断ブロック410において、開始タグがすでにスタック内に存在するかどうかが判断される。開始タグがスタック内にすでに存在する場合、親領域238は、スタックの上部の現在のアイテムへのポインタで満たされる(ブロック412)。例えば、図3A内のXML文字列302を用いて、ElementTagは、InnerTagの親である。これは、図3Eの連結リストノード構造372においても同様に示される。プロセスは、その後ブロック414へ進む。
【0071】
ブロック410へ戻り、開始タグはスタック内に存在しないと判断される場合(すなわち、スタックは、空である)、プロセスは、ブロック414へ進む。
【0072】
ブロック414において、現在の連結リストノード構造の開始タグは、スタック上に置かれる。プロセスは、次の連結リンクノード構造を受信するために、ブロック406へ戻る。
【0073】
ブロック408へ戻り、連結リストノード構造が終了タグであると判断される場合、プロセスは、ブロック416へ進む。ブロック416において、スタックの上部の開始タグは、スタックからポップオフされる。
【0074】
ブロック418において、ポップされた開始タグのピア領域240は、現在の終了タグの次領域ポインタ236で満たされる。次のXML構造は、ピアを説明する。
<u:ElementTag id=""TestValue">
<InnerTag>SampleValue</InnerTag>
<AnotherTag>AnotherValue</AnotherTag>
</u:ElementTag>
上の例において、InnerTagおよびAnotherTagは複数のピアである。InnerTagおよびAnotherTagは、同様に両方とも、u:ElementTagの子供たちである。プロセスは、判断ブロック420へ進む。
【0075】
判断ブロック420において、ポップオフされた開始タグが現在の終了タグに適合するかどうかが判断される。ポップオフされた開始タグが現在の終了タグと適合する場合、XML文字列は、有効な文字列であるとみなされる(ブロック422)。言い換えれば、XML文字列のシンタックスは、この時点では、正しい。終了タグ領域242は、現在の終了タグで満たされる(ブロック424)。
【0076】
判断ブロック426において、現在の連結リストノード構造が現在のXML文字列のための最後の構造かどうかが判断される。現在の連結リストノード構造が現在のXML文字列のための最後の構造ではないと判断される場合、プロセスは、次の連結リストノード構造を受信するためにブロック406へ戻る。
【0077】
判断ブロック426へ戻り、現在の連結リストノード構造が現在のXML文字列のための最後の構造であると判断される場合、プロセスはブロック430へ進み、プロセスは終了する。
【0078】
判断ブロック420へ戻り、ポップオフされた開始タグが現在の終了タグに適合しないと判断される場合、XML文字列は無効な文字列とみなされる(ブロック428)。プロセスは、ブロック430へ進み、プロセスは、直ちに終了する。
【0079】
アプリケーションが与えられる要素内に含まれる複数の属性へのアクセスを望む場合、アプリケーションは、ゼロコピー文字列パーサ102に連結リストノード構造を与えてよい。ゼロコピー文字列パーサ102は、複数の属性を解析するために、要素の複数の予約ポインタを使用する。ゼロコピー文字列パーサ102は、複数の属性構造の連結リストを返し、複数の値の長さを表す複数の特性と同様に属性名および属性値を表すために、これは、元の文字列への複数のポインタを有する。属性解析がアプリケーションにより要求されないので、複数の属性を解析するためにこの方法を使用することは、大多数のケースにとって、より少ないオーバーヘッドをもたらす。同様に、複数の属性が解析される場合、メモリコピーが無く、これは、旧来の複数の解析方法と比べて、より高い性能およびより少ないリソースの使用をもたらす。
【0080】
図5Aおよび図5Bは、本発明の一実施形態に従って連結リストノード構造から複数の属性構造の連結リストを作成するための一例の方法を説明するフロー図208である。本発明は、フロー図208に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、図5Aのブロック502で始まり、プロセスは、直ちにブロック504へ進む。
【0081】
ブロック504において、開始タグのための連結リストノードは、ゼロコピー文字列パーサ102への入力である。
【0082】
ブロック506において、連結リストノード構造からの予約ポインタの位置を用いて、予約ポインタは、XML文字列内に開括弧が見つかるまで、減らされる。開括弧文字から予約ポインタの間の情報は、属性文字列を定義する。
【0083】
ブロック508において、属性文字列は、スペース文字を用いて複数のトークンへ解析される。前に示されたように、一番目のトークンは、タグ名称である。残りのトークンまたは複数のトークンは、幾らかでもあれば、実際の複数の属性である。ブロック510において、一番目のトークンは、属性ではないので廃棄される。
【0084】
ブロック512において、残りのトークンまたは複数のトークンは、属性名称を属性値から分離させるために、等号文字を用いて解析される。属性名称は、等号の左の複数の文字の全てに等しく、また、属性値は、等号の右の複数の文字の全てに等しい(ブロック514)。
【0085】
ブロック516において、属性名称は、存在するならば接頭辞を得るために、コロン記号(すなわち、":")を用いて解析される。図5Bの判断ブロック518において、属性名称内にコロン文字が見つかるかどうかが判断される。コロン文字が見つかる場合、コロンの左の全ては、接頭辞名称としてセットされ、コロンの右の全ては、属性名称としてセットされる(ブロック520)。属性名称内にコロン文字が存在しないと判断される場合、ブロック522において、全体のトークンが属性名称としてセットされる。
【0086】
ブロック524において、属性名称、属性値、および接頭辞名称の長さが決定される。接頭辞名称が存在しない場合、接頭辞名称の長さは、ゼロにセットされる。
【0087】
ブロック526において、XML文字列内に別の属性が存在する場合、次属性領域264は、次の属性へのポインタとしてセットされる。
【0088】
図5Cは、図3Aの一例のXML文字列302のための本発明の一実施形態に係る一例の連結リスト属性構造530を説明する。図5Cに示されるように、唯一の属性、すなわち、id="TestValue"は、XML文字列302に含まれる。連結リスト属性構造530内の複数のポインタは、XML文字列302内の位置を指し示す複数の矢印を用いて示される。残りの複数の領域254,258,および262は、それぞれ、属性名称、接頭辞名称、および属性値の長さを示す。XML文字列302は、1つの属性のみを有するので、次属性領域264は、XML文字列302内の位置へのポインタを含まない。
【0089】
アプリケーションが要素内に含まれるデータへのアクセスを望む場合、一つの実施形態では、アプリケーションは、開始連結リストノード構造をゼロコピー文字列パーサモジュール102へ与える。開始連結リストノード構造内の複数のポインタを用いて、ゼロコピー文字列パーサモジュール102は、終了タグを配置する。他の実施形態では、アプリケーションは、開始および終了連結リストノード構造をゼロコピー文字列パーサモジュール102へ与える。ゼロコピー文字列パーサモジュール102は、データセグメントを決定するために、パーサ102に渡される複数の構造のための開始および終了タグの複数の予約ポインタを使用し、データセグメントをアプリケーションへ返す。
【0090】
図6Aは、本発明の一実施形態に従って開始および終了連結リストノード構造からデータセグメントを得るための一例の方法を説明するフロー図210である。本発明は、フロー図210に関し、ここで説明される実施形態に制限されない。それどころか、当業者には、ここで提供される複数の内容を読んだ後、他の複数の機能フロー図が本発明の範囲内であることは、明白である。プロセスは、ブロック602で始まり、プロセスは、直ちにブロック604へ進む。
【0091】
ブロック604において、対応する開始および終了タグのための両方の連結リストノード構造が受け取られる。
【0092】
ブロック606において、開始および終了タグの複数の予約ポインタを用いて、データセグメントは、決定される。開始タグのための予約ポインタは、閉括弧を指し示し、終了タグのための予約ポインタは、開括弧を指し示す。したがって、データセグメントは、これら2つの予約ポインタの間の全てである。図6Bは、本発明の一実施形態に従って図3Aの一例のXML文字列から抽出されるデータを説明する。InnerTagの開始タグのための予約ポインタ610は、InnerTagの閉括弧を指し示しており、さらに、/InnerTagの終了タグのための予約ポインタ612は、/InnerTagの開または開始括弧を指し示している。したがって、SampleValue614は、複数の予約ポインタ610および612それぞれの間に位置するので、データセグメントである。
【0093】
ブロック608において、データセグメントは、アプリケーションへ返される。
【0094】
本発明の複数の実施形態の特定の複数の側面は、ハードウェア、ソフトウェア、またはその組み合わせを用いて実装され、1つ以上のコンピュータシステムまたは他の複数のプロセッシングシステム内に実装される。実際、1つの実施形態において、複数の方法は、複数の携帯できるまたは固定されたコンピュータ、複数のパーソナルディジタルアシスタント(PDA)、複数のセットトップボックス、複数の携帯電話および複数のページャ、ならびにそれぞれがプロセッサ、プロセッサにより読み込み可能な記憶媒体(揮発性および不揮発性メモリおよび/または複数の記憶要素を含む)、少なくとも1つの入力デバイス、および1つ以上の出力デバイスを備える他の複数の電子デバイスなどの複数のプログラム可能マシン上で実行している複数のプログラムで実装される説明された複数の機能を実行するためにおよび出力情報を生成するために、プログラムコードは、入力デバイスを用いて入力されるデータに適用される。出力情報は、1つ以上の出力デバイスに適用される。当業者であれば、本発明の複数の実施形態は、複数のマルチプロセッサシステム、複数のミニコンピュータ、複数のメインフレームコンピュータ、および同様なものを含むさまざまなコンピュータシステム構成で実行されることを理解するだろう。本発明の複数の実施形態は、同様に、複数の分散コンピューティング環境で実行され、複数のタスクは、コミュニケーションネットワークを介してリンクされる複数のリモートプロセッシングデバイスにより実行される。
【0095】
それぞれのプログラムは、プロセッシングシステムと通信するために、高水準手続き型またはオブジェクト指向プログラミング言語で実装される。しかしながら、所望されれば、複数のプログラムは、アセンブリまたは機械言語で実装される。どんな場合でも、言語は、コンパイルまたは解釈される。
【0096】
複数のプログラム命令は、複数の命令でプログラムされる汎用または特定用途プロセッシングシステムにここで説明された複数の方法を実行させるために使用される。あるいは、複数の方法は、複数の方法を実行するためのハードウェアロジックを備える特定の複数のハードウェアコンポーネントにより、または複数のプログラムされたコンピュータコンポーネントおよび複数のカスタムハードウェアコンポーネントの任意の組み合わせにより実行される。ここで説明される複数の方法は、プロセッサシステムまたは他の電子デバイスが本複数の方法を実行するようにプログラムするために使用される複数の命令がそこに記憶される機械可読媒体を含むコンピュータプログラム製品として提供される。ここで用いられる用語"機械可読媒体"または"機械アクセス可能媒体"は、機械による実行のために複数の命令の列を記憶またはエンコードでき、機械にここで説明される複数の方法の任意の一つを実行させる任意の媒体を含む。複数の用語"機械可読媒体"および"機械アクセス可能媒体"は、それ故に、複数の半導体メモリ、複数の光学および磁気ディスク、およびデータ信号をエンコードする搬送波を含むが、制限はされない。その上、どのような形(例えば、プログラム、プロシージャ、プロセス、アプリケーション、モジュール、ロジック等)にせよ、動作を起こすまたは結果をもたらすように技術的にソフトウェアについて言及することは、一般的である。このような複数の表現は、単に、プロセッサに行為を遂行させるまたは結果を生成させるプロセッシングシステムによるソフトウェアの実行を述べる簡単な方法である。
【0097】
上記において、本発明のさまざまな実施形態が説明されたが、それらは、ほんの例として示され、制限ではないことは、理解されるべきである。添付の複数の請求項に定義される本発明の精神および範囲から逸脱することなく、形式および詳細のさまざまな変更がそこになされることは、当業者には理解されるだろう。したがって、本発明の広さおよび範囲は、上記において説明された例の複数の実施形態のいずれかにより制限されるべきではなく、複数の請求項およびそれらの複数の均等物に従って定義されるべきである。
【特許請求の範囲】
【請求項1】
複数のマークアップ言語記述を分けるための方法であって、
入力文字列を複数の連結リストノード構造に変形する段階と、
前記入力文字列のシンタックスを検証する段階と、
複数の属性を有する前記複数の連結リストノード構造から、連結リスト属性構造を作成する段階と、
データを有する前記複数の連結リストノード構造からデータセグメントを得る段階と、
前記複数の連結リストノード構造および複数の属性構造を解放する段階と
を備える方法。
【請求項2】
前記複数の連結リストノード構造および複数の属性構造を解放する段階は、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への前記複数の連結リストノードおよび属性構造の中で定義される複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する請求項1に記載の方法。
【請求項3】
前記複数の連結リストノード構造の中の前記複数のポインタは、タグ名称、名称空間、予約位置、次タグ、親タグ、ピア要素、および終了タグへの1つ以上のポインタを備える請求項2に記載の方法。
【請求項4】
前記複数の連結リスト属性構造の中の複数のポインタは、属性名称、属性値、接頭辞名称、および次属性への1つ以上のポインタを備える請求項2に記載の方法。
【請求項5】
前記予約位置への前記ポインタは、開始タグのために次の閉括弧へのポインタおよび終了タグのために開括弧へのポインタを備える請求項3に記載の方法。
【請求項6】
入力文字列を複数の連結リストノード構造に変形する段階は、
前記入力文字列および区切り文字として開括弧文字を受け取る段階と、
前記開括弧の区切り文字を用いて、前記入力文字列を解析する段階と、
複数のトークンの連結リストを返す段階と
を備え、
前記連結リストのそれぞれのトークンは、1つの連結リストノード構造を提供するために解析される請求項1に記載の方法。
【請求項7】
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析する段階は、
前記トークンがスラッシュ("/")で始まるかどうかを判断する段階と、
前記トークンが前記スラッシュで始まらない場合、前記連結リストノード構造の中の開始タグ領域をセットし、および前記トークンが前記スラッシュで始まる場合、前記開始タグ領域を消去する段階と、
スペース文字が前記トークンの中で見つかる場合、前記トークンを一番目の部分および二番目の部分に分けるために、前記区切り文字として前記スペース文字を用いて前記トークンを解析する段階と
を備え、
前記スペース文字が前記トークンの中で見つかる場合、
名称空間のために前記連結リストノード構造の中の名称空間ポインタを前記トークンの前記一番目の部分の中の一番目の文字にセットする段階であって、前記名称空間の前記長さは、前記トークンの前記一番目の部分の中の一番目の文字から前記トークンの前記一番目の部分の中のコロンに先立つ文字にわたる段階と、
タグ名称のために前記連結リストノード構造の中のタグ名称ポインタを前記トークンの前記一番目の部分の中の前記コロンの右の文字にセットする段階であって、前記タグ名称の前記長さは、前記コロンの前記右の前記文字から前記トークンの前記一番目の部分の最後の文字にわたる段階と
を備え、
前記スペース文字が前記トークンの中で見つからない場合、
前記連結リストノード構造の中の前記タグ名称ポインタを前記トークンの中の前記複数の文字にセットする段階であって、前記タグ名称の前記長さは、前記トークンの前記長さである段階と、
前記連結リストノード構造の中の前記名称空間ポインタをnullポインタとしてセットする段階であって、前記名称空間の前記長さは、ゼロである段階と
を備え、
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析する段階は、
前記連結リストノード構造の中の次領域ポインタが前記次のトークンの先頭を指し示すようにセットする段階を備える請求項6に記載の方法。
【請求項8】
前記トークンが開始タグの場合、前記連結リストノード構造の中の予約ポインタが前記トークンの前記最後の閉括弧を指し示すようにセットし、および前記トークンが終了タグの場合、前記予約ポインタが前記トークンの前記先頭の開括弧を指し示すようにセットする段階をさらに備える請求項7に記載の方法。
【請求項9】
前記トークンの前記二番目の部分の一番目の文字が前記スラッシュで始まるかどうかを判断する段階と、
前記トークンの前記二番目の部分が前記スラッシュで始まる場合、前記連結リストノード構造の中の空タグ領域をセットする段階と、
前記トークンの前記二番目の部分が前記スラッシュで始まらない場合、前記連結リストノード構造の中の空タグ領域を消去する段階と
をさらに備える請求項7に記載の方法。
【請求項10】
前記入力文字列のシンタックスを検証する段階は、
スタックを初期化する段階と、
入力文字列のための連結リストノード構造を受け取る段階と、
前記連結リストノード構造が開始タグおよび終了タグの1つを表すかどうかを判断する段階と
を備え、
前記連結リストノード構造が現在の開始タグを表す場合、
前記連結リストノード構造の中の親領域を前記スタックの上部の前記開始タグへのポインタで満たす段階と、
前記現在の開始タグを前記スタックに置く段階と
を備え、
前記連結リストノード構造が現在の終了タグを表す場合、
前記スタックの前記上部の前記開始タグをポップオフする段階と、
前記連結リストノード構造の中のピア領域を前記現在の終了タグの次領域ポインタへのポインタで満たす段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合するかどうかを判断する段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合しない場合、前記入力文字列を無効であると示す段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合する場合、前記入力文字列を有効であると示し、前記連結リストノード構造の終了タグを前記現在の終了タグで満たす段階と
を備え、
前記入力文字列が有効であり、かつ、前記連結リストノード構造が前記入力文字列のための前記最後の連結リストノード構造でない場合、前記スタックの前記初期化を除いて、前記入力文字列からの前記次の連結リストノード構造を用いて、上記プロセスを繰り返す段階を備える請求項7に記載の方法。
【請求項11】
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成する段階は、
開始タグのための連結リストノード構造を受け取る段階と、
前記連結リストノード構造の中の予約ポインタを用いる段階であって、開括弧文字が前記入力文字列の中で見つかるまで、前記予約ポインタの位置を減らし、前記開括弧文字と前記予約ポインタとの間の全ての文字は、属性文字列を表す段階と、
前記属性文字列の一番目の部分および前記属性文字列の二番目の部分を提供するために、区切り文字としてスペース文字を用いて、前記属性文字列を解析する段階と、
前記属性文字列の前記一番目の部分を廃棄する段階と、
前記区切り文字として等号を用いて、前記属性文字列の前記二番目の部分を解析する段階と、
前記連結リスト属性構造の中の属性値ポインタを前記属性文字列の前記二番目の部分の前記等号の後の前記一番目の文字へセットする段階であって、属性値長は、前記属性文字列の前記二番目の部分の前記一番目の文字から前記属性文字列の前記二番目の部分の最後にわたる段階と、
前記区切り文字としてコロンを用いて、前記属性文字列の前記一番目の部分を解析する段階と
を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つかる場合、
前記連結リスト属性構造の中の接頭辞名称ポインタを前記属性文字列の前記一番目の部分の中の前記一番目の文字へセットする段階であって、接頭辞名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記一番目の文字から前記属性文字列の前記一番目の部分の中の前記コロンに先立つ文字にわたる段階と、
前記連結リスト属性構造の中の属性名称ポインタを前記属性文字列の前記一番目の部分の中の前記コロンの後の一番目の文字へセットする段階であって、属性名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記コロンの後の前記一番目の文字から前記属性文字列の前記一番目の部分の前記最後の文字にわたる段階と
を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つからない場合、
前記連結リスト属性構造の中の前記接頭辞名称ポインタをnullポインタとしてセットする段階であって、前記接頭辞名称の前記長さは、ゼロである段階と、
前記連結リスト属性構造の中の前記属性名称ポインタを前記属性文字列の前記一番目の部分の前記一番目の文字としてセットする段階であって、前記属性名称の前記長さは、前記属性文字列の前記一番目の部分の前記長さである段階と
を備え、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成する段階は、
前記連結リスト属性構造の中の次属性領域が前記入力文字列の中の前記次の属性を指し示すようにセットする段階を備える請求項1に記載の方法。
【請求項12】
データを有する前記複数の連結リストノード構造からデータセグメントを得る段階は、
対応する開始タグおよび終了タグのための前記複数の連結リストノード構造を受け取る段階と、
前記開始および終了タグの前記複数の連結リストノード構造が前記データセグメントを決定するために、複数の予約ポインタを使用する段階であって、前記データセグメントは、前記開始タグの前記予約ポインタおよび前記終了タグの前記予約ポインタの間の前記データを有する段階と
を備える請求項1に記載の方法。
【請求項13】
前記入力文字列は、XML(拡張可能マークアップ言語)入力文字列を備える請求項1に記載の方法。
【請求項14】
複数の機械アクセス可能命令を有する記憶媒体を備え、前記複数の命令がプロセッサにより実行された場合、前記複数の命令は、
入力文字列を複数の連結リストノード構造に変形すること、
前記入力文字列のシンタックスを検証すること、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成すること、
データを有する前記複数の連結リストノード構造からデータセグメントを得ること、および
前記複数の連結リストノード構造および属性構造を解放すること
を提供する製品。
【請求項15】
前記複数の連結リストノード構造および複数の属性構造を解放することは、前記複数の連結リストノードおよび属性構造の中で定義される、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する請求項14に記載の製品。
【請求項16】
前記複数の連結リストノード構造の中の前記複数のポインタは、タグ名称、名称空間、予約位置、次タグ、親タグ、ピア要素、および終了タグへの1つ以上のポインタを備える請求項15に記載の製品。
【請求項17】
前記複数の連結リスト属性構造の中の複数のポインタは、属性名称、属性値、接頭辞名称、および次属性への1つ以上のポインタを備える請求項15に記載の製品。
【請求項18】
前記予約位置への前記ポインタは、開始タグのために次の閉括弧へのポインタおよび終了タグのために開括弧へのポインタを備える請求項16に記載の製品。
【請求項19】
入力文字列を複数の連結リストノード構造に変形することのための複数の命令は、
前記入力文字列および区切り文字として開括弧文字を受け取ることと、
前記開括弧の区切り文字を用いて、前記入力文字列を解析することと、
複数のトークンの連結リストを返すことと
のための複数の命令を備え、
前記連結リストのそれぞれのトークンは、1つの連結リストノード構造を提供するために解析される請求項14に記載の製品。
【請求項20】
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析することのための複数の命令は、
前記トークンがスラッシュ("/")で始まるかどうかを判断することと、
前記トークンが前記スラッシュで始まらない場合、前記連結リストノード構造の中の開始タグ領域をセットし、および前記トークンが前記スラッシュで始まる場合、前記開始タグ領域を消去することと、
スペース文字が前記トークンの中で見つかる場合、前記トークンを一番目の部分および二番目の部分に分けるために、前記区切り文字として前記スペース文字を用いて前記トークンを解析することと
のための複数の命令を備え、
前記スペース文字が前記トークンの中で見つかる場合、
名称空間のために前記連結リストノード構造の中の名称空間ポインタを前記トークンの前記一番目の部分の中の一番目の文字にセットすることであって、前記名称空間の長さは、前記トークンの前記一番目の部分の中の一番目の文字から前記トークンの前記一番目の部分の中のコロンに先立つ文字にわたることと、
タグ名称のために前記連結リストノード構造の中のタグ名称ポインタを前記トークンの前記一番目の部分の中の前記コロンの右の文字にセットすることであって、前記タグ名称の前記長さは、前記コロンの右の前記文字から前記トークンの前記一番目の部分の最後の文字にわたることと
のための複数の命令を備え、
前記スペース文字が前記トークンの中で見つからない場合、
前記連結リストノード構造の中の前記タグ名称ポインタを前記トークンの中の前記複数の文字にセットすることであって、前記タグ名称の前記長さは、前記トークンの前記長さであることと、
前記連結リストノード構造の中の前記名称空間ポインタをnullポインタとしてセットすることであって、前記名称空間の前記長さは、ゼロであることと
のための複数の命令を備え、
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析することのための複数の命令は、
前記連結リストノード構造の中の次領域ポインタが前記次のトークンの先頭を指し示すようにセットすることのための複数の命令を備える請求項19に記載の製品。
【請求項21】
前記トークンが開始タグの場合、前記連結リストノード構造の中の予約ポインタが前記トークンの前記最後の閉括弧を指し示すようにセットし、および前記トークンが終了タグの場合、前記予約ポインタが前記トークンの前記先頭の開括弧を指し示すようにセットすることのための複数の命令をさらに備える請求項20に記載の製品。
【請求項22】
前記トークンの前記二番目の部分の一番目の文字が前記スラッシュで始まるかどうかを判断することと、
前記トークンの前記二番目の部分が前記スラッシュで始まる場合、前記連結リストノード構造の中の空タグ領域をセットすることと、
前記トークンの前記二番目の部分が前記スラッシュで始まらない場合、前記連結リストノード構造の中の空タグ領域を消去することと
のための複数の命令をさらに備える請求項20に記載の製品。
【請求項23】
前記入力文字列のシンタックスを検証することのための複数の命令は、
スタックを初期化することと、
入力文字列のための連結リストノード構造を受け取ることと、
前記連結リストノード構造が開始タグおよび終了タグの1つを表すかどうかを判断することと
のための複数の命令を備え、
前記連結リストノード構造が現在の開始タグを表す場合、
前記連結リストノード構造の中の親領域を前記スタックの上部の前記開始タグへのポインタで満たすことと、
前記現在の開始タグを前記スタックに置くことと
のための複数の命令を備え、
前記連結リストノード構造が現在の終了タグを表す場合、
前記スタックの前記上部の前記開始タグをポップオフすることと、
前記連結リストノード構造の中のピア領域を前記現在の終了タグの次領域ポインタへのポインタで満たすことと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合するかどうかを判断することと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合しない場合、前記入力文字列を無効であると示すことと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合する場合、前記入力文字列を有効であると示し、前記連結リストノード構造の終了タグを前記現在の終了タグで満たすことと
のための複数の命令を備え、
前記入力文字列が有効であり、かつ、前記連結リストノード構造が前記入力文字列のための最後の連結リストノード構造でない場合、前記スタックの前記初期化を除いて、前記入力文字列からの前記次の連結リストノード構造を用いて、上記プロセスを繰り返すことのための複数の命令を備える請求項14に記載の製品。
【請求項24】
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成することのための複数の命令は、
開始タグのための連結リストノード構造を受け取ることと、
前記連結リストノード構造の中の予約ポインタを用いて、開括弧文字が前記入力文字列の中で見つかるまで、前記予約ポインタの位置を減らすことであって、前記開括弧文字と前記予約ポインタとの間の全ての文字は、属性文字列を表すことと、
前記属性文字列の一番目の部分および前記属性文字列の二番目の部分を提供するために、区切り文字としてスペース文字を用いて、前記属性文字列を解析することと、
前記属性文字列の前記一番目の部分を廃棄することと、
前記区切り文字として等号を用いて、前記属性文字列の前記二番目の部分を解析することと、
前記連結リスト属性構造の中の属性値ポインタを前記属性文字列の前記二番目の部分の前記等号の後の前記一番目の文字へセットすることであって、属性値長は、前記属性文字列の前記二番目の部分の前記一番目の文字から前記属性文字列の前記二番目の部分の最後にわたることと、
前記区切り文字としてコロンを用いて、前記属性文字列の前記一番目の部分を解析することと
のための複数の命令を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つかる場合、
前記連結リスト属性構造の中の接頭辞名称ポインタを前記属性文字列の前記一番目の部分の中の前記一番目の文字へセットすることであって、接頭辞名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記一番目の文字から前記属性文字列の前記一番目の部分の中の前記コロンに先立つ文字にわたることと、
前記連結リスト属性構造の中の属性名称ポインタを前記属性文字列の前記一番目の部分の中の前記コロンの後の一番目の文字へセットすることであって、属性名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記コロンの後の前記一番目の文字から前記属性文字列の前記一番目の部分の前記最後の文字にわたることと
のための複数の命令を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つからない場合、
前記連結リスト属性構造の中の前記接頭辞名称ポインタをnullポインタとしてセットすることであって、前記接頭辞名称の前記長さは、ゼロであることと、
前記連結リスト属性構造の中の前記属性名称ポインタを前記属性文字列の前記一番目の部分の前記一番目の文字としてセットすることであって、前記属性名称の前記長さは、前記属性文字列の前記一番目の部分の前記長さであることと
のための複数の命令を備え、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成することのための複数の命令は、
前記連結リスト属性構造の中の次属性領域が前記入力文字列の中の前記次の属性を指し示すようにセットすることのための複数の命令を備える請求項14に記載の製品。
【請求項25】
データを有する前記複数の連結リストノード構造からデータセグメントを得ることのための複数の命令は、
対応する開始タグおよび終了タグのための前記複数の連結リストノード構造を受け取ることと、
前記開始および終了タグの前記複数の連結リストノード構造が前記データセグメントを決定するために、複数の予約ポインタを使用することであって、前記データセグメントは、前記開始タグの前記予約ポインタおよび前記終了タグの前記予約ポインタの間の前記データを有することと
のための複数の命令を備える請求項14に記載の製品。
【請求項26】
前記入力文字列は、XML(拡張可能マークアップ言語)入力文字列を備える請求項14に記載の製品。
【請求項27】
複数のマークアップ言語記述を分けるためのシステムであって、
ゼロコピー文字列パーサ、および
前記ゼロコピー文字列パーサに結合されるロジックパーサを備え、
前記ゼロコピー文字列パーサおよび前記ロジックパーサは、入力文字列をメモリにコピーすることなくアプリケーションからの前記入力文字列を解析するために、対話するシステム。
【請求項28】
前記ゼロコピー文字列パーサは、シングルパスパーサを備える請求項27に記載のシステム。
【請求項29】
前記ロジックパーサは、XML(拡張可能マークアップ言語)文字列を解析するために要求されるロジックを備える請求項27に記載のシステム。
【請求項30】
前記入力文字列は、前記入力文字列に関連する長さを有し、および前記ロジックパーサは、前記ゼロコピー文字列パーサが前記入力文字列を1つ以上の連結リストノード構造に解析することを可能にするために、区切り文字を前記ゼロコピー文字列パーサに提供する請求項27に記載のシステム。
【請求項31】
前記1つ以上の連結リストノード構造は、前記ゼロコピー文字列パーサがさらに複数の連結リスト属性構造を作成するために前記複数のポインタを用いて前記入力文字列を解析することを可能にするために、前記入力文字列への複数のポインタを有し、
前記複数の連結リスト属性構造は、前記入力文字列の中で見つかる1つ以上の属性への付加的な複数のポインタを含む請求項30に記載のシステム。
【請求項32】
前記1つ以上の連結リストノード構造は、前記ゼロコピー文字列パーサが前記入力文字列に含まれる要素の中に見つかるデータを得るために前記入力文字列をさらに解析することを可能にするために、前記入力文字列への複数の予約ポインタを備える請求項30に記載のシステム。
【請求項1】
複数のマークアップ言語記述を分けるための方法であって、
入力文字列を複数の連結リストノード構造に変形する段階と、
前記入力文字列のシンタックスを検証する段階と、
複数の属性を有する前記複数の連結リストノード構造から、連結リスト属性構造を作成する段階と、
データを有する前記複数の連結リストノード構造からデータセグメントを得る段階と、
前記複数の連結リストノード構造および複数の属性構造を解放する段階と
を備える方法。
【請求項2】
前記複数の連結リストノード構造および複数の属性構造を解放する段階は、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への前記複数の連結リストノードおよび属性構造の中で定義される複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する請求項1に記載の方法。
【請求項3】
前記複数の連結リストノード構造の中の前記複数のポインタは、タグ名称、名称空間、予約位置、次タグ、親タグ、ピア要素、および終了タグへの1つ以上のポインタを備える請求項2に記載の方法。
【請求項4】
前記複数の連結リスト属性構造の中の複数のポインタは、属性名称、属性値、接頭辞名称、および次属性への1つ以上のポインタを備える請求項2に記載の方法。
【請求項5】
前記予約位置への前記ポインタは、開始タグのために次の閉括弧へのポインタおよび終了タグのために開括弧へのポインタを備える請求項3に記載の方法。
【請求項6】
入力文字列を複数の連結リストノード構造に変形する段階は、
前記入力文字列および区切り文字として開括弧文字を受け取る段階と、
前記開括弧の区切り文字を用いて、前記入力文字列を解析する段階と、
複数のトークンの連結リストを返す段階と
を備え、
前記連結リストのそれぞれのトークンは、1つの連結リストノード構造を提供するために解析される請求項1に記載の方法。
【請求項7】
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析する段階は、
前記トークンがスラッシュ("/")で始まるかどうかを判断する段階と、
前記トークンが前記スラッシュで始まらない場合、前記連結リストノード構造の中の開始タグ領域をセットし、および前記トークンが前記スラッシュで始まる場合、前記開始タグ領域を消去する段階と、
スペース文字が前記トークンの中で見つかる場合、前記トークンを一番目の部分および二番目の部分に分けるために、前記区切り文字として前記スペース文字を用いて前記トークンを解析する段階と
を備え、
前記スペース文字が前記トークンの中で見つかる場合、
名称空間のために前記連結リストノード構造の中の名称空間ポインタを前記トークンの前記一番目の部分の中の一番目の文字にセットする段階であって、前記名称空間の前記長さは、前記トークンの前記一番目の部分の中の一番目の文字から前記トークンの前記一番目の部分の中のコロンに先立つ文字にわたる段階と、
タグ名称のために前記連結リストノード構造の中のタグ名称ポインタを前記トークンの前記一番目の部分の中の前記コロンの右の文字にセットする段階であって、前記タグ名称の前記長さは、前記コロンの前記右の前記文字から前記トークンの前記一番目の部分の最後の文字にわたる段階と
を備え、
前記スペース文字が前記トークンの中で見つからない場合、
前記連結リストノード構造の中の前記タグ名称ポインタを前記トークンの中の前記複数の文字にセットする段階であって、前記タグ名称の前記長さは、前記トークンの前記長さである段階と、
前記連結リストノード構造の中の前記名称空間ポインタをnullポインタとしてセットする段階であって、前記名称空間の前記長さは、ゼロである段階と
を備え、
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析する段階は、
前記連結リストノード構造の中の次領域ポインタが前記次のトークンの先頭を指し示すようにセットする段階を備える請求項6に記載の方法。
【請求項8】
前記トークンが開始タグの場合、前記連結リストノード構造の中の予約ポインタが前記トークンの前記最後の閉括弧を指し示すようにセットし、および前記トークンが終了タグの場合、前記予約ポインタが前記トークンの前記先頭の開括弧を指し示すようにセットする段階をさらに備える請求項7に記載の方法。
【請求項9】
前記トークンの前記二番目の部分の一番目の文字が前記スラッシュで始まるかどうかを判断する段階と、
前記トークンの前記二番目の部分が前記スラッシュで始まる場合、前記連結リストノード構造の中の空タグ領域をセットする段階と、
前記トークンの前記二番目の部分が前記スラッシュで始まらない場合、前記連結リストノード構造の中の空タグ領域を消去する段階と
をさらに備える請求項7に記載の方法。
【請求項10】
前記入力文字列のシンタックスを検証する段階は、
スタックを初期化する段階と、
入力文字列のための連結リストノード構造を受け取る段階と、
前記連結リストノード構造が開始タグおよび終了タグの1つを表すかどうかを判断する段階と
を備え、
前記連結リストノード構造が現在の開始タグを表す場合、
前記連結リストノード構造の中の親領域を前記スタックの上部の前記開始タグへのポインタで満たす段階と、
前記現在の開始タグを前記スタックに置く段階と
を備え、
前記連結リストノード構造が現在の終了タグを表す場合、
前記スタックの前記上部の前記開始タグをポップオフする段階と、
前記連結リストノード構造の中のピア領域を前記現在の終了タグの次領域ポインタへのポインタで満たす段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合するかどうかを判断する段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合しない場合、前記入力文字列を無効であると示す段階と、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合する場合、前記入力文字列を有効であると示し、前記連結リストノード構造の終了タグを前記現在の終了タグで満たす段階と
を備え、
前記入力文字列が有効であり、かつ、前記連結リストノード構造が前記入力文字列のための前記最後の連結リストノード構造でない場合、前記スタックの前記初期化を除いて、前記入力文字列からの前記次の連結リストノード構造を用いて、上記プロセスを繰り返す段階を備える請求項7に記載の方法。
【請求項11】
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成する段階は、
開始タグのための連結リストノード構造を受け取る段階と、
前記連結リストノード構造の中の予約ポインタを用いる段階であって、開括弧文字が前記入力文字列の中で見つかるまで、前記予約ポインタの位置を減らし、前記開括弧文字と前記予約ポインタとの間の全ての文字は、属性文字列を表す段階と、
前記属性文字列の一番目の部分および前記属性文字列の二番目の部分を提供するために、区切り文字としてスペース文字を用いて、前記属性文字列を解析する段階と、
前記属性文字列の前記一番目の部分を廃棄する段階と、
前記区切り文字として等号を用いて、前記属性文字列の前記二番目の部分を解析する段階と、
前記連結リスト属性構造の中の属性値ポインタを前記属性文字列の前記二番目の部分の前記等号の後の前記一番目の文字へセットする段階であって、属性値長は、前記属性文字列の前記二番目の部分の前記一番目の文字から前記属性文字列の前記二番目の部分の最後にわたる段階と、
前記区切り文字としてコロンを用いて、前記属性文字列の前記一番目の部分を解析する段階と
を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つかる場合、
前記連結リスト属性構造の中の接頭辞名称ポインタを前記属性文字列の前記一番目の部分の中の前記一番目の文字へセットする段階であって、接頭辞名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記一番目の文字から前記属性文字列の前記一番目の部分の中の前記コロンに先立つ文字にわたる段階と、
前記連結リスト属性構造の中の属性名称ポインタを前記属性文字列の前記一番目の部分の中の前記コロンの後の一番目の文字へセットする段階であって、属性名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記コロンの後の前記一番目の文字から前記属性文字列の前記一番目の部分の前記最後の文字にわたる段階と
を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つからない場合、
前記連結リスト属性構造の中の前記接頭辞名称ポインタをnullポインタとしてセットする段階であって、前記接頭辞名称の前記長さは、ゼロである段階と、
前記連結リスト属性構造の中の前記属性名称ポインタを前記属性文字列の前記一番目の部分の前記一番目の文字としてセットする段階であって、前記属性名称の前記長さは、前記属性文字列の前記一番目の部分の前記長さである段階と
を備え、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成する段階は、
前記連結リスト属性構造の中の次属性領域が前記入力文字列の中の前記次の属性を指し示すようにセットする段階を備える請求項1に記載の方法。
【請求項12】
データを有する前記複数の連結リストノード構造からデータセグメントを得る段階は、
対応する開始タグおよび終了タグのための前記複数の連結リストノード構造を受け取る段階と、
前記開始および終了タグの前記複数の連結リストノード構造が前記データセグメントを決定するために、複数の予約ポインタを使用する段階であって、前記データセグメントは、前記開始タグの前記予約ポインタおよび前記終了タグの前記予約ポインタの間の前記データを有する段階と
を備える請求項1に記載の方法。
【請求項13】
前記入力文字列は、XML(拡張可能マークアップ言語)入力文字列を備える請求項1に記載の方法。
【請求項14】
複数の機械アクセス可能命令を有する記憶媒体を備え、前記複数の命令がプロセッサにより実行された場合、前記複数の命令は、
入力文字列を複数の連結リストノード構造に変形すること、
前記入力文字列のシンタックスを検証すること、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成すること、
データを有する前記複数の連結リストノード構造からデータセグメントを得ること、および
前記複数の連結リストノード構造および属性構造を解放すること
を提供する製品。
【請求項15】
前記複数の連結リストノード構造および複数の属性構造を解放することは、前記複数の連結リストノードおよび属性構造の中で定義される、前記入力文字列に含まれる複数の要素のそれぞれの内にデータおよび複数の属性を定義する前記入力文字列への複数のポインタを維持しながら前記複数の連結リストノードおよび属性構造を削除する請求項14に記載の製品。
【請求項16】
前記複数の連結リストノード構造の中の前記複数のポインタは、タグ名称、名称空間、予約位置、次タグ、親タグ、ピア要素、および終了タグへの1つ以上のポインタを備える請求項15に記載の製品。
【請求項17】
前記複数の連結リスト属性構造の中の複数のポインタは、属性名称、属性値、接頭辞名称、および次属性への1つ以上のポインタを備える請求項15に記載の製品。
【請求項18】
前記予約位置への前記ポインタは、開始タグのために次の閉括弧へのポインタおよび終了タグのために開括弧へのポインタを備える請求項16に記載の製品。
【請求項19】
入力文字列を複数の連結リストノード構造に変形することのための複数の命令は、
前記入力文字列および区切り文字として開括弧文字を受け取ることと、
前記開括弧の区切り文字を用いて、前記入力文字列を解析することと、
複数のトークンの連結リストを返すことと
のための複数の命令を備え、
前記連結リストのそれぞれのトークンは、1つの連結リストノード構造を提供するために解析される請求項14に記載の製品。
【請求項20】
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析することのための複数の命令は、
前記トークンがスラッシュ("/")で始まるかどうかを判断することと、
前記トークンが前記スラッシュで始まらない場合、前記連結リストノード構造の中の開始タグ領域をセットし、および前記トークンが前記スラッシュで始まる場合、前記開始タグ領域を消去することと、
スペース文字が前記トークンの中で見つかる場合、前記トークンを一番目の部分および二番目の部分に分けるために、前記区切り文字として前記スペース文字を用いて前記トークンを解析することと
のための複数の命令を備え、
前記スペース文字が前記トークンの中で見つかる場合、
名称空間のために前記連結リストノード構造の中の名称空間ポインタを前記トークンの前記一番目の部分の中の一番目の文字にセットすることであって、前記名称空間の長さは、前記トークンの前記一番目の部分の中の一番目の文字から前記トークンの前記一番目の部分の中のコロンに先立つ文字にわたることと、
タグ名称のために前記連結リストノード構造の中のタグ名称ポインタを前記トークンの前記一番目の部分の中の前記コロンの右の文字にセットすることであって、前記タグ名称の前記長さは、前記コロンの右の前記文字から前記トークンの前記一番目の部分の最後の文字にわたることと
のための複数の命令を備え、
前記スペース文字が前記トークンの中で見つからない場合、
前記連結リストノード構造の中の前記タグ名称ポインタを前記トークンの中の前記複数の文字にセットすることであって、前記タグ名称の前記長さは、前記トークンの前記長さであることと、
前記連結リストノード構造の中の前記名称空間ポインタをnullポインタとしてセットすることであって、前記名称空間の前記長さは、ゼロであることと
のための複数の命令を備え、
1つの連結リストノード構造を提供するために前記連結リストの中のそれぞれのトークンを解析することのための複数の命令は、
前記連結リストノード構造の中の次領域ポインタが前記次のトークンの先頭を指し示すようにセットすることのための複数の命令を備える請求項19に記載の製品。
【請求項21】
前記トークンが開始タグの場合、前記連結リストノード構造の中の予約ポインタが前記トークンの前記最後の閉括弧を指し示すようにセットし、および前記トークンが終了タグの場合、前記予約ポインタが前記トークンの前記先頭の開括弧を指し示すようにセットすることのための複数の命令をさらに備える請求項20に記載の製品。
【請求項22】
前記トークンの前記二番目の部分の一番目の文字が前記スラッシュで始まるかどうかを判断することと、
前記トークンの前記二番目の部分が前記スラッシュで始まる場合、前記連結リストノード構造の中の空タグ領域をセットすることと、
前記トークンの前記二番目の部分が前記スラッシュで始まらない場合、前記連結リストノード構造の中の空タグ領域を消去することと
のための複数の命令をさらに備える請求項20に記載の製品。
【請求項23】
前記入力文字列のシンタックスを検証することのための複数の命令は、
スタックを初期化することと、
入力文字列のための連結リストノード構造を受け取ることと、
前記連結リストノード構造が開始タグおよび終了タグの1つを表すかどうかを判断することと
のための複数の命令を備え、
前記連結リストノード構造が現在の開始タグを表す場合、
前記連結リストノード構造の中の親領域を前記スタックの上部の前記開始タグへのポインタで満たすことと、
前記現在の開始タグを前記スタックに置くことと
のための複数の命令を備え、
前記連結リストノード構造が現在の終了タグを表す場合、
前記スタックの前記上部の前記開始タグをポップオフすることと、
前記連結リストノード構造の中のピア領域を前記現在の終了タグの次領域ポインタへのポインタで満たすことと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合するかどうかを判断することと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合しない場合、前記入力文字列を無効であると示すことと、
前記現在の終了タグが前記スタックからポップオフされる前記開始タグと適合する場合、前記入力文字列を有効であると示し、前記連結リストノード構造の終了タグを前記現在の終了タグで満たすことと
のための複数の命令を備え、
前記入力文字列が有効であり、かつ、前記連結リストノード構造が前記入力文字列のための最後の連結リストノード構造でない場合、前記スタックの前記初期化を除いて、前記入力文字列からの前記次の連結リストノード構造を用いて、上記プロセスを繰り返すことのための複数の命令を備える請求項14に記載の製品。
【請求項24】
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成することのための複数の命令は、
開始タグのための連結リストノード構造を受け取ることと、
前記連結リストノード構造の中の予約ポインタを用いて、開括弧文字が前記入力文字列の中で見つかるまで、前記予約ポインタの位置を減らすことであって、前記開括弧文字と前記予約ポインタとの間の全ての文字は、属性文字列を表すことと、
前記属性文字列の一番目の部分および前記属性文字列の二番目の部分を提供するために、区切り文字としてスペース文字を用いて、前記属性文字列を解析することと、
前記属性文字列の前記一番目の部分を廃棄することと、
前記区切り文字として等号を用いて、前記属性文字列の前記二番目の部分を解析することと、
前記連結リスト属性構造の中の属性値ポインタを前記属性文字列の前記二番目の部分の前記等号の後の前記一番目の文字へセットすることであって、属性値長は、前記属性文字列の前記二番目の部分の前記一番目の文字から前記属性文字列の前記二番目の部分の最後にわたることと、
前記区切り文字としてコロンを用いて、前記属性文字列の前記一番目の部分を解析することと
のための複数の命令を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つかる場合、
前記連結リスト属性構造の中の接頭辞名称ポインタを前記属性文字列の前記一番目の部分の中の前記一番目の文字へセットすることであって、接頭辞名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記一番目の文字から前記属性文字列の前記一番目の部分の中の前記コロンに先立つ文字にわたることと、
前記連結リスト属性構造の中の属性名称ポインタを前記属性文字列の前記一番目の部分の中の前記コロンの後の一番目の文字へセットすることであって、属性名称の前記長さは、前記属性文字列の前記一番目の部分の中の前記コロンの後の前記一番目の文字から前記属性文字列の前記一番目の部分の前記最後の文字にわたることと
のための複数の命令を備え、
前記属性文字列の前記一番目の部分の中に前記コロンの文字が見つからない場合、
前記連結リスト属性構造の中の前記接頭辞名称ポインタをnullポインタとしてセットすることであって、前記接頭辞名称の前記長さは、ゼロであることと、
前記連結リスト属性構造の中の前記属性名称ポインタを前記属性文字列の前記一番目の部分の前記一番目の文字としてセットすることであって、前記属性名称の前記長さは、前記属性文字列の前記一番目の部分の前記長さであることと
のための複数の命令を備え、
複数の属性を有する前記複数の連結リストノード構造から連結リスト属性構造を作成することのための複数の命令は、
前記連結リスト属性構造の中の次属性領域が前記入力文字列の中の前記次の属性を指し示すようにセットすることのための複数の命令を備える請求項14に記載の製品。
【請求項25】
データを有する前記複数の連結リストノード構造からデータセグメントを得ることのための複数の命令は、
対応する開始タグおよび終了タグのための前記複数の連結リストノード構造を受け取ることと、
前記開始および終了タグの前記複数の連結リストノード構造が前記データセグメントを決定するために、複数の予約ポインタを使用することであって、前記データセグメントは、前記開始タグの前記予約ポインタおよび前記終了タグの前記予約ポインタの間の前記データを有することと
のための複数の命令を備える請求項14に記載の製品。
【請求項26】
前記入力文字列は、XML(拡張可能マークアップ言語)入力文字列を備える請求項14に記載の製品。
【請求項27】
複数のマークアップ言語記述を分けるためのシステムであって、
ゼロコピー文字列パーサ、および
前記ゼロコピー文字列パーサに結合されるロジックパーサを備え、
前記ゼロコピー文字列パーサおよび前記ロジックパーサは、入力文字列をメモリにコピーすることなくアプリケーションからの前記入力文字列を解析するために、対話するシステム。
【請求項28】
前記ゼロコピー文字列パーサは、シングルパスパーサを備える請求項27に記載のシステム。
【請求項29】
前記ロジックパーサは、XML(拡張可能マークアップ言語)文字列を解析するために要求されるロジックを備える請求項27に記載のシステム。
【請求項30】
前記入力文字列は、前記入力文字列に関連する長さを有し、および前記ロジックパーサは、前記ゼロコピー文字列パーサが前記入力文字列を1つ以上の連結リストノード構造に解析することを可能にするために、区切り文字を前記ゼロコピー文字列パーサに提供する請求項27に記載のシステム。
【請求項31】
前記1つ以上の連結リストノード構造は、前記ゼロコピー文字列パーサがさらに複数の連結リスト属性構造を作成するために前記複数のポインタを用いて前記入力文字列を解析することを可能にするために、前記入力文字列への複数のポインタを有し、
前記複数の連結リスト属性構造は、前記入力文字列の中で見つかる1つ以上の属性への付加的な複数のポインタを含む請求項30に記載のシステム。
【請求項32】
前記1つ以上の連結リストノード構造は、前記ゼロコピー文字列パーサが前記入力文字列に含まれる要素の中に見つかるデータを得るために前記入力文字列をさらに解析することを可能にするために、前記入力文字列への複数の予約ポインタを備える請求項30に記載のシステム。
【図1】
【図2A】
【図2B】
【図2C】
【図3A】
【図3B】
【図3C】
【図3D】
【図3E】
【図4】
【図5A】
【図5B】
【図5C】
【図6A】
【図6B】
【図2A】
【図2B】
【図2C】
【図3A】
【図3B】
【図3C】
【図3D】
【図3E】
【図4】
【図5A】
【図5B】
【図5C】
【図6A】
【図6B】
【公表番号】特表2007−514239(P2007−514239A)
【公表日】平成19年5月31日(2007.5.31)
【国際特許分類】
【出願番号】特願2006−543885(P2006−543885)
【出願日】平成16年12月1日(2004.12.1)
【国際出願番号】PCT/US2004/040277
【国際公開番号】WO2005/064461
【国際公開日】平成17年7月14日(2005.7.14)
【出願人】(591003943)インテル・コーポレーション (1,101)
【Fターム(参考)】
【公表日】平成19年5月31日(2007.5.31)
【国際特許分類】
【出願日】平成16年12月1日(2004.12.1)
【国際出願番号】PCT/US2004/040277
【国際公開番号】WO2005/064461
【国際公開日】平成17年7月14日(2005.7.14)
【出願人】(591003943)インテル・コーポレーション (1,101)
【Fターム(参考)】
[ Back to top ]