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

[translation/orbot] Update translations for orbot
by translation＠torproject.org 24 Oct '12

24 Oct '12

commit 7f5157b5ca731c81e9608ad1117af98e2acea985 Author: Translation commit bot <translation(a)torproject.org> Date: Wed Oct 24 11:15:06 2012 +0000 Update translations for orbot --- values-fa/strings.xml | 6 ++++++ 1 files changed, 6 insertions(+), 0 deletions(-) diff --git a/values-fa/strings.xml b/values-fa/strings.xml index 4cbbb18..7afc086 100644 --- a/values-fa/strings.xml +++ b/values-fa/strings.xml @@ -75,7 +75,11 @@ <string name="wizard_tips_otrchat">ربات پرچونه - کلاینت گفتگوی امن برای اندروید</string> <string name="wizard_tips_proxy">تنظیمات پروکسی - یادگیری تنظیم اپلیکیشن ها برای کار با ربات پیازی</string> <string name="wizard_tips_duckgo">اپلیکیشن موتور جستجوی داک داک گو</string> + <string name="duckgo_apk_url">https://duckduckgo.com/android/latest.apk</string> + <string name="wizard_tips_firefox">Proxy Mobile add-on for Firefox (http://tinyurl.com/getproxymob)</string> + <string name="proxymob_setup_url">https://guardianproject.info/releases/proxymob-latest.xpi</string> <string name="wizard_tips_twitter">توییتر از \"http proxy \"localhost:8118 پشتیبانی می کند</string> + <string name="twitter_setup_url">https://guardianproject.info/2012/05/02/orbot-your-twitter/</string> <string name="wizard_proxy_help_info">تنظیمات پروکسی</string> <string name="wizard_proxy_help_msg">اگر اپلیکشین آندروید مورد استفاده شما قابلیت کار با HTTP و یا SOCKS پروکسی دارد می توانید تنظیمش کنید تا به ربات پیازی وصل شود و از تور استفاده کند. تنظیمات سرویس دهنده 127.0.0.1 و یا \"سرویس-ده محلی\" است. برای HTTP تنظیمات پورت 8118 است. برای SOCKS، پروکسی مناسب، 9050 است. شما می بایست SOCKS4A و یا در صورت امکان از socks5 استفاده کنید. در صورت نیاز به اطلاعات بیشتر در مورد انتقالده اندروید، می توانید به FAQ (سوالهای معمول) در http://tinyurl.com/proxyandroid مراجعه کنید.</string> <string name="wizard_final">ربات پیازی آماده استفاده میباشد!</string> @@ -104,6 +108,8 @@ <string name="gibberbot_apk_url">https://market.android.com/details?id=info.guardianproject.otr.app.im</string> <string name="wizard_tips_orweb">مرورگر پیازی: مرورگر طراحی شده برای حفظ حریم خصوصی و افزونساز ربات پیازی</string> <string name="orweb_apk_url">market://search?q=pname:nfo.guardianproject.browser</string> + <string name="wizard_tips_play">تمامي برنامه هاي Guardian Project را در Google Play پيدا كنيد.</string> + <string name="wizard_tips_play_url">https://play.google.com/store/search?q=guardianproject</string> <!--<string name="wizard_tips_firefox">Firefox - Android browser - To be used along with ProxyMob Add-on </string> <string name="wizard_tips_proxymob">ProxyMob - Simple Firefox Add-on for setting HTTP, SOCKS and SSL proxy settings</string> <string name="firefox_apk_url">https://market.android.com/details?id=org.mozilla.firefox</string>

1 0

[translation/liveusb-creator] Update translations for liveusb-creator
by translation＠torproject.org 24 Oct '12

24 Oct '12

commit 5ec247bf47caab9f1e37a3b325127024d10fc480 Author: Translation commit bot <translation(a)torproject.org> Date: Wed Oct 24 10:45:35 2012 +0000 Update translations for liveusb-creator --- fa/fa.po | 39 ++++++++++++++++++++------------------- 1 files changed, 20 insertions(+), 19 deletions(-) diff --git a/fa/fa.po b/fa/fa.po index a082d68..6b0c7cb 100644 --- a/fa/fa.po +++ b/fa/fa.po @@ -3,13 +3,14 @@ # This file is distributed under the same license as the PACKAGE package. # # Translators: +# <joe_ironsmith(a)yahoo.com>, 2012. msgid "" msgstr "" "Project-Id-Version: The Tor Project\n" "Report-Msgid-Bugs-To: https://trac.torproject.org/projects/tor\n" "POT-Creation-Date: 2012-04-13 14:16+0200\n" -"PO-Revision-Date: 2012-10-03 18:09+0000\n" -"Last-Translator: Tor Project <tor-assistants(a)torproject.org>\n" +"PO-Revision-Date: 2012-10-24 10:37+0000\n" +"Last-Translator: Joe.Ironsmith <joe_ironsmith(a)yahoo.com>\n" "Language-Team: LANGUAGE <LL(a)li.org>\n" "MIME-Version: 1.0\n" "Content-Type: text/plain; charset=UTF-8\n" @@ -30,7 +31,7 @@ msgstr "در حال بارگیری %s..." #: ../liveusb/gui.py:197 #, python-format msgid "Device is too small: it must be at least %s MiB." -msgstr "" +msgstr "دستگاه خيلي كوچك است: بايد حداقل %s مگابايت باشد." #: ../liveusb/gui.py:226 msgid "" @@ -41,7 +42,7 @@ msgstr "خطا: نمی تواند برچسب را تنظیم کند و یا UUID #: ../liveusb/gui.py:276 #, python-format msgid "Installation complete! (%s)" -msgstr "" +msgstr "عمليات نصب به پايان رسيد! (%s)" #: ../liveusb/gui.py:281 msgid "LiveUSB creation failed!" @@ -52,17 +53,17 @@ msgid "" "Warning: This tool needs to be run as an Administrator. To do this, right " "click on the icon and open the Properties. Under the Compatibility tab, " "check the \"Run this program as an administrator\" box." -msgstr "" +msgstr "هشدار: اين ابزار نياز به اجرا شدن توسط مدير سيستم دارد. براي انجام اين كار، بر روي آيكون راست كليك كرده، سپس Properties را انتخاب كرده و از لبه Compatibility، گزينه Run the program as an administrator را انتخاب كنيد." #: ../liveusb/gui.py:413 msgid "Unable to find any USB drive" -msgstr "" +msgstr "قادر به یافتن هیچ درایو یو اس بی نیست" #: ../liveusb/gui.py:521 msgid "" "Device is not yet mounted, so we cannot determine the amount of free space." " Setting a maximum limit of 8G for the persistent storage." -msgstr "" +msgstr "دستگاه هنوز متصل نشده است، بنابراين ما نميتوانيم فضاي خالي را بررسي كنيم. حداكثر فضاي 8 گيگابايتي براي ذخيره سازي مداوم انتخاب مي شود." #: ../liveusb/gui.py:528 #, python-format @@ -75,15 +76,15 @@ msgstr "" #: ../liveusb/gui.py:577 msgid "Persistent Storage" -msgstr "" +msgstr "ذخيره سازي مداوم" #: ../liveusb/gui.py:586 msgid "Installation complete!" -msgstr "" +msgstr "عمليات نصب به پايان رسيد!" #: ../liveusb/gui.py:587 msgid "Installation was completed. Press OK to close this program." -msgstr "" +msgstr "عمليات نصب به پايان رسيد. دكمه OK را براي بستن برنامه بزنيد." #: ../liveusb/gui.py:610 msgid "" @@ -100,19 +101,19 @@ msgstr "" #: ../liveusb/gui.py:638 msgid "Unable to mount device" -msgstr "" +msgstr "فادر به بارگذاري دستگاه نيست." #: ../liveusb/gui.py:644 msgid "Warning: All data on the selected drive will be lost." -msgstr "" +msgstr "هشدار: تمامي اطلاعات درايو انتخاب شده از بين خواهد رفت." #: ../liveusb/gui.py:646 ../liveusb/gui.py:663 msgid "Press 'Next' if you wish to continue." -msgstr "" +msgstr "اگر مايل به ادامه هستيد، دكمه 'بعدي' را بزنيد." #: ../liveusb/gui.py:648 ../liveusb/gui.py:665 msgid "Next" -msgstr "" +msgstr "بعدي" #: ../liveusb/gui.py:658 msgid "" @@ -145,13 +146,13 @@ msgstr "انتخاب ایزوی لایو" msgid "" "The selected file is unreadable.Please fix its permissions or select another" " file." -msgstr "" +msgstr "فايل انتخاب شده غير قابل خواندن است. لطفاً دسترسي آن را تصحيح كرده يا فايل ديگري را انتخاب كنيد." #: ../liveusb/gui.py:737 msgid "" "Unable to use the selected file. You may have better luck if you move your " "ISO to the root of your drive (ie: C:\\)" -msgstr "" +msgstr "قادر به استفاده از فايل انتخاب شده نيست. اگر فايل ايزو را به ريشه درايو خود (مثلاً C) منتقل كنيد ممكن است شانس بيتشري داشته باشيد." #: ../liveusb/gui.py:743 #, python-format @@ -160,7 +161,7 @@ msgstr "" #: ../liveusb/creator.py:91 msgid "You must run this application as root" -msgstr "" +msgstr "شما بايد اين برنامه را با دسترسي روت اجرا كنيد" #: ../liveusb/creator.py:130 msgid "" @@ -275,7 +276,7 @@ msgstr "" #: ../liveusb/creator.py:786 ../liveusb/creator.py:886 msgid "Unknown filesystem. Your device may need to be reformatted." -msgstr "" +msgstr "نوع فايل سيستم ناشناخته است. دستگاه شما ممكن است نياز به فرمت مجدد داشته باشد." #: ../liveusb/creator.py:789 #, python-format @@ -301,7 +302,7 @@ msgstr "" #: ../liveusb/creator.py:823 msgid "No mount points found" -msgstr "" +msgstr "هيچ نقطه بازگذاري يافت نشد" #: ../liveusb/creator.py:834 #, python-format

1 0

[tor/release-0.2.3] prep for next rc
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit 89dc27b989509600a557181be376c7848800f02b Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Oct 23 22:12:08 2012 -0400 prep for next rc --- ChangeLog | 22 ++++++++++++++++++++++ changes/bug7190 | 6 ------ changes/bug7191 | 5 ----- changes/bug7192 | 10 ---------- 4 files changed, 22 insertions(+), 21 deletions(-) diff --git a/ChangeLog b/ChangeLog index 173fed6..39d6e4b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,25 @@ +Changes in version 0.2.3.24-rc - 2012-10-2? + o Major bugfixes: + - Fix a denial of service attack by which any directory authority + could crash all the others, or by which a single v2 directory + authority could crash everybody downloading v2 directory + information. Fixes bug 7191; bugfix on 0.2.0.10-alpha. + - When parsing exit policy summaries from microdescriptors, we had + previously been ignoring the last character in each one, so that + "accept 80,443,8080" would be treated by clients as indicating + a node that allows access to ports 80, 443, and 808. That would + lead to clients attempting connections that could never work, + and ignoring exit nodes that would support their connections. Now + clients parse these exit policy summaries correctly. Fixes bug 7192; + bugfix on 0.2.3.1-alpha. + + o Minor bugfixes: + - Clients now consider the ClientRejectInternalAddresses config option + when using a microdescriptor consensus stanza to decide whether + an exit relay would allow exiting to an internal address. Fixes + bug 7190; bugfix on 0.2.3.1-alpha. + + Changes in version 0.2.3.23-rc - 2012-10-20 Tor 0.2.3.23-rc adds a new v3 directory authority, fixes a privacy vulnerability introduced by a change in OpenSSL, and fixes a variety diff --git a/changes/bug7190 b/changes/bug7190 deleted file mode 100644 index 1607f79..0000000 --- a/changes/bug7190 +++ /dev/null @@ -1,6 +0,0 @@ - o Minor bugfixes: - - Clients now consider the ClientRejectInternalAddresses config option - when using a microdescriptor consensus stanza to decide whether - an exit relay would allow exiting to an internal address. Fixes - bug 7190; bugfix on 0.2.3.1-alpha. - diff --git a/changes/bug7191 b/changes/bug7191 deleted file mode 100644 index a3bee6e..0000000 --- a/changes/bug7191 +++ /dev/null @@ -1,5 +0,0 @@ - o Major bugfixes: - - Fix a denial of service attack by which any directory authority - could crash all the others, or by which a single v2 directory - authority could crash everybody downloading v2 directory - information. Fixes bug 7191; bugfix on 0.2.0.10-alpha. diff --git a/changes/bug7192 b/changes/bug7192 deleted file mode 100644 index 10cbc24..0000000 --- a/changes/bug7192 +++ /dev/null @@ -1,10 +0,0 @@ - o Major bugfixes: - - When parsing exit policy summaries from microdescriptors, we had - previously been ignoring the last character in each one, so that - "accept 80,443,8080" would be treated by clients as indicating a - node that allows access to ports 80, 443, and 808. That would lead - to clients attempting connections that could never work, and - ignoring exit nodes that would support their connections. Now clients - parse these exit policy summaries correctly. Fixes bug 7192; - bugfix on 0.2.3.1-alpha. -

1 0

[tor/release-0.2.3] Make unit test for bug7191 work with new smartlist_new() name
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit b99457d4295b2329e65f3e01b24b57d5c78ca017 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 23 21:49:46 2012 -0400 Make unit test for bug7191 work with new smartlist_new() name --- src/test/test_containers.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/test/test_containers.c b/src/test/test_containers.c index 9a306ad..45898df 100644 --- a/src/test/test_containers.c +++ b/src/test/test_containers.c @@ -229,7 +229,7 @@ test_container_smartlist_strings(void) test_eq(f, 0); /* Test trivial cases for list of length 0 or 1 */ - tmp = smartlist_create(); + tmp = smartlist_new(); test_eq(0, smartlist_bsearch_idx(tmp, "foo", compare_strs_for_bsearch_, &f)); test_eq(f, 0);

1 0

[tor/release-0.2.3] Merge remote-tracking branch 'origin/maint-0.2.2' into maint-0.2.3
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit b0646cc1423d4ea28d68c84e38e90ba8a6cb4e29 Merge: 2ecee3f cb693ef Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 23 21:48:50 2012 -0400 Merge remote-tracking branch 'origin/maint-0.2.2' into maint-0.2.3 changes/bug7191 | 5 +++++ src/common/container.c | 23 ++++++++++++++++++++++- src/test/test_containers.c | 36 ++++++++++++++++++++++++++++++++++++ 3 files changed, 63 insertions(+), 1 deletions(-)

1 0

[tor/release-0.2.3] Add some unit tests for smartlist_bsearch_idx() on short lists
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit cb693ef56e5fcef2a6d1844cb71c849022628bd8 Author: Andrea Shepard <andrea(a)torproject.org> Date: Tue Oct 23 14:28:19 2012 -0700 Add some unit tests for smartlist_bsearch_idx() on short lists Conflicts: src/test/test_containers.c --- src/test/test_containers.c | 36 ++++++++++++++++++++++++++++++++++++ 1 files changed, 36 insertions(+), 0 deletions(-) diff --git a/src/test/test_containers.c b/src/test/test_containers.c index af9fb1c..46cc82d 100644 --- a/src/test/test_containers.c +++ b/src/test/test_containers.c @@ -16,6 +16,15 @@ _compare_strs(const void **a, const void **b) return strcmp(s1, s2); } +/** Helper: return a tristate based on comparing the strings in a and + * *b. */ +static int +compare_strs_for_bsearch_(const void *a, const void **b) +{ + const char *s1 = a, *s2 = *b; + return strcmp(s1, s2); +} + /** Helper: return a tristate based on comparing the strings in *a and * *b, excluding a's first character, and ignoring case. */ static int @@ -204,6 +213,8 @@ test_container_smartlist_strings(void) /* Test bsearch_idx */ { int f; + smartlist_t *tmp = NULL; + test_eq(0, smartlist_bsearch_idx(sl," aaa",_compare_without_first_ch,&f)); test_eq(f, 0); test_eq(0, smartlist_bsearch_idx(sl," and",_compare_without_first_ch,&f)); @@ -216,6 +227,31 @@ test_container_smartlist_strings(void) test_eq(f, 0); test_eq(7, smartlist_bsearch_idx(sl," zzzz",_compare_without_first_ch,&f)); test_eq(f, 0); + + /* Test trivial cases for list of length 0 or 1 */ + tmp = smartlist_create(); + test_eq(0, smartlist_bsearch_idx(tmp, "foo", + compare_strs_for_bsearch_, &f)); + test_eq(f, 0); + smartlist_insert(tmp, 0, (void *)("bar")); + test_eq(1, smartlist_bsearch_idx(tmp, "foo", + compare_strs_for_bsearch_, &f)); + test_eq(f, 0); + test_eq(0, smartlist_bsearch_idx(tmp, "aaa", + compare_strs_for_bsearch_, &f)); + test_eq(f, 0); + test_eq(0, smartlist_bsearch_idx(tmp, "bar", + compare_strs_for_bsearch_, &f)); + test_eq(f, 1); + /* ... and one for length 2 */ + smartlist_insert(tmp, 1, (void *)("foo")); + test_eq(1, smartlist_bsearch_idx(tmp, "foo", + compare_strs_for_bsearch_, &f)); + test_eq(f, 1); + test_eq(2, smartlist_bsearch_idx(tmp, "goo", + compare_strs_for_bsearch_, &f)); + test_eq(f, 0); + smartlist_free(tmp); } /* Test reverse() and pop_last() */

1 0

[tor/release-0.2.3] Merge branch 'maint-0.2.3' into release-0.2.3
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit 44620d3b6b4909c355b5e305cf2137fa841e37a6 Merge: 36801ba b99457d Author: Roger Dingledine <arma(a)torproject.org> Date: Tue Oct 23 22:06:09 2012 -0400 Merge branch 'maint-0.2.3' into release-0.2.3 changes/bug7191 | 5 +++++ src/common/container.c | 23 ++++++++++++++++++++++- src/test/test_containers.c | 36 ++++++++++++++++++++++++++++++++++++ 3 files changed, 63 insertions(+), 1 deletions(-)

1 0

[tor/release-0.2.3] Fix binary search on lists of 0 or 1 element.
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit 8905789170269d29ad87530642ecc2a6a891219b Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 23 17:12:37 2012 -0400 Fix binary search on lists of 0 or 1 element. The implementation we added has a tendency to crash with lists of 0 or one element. That can happen if we get a consensus vote, v2 consensus, consensus, or geoip file with 0 or 1 element. There's a DOS opportunity there that authorities could exploit against one another, and which an evil v2 authority could exploit against anything downloading v2 directory information.. This fix is minimalistic: It just adds a special-case for 0- and 1-element lists. For 0.2.4 (the current alpha series) we'll want a better patch. This is bug 7191; it's a fix on 0.2.0.10-alpha. --- src/common/container.c | 23 ++++++++++++++++++++++- 1 files changed, 22 insertions(+), 1 deletions(-) diff --git a/src/common/container.c b/src/common/container.c index 5f53222..c047562 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -572,7 +572,28 @@ smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member), int *found_out) { - int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid; + const int len = smartlist_len(sl); + int hi, lo, cmp, mid; + + if (len == 0) { + *found_out = 0; + return 0; + } else if (len == 1) { + cmp = compare(key, (const void **) &sl->list[0]); + if (cmp == 0) { + *found_out = 1; + return 0; + } else if (cmp < 0) { + *found_out = 0; + return 0; + } else { + *found_out = 0; + return 1; + } + } + + hi = smartlist_len(sl) - 1; + lo = 0; while (lo <= hi) { mid = (lo + hi) / 2;

1 0

[tor/release-0.2.3] Add a changes file for bug 7191.
by arma＠torproject.org 24 Oct '12

24 Oct '12

commit 3365def68b91cb2bd9e741df679777155b746cf3 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Oct 23 21:31:42 2012 -0400 Add a changes file for bug 7191. --- changes/bug7191 | 5 +++++ 1 files changed, 5 insertions(+), 0 deletions(-) diff --git a/changes/bug7191 b/changes/bug7191 new file mode 100644 index 0000000..a3bee6e --- /dev/null +++ b/changes/bug7191 @@ -0,0 +1,5 @@ + o Major bugfixes: + - Fix a denial of service attack by which any directory authority + could crash all the others, or by which a single v2 directory + authority could crash everybody downloading v2 directory + information. Fixes bug 7191; bugfix on 0.2.0.10-alpha.

1 0

[tor/master] Rewrite smartlist_bsearch_idx() to not be broken for lists of length zero or one (fixes bug 7191)
by nickm＠torproject.org 24 Oct '12

24 Oct '12

commit fb97c0214b500741c16cb98b513ab3c96c7ab980 Author: Andrea Shepard <andrea(a)torproject.org> Date: Tue Oct 23 14:27:56 2012 -0700 Rewrite smartlist_bsearch_idx() to not be broken for lists of length zero or one (fixes bug 7191) --- changes/bug7191 | 3 + src/common/container.c | 112 ++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 98 insertions(+), 17 deletions(-) diff --git a/changes/bug7191 b/changes/bug7191 new file mode 100644 index 0000000..f50b16e --- /dev/null +++ b/changes/bug7191 @@ -0,0 +1,3 @@ + o Bugfixes + - The smartlist_bsearch_idx() function was broken for lists of length zero + or one; fix it. This fixes bug7191. diff --git a/src/common/container.c b/src/common/container.c index d941048..d4a2f89 100644 --- a/src/common/container.c +++ b/src/common/container.c @@ -571,31 +571,109 @@ smartlist_bsearch_idx(const smartlist_t *sl, const void *key, int (*compare)(const void *key, const void **member), int *found_out) { - int hi = smartlist_len(sl) - 1, lo = 0, cmp, mid; + int hi, lo, cmp, mid, len, diff; + + tor_assert(sl); + tor_assert(compare); + tor_assert(found_out); + + len = smartlist_len(sl); + + /* Check for the trivial case of a zero-length list */ + if (len == 0) { + *found_out = 0; + /* We already know smartlist_len(sl) is 0 in this case */ + return 0; + } + + /* Okay, we have a real search to do */ + tor_assert(len > 0); + lo = 0; + hi = len - 1; + + /* + * These invariants are always true: + * + * For all i such that 0 <= i < lo, sl[i] < key + * For all i such that hi key + */ while (lo <= hi) { - mid = (lo + hi) / 2; + diff = hi - lo; + /* + * We want mid = (lo + hi) / 2, but that could lead to overflow, so + * instead diff = hi - lo (non-negative because of loop condition), and + * then hi = lo + diff, mid = (lo + lo + diff) / 2 = lo + (diff / 2). + */ + mid = lo + (diff / 2); cmp = compare(key, (const void**) &(sl->list[mid])); - if (cmp>0) { /* key > sl[mid] */ - lo = mid+1; - } else if (cmp<0) { /* key < sl[mid] */ - hi = mid-1; - } else { /* key == sl[mid] */ + if (cmp == 0) { + /* sl[mid] == key; we found it */ *found_out = 1; return mid; - } - } - /* lo > hi. */ - { - tor_assert(lo >= 0); - if (lo < smartlist_len(sl)) { - cmp = compare(key, (const void**) &(sl->list[lo])); + } else if (cmp > 0) { + /* + * key > sl[mid] and an index i such that sl[i] == key must + * have i > mid if it exists. + */ + + /* + * Since lo <= mid <= hi, hi can only decrease on each iteration (by + * being set to mid - 1) and hi is initially len - 1, mid < len should + * always hold, and this is not symmetric with the left end of list + * mid > 0 test below. A key greater than the right end of the list + * should eventually lead to lo == hi == mid == len - 1, and then + * we set lo to len below and fall out to the same exit we hit for + * a key in the middle of the list but not matching. Thus, we just + * assert for consistency here rather than handle a mid == len case. + */ + tor_assert(mid < len); + /* Move lo to the element immediately after sl[mid] */ + lo = mid + 1; + } else { + /* This should always be true in this case */ tor_assert(cmp < 0); - } else if (smartlist_len(sl)) { - cmp = compare(key, (const void**) &(sl->list[smartlist_len(sl)-1])); - tor_assert(cmp > 0); + + /* + * key < sl[mid] and an index i such that sl[i] == key must + * have i < mid if it exists. + */ + + if (mid > 0) { + /* Normal case, move hi to the element immediately before sl[mid] */ + hi = mid - 1; + } else { + /* These should always be true in this case */ + tor_assert(mid == lo); + tor_assert(mid == 0); + /* + * We were at the beginning of the list and concluded that every + * element e compares e > key. + */ + *found_out = 0; + return 0; + } } } + + /* + * lo > hi; we have no element matching key but we have elements falling + * on both sides of it. The lo index points to the first element > key. + */ + tor_assert(lo == hi + 1); /* All other cases should have been handled */ + tor_assert(lo >= 0); + tor_assert(lo <= len); + tor_assert(hi >= 0); + tor_assert(hi <= len); + + if (lo < len) { + cmp = compare(key, (const void **) &(sl->list[lo])); + tor_assert(cmp < 0); + } else { + cmp = compare(key, (const void **) &(sl->list[len-1])); + tor_assert(cmp > 0); + } + *found_out = 0; return lo; }

1 0