October 2012 - tor-commits - lists.torproject.org

[translation/tsum] Update translations for tsum
by translation＠torproject.org 31 Oct '12

31 Oct '12

commit b649f98451c5d3100c3ae631214c6e3c639fcebc Author: Translation commit bot <translation(a)torproject.org> Date: Wed Oct 31 18:45:11 2012 +0000 Update translations for tsum --- ja/short-user-manual_ja_noimg.xhtml | 20 ++++++++++---------- 1 files changed, 10 insertions(+), 10 deletions(-) diff --git a/ja/short-user-manual_ja_noimg.xhtml b/ja/short-user-manual_ja_noimg.xhtml index 49d8141..de65f0e 100644 --- a/ja/short-user-manual_ja_noimg.xhtml +++ b/ja/short-user-manual_ja_noimg.xhtml @@ -42,7 +42,7 @@ 以下のように表示されるはずです: <pre> <code>pub 2048R/63FEE659 2003-10-16 - Key fingerprint = 8738 A680 B84B 3031 A630 F2DB 416F 0610 63FE E659 + 指紋 = 8738 A680 B84B 3031 A630 F2DB 416F 0610 63FE E659 uid Erinn Clark <erinn(a)torproject.org> uid Erinn Clark <erinn(a)debian.org> uid Erinn Clark <erinn(a)double-helix.org> @@ -54,8 +54,8 @@ sub 2048R/EB399FD7 2003-10-16 <code>gpg --verify tor-browser-2.2.33-2_en-US.exe.asc tor-browser-2.2.33-2_en-US.exe </code> </pre> - 出力は"Good signature"になるはずです。悪い署名はファイルが改竄されていることを示唆します。もしあなたが悪い署名を確認したら、パッケージをどこからダウンロードしたか、どのように署名を検証したか、それにGnuPGの出力をhelp(a)rt.torproject.xn--org-u63b4bub2ewa1ai7bz1izd4j0726k. - 署名を検証して"Good signature"の出力が得られたら、先に進みパッケージアーカイブを展開します。tor-browser_en-USのようなディレクトリができるはずです。このディレクトリにはchangelogという名前のファイルを含むDocsという名前のディレクトリがあります。changelogファイルの先頭行のバージョン番号がファイル名のバージョン番号と一致することを確認してください。 + 出力は"正しい署名"になるはずです。不正な署名はファイルが改竄されていることを示唆します。もしあなたが不正な署名を確認したら、パッケージをどこからダウンロードしたか、どのように署名を検証したか、それにGnuPGの出力をhelp(a)rt.torproject.xn--org-u63b4bub2ewa1ai7bz1izd4j0726k. + 署名を検証して"正しい署名"の出力が得られたら、先に進みパッケージアーカイブを展開します。tor-browser_en-USのようなディレクトリができるはずです。このディレクトリにはchangelogという名前のファイルを含むDocsという名前のディレクトリがあります。changelogファイルの先頭行のバージョン番号がファイル名のバージョン番号と一致することを確認してください。 <h3 id="how-to-use-the-tor-browser-bundle">Tor Browser Bundleの使い方</h3> After downloading the Tor Browser Bundle, extract the package onto your desktop or a USB stick. You should have a directory containing a few files. One of the files is an executable called "Start Tor Browser" (or "start-tor-browser", depending on your operating system). Tor Browser Bundleを開始すると、初めににVidaliaが起動しTorネットワークへ接続されます。その後、Torを使っていることを確認する画面が表示されます。これは<a href="https://check.torproject.org/">https://check.torproject.org/</a>を表示することで行われます。これでインターネットをTor経由で利用する準備が整いました。 @@ -64,7 +64,7 @@ sub 2048R/EB399FD7 2003-10-16 <h3 id="what-to-do-when-tor-does-not-connect">Torが接続できないときにすべきこと</h3> いくらかのユーザーはVidaliaがTorネットワークへの接続に失敗するかもしれません。この場合、インターネットへ接続していることを確認してください。もしプロキシサーバーへの接続を望むなら、下のオープンプロキシの利用方法を見てください。 - もし通常のインターネット接続が動いているのに、Torがネットワークに接続できない場合、以下を試してください: Vidaliaのコントロールパネルを開き、メッセージログをクリックし、詳細タブを選択します。Torが接続できない理由があるかもしれません: + もし通常のインターネット接続が動いているのに、Torがネットワークに接続できない場合、以下を試してください: Vidaliaのコントロールパネルを開き、Message Logをクリックし、Advancedタブを選択します。Torが接続できない理由があるかもしれません: Your system clock is off: あなたのシステムの日付と時刻が正しいことを確認して、Torを再起動してください。システムクロックをインターネットタイムサーバーと同期する必要があるかもしれません。 You are behind a restrictive firewall: Torが80番と443番のポートだけを試すよう、Vidaliaのコントロールパネルを開き、SettingsそしてNetworkをクリックし、My firewall only lets me connect to certain portsにチェックをつけてください。 Your anti-virus program is blocking Tor: アンチウィルスプログラムを確認しTorがネットワークに接続することを阻まないようにしてください。 @@ -114,12 +114,12 @@ sub 2048R/EB399FD7 2003-10-16 <li>登録されている拡張子は表示しないのチェックを外しOKをクリックします</li> </ol> <h3 id="vidalia-asks-for-a-password">Vidaliaがパスワードを要求する</h3> - You should not have to enter a password when starting Vidalia. If you are prompted for one, you are likely affected by one of these problems: - You are already running Vidalia and Tor: For example, this situation can happen if you installed the Vidalia bundle and now you're trying to run the Tor Browser Bundle. In that case, you will need to close the old Vidalia and Tor before you can run this one. - Vidalia crashed, but left Tor running: If the dialog that prompts you for a control password has a Reset button, you can click the button and Vidalia will restart Tor with a new random control password. If you do not see a Reset button, or if Vidalia is unable to restart Tor for you; go into your process or task manager, and terminate the Tor process. Then use Vidalia to restart Tor. - For more information, see the <a href="https://torproject.org/docs/faq.html#VidaliaPassword">FAQ</a> on the Tor Project website. - <h3 id="flash-does-not-work">Flash does not work</h3> - For security reasons, Flash, Java, and other plugins are currently disabled for Tor. Plugins operate independently from Firefox and can perform activity on your computer that ruins your anonymity. + Vidaliaの起動時にパスワードを入力する必要はありません。もし入力を促されたなら、おそらくこれらの問題の影響を受けています: + VidaliaとTorが既に起動している: 例えば、すでにVidalia BundleをインストールしていてTor Browser Bundleを実行しようとした時に起こります、この場合Tor Browser Bundleを実行する前に古いVidaliaとTorを閉じてください。 + Vidaliaがクラッシュしたが、Torは実行し続けている: コントロールパスワードの入力を促すResetボタンを持つダイアログが表示されたら、ボタンをクリックしVidaliaが新しいランダムなコントロールパスワードでTorを再起動するように出来ます。Resetボタンが見当たらないか、VidaliaがTorを再起動出来ないなら; プロセスかタスクマネージャに行き、Torプロセスを終了させてください。それからVidaliaでTorを再起動します。 + より詳細な情報はTor Projectウェブサイトの<a href="https://torproject.org/docs/faq.html#VidaliaPassword">FAQ</a>を参照してください。 + <h3 id="flash-does-not-work">Flashが動かない</h3> + セキュリティ上の理由により、 Most YouTube videos work with HTML5, and it is possible to view these videos over Tor. You need to join the <a href="https://www.youtube.com/html5">HTML5 trial</a> on the YouTube website before you can use the HTML5 player. Note that the browser will not remember that you joined the trial once you close it, so you will need to re-join the trial the next time you run the Tor Browser Bundle. Please see the <a href="https://www.torproject.org/torbutton/torbutton-faq.html#noflash">Torbutton FAQ</a> for more information.

1 0

[translation/tsum] Update translations for tsum
by translation＠torproject.org 31 Oct '12

31 Oct '12

commit d91db0c44679a910c1736917489edd92e4dac99b Author: Translation commit bot <translation(a)torproject.org> Date: Wed Oct 31 18:15:12 2012 +0000 Update translations for tsum --- ja/short-user-manual_ja_noimg.xhtml | 6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) diff --git a/ja/short-user-manual_ja_noimg.xhtml b/ja/short-user-manual_ja_noimg.xhtml index 31e28c0..49d8141 100644 --- a/ja/short-user-manual_ja_noimg.xhtml +++ b/ja/short-user-manual_ja_noimg.xhtml @@ -63,8 +63,8 @@ sub 2048R/EB399FD7 2003-10-16 あなたのブラウザーではなく、バンドルに付属するブラウザーを利用することが重要であるということに注意してください。 <h3 id="what-to-do-when-tor-does-not-connect">Torが接続できないときにすべきこと</h3> - いくらかのユーザーはVidaliaがTorネットワークへの接続に失敗することに気づくでしょう。この場合、インターネットへ接続していることを確認してください。もしプロキシサーバーへの接続を望むなら、下のオープンプロキシの利用方法を見てください。 - もし通常のインターネット接続が動いているのに、Torがネットワークに接続できない場合、以下を試してください: Vidaliaのコントロールパネルを開き、Message Logをクリックし、Advancedタブを選択します。Torが接続できない理由があるかもしれません: + いくらかのユーザーはVidaliaがTorネットワークへの接続に失敗するかもしれません。この場合、インターネットへ接続していることを確認してください。もしプロキシサーバーへの接続を望むなら、下のオープンプロキシの利用方法を見てください。 + もし通常のインターネット接続が動いているのに、Torがネットワークに接続できない場合、以下を試してください: Vidaliaのコントロールパネルを開き、メッセージログをクリックし、詳細タブを選択します。Torが接続できない理由があるかもしれません: Your system clock is off: あなたのシステムの日付と時刻が正しいことを確認して、Torを再起動してください。システムクロックをインターネットタイムサーバーと同期する必要があるかもしれません。 You are behind a restrictive firewall: Torが80番と443番のポートだけを試すよう、Vidaliaのコントロールパネルを開き、SettingsそしてNetworkをクリックし、My firewall only lets me connect to certain portsにチェックをつけてください。 Your anti-virus program is blocking Tor: アンチウィルスプログラムを確認しTorがネットワークに接続することを阻まないようにしてください。 @@ -113,7 +113,7 @@ sub 2048R/EB399FD7 2003-10-16 <li>表示タブをクリックします</li> <li>登録されている拡張子は表示しないのチェックを外しOKをクリックします</li> </ol> - <h3 id="vidalia-asks-for-a-password">Vidalia asks for a password</h3> + <h3 id="vidalia-asks-for-a-password">Vidaliaがパスワードを要求する</h3> You should not have to enter a password when starting Vidalia. If you are prompted for one, you are likely affected by one of these problems: You are already running Vidalia and Tor: For example, this situation can happen if you installed the Vidalia bundle and now you're trying to run the Tor Browser Bundle. In that case, you will need to close the old Vidalia and Tor before you can run this one. Vidalia crashed, but left Tor running: If the dialog that prompts you for a control password has a Reset button, you can click the button and Vidalia will restart Tor with a new random control password. If you do not see a Reset button, or if Vidalia is unable to restart Tor for you; go into your process or task manager, and terminate the Tor process. Then use Vidalia to restart Tor.

1 0

[ooni-probe/master] * Fix import error.
by isis＠torproject.org 31 Oct '12

31 Oct '12

commit f4b45f970b057b45ae05e7a8561ffff29f264ef0 Author: Isis Lovecruft <isis(a)torproject.org> Date: Wed Oct 31 17:28:06 2012 +0000 * Fix import error. --- ooni/reporter.py | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/ooni/reporter.py b/ooni/reporter.py index 14327ef..191708c 100644 --- a/ooni/reporter.py +++ b/ooni/reporter.py @@ -16,7 +16,7 @@ from twisted.python.util import untilConcludes from twisted.trial import reporter from twisted.internet import defer -from ooni.templates.httpt import BodyReceiver, StringProducer +from ooni.templates.httpt import BodyReceiver from ooni.utils import date, log, geodata try:

1 0

[stem/master] Using absolute paths for whitespace checks
by atagar＠torproject.org 31 Oct '12

31 Oct '12

commit d46292f0dce4a189457b02a1ea951e845094c509 Author: Damian Johnson <atagar(a)torproject.org> Date: Wed Oct 31 08:40:21 2012 -0700 Using absolute paths for whitespace checks We were using relative paths for our whitespace checks, which caused varying behavior based on our cwd... atagar@morrigan:~/Desktop/stem$ ./run_tests.py --unit ... TESTING PASSED (7 seconds) atagar@morrigan:~/Desktop/stem$ cd .. atagar@morrigan:~/Desktop$ stem/run_tests.py --unit ... WHITESPACE ISSUES * stem/example.py line 18 - indentation should match surrounding content (2 spaces) line 19 - missing 'with' import (from __future__ import with_statement) line 23 - indentation should match surrounding content (2 or 8 spaces) line 35 - indentation should match surrounding content (4 spaces) line 72 - line has trailing whitespace line 76 - indentation should match surrounding content (0 spaces) line 77 - indentation should match surrounding content (0 spaces) * stem/run_tests.py line 289 - indentation should match surrounding content (2 spaces) line 486 - line has trailing whitespace TESTING PASSED (19 seconds) Note that 'example.py' isn't part of stem. It's an untracked file that I have in the stem directory. The reason that it's being included in the whitespace check is that we're grabbing all python files under 'stem' which, now that we're one level up, is the whole project. Using absolute paths that are relative of run_tests.py so we get consistent results. --- run_tests.py | 7 ++++--- 1 files changed, 4 insertions(+), 3 deletions(-) diff --git a/run_tests.py b/run_tests.py index 266ed0e..2e35beb 100755 --- a/run_tests.py +++ b/run_tests.py @@ -455,9 +455,10 @@ if __name__ == '__main__': # TODO: note unused config options afterward? - whitespace_issues = test.check_whitespace.get_issues("stem") - whitespace_issues.update(test.check_whitespace.get_issues("test")) - whitespace_issues.update(test.check_whitespace.get_issues("run_tests.py")) + base_path = os.path.sep.join(__file__.split(os.path.sep)[:-1]) + whitespace_issues = test.check_whitespace.get_issues(os.path.join(base_path, "stem")) + whitespace_issues.update(test.check_whitespace.get_issues(os.path.join(base_path, "test"))) + whitespace_issues.update(test.check_whitespace.get_issues(os.path.join(base_path, "run_tests.py"))) if whitespace_issues: test.output.print_line("WHITESPACE ISSUES", term.Color.BLUE, term.Attr.BOLD)

1 0

[stem/master] Supporting files in whitespace checks
by atagar＠torproject.org 31 Oct '12

31 Oct '12

commit 54e3970b674665d58b786b52af02b18bdb686136 Author: Damian Johnson <atagar(a)torproject.org> Date: Wed Oct 31 08:46:55 2012 -0700 Supporting files in whitespace checks We called os.walk() when determining the files for which we want to check whitespace. However, when presented with a file rather than a directory this causes us to not check anything... >>> list(os.walk("/tmp/foo")) [] This broke our attempts to check 'run_tests.py', and let a couple whitespace issues slip in. Fixing get_issues()'s handling for individual files. Issue caught by Eoin on... https://trac.torproject.org/7263 --- run_tests.py | 4 ++-- test/check_whitespace.py | 12 ++++++++---- 2 files changed, 10 insertions(+), 6 deletions(-) diff --git a/run_tests.py b/run_tests.py index 2e35beb..b4f0c06 100755 --- a/run_tests.py +++ b/run_tests.py @@ -286,7 +286,7 @@ if __name__ == '__main__': # count how many tests have been skipped. skipped_test_count = 0 - + # loads and validates our various configurations test_config = stem.util.conf.get_config("test") @@ -484,7 +484,7 @@ if __name__ == '__main__': elif skipped_test_count > 0: test.output.print_line("%i TESTS WERE SKIPPED" % skipped_test_count, term.Color.BLUE, term.Attr.BOLD) test.output.print_line("ALL OTHER TESTS PASSED %s" % runtime_label, term.Color.GREEN, term.Attr.BOLD) - print + print else: test.output.print_line("TESTING PASSED %s" % runtime_label, term.Color.GREEN, term.Attr.BOLD) print diff --git a/test/check_whitespace.py b/test/check_whitespace.py index 314230f..fa26a09 100644 --- a/test/check_whitespace.py +++ b/test/check_whitespace.py @@ -107,10 +107,14 @@ def _get_files_with_suffix(base_path, suffix = ".py"): :returns: iterator that yields the absolute path for files with the given suffix """ - for root, _, files in os.walk(base_path): - for filename in files: - if filename.endswith(suffix): - yield os.path.join(root, filename) + if os.path.isfile(base_path): + if base_path.endswith(suffix): + yield base_path + else: + for root, _, files in os.walk(base_path): + for filename in files: + if filename.endswith(suffix): + yield os.path.join(root, filename) if __name__ == '__main__': issues = get_issues()

1 0

[tor/master] Fix whitespace
by nickm＠torproject.org 31 Oct '12

31 Oct '12

commit 9327a9f60777b3deb4f169f8a142164007ccb211 Author: Nick Mathewson <nickm(a)torproject.org> Date: Wed Oct 31 11:27:13 2012 -0400 Fix whitespace --- src/or/channel.c | 1 - 1 files changed, 0 insertions(+), 1 deletions(-) diff --git a/src/or/channel.c b/src/or/channel.c index cd5972f..cbf7f99 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -2462,7 +2462,6 @@ channel_process_cells(channel_t *chan) break; } } - } /**

1 0

[ooni-probe/master] Implement reporter for OONIB
by art＠torproject.org 31 Oct '12

31 Oct '12

commit 09b5124f23682f052c985b997e8b7c67c897e64c Author: Arturo Filastò <arturo(a)filasto.net> Date: Wed Oct 31 14:06:19 2012 +0000 Implement reporter for OONIB * Fix bad bug in reporter for OONIC --- ooni/reporter.py | 56 ++++++++++++++++++++++++++++++++++++++++++++++++----- 1 files changed, 50 insertions(+), 6 deletions(-) diff --git a/ooni/reporter.py b/ooni/reporter.py index 4d09729..14327ef 100644 --- a/ooni/reporter.py +++ b/ooni/reporter.py @@ -3,6 +3,7 @@ import logging import sys import time import yaml +import json import traceback from yaml.representer import * @@ -14,6 +15,8 @@ from datetime import datetime from twisted.python.util import untilConcludes from twisted.trial import reporter from twisted.internet import defer + +from ooni.templates.httpt import BodyReceiver, StringProducer from ooni.utils import date, log, geodata try: @@ -76,6 +79,47 @@ def safe_dump(data, stream=None, **kw): """ return yaml.dump_all([data], stream, Dumper=OSafeDumper, **kw) +class OONIBReporter(object): + def __init__(self, backend_url): + from twisted.web.client import Agent + from twisted.internet import reactor + + self.agent = Agent(reactor) + self.backend_url = backend_url + + def _newReportCreated(self, data): + #log.debug("Got this as result: %s" % data) + print "Got this as result: %s" % data + + return data + + def _processResponseBody(self, response, body_cb): + #log.debug("Got response %s" % response) + print "Got response %s" % response + + done = defer.Deferred() + response.deliverBody(BodyReceiver(done)) + done.addCallback(body_cb) + return done + + def newReport(self, test_name, test_version): + url = self.backend_url + '/new' + print "Creating report via url %s" % url + + software_version = '0.0.1' + + request = {'software_name': 'ooni-probe', + 'software_version': software_version, + 'test_name': test_name, 'test_version': test_version, + 'progress': 0} + + #log.debug("Creating report via url %s" % url) + bodyProducer = StringProducer(json.dumps(request)) + d = self.agent.request("POST", url, bodyProducer=bodyProducer) + d.addCallback(self._processResponseBody, self._newReportCreated) + return d + + class OReporter(pyunit.TestResult): """ This is an extension of the unittest TestResult. It adds support for @@ -269,11 +313,11 @@ class OONIReporter(OReporter): self.writeYamlLine(self.report) def addSuccess(self, test): - OONIReporter.addSuccess(self, test) + OReporter.addSuccess(self, test) #self.report['result'] = {'value': 'success'} def addError(self, test, exception): - OONIReporter.addError(self, test, exception) + OReporter.addError(self, test, exception) exc_type, exc_value, exc_traceback = exception log.err(exc_type) log.err(str(exc_value)) @@ -282,19 +326,19 @@ class OONIReporter(OReporter): log.err(line) def addFailure(self, *args): - OONIReporter.addFailure(self, *args) + OReporter.addFailure(self, *args) log.warn(args) def addSkip(self, *args): - OONIReporter.addSkip(self, *args) + OReporter.addSkip(self, *args) #self.report['result'] = {'value': 'skip', 'args': args} def addExpectedFailure(self, *args): - OONIReporter.addExpectedFailure(self, *args) + OReporter.addExpectedFailure(self, *args) #self.report['result'] = {'value': 'expectedFailure', 'args': args} def addUnexpectedSuccess(self, *args): - OONIReporter.addUnexpectedSuccess(self, *args) + OReporter.addUnexpectedSuccess(self, *args) #self.report['result'] = {'args': args, 'value': 'unexpectedSuccess'}

1 0

[tor/master] Add a copy of the queue(3) manpage to the git repository.
by nickm＠torproject.org 30 Oct '12

30 Oct '12

commit 965d778b2682158cb9d362c71bce8eb61c4df21d Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 30 19:16:07 2012 -0400 Add a copy of the queue(3) manpage to the git repository. See 7105 --- src/ext/tor_queue.txt | 883 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 883 insertions(+), 0 deletions(-) diff --git a/src/ext/tor_queue.txt b/src/ext/tor_queue.txt new file mode 100644 index 0000000..f284e71 --- /dev/null +++ b/src/ext/tor_queue.txt @@ -0,0 +1,883 @@ +Below follows the manpage for tor_queue.h, as included with OpenBSD's +sys/queue.h. License follows at the end of the file. + +====================================================================== +QUEUE(3) OpenBSD Programmer's Manual QUEUE(3) + +NAME + SLIST_ENTRY, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_FIRST, SLIST_NEXT, + SLIST_END, SLIST_EMPTY, SLIST_FOREACH, SLIST_FOREACH_SAFE, SLIST_INIT, + SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_REMOVE_AFTER, + SLIST_REMOVE_HEAD, SLIST_REMOVE, LIST_ENTRY, LIST_HEAD, + LIST_HEAD_INITIALIZER, LIST_FIRST, LIST_NEXT, LIST_END, LIST_EMPTY, + LIST_FOREACH, LIST_FOREACH_SAFE, LIST_INIT, LIST_INSERT_AFTER, + LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_REMOVE, LIST_REPLACE, + SIMPLEQ_ENTRY, SIMPLEQ_HEAD, SIMPLEQ_HEAD_INITIALIZER, SIMPLEQ_FIRST, + SIMPLEQ_NEXT, SIMPLEQ_END, SIMPLEQ_EMPTY, SIMPLEQ_FOREACH, + SIMPLEQ_FOREACH_SAFE, SIMPLEQ_INIT, SIMPLEQ_INSERT_AFTER, + SIMPLEQ_INSERT_HEAD, SIMPLEQ_INSERT_TAIL, SIMPLEQ_REMOVE_AFTER, + SIMPLEQ_REMOVE_HEAD, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, + TAILQ_FIRST, TAILQ_NEXT, TAILQ_END, TAILQ_LAST, TAILQ_PREV, TAILQ_EMPTY, + TAILQ_FOREACH, TAILQ_FOREACH_SAFE, TAILQ_FOREACH_REVERSE, + TAILQ_FOREACH_REVERSE_SAFE, TAILQ_INIT, TAILQ_INSERT_AFTER, + TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE, + TAILQ_REPLACE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER, + CIRCLEQ_FIRST, CIRCLEQ_LAST, CIRCLEQ_END, CIRCLEQ_NEXT, CIRCLEQ_PREV, + CIRCLEQ_EMPTY, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_SAFE, + CIRCLEQ_FOREACH_REVERSE_SAFE, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER, + CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL, + CIRCLEQ_REMOVE, CIRCLEQ_REPLACE - implementations of singly-linked lists, + doubly-linked lists, simple queues, tail queues, and circular queues + +SYNOPSIS + #include <sys/queue.h> + + SLIST_ENTRY(TYPE); + + SLIST_HEAD(HEADNAME, TYPE); + + SLIST_HEAD_INITIALIZER(SLIST_HEAD head); + + struct TYPE * + SLIST_FIRST(SLIST_HEAD *head); + + struct TYPE * + SLIST_NEXT(struct TYPE *listelm, SLIST_ENTRY NAME); + + struct TYPE * + SLIST_END(SLIST_HEAD *head); + + int + SLIST_EMPTY(SLIST_HEAD *head); + + SLIST_FOREACH(VARNAME, SLIST_HEAD *head, SLIST_ENTRY NAME); + + SLIST_FOREACH_SAFE(VARNAME, SLIST_HEAD *head, SLIST_ENTRY + NAME, TEMP_VARNAME); + + void + SLIST_INIT(SLIST_HEAD *head); + + void + SLIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, SLIST_ENTRY + NAME); + + void + SLIST_INSERT_HEAD(SLIST_HEAD *head, struct TYPE *elm, SLIST_ENTRY NAME); + + void + SLIST_REMOVE_AFTER(struct TYPE *elm, SLIST_ENTRY NAME); + + void + SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME); + + void + SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm, TYPE, SLIST_ENTRY NAME); + + LIST_ENTRY(TYPE); + + LIST_HEAD(HEADNAME, TYPE); + + LIST_HEAD_INITIALIZER(LIST_HEAD head); + + struct TYPE * + LIST_FIRST(LIST_HEAD *head); + + struct TYPE * + LIST_NEXT(struct TYPE *listelm, LIST_ENTRY NAME); + + struct TYPE * + LIST_END(LIST_HEAD *head); + + int + LIST_EMPTY(LIST_HEAD *head); + + LIST_FOREACH(VARNAME, LIST_HEAD *head, LIST_ENTRY NAME); + + LIST_FOREACH_SAFE(VARNAME, LIST_HEAD *head, LIST_ENTRY + NAME, TEMP_VARNAME); + + void + LIST_INIT(LIST_HEAD *head); + + void + LIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY + NAME); + + void + LIST_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY + NAME); + + void + LIST_INSERT_HEAD(LIST_HEAD *head, struct TYPE *elm, LIST_ENTRY NAME); + + void + LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME); + + void + LIST_REPLACE(struct TYPE *elm, struct TYPE *elm2, LIST_ENTRY NAME); + + SIMPLEQ_ENTRY(TYPE); + + SIMPLEQ_HEAD(HEADNAME, TYPE); + + SIMPLEQ_HEAD_INITIALIZER(SIMPLEQ_HEAD head); + + struct TYPE * + SIMPLEQ_FIRST(SIMPLEQ_HEAD *head); + + struct TYPE * + SIMPLEQ_NEXT(struct TYPE *listelm, SIMPLEQ_ENTRY NAME); + + struct TYPE * + SIMPLEQ_END(SIMPLEQ_HEAD *head); + + int + SIMPLEQ_EMPTY(SIMPLEQ_HEAD *head); + + SIMPLEQ_FOREACH(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME); + + SIMPLEQ_FOREACH_SAFE(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY + NAME, TEMP_VARNAME); + + void + SIMPLEQ_INIT(SIMPLEQ_HEAD *head); + + void + SIMPLEQ_INSERT_AFTER(SIMPLEQ_HEAD *head, struct TYPE *listelm, struct + TYPE *elm, SIMPLEQ_ENTRY NAME); + + void + SIMPLEQ_INSERT_HEAD(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY + NAME); + + void + SIMPLEQ_INSERT_TAIL(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY + NAME); + + void + SIMPLEQ_REMOVE_AFTER(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY + NAME); + + void + SIMPLEQ_REMOVE_HEAD(SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME); + + TAILQ_ENTRY(TYPE); + + TAILQ_HEAD(HEADNAME, TYPE); + + TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head); + + struct TYPE * + TAILQ_FIRST(TAILQ_HEAD *head); + + struct TYPE * + TAILQ_NEXT(struct TYPE *listelm, TAILQ_ENTRY NAME); + + struct TYPE * + TAILQ_END(TAILQ_HEAD *head); + + struct TYPE * + TAILQ_LAST(TAILQ_HEAD *head, HEADNAME NAME); + + struct TYPE * + TAILQ_PREV(struct TYPE *listelm, HEADNAME NAME, TAILQ_ENTRY NAME); + + int + TAILQ_EMPTY(TAILQ_HEAD *head); + + TAILQ_FOREACH(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY NAME); + + TAILQ_FOREACH_SAFE(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY + NAME, TEMP_VARNAME); + + TAILQ_FOREACH_REVERSE(VARNAME, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY + NAME); + + TAILQ_FOREACH_REVERSE_SAFE(VARNAME, TAILQ_HEAD + *head, HEADNAME, TAILQ_ENTRY NAME, TEMP_VARNAME); + + void + TAILQ_INIT(TAILQ_HEAD *head); + + void + TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm, struct TYPE + *elm, TAILQ_ENTRY NAME); + + void + TAILQ_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, TAILQ_ENTRY + NAME); + + void + TAILQ_INSERT_HEAD(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); + + void + TAILQ_INSERT_TAIL(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); + + void + TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME); + + void + TAILQ_REPLACE(TAILQ_HEAD *head, struct TYPE *elm, struct TYPE + *elm2, TAILQ_ENTRY NAME); + + CIRCLEQ_ENTRY(TYPE); + + CIRCLEQ_HEAD(HEADNAME, TYPE); + + CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head); + + struct TYPE * + CIRCLEQ_FIRST(CIRCLEQ_HEAD *head); + + struct TYPE * + CIRCLEQ_LAST(CIRCLEQ_HEAD *head); + + struct TYPE * + CIRCLEQ_END(CIRCLEQ_HEAD *head); + + struct TYPE * + CIRCLEQ_NEXT(struct TYPE *listelm, CIRCLEQ_ENTRY NAME); + + struct TYPE * + CIRCLEQ_PREV(struct TYPE *listelm, CIRCLEQ_ENTRY NAME); + + int + CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head); + + CIRCLEQ_FOREACH(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME); + + CIRCLEQ_FOREACH_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY + NAME, TEMP_VARNAME); + + CIRCLEQ_FOREACH_REVERSE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME); + + CIRCLEQ_FOREACH_REVERSE_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY + NAME, TEMP_VARNAME); + + void + CIRCLEQ_INIT(CIRCLEQ_HEAD *head); + + void + CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct + TYPE *elm, CIRCLEQ_ENTRY NAME); + + void + CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct + TYPE *elm, CIRCLEQ_ENTRY NAME); + + void + CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY + NAME); + + void + CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY + NAME); + + void + CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY NAME); + + void + CIRCLEQ_REPLACE(CIRCLEQ_HEAD *head, struct TYPE *elm, struct TYPE + *elm2, CIRCLEQ_ENTRY NAME); + +DESCRIPTION + These macros define and operate on five types of data structures: singly- + linked lists, simple queues, lists, tail queues, and circular queues. + All five structures support the following functionality: + + 1. Insertion of a new entry at the head of the list. + 2. Insertion of a new entry after any element in the list. + 3. Removal of an entry from the head of the list. + 4. Forward traversal through the list. + + Singly-linked lists are the simplest of the five data structures and + support only the above functionality. Singly-linked lists are ideal for + applications with large datasets and few or no removals, or for + implementing a LIFO queue. + + Simple queues add the following functionality: + + 1. Entries can be added at the end of a list. + + However: + + 1. All list insertions must specify the head of the list. + 2. Each head entry requires two pointers rather than one. + 3. Code size is about 15% greater and operations run about 20% + slower than singly-linked lists. + + Simple queues are ideal for applications with large datasets and few or + no removals, or for implementing a FIFO queue. + + All doubly linked types of data structures (lists, tail queues, and + circle queues) additionally allow: + + 1. Insertion of a new entry before any element in the list. + 2. Removal of any entry in the list. + + However: + + 1. Each element requires two pointers rather than one. + 2. Code size and execution time of operations (except for + removal) is about twice that of the singly-linked data- + structures. + + Lists are the simplest of the doubly linked data structures and support + only the above functionality over singly-linked lists. + + Tail queues add the following functionality: + + 1. Entries can be added at the end of a list. + 2. They may be traversed backwards, at a cost. + + However: + + 1. All list insertions and removals must specify the head of the + list. + 2. Each head entry requires two pointers rather than one. + 3. Code size is about 15% greater and operations run about 20% + slower than singly-linked lists. + + Circular queues add the following functionality: + + 1. Entries can be added at the end of a list. + 2. They may be traversed backwards, from tail to head. + + However: + + 1. All list insertions and removals must specify the head of the + list. + 2. Each head entry requires two pointers rather than one. + 3. The termination condition for traversal is more complex. + 4. Code size is about 40% greater and operations run about 45% + slower than lists. + + In the macro definitions, TYPE is the name tag of a user defined + structure that must contain a field of type SLIST_ENTRY, LIST_ENTRY, + SIMPLEQ_ENTRY, TAILQ_ENTRY, or CIRCLEQ_ENTRY, named NAME. The argument + HEADNAME is the name tag of a user defined structure that must be + declared using the macros SLIST_HEAD(), LIST_HEAD(), SIMPLEQ_HEAD(), + TAILQ_HEAD(), or CIRCLEQ_HEAD(). See the examples below for further + explanation of how these macros are used. + +SINGLY-LINKED LISTS + A singly-linked list is headed by a structure defined by the SLIST_HEAD() + macro. This structure contains a single pointer to the first element on + the list. The elements are singly linked for minimum space and pointer + manipulation overhead at the expense of O(n) removal for arbitrary + elements. New elements can be added to the list after an existing + element or at the head of the list. A SLIST_HEAD structure is declared + as follows: + + SLIST_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the list. A pointer + to the head of the list can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The HEADNAME facility is often not used, leading to the following bizarre + code: + + SLIST_HEAD(, TYPE) head, *headp; + + The SLIST_ENTRY() macro declares a structure that connects the elements + in the list. + + The SLIST_INIT() macro initializes the list referenced by head. + + The list can also be initialized statically by using the + SLIST_HEAD_INITIALIZER() macro like this: + + SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head); + + The SLIST_INSERT_HEAD() macro inserts the new element elm at the head of + the list. + + The SLIST_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The SLIST_REMOVE_HEAD() macro removes the first element of the list + pointed by head. + + The SLIST_REMOVE_AFTER() macro removes the list element immediately + following elm. + + The SLIST_REMOVE() macro removes the element elm of the list pointed by + head. + + The SLIST_FIRST() and SLIST_NEXT() macros can be used to traverse the + list: + + for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, NAME)) + + Or, for simplicity, one can use the SLIST_FOREACH() macro: + + SLIST_FOREACH(np, head, NAME) + + The macro SLIST_FOREACH_SAFE() traverses the list referenced by head in a + forward direction, assigning each element in turn to var. However, + unlike SLIST_FOREACH() it is permitted to remove var as well as free it + from within the loop safely without interfering with the traversal. + + The SLIST_EMPTY() macro should be used to check whether a simple list is + empty. + +SINGLY-LINKED LIST EXAMPLE + SLIST_HEAD(listhead, entry) head; + struct entry { + ... + SLIST_ENTRY(entry) entries; /* Simple list. */ + ... + } *n1, *n2, *np; + + SLIST_INIT(&head); /* Initialize simple list. */ + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + SLIST_INSERT_HEAD(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + SLIST_INSERT_AFTER(n1, n2, entries); + + SLIST_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + + while (!SLIST_EMPTY(&head)) { /* Delete. */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); + } + + +LISTS + A list is headed by a structure defined by the LIST_HEAD() macro. This + structure contains a single pointer to the first element on the list. + The elements are doubly linked so that an arbitrary element can be + removed without traversing the list. New elements can be added to the + list after an existing element, before an existing element, or at the + head of the list. A LIST_HEAD structure is declared as follows: + + LIST_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the list. A pointer + to the head of the list can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The HEADNAME facility is often not used, leading to the following bizarre + code: + + LIST_HEAD(, TYPE) head, *headp; + + The LIST_ENTRY() macro declares a structure that connects the elements in + the list. + + The LIST_INIT() macro initializes the list referenced by head. + + The list can also be initialized statically by using the + LIST_HEAD_INITIALIZER() macro like this: + + LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head); + + The LIST_INSERT_HEAD() macro inserts the new element elm at the head of + the list. + + The LIST_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The LIST_INSERT_BEFORE() macro inserts the new element elm before the + element listelm. + + The LIST_REMOVE() macro removes the element elm from the list. + + The LIST_REPLACE() macro replaces the list element elm with the new + element elm2. + + The LIST_FIRST() and LIST_NEXT() macros can be used to traverse the list: + + for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, NAME)) + + Or, for simplicity, one can use the LIST_FOREACH() macro: + + LIST_FOREACH(np, head, NAME) + + The macro LIST_FOREACH_SAFE() traverses the list referenced by head in a + forward direction, assigning each element in turn to var. However, + unlike LIST_FOREACH() it is permitted to remove var as well as free it + from within the loop safely without interfering with the traversal. + + The LIST_EMPTY() macro should be used to check whether a list is empty. + +LIST EXAMPLE + LIST_HEAD(listhead, entry) head; + struct entry { + ... + LIST_ENTRY(entry) entries; /* List. */ + ... + } *n1, *n2, *np; + + LIST_INIT(&head); /* Initialize list. */ + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + LIST_INSERT_HEAD(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + LIST_INSERT_AFTER(n1, n2, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert before. */ + LIST_INSERT_BEFORE(n1, n2, entries); + /* Forward traversal. */ + LIST_FOREACH(np, &head, entries) + np-> ... + + while (!LIST_EMPTY(&head)) /* Delete. */ + n1 = LIST_FIRST(&head); + LIST_REMOVE(n1, entries); + free(n1); + } + +SIMPLE QUEUES + A simple queue is headed by a structure defined by the SIMPLEQ_HEAD() + macro. This structure contains a pair of pointers, one to the first + element in the simple queue and the other to the last element in the + simple queue. The elements are singly linked. New elements can be added + to the queue after an existing element, at the head of the queue or at + the tail of the queue. A SIMPLEQ_HEAD structure is declared as follows: + + SIMPLEQ_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the queue. A pointer + to the head of the queue can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The SIMPLEQ_ENTRY() macro declares a structure that connects the elements + in the queue. + + The SIMPLEQ_INIT() macro initializes the queue referenced by head. + + The queue can also be initialized statically by using the + SIMPLEQ_HEAD_INITIALIZER() macro like this: + + SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head); + + The SIMPLEQ_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The SIMPLEQ_INSERT_HEAD() macro inserts the new element elm at the head + of the queue. + + The SIMPLEQ_INSERT_TAIL() macro inserts the new element elm at the end of + the queue. + + The SIMPLEQ_REMOVE_AFTER() macro removes the queue element immediately + following elm. + + The SIMPLEQ_REMOVE_HEAD() macro removes the first element from the queue. + + The SIMPLEQ_FIRST() and SIMPLEQ_NEXT() macros can be used to traverse the + queue. The SIMPLEQ_FOREACH() is used for queue traversal: + + SIMPLEQ_FOREACH(np, head, NAME) + + The macro SIMPLEQ_FOREACH_SAFE() traverses the queue referenced by head + in a forward direction, assigning each element in turn to var. However, + unlike SIMPLEQ_FOREACH() it is permitted to remove var as well as free it + from within the loop safely without interfering with the traversal. + + The SIMPLEQ_EMPTY() macro should be used to check whether a list is + empty. + +SIMPLE QUEUE EXAMPLE + SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head); + struct entry { + ... + SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ + ... + } *n1, *n2, *np; + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + SIMPLEQ_INSERT_HEAD(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ + SIMPLEQ_INSERT_TAIL(&head, n2, entries); + /* Forward traversal. */ + SIMPLEQ_FOREACH(np, &head, entries) + np-> ... + /* Delete. */ + while (!SIMPLEQ_EMPTY(&head)) { + n1 = SIMPLEQ_FIRST(&head); + SIMPLEQ_REMOVE_HEAD(&head, entries); + free(n1); + } + +TAIL QUEUES + A tail queue is headed by a structure defined by the TAILQ_HEAD() macro. + This structure contains a pair of pointers, one to the first element in + the tail queue and the other to the last element in the tail queue. The + elements are doubly linked so that an arbitrary element can be removed + without traversing the tail queue. New elements can be added to the + queue after an existing element, before an existing element, at the head + of the queue, or at the end of the queue. A TAILQ_HEAD structure is + declared as follows: + + TAILQ_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the tail queue. A + pointer to the head of the tail queue can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The TAILQ_ENTRY() macro declares a structure that connects the elements + in the tail queue. + + The TAILQ_INIT() macro initializes the tail queue referenced by head. + + The tail queue can also be initialized statically by using the + TAILQ_HEAD_INITIALIZER() macro. + + The TAILQ_INSERT_HEAD() macro inserts the new element elm at the head of + the tail queue. + + The TAILQ_INSERT_TAIL() macro inserts the new element elm at the end of + the tail queue. + + The TAILQ_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The TAILQ_INSERT_BEFORE() macro inserts the new element elm before the + element listelm. + + The TAILQ_REMOVE() macro removes the element elm from the tail queue. + + The TAILQ_REPLACE() macro replaces the list element elm with the new + element elm2. + + TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() are used for traversing a + tail queue. TAILQ_FOREACH() starts at the first element and proceeds + towards the last. TAILQ_FOREACH_REVERSE() starts at the last element and + proceeds towards the first. + + TAILQ_FOREACH(np, &head, NAME) + TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, NAME) + + The macros TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_REVERSE_SAFE() traverse + the list referenced by head in a forward or reverse direction + respectively, assigning each element in turn to var. However, unlike + their unsafe counterparts, they permit both the removal of var as well as + freeing it from within the loop safely without interfering with the + traversal. + + The TAILQ_FIRST(), TAILQ_NEXT(), TAILQ_LAST() and TAILQ_PREV() macros can + be used to manually traverse a tail queue or an arbitrary part of one. + + The TAILQ_EMPTY() macro should be used to check whether a tail queue is + empty. + +TAIL QUEUE EXAMPLE + TAILQ_HEAD(tailhead, entry) head; + struct entry { + ... + TAILQ_ENTRY(entry) entries; /* Tail queue. */ + ... + } *n1, *n2, *np; + + TAILQ_INIT(&head); /* Initialize queue. */ + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + TAILQ_INSERT_HEAD(&head, n1, entries); + + n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ + TAILQ_INSERT_TAIL(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + TAILQ_INSERT_AFTER(&head, n1, n2, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert before. */ + TAILQ_INSERT_BEFORE(n1, n2, entries); + /* Forward traversal. */ + TAILQ_FOREACH(np, &head, entries) + np-> ... + /* Manual forward traversal. */ + for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries)) + np-> ... + /* Delete. */ + while ((np = TAILQ_FIRST(&head))) { + TAILQ_REMOVE(&head, np, entries); + free(np); + } + + +CIRCULAR QUEUES + A circular queue is headed by a structure defined by the CIRCLEQ_HEAD() + macro. This structure contains a pair of pointers, one to the first + element in the circular queue and the other to the last element in the + circular queue. The elements are doubly linked so that an arbitrary + element can be removed without traversing the queue. New elements can be + added to the queue after an existing element, before an existing element, + at the head of the queue, or at the end of the queue. A CIRCLEQ_HEAD + structure is declared as follows: + + CIRCLEQ_HEAD(HEADNAME, TYPE) head; + + where HEADNAME is the name of the structure to be defined, and struct + TYPE is the type of the elements to be linked into the circular queue. A + pointer to the head of the circular queue can later be declared as: + + struct HEADNAME *headp; + + (The names head and headp are user selectable.) + + The CIRCLEQ_ENTRY() macro declares a structure that connects the elements + in the circular queue. + + The CIRCLEQ_INIT() macro initializes the circular queue referenced by + head. + + The circular queue can also be initialized statically by using the + CIRCLEQ_HEAD_INITIALIZER() macro. + + The CIRCLEQ_INSERT_HEAD() macro inserts the new element elm at the head + of the circular queue. + + The CIRCLEQ_INSERT_TAIL() macro inserts the new element elm at the end of + the circular queue. + + The CIRCLEQ_INSERT_AFTER() macro inserts the new element elm after the + element listelm. + + The CIRCLEQ_INSERT_BEFORE() macro inserts the new element elm before the + element listelm. + + The CIRCLEQ_REMOVE() macro removes the element elm from the circular + queue. + + The CIRCLEQ_REPLACE() macro replaces the list element elm with the new + element elm2. + + The CIRCLEQ_FIRST(), CIRCLEQ_LAST(), CIRCLEQ_END(), CIRCLEQ_NEXT() and + CIRCLEQ_PREV() macros can be used to traverse a circular queue. The + CIRCLEQ_FOREACH() is used for circular queue forward traversal: + + CIRCLEQ_FOREACH(np, head, NAME) + + The CIRCLEQ_FOREACH_REVERSE() macro acts like CIRCLEQ_FOREACH() but + traverses the circular queue backwards. + + The macros CIRCLEQ_FOREACH_SAFE() and CIRCLEQ_FOREACH_REVERSE_SAFE() + traverse the list referenced by head in a forward or reverse direction + respectively, assigning each element in turn to var. However, unlike + their unsafe counterparts, they permit both the removal of var as well as + freeing it from within the loop safely without interfering with the + traversal. + + The CIRCLEQ_EMPTY() macro should be used to check whether a circular + queue is empty. + +CIRCULAR QUEUE EXAMPLE + CIRCLEQ_HEAD(circleq, entry) head; + struct entry { + ... + CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ + ... + } *n1, *n2, *np; + + CIRCLEQ_INIT(&head); /* Initialize circular queue. */ + + n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ + CIRCLEQ_INSERT_HEAD(&head, n1, entries); + + n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ + CIRCLEQ_INSERT_TAIL(&head, n1, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert after. */ + CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); + + n2 = malloc(sizeof(struct entry)); /* Insert before. */ + CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); + /* Forward traversal. */ + CIRCLEQ_FOREACH(np, &head, entries) + np-> ... + /* Reverse traversal. */ + CIRCLEQ_FOREACH_REVERSE(np, &head, entries) + np-> ... + /* Delete. */ + while (!CIRCLEQ_EMPTY(&head)) { + n1 = CIRCLEQ_FIRST(&head); + CIRCLEQ_REMOVE(&head, n1, entries); + free(n1); + } + +NOTES + It is an error to assume the next and previous fields are preserved after + an element has been removed from a list or queue. Using any macro + (except the various forms of insertion) on an element removed from a list + or queue is incorrect. An example of erroneous usage is removing the + same element twice. + + The SLIST_END(), LIST_END(), SIMPLEQ_END() and TAILQ_END() macros are + provided for symmetry with CIRCLEQ_END(). They expand to NULL and don't + serve any useful purpose. + + Trying to free a list in the following way is a common error: + + LIST_FOREACH(var, head, entry) + free(var); + free(head); + + Since var is free'd, the FOREACH macros refer to a pointer that may have + been reallocated already. A similar situation occurs when the current + element is deleted from the list. In cases like these the data + structure's FOREACH_SAFE macros should be used instead. + +HISTORY + The queue functions first appeared in 4.4BSD. + +OpenBSD 5.0 April 11, 2012 OpenBSD 5.0 +====================================================================== +.\" $OpenBSD: queue.3,v 1.56 2012/04/11 13:29:14 naddy Exp $ +.\" $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $ +.\" +.\" Copyright (c) 1993 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +

1 0

[tor/master] Use SIMPLEQ, not smartlist_t, for channel cell queues.
by andrea＠torproject.org 30 Oct '12

30 Oct '12

commit 7c9954a02abd16e5c74c2a5dea9ed0f65af230be Author: Nick Mathewson <nickm(a)torproject.org> Date: Fri Oct 12 17:58:01 2012 -0400 Use SIMPLEQ, not smartlist_t, for channel cell queues. This lets us use fewer memory allocations, and avoid O(n^2) iterations --- src/or/channel.c | 158 ++++++++++++++++++++---------------------------------- src/or/channel.h | 9 +++- 2 files changed, 66 insertions(+), 101 deletions(-) diff --git a/src/or/channel.c b/src/or/channel.c index 6527288..b594d05 100644 --- a/src/or/channel.c +++ b/src/or/channel.c @@ -31,6 +31,7 @@ typedef struct cell_queue_entry_s cell_queue_entry_t; struct cell_queue_entry_s { + SIMPLEQ_ENTRY(cell_queue_entry_s) next; enum { CELL_QUEUE_FIXED, CELL_QUEUE_VAR, @@ -768,6 +769,10 @@ channel_init(channel_t *chan) /* Init next_circ_id */ chan->next_circ_id = crypto_rand_int(1 << 15); + /* Initialize queues. */ + SIMPLEQ_INIT(&chan->incoming_queue); + SIMPLEQ_INIT(&chan->outgoing_queue); + /* Timestamp it */ channel_timestamp_created(chan); } @@ -861,6 +866,7 @@ channel_listener_free(channel_listener_t *chan_l) static void channel_force_free(channel_t *chan) { + cell_queue_entry_t *cell, *cell_tmp; tor_assert(chan); /* Call a free method if there is one */ @@ -869,26 +875,16 @@ channel_force_free(channel_t *chan) channel_clear_remote_end(chan); /* We might still have a cell queue; kill it */ - if (chan->incoming_queue) { - SMARTLIST_FOREACH_BEGIN(chan->incoming_queue, - cell_queue_entry_t *, q) { - cell_queue_entry_free(q, 0); - } SMARTLIST_FOREACH_END(q); - - smartlist_free(chan->incoming_queue); - chan->incoming_queue = NULL; + SIMPLEQ_FOREACH_SAFE(cell, &chan->incoming_queue, next, cell_tmp) { + cell_queue_entry_free(cell, 0); } + SIMPLEQ_INIT(&chan->incoming_queue); /* Outgoing cell queue is similar, but we can have to free packed cells */ - if (chan->outgoing_queue) { - SMARTLIST_FOREACH_BEGIN(chan->outgoing_queue, - cell_queue_entry_t *, q) { - cell_queue_entry_free(q, 0); - } SMARTLIST_FOREACH_END(q); - - smartlist_free(chan->outgoing_queue); - chan->outgoing_queue = NULL; + SIMPLEQ_FOREACH_SAFE(cell, &chan->outgoing_queue, next, cell_tmp) { + cell_queue_entry_free(cell, 0); } + SIMPLEQ_INIT(&chan->outgoing_queue); tor_free(chan); } @@ -1046,8 +1042,7 @@ channel_set_cell_handlers(channel_t *chan, chan->var_cell_handler = var_cell_handler; /* Re-run the queue if we have one and there's any reason to */ - if (chan->incoming_queue && - (smartlist_len(chan->incoming_queue) > 0) && + if (! SIMPLEQ_EMPTY(&chan->incoming_queue) && try_again && (chan->cell_handler || chan->var_cell_handler)) channel_process_cells(chan); @@ -1669,9 +1664,8 @@ channel_write_cell_queue_entry(channel_t *chan, cell_queue_entry_t *q) } /* Can we send it right out? If so, try */ - if (!(chan->outgoing_queue && - (smartlist_len(chan->outgoing_queue) > 0)) && - chan->state == CHANNEL_STATE_OPEN) { + if (SIMPLEQ_EMPTY(&chan->outgoing_queue) && + chan->state == CHANNEL_STATE_OPEN) { /* Pick the right write function for this cell type and save the result */ switch (q->type) { case CELL_QUEUE_FIXED: @@ -1707,14 +1701,12 @@ channel_write_cell_queue_entry(channel_t *chan, cell_queue_entry_t *q) if (!sent) { /* Not sent, queue it */ - if (!(chan->outgoing_queue)) - chan->outgoing_queue = smartlist_new(); /* * We have to copy the queue entry passed in, since the caller probably * used the stack. */ tmp = cell_queue_entry_dup(q); - smartlist_add(chan->outgoing_queue, tmp); + SIMPLEQ_INSERT_TAIL(&chan->outgoing_queue, tmp, next); /* Try to process the queue? */ if (chan->state == CHANNEL_STATE_OPEN) channel_flush_cells(chan); } @@ -1900,19 +1892,15 @@ channel_change_state(channel_t *chan, channel_state_t to_state) channel_do_open_actions(chan); /* Check for queued cells to process */ - if (chan->incoming_queue && - smartlist_len(chan->incoming_queue) > 0) + if (! SIMPLEQ_EMPTY(&chan->incoming_queue)) channel_process_cells(chan); - if (chan->outgoing_queue && - smartlist_len(chan->outgoing_queue) > 0) + if (! SIMPLEQ_EMPTY(&chan->outgoing_queue)) channel_flush_cells(chan); } else if (to_state == CHANNEL_STATE_CLOSED || to_state == CHANNEL_STATE_ERROR) { /* Assert that all queues are empty */ - tor_assert(!(chan->incoming_queue) || - smartlist_len(chan->incoming_queue) == 0); - tor_assert(!(chan->outgoing_queue) || - smartlist_len(chan->outgoing_queue) == 0); + tor_assert(SIMPLEQ_EMPTY(&chan->incoming_queue)); + tor_assert(SIMPLEQ_EMPTY(&chan->outgoing_queue)); } } @@ -2086,16 +2074,9 @@ channel_flush_some_cells_from_outgoing_queue(channel_t *chan, /* If we aren't in CHANNEL_STATE_OPEN, nothing goes through */ if (chan->state == CHANNEL_STATE_OPEN) { while ((unlimited || num_cells > flushed) && - (chan->outgoing_queue && - (smartlist_len(chan->outgoing_queue) > 0))) { - /* - * Ewww, smartlist_del_keeporder() is O(n) in list length; maybe a - * a linked list would make more sense for the queue. - */ - - /* Get the head of the queue */ - q = smartlist_get(chan->outgoing_queue, 0); - if (q) { + NULL != (q = SIMPLEQ_FIRST(&chan->outgoing_queue))) { + + if (1) { /* * Okay, we have a good queue entry, try to give it to the lower * layer. @@ -2180,26 +2161,17 @@ channel_flush_some_cells_from_outgoing_queue(channel_t *chan, cell_queue_entry_free(q, 0); q = NULL; } - } else { - /* This shouldn't happen; log and throw it away */ - log_info(LD_CHANNEL, - "Saw a NULL entry in the outgoing cell queue on channel %p " - "(global ID " U64_FORMAT "); this is definitely a bug.", - chan, U64_PRINTF_ARG(chan->global_identifier)); - /* q is already NULL, so we know to delete that queue entry */ - } - /* if q got NULLed out, we used it and should remove the queue entry */ - if (!q) smartlist_del_keeporder(chan->outgoing_queue, 0); - /* No cell removed from list, so we can't go on any further */ - else break; + /* if q got NULLed out, we used it and should remove the queue entry */ + if (!q) SIMPLEQ_REMOVE_HEAD(&chan->outgoing_queue, next); + /* No cell removed from list, so we can't go on any further */ + else break; + } } } /* Did we drain the queue? */ - if (!(chan->outgoing_queue) || - smartlist_len(chan->outgoing_queue) == 0) { - /* Timestamp it */ + if (SIMPLEQ_EMPTY(&chan->outgoing_queue)) { channel_timestamp_drained(chan); } @@ -2233,8 +2205,8 @@ channel_more_to_flush(channel_t *chan) tor_assert(chan); /* Check if we have any queued */ - if (chan->incoming_queue && - smartlist_len(chan->incoming_queue) > 0) return 1; + if (! SIMPLEQ_EMPTY(&chan->incoming_queue)) + return 1; /* Check if any circuits would like to queue some */ if (circuitmux_num_cells(chan->cmux) > 0) return 1; @@ -2427,8 +2399,7 @@ channel_listener_queue_incoming(channel_listener_t *listener, void channel_process_cells(channel_t *chan) { - smartlist_t *queue; - int putback = 0; + cell_queue_entry_t *q; tor_assert(chan); tor_assert(chan->state == CHANNEL_STATE_CLOSING || chan->state == CHANNEL_STATE_MAINT || @@ -2442,24 +2413,21 @@ channel_process_cells(channel_t *chan) if (!(chan->cell_handler || chan->var_cell_handler)) return; /* Nothing we can do if we have no cells */ - if (!(chan->incoming_queue)) return; + if (SIMPLEQ_EMPTY(&chan->incoming_queue)) return; - queue = chan->incoming_queue; - chan->incoming_queue = NULL; /* * Process cells until we're done or find one we have no current handler * for. */ - SMARTLIST_FOREACH_BEGIN(queue, cell_queue_entry_t *, q) { + while (NULL != (q = SIMPLEQ_FIRST(&chan->incoming_queue))) { tor_assert(q); tor_assert(q->type == CELL_QUEUE_FIXED || q->type == CELL_QUEUE_VAR); - if (putback) { - smartlist_add(chan->incoming_queue, q); - } else if (q->type == CELL_QUEUE_FIXED && + if (q->type == CELL_QUEUE_FIXED && chan->cell_handler) { /* Handle a fixed-length cell */ + SIMPLEQ_REMOVE_HEAD(&chan->incoming_queue, next); tor_assert(q->u.fixed.cell); log_debug(LD_CHANNEL, "Processing incoming cell_t %p for channel %p (global ID " @@ -2471,6 +2439,7 @@ channel_process_cells(channel_t *chan) } else if (q->type == CELL_QUEUE_VAR && chan->var_cell_handler) { /* Handle a variable-length cell */ + SIMPLEQ_REMOVE_HEAD(&chan->incoming_queue, next); tor_assert(q->u.var.var_cell); log_debug(LD_CHANNEL, "Processing incoming var_cell_t %p for channel %p (global ID " @@ -2481,15 +2450,10 @@ channel_process_cells(channel_t *chan) tor_free(q); } else { /* Can't handle this one */ - if (!chan->incoming_queue) - chan->incoming_queue = smartlist_new(); - smartlist_add(chan->incoming_queue, q); - putback = 1; + break; } - } SMARTLIST_FOREACH_END(q); + } - /* If the list is empty, free it */ - smartlist_free(queue); } /** @@ -2511,15 +2475,9 @@ channel_queue_cell(channel_t *chan, cell_t *cell) /* Do we need to queue it, or can we just call the handler right away? */ if (!(chan->cell_handler)) need_to_queue = 1; - if (chan->incoming_queue && - (smartlist_len(chan->incoming_queue) > 0)) + if (! SIMPLEQ_EMPTY(&chan->incoming_queue)) need_to_queue = 1; - /* If we need to queue and have no queue, create one */ - if (need_to_queue && !(chan->incoming_queue)) { - chan->incoming_queue = smartlist_new(); - } - /* Timestamp for receiving */ channel_timestamp_recv(chan); @@ -2537,14 +2495,13 @@ channel_queue_cell(channel_t *chan, cell_t *cell) chan->cell_handler(chan, cell); } else { /* Otherwise queue it and then process the queue if possible. */ - tor_assert(chan->incoming_queue); q = cell_queue_entry_new_fixed(cell); log_debug(LD_CHANNEL, "Queueing incoming cell_t %p for channel %p " "(global ID " U64_FORMAT ")", cell, chan, U64_PRINTF_ARG(chan->global_identifier)); - smartlist_add(chan->incoming_queue, q); + SIMPLEQ_INSERT_TAIL(&chan->incoming_queue, q, next); if (chan->cell_handler || chan->var_cell_handler) { channel_process_cells(chan); @@ -2571,15 +2528,9 @@ channel_queue_var_cell(channel_t *chan, var_cell_t *var_cell) /* Do we need to queue it, or can we just call the handler right away? */ if (!(chan->var_cell_handler)) need_to_queue = 1; - if (chan->incoming_queue && - (smartlist_len(chan->incoming_queue) > 0)) + if (! SIMPLEQ_EMPTY(&chan->incoming_queue)) need_to_queue = 1; - /* If we need to queue and have no queue, create one */ - if (need_to_queue && !(chan->incoming_queue)) { - chan->incoming_queue = smartlist_new(); - } - /* Timestamp for receiving */ channel_timestamp_recv(chan); @@ -2597,14 +2548,13 @@ channel_queue_var_cell(channel_t *chan, var_cell_t *var_cell) chan->var_cell_handler(chan, var_cell); } else { /* Otherwise queue it and then process the queue if possible. */ - tor_assert(chan->incoming_queue); q = cell_queue_entry_new_var(var_cell); log_debug(LD_CHANNEL, "Queueing incoming var_cell_t %p for channel %p " "(global ID " U64_FORMAT ")", var_cell, chan, U64_PRINTF_ARG(chan->global_identifier)); - smartlist_add(chan->incoming_queue, q); + SIMPLEQ_INSERT_TAIL(&chan->incoming_queue, q, next); if (chan->cell_handler || chan->var_cell_handler) { channel_process_cells(chan); @@ -3134,6 +3084,19 @@ channel_listener_describe_transport(channel_listener_t *chan_l) } /** + * Return the number of entries in queue + */ +static int +chan_cell_queue_len(const chan_cell_queue_t *queue) +{ + int r = 0; + cell_queue_entry_t *cell; + SIMPLEQ_FOREACH(cell, queue, next) + ++r; + return r; +} + +/** * Dump channel statistics * * Dump statistics for one channel to the log @@ -3246,10 +3209,8 @@ channel_dump_statistics(channel_t *chan, int severity) " * Channel " U64_FORMAT " has %d queued incoming cells" " and %d queued outgoing cells", U64_PRINTF_ARG(chan->global_identifier), - (chan->incoming_queue != NULL) ? - smartlist_len(chan->incoming_queue) : 0, - (chan->outgoing_queue != NULL) ? - smartlist_len(chan->outgoing_queue) : 0); + chan_cell_queue_len(&chan->incoming_queue), + chan_cell_queue_len(&chan->outgoing_queue)); /* Describe circuits */ log(severity, LD_GENERAL, @@ -3498,8 +3459,7 @@ channel_has_queued_writes(channel_t *chan) tor_assert(chan); tor_assert(chan->has_queued_writes); - if (chan->outgoing_queue && - smartlist_len(chan->outgoing_queue) > 0) { + if (! SIMPLEQ_EMPTY(&chan->outgoing_queue)) { has_writes = 1; } else { /* Check with the lower layer */ diff --git a/src/or/channel.h b/src/or/channel.h index cb9835a..ccb8fe8 100644 --- a/src/or/channel.h +++ b/src/or/channel.h @@ -10,6 +10,7 @@ #define _TOR_CHANNEL_H #include "or.h" +#include "tor_queue.h" #include "circuitmux.h" /* Channel handler function pointer typedefs */ @@ -17,6 +18,10 @@ typedef void (*channel_listener_fn_ptr)(channel_listener_t *, channel_t *); typedef void (*channel_cell_handler_fn_ptr)(channel_t *, cell_t *); typedef void (*channel_var_cell_handler_fn_ptr)(channel_t *, var_cell_t *); +struct cell_queue_entry_s; +SIMPLEQ_HEAD(chan_cell_queue, cell_queue_entry_s) incoming_queue; +typedef struct chan_cell_queue chan_cell_queue_t; + /* * Channel struct; see the channel_t typedef in or.h. A channel is an * abstract interface for the OR-to-OR connection, similar to connection_or_t, @@ -120,10 +125,10 @@ struct channel_s { channel_t *next_with_same_id, *prev_with_same_id; /* List of incoming cells to handle */ - smartlist_t *incoming_queue; + chan_cell_queue_t incoming_queue; /* List of queued outgoing cells */ - smartlist_t *outgoing_queue; + chan_cell_queue_t outgoing_queue; /* Circuit mux for circuits sending on this channel */ circuitmux_t *cmux;

1 0

[tor/master] Add a copy of OpenBSD's sys/queue.h as tor_queue.h
by andrea＠torproject.org 30 Oct '12

30 Oct '12

commit b555388dac71696c6a1028805094e16b5e5b2b82 Author: Nick Mathewson <nickm(a)torproject.org> Date: Fri Oct 12 17:05:06 2012 -0400 Add a copy of OpenBSD's sys/queue.h as tor_queue.h There are as many divergent implementations of sys/queue.h as there are operating systems shipping it, it would seem. They have some code in common, but have drifted apart, and have added other stuff named differently. So I'm taking a relatively sane one, and hoping for the best. I'm taking OpenBSD's in particular because of the lack of external dependencies, the presence of a CIRCLEQ (we could use one of those in places), and the liberal licensing terms. I'm naming the file tor_queue.h, since historically we've run into trouble having headers with the same names as system headers (log.h, for example.) --- LICENSE | 29 +++ changes/bsd_queue | 7 + src/ext/README | 8 + src/ext/include.am | 3 +- src/ext/tor_queue.h | 568 +++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 614 insertions(+), 1 deletions(-) diff --git a/LICENSE b/LICENSE index 47eaf97..3058377 100644 --- a/LICENSE +++ b/LICENSE @@ -70,6 +70,35 @@ under the following license: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +=============================================================================== +src/ext/tor_queue.h is licensed under the following license: + + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. =============================================================================== src/config/geoip is licensed under the following license: diff --git a/changes/bsd_queue b/changes/bsd_queue new file mode 100644 index 0000000..024ca6f --- /dev/null +++ b/changes/bsd_queue @@ -0,0 +1,7 @@ + o Code simplification and refactoring: + - Start using OpenBSD's implementation of queue.h, so that we don't + need to hand-roll our own pointer and list structures whenever we + need them. (We can't rely on a sys/queue.h, since some operating + systems don't have them, and the ones that do have them don't all + present the same extensions.) + diff --git a/src/ext/README b/src/ext/README index 2c303c1..7aeaba5 100644 --- a/src/ext/README +++ b/src/ext/README @@ -29,3 +29,11 @@ tinytest_macros.h A unit testing framework. https://github.com/nmathewson/tinytest +tor_queue.h + + A copy of sys/queue.h from OpenBSD. We keep our own copy rather + than using sys/queue.h, since some platforms don't have a + sys/queue.h, and the ones that do have diverged in incompatible + ways. (CIRCLEQ or no CIRCLEQ? SIMPLQ or STAILQ?) + + diff --git a/src/ext/include.am b/src/ext/include.am index fa9ee94..ea7e58e 100644 --- a/src/ext/include.am +++ b/src/ext/include.am @@ -9,7 +9,8 @@ EXTHEADERS = \ src/ext/tinytest.h \ src/ext/strlcat.c \ src/ext/strlcpy.c \ - src/ext/tinytest_macros.h + src/ext/tinytest_macros.h \ + src/ext/tor_queue.h noinst_HEADERS+= $(EXTHEADERS) diff --git a/src/ext/tor_queue.h b/src/ext/tor_queue.h new file mode 100644 index 0000000..622301d --- /dev/null +++ b/src/ext/tor_queue.h @@ -0,0 +1,568 @@ +/* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ +/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ + +/* + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * @(#)queue.h 8.5 (Berkeley) 8/20/94 + */ + +#ifndef _SYS_QUEUE_H_ +#define _SYS_QUEUE_H_ + +/* + * This file defines five types of data structures: singly-linked lists, + * lists, simple queues, tail queues, and circular queues. + * + * + * A singly-linked list is headed by a single forward pointer. The elements + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary elements. New elements can be + * added to the list after an existing element or at the head of the list. + * Elements being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The elements are doubly linked + * so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before + * or after an existing element or at the head of the list. A list + * may only be traversed in the forward direction. + * + * A simple queue is headed by a pair of pointers, one the head of the + * list and the other to the tail of the list. The elements are singly + * linked to save space, so elements can only be removed from the + * head of the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the + * list. A simple queue may only be traversed in the forward direction. + * + * A tail queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or + * after an existing element, at the head of the list, or at the end of + * the list. A tail queue may be traversed in either direction. + * + * A circle queue is headed by a pair of pointers, one to the head of the + * list and the other to the tail of the list. The elements are doubly + * linked so that an arbitrary element can be removed without a need to + * traverse the list. New elements can be added to the list before or after + * an existing element, at the head of the list, or at the end of the list. + * A circle queue may be traversed in either direction, but has a more + * complex end of list detection. + * + * For details on the use of these macros, see the queue(3) manual page. + */ + +#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) +#define _Q_INVALIDATE(a) (a) = ((void *)-1) +#else +#define _Q_INVALIDATE(a) +#endif + +/* + * Singly-linked List definitions. + */ +#define SLIST_HEAD(name, type) \ +struct name { \ + struct type *slh_first; /* first element */ \ +} + +#define SLIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define SLIST_ENTRY(type) \ +struct { \ + struct type *sle_next; /* next element */ \ +} + +/* + * Singly-linked List access methods. + */ +#define SLIST_FIRST(head) ((head)->slh_first) +#define SLIST_END(head) NULL +#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head)) +#define SLIST_NEXT(elm, field) ((elm)->field.sle_next) + +#define SLIST_FOREACH(var, head, field) \ + for((var) = SLIST_FIRST(head); \ + (var) != SLIST_END(head); \ + (var) = SLIST_NEXT(var, field)) + +#define SLIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SLIST_FIRST(head); \ + (var) && ((tvar) = SLIST_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Singly-linked List functions. + */ +#define SLIST_INIT(head) { \ + SLIST_FIRST(head) = SLIST_END(head); \ +} + +#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ + (elm)->field.sle_next = (slistelm)->field.sle_next; \ + (slistelm)->field.sle_next = (elm); \ +} while (0) + +#define SLIST_INSERT_HEAD(head, elm, field) do { \ + (elm)->field.sle_next = (head)->slh_first; \ + (head)->slh_first = (elm); \ +} while (0) + +#define SLIST_REMOVE_AFTER(elm, field) do { \ + (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \ +} while (0) + +#define SLIST_REMOVE_HEAD(head, field) do { \ + (head)->slh_first = (head)->slh_first->field.sle_next; \ +} while (0) + +#define SLIST_REMOVE(head, elm, type, field) do { \ + if ((head)->slh_first == (elm)) { \ + SLIST_REMOVE_HEAD((head), field); \ + } else { \ + struct type *curelm = (head)->slh_first; \ + \ + while (curelm->field.sle_next != (elm)) \ + curelm = curelm->field.sle_next; \ + curelm->field.sle_next = \ + curelm->field.sle_next->field.sle_next; \ + _Q_INVALIDATE((elm)->field.sle_next); \ + } \ +} while (0) + +/* + * List definitions. + */ +#define LIST_HEAD(name, type) \ +struct name { \ + struct type *lh_first; /* first element */ \ +} + +#define LIST_HEAD_INITIALIZER(head) \ + { NULL } + +#define LIST_ENTRY(type) \ +struct { \ + struct type *le_next; /* next element */ \ + struct type **le_prev; /* address of previous next element */ \ +} + +/* + * List access methods + */ +#define LIST_FIRST(head) ((head)->lh_first) +#define LIST_END(head) NULL +#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head)) +#define LIST_NEXT(elm, field) ((elm)->field.le_next) + +#define LIST_FOREACH(var, head, field) \ + for((var) = LIST_FIRST(head); \ + (var)!= LIST_END(head); \ + (var) = LIST_NEXT(var, field)) + +#define LIST_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = LIST_FIRST(head); \ + (var) && ((tvar) = LIST_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * List functions. + */ +#define LIST_INIT(head) do { \ + LIST_FIRST(head) = LIST_END(head); \ +} while (0) + +#define LIST_INSERT_AFTER(listelm, elm, field) do { \ + if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ + (listelm)->field.le_next->field.le_prev = \ + &(elm)->field.le_next; \ + (listelm)->field.le_next = (elm); \ + (elm)->field.le_prev = &(listelm)->field.le_next; \ +} while (0) + +#define LIST_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.le_prev = (listelm)->field.le_prev; \ + (elm)->field.le_next = (listelm); \ + *(listelm)->field.le_prev = (elm); \ + (listelm)->field.le_prev = &(elm)->field.le_next; \ +} while (0) + +#define LIST_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.le_next = (head)->lh_first) != NULL) \ + (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ + (head)->lh_first = (elm); \ + (elm)->field.le_prev = &(head)->lh_first; \ +} while (0) + +#define LIST_REMOVE(elm, field) do { \ + if ((elm)->field.le_next != NULL) \ + (elm)->field.le_next->field.le_prev = \ + (elm)->field.le_prev; \ + *(elm)->field.le_prev = (elm)->field.le_next; \ + _Q_INVALIDATE((elm)->field.le_prev); \ + _Q_INVALIDATE((elm)->field.le_next); \ +} while (0) + +#define LIST_REPLACE(elm, elm2, field) do { \ + if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \ + (elm2)->field.le_next->field.le_prev = \ + &(elm2)->field.le_next; \ + (elm2)->field.le_prev = (elm)->field.le_prev; \ + *(elm2)->field.le_prev = (elm2); \ + _Q_INVALIDATE((elm)->field.le_prev); \ + _Q_INVALIDATE((elm)->field.le_next); \ +} while (0) + +/* + * Simple queue definitions. + */ +#define SIMPLEQ_HEAD(name, type) \ +struct name { \ + struct type *sqh_first; /* first element */ \ + struct type **sqh_last; /* addr of last next element */ \ +} + +#define SIMPLEQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).sqh_first } + +#define SIMPLEQ_ENTRY(type) \ +struct { \ + struct type *sqe_next; /* next element */ \ +} + +/* + * Simple queue access methods. + */ +#define SIMPLEQ_FIRST(head) ((head)->sqh_first) +#define SIMPLEQ_END(head) NULL +#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head)) +#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) + +#define SIMPLEQ_FOREACH(var, head, field) \ + for((var) = SIMPLEQ_FIRST(head); \ + (var) != SIMPLEQ_END(head); \ + (var) = SIMPLEQ_NEXT(var, field)) + +#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = SIMPLEQ_FIRST(head); \ + (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \ + (var) = (tvar)) + +/* + * Simple queue functions. + */ +#define SIMPLEQ_INIT(head) do { \ + (head)->sqh_first = NULL; \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (0) + +#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (head)->sqh_first = (elm); \ +} while (0) + +#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.sqe_next = NULL; \ + *(head)->sqh_last = (elm); \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (0) + +#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ + (head)->sqh_last = &(elm)->field.sqe_next; \ + (listelm)->field.sqe_next = (elm); \ +} while (0) + +#define SIMPLEQ_REMOVE_HEAD(head, field) do { \ + if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ + (head)->sqh_last = &(head)->sqh_first; \ +} while (0) + +#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ + if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \ + == NULL) \ + (head)->sqh_last = &(elm)->field.sqe_next; \ +} while (0) + +/* + * Tail queue definitions. + */ +#define TAILQ_HEAD(name, type) \ +struct name { \ + struct type *tqh_first; /* first element */ \ + struct type **tqh_last; /* addr of last next element */ \ +} + +#define TAILQ_HEAD_INITIALIZER(head) \ + { NULL, &(head).tqh_first } + +#define TAILQ_ENTRY(type) \ +struct { \ + struct type *tqe_next; /* next element */ \ + struct type **tqe_prev; /* address of previous next element */ \ +} + +/* + * tail queue access methods + */ +#define TAILQ_FIRST(head) ((head)->tqh_first) +#define TAILQ_END(head) NULL +#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) +#define TAILQ_LAST(head, headname) \ + (*(((struct headname *)((head)->tqh_last))->tqh_last)) +/* XXX */ +#define TAILQ_PREV(elm, headname, field) \ + (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) +#define TAILQ_EMPTY(head) \ + (TAILQ_FIRST(head) == TAILQ_END(head)) + +#define TAILQ_FOREACH(var, head, field) \ + for((var) = TAILQ_FIRST(head); \ + (var) != TAILQ_END(head); \ + (var) = TAILQ_NEXT(var, field)) + +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST(head); \ + (var) != TAILQ_END(head) && \ + ((tvar) = TAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) + + +#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ + for((var) = TAILQ_LAST(head, headname); \ + (var) != TAILQ_END(head); \ + (var) = TAILQ_PREV(var, headname, field)) + +#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = TAILQ_LAST(head, headname); \ + (var) != TAILQ_END(head) && \ + ((tvar) = TAILQ_PREV(var, headname, field), 1); \ + (var) = (tvar)) + +/* + * Tail queue functions. + */ +#define TAILQ_INIT(head) do { \ + (head)->tqh_first = NULL; \ + (head)->tqh_last = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_HEAD(head, elm, field) do { \ + if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ + (head)->tqh_first->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (head)->tqh_first = (elm); \ + (elm)->field.tqe_prev = &(head)->tqh_first; \ +} while (0) + +#define TAILQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.tqe_next = NULL; \ + (elm)->field.tqe_prev = (head)->tqh_last; \ + *(head)->tqh_last = (elm); \ + (head)->tqh_last = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ + if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ + (elm)->field.tqe_next->field.tqe_prev = \ + &(elm)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm)->field.tqe_next; \ + (listelm)->field.tqe_next = (elm); \ + (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ +} while (0) + +#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ + (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ + (elm)->field.tqe_next = (listelm); \ + *(listelm)->field.tqe_prev = (elm); \ + (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ +} while (0) + +#define TAILQ_REMOVE(head, elm, field) do { \ + if (((elm)->field.tqe_next) != NULL) \ + (elm)->field.tqe_next->field.tqe_prev = \ + (elm)->field.tqe_prev; \ + else \ + (head)->tqh_last = (elm)->field.tqe_prev; \ + *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ + _Q_INVALIDATE((elm)->field.tqe_prev); \ + _Q_INVALIDATE((elm)->field.tqe_next); \ +} while (0) + +#define TAILQ_REPLACE(head, elm, elm2, field) do { \ + if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \ + (elm2)->field.tqe_next->field.tqe_prev = \ + &(elm2)->field.tqe_next; \ + else \ + (head)->tqh_last = &(elm2)->field.tqe_next; \ + (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \ + *(elm2)->field.tqe_prev = (elm2); \ + _Q_INVALIDATE((elm)->field.tqe_prev); \ + _Q_INVALIDATE((elm)->field.tqe_next); \ +} while (0) + +/* + * Circular queue definitions. + */ +#define CIRCLEQ_HEAD(name, type) \ +struct name { \ + struct type *cqh_first; /* first element */ \ + struct type *cqh_last; /* last element */ \ +} + +#define CIRCLEQ_HEAD_INITIALIZER(head) \ + { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } + +#define CIRCLEQ_ENTRY(type) \ +struct { \ + struct type *cqe_next; /* next element */ \ + struct type *cqe_prev; /* previous element */ \ +} + +/* + * Circular queue access methods + */ +#define CIRCLEQ_FIRST(head) ((head)->cqh_first) +#define CIRCLEQ_LAST(head) ((head)->cqh_last) +#define CIRCLEQ_END(head) ((void *)(head)) +#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) +#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) +#define CIRCLEQ_EMPTY(head) \ + (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) + +#define CIRCLEQ_FOREACH(var, head, field) \ + for((var) = CIRCLEQ_FIRST(head); \ + (var) != CIRCLEQ_END(head); \ + (var) = CIRCLEQ_NEXT(var, field)) + +#define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = CIRCLEQ_FIRST(head); \ + (var) != CIRCLEQ_END(head) && \ + ((tvar) = CIRCLEQ_NEXT(var, field), 1); \ + (var) = (tvar)) + +#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ + for((var) = CIRCLEQ_LAST(head); \ + (var) != CIRCLEQ_END(head); \ + (var) = CIRCLEQ_PREV(var, field)) + +#define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ + for ((var) = CIRCLEQ_LAST(head, headname); \ + (var) != CIRCLEQ_END(head) && \ + ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \ + (var) = (tvar)) + +/* + * Circular queue functions. + */ +#define CIRCLEQ_INIT(head) do { \ + (head)->cqh_first = CIRCLEQ_END(head); \ + (head)->cqh_last = CIRCLEQ_END(head); \ +} while (0) + +#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ + (elm)->field.cqe_next = (listelm)->field.cqe_next; \ + (elm)->field.cqe_prev = (listelm); \ + if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ + (head)->cqh_last = (elm); \ + else \ + (listelm)->field.cqe_next->field.cqe_prev = (elm); \ + (listelm)->field.cqe_next = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ + (elm)->field.cqe_next = (listelm); \ + (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ + if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ + (head)->cqh_first = (elm); \ + else \ + (listelm)->field.cqe_prev->field.cqe_next = (elm); \ + (listelm)->field.cqe_prev = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ + (elm)->field.cqe_next = (head)->cqh_first; \ + (elm)->field.cqe_prev = CIRCLEQ_END(head); \ + if ((head)->cqh_last == CIRCLEQ_END(head)) \ + (head)->cqh_last = (elm); \ + else \ + (head)->cqh_first->field.cqe_prev = (elm); \ + (head)->cqh_first = (elm); \ +} while (0) + +#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ + (elm)->field.cqe_next = CIRCLEQ_END(head); \ + (elm)->field.cqe_prev = (head)->cqh_last; \ + if ((head)->cqh_first == CIRCLEQ_END(head)) \ + (head)->cqh_first = (elm); \ + else \ + (head)->cqh_last->field.cqe_next = (elm); \ + (head)->cqh_last = (elm); \ +} while (0) + +#define CIRCLEQ_REMOVE(head, elm, field) do { \ + if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ + (head)->cqh_last = (elm)->field.cqe_prev; \ + else \ + (elm)->field.cqe_next->field.cqe_prev = \ + (elm)->field.cqe_prev; \ + if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ + (head)->cqh_first = (elm)->field.cqe_next; \ + else \ + (elm)->field.cqe_prev->field.cqe_next = \ + (elm)->field.cqe_next; \ + _Q_INVALIDATE((elm)->field.cqe_prev); \ + _Q_INVALIDATE((elm)->field.cqe_next); \ +} while (0) + +#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ + if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ + CIRCLEQ_END(head)) \ + (head).cqh_last = (elm2); \ + else \ + (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ + if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ + CIRCLEQ_END(head)) \ + (head).cqh_first = (elm2); \ + else \ + (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ + _Q_INVALIDATE((elm)->field.cqe_prev); \ + _Q_INVALIDATE((elm)->field.cqe_next); \ +} while (0) + +#endif /* !_SYS_QUEUE_H_ */

1 0