Permalink
Switch branches/tags
coverity_scan doc/1.7 i110/append-index-file-name-to-script-name i110/asan-symbols i110/channel_notify_method-error-handling i110/clang-format-diff i110/config-stash i110/doc-directive-list i110/doc-navigatable-selected-tab i110/doc-stash i110/dynamic-default-mime-type i110/dynamic-socketpool i110/embed-mruby-redis i110/empty_port_testing i110/error-doc-allows-multiple-statuses i110/fix-access-log-body-size i110/fix-broken-trailers i110/fix-duplicate-date-headers i110/fix-h2client-conn-linklist-failure i110/fix-h2o_mruby_new_str i110/fix-header-search-paths i110/fix-keepalived-informational i110/fix-kqueue-eintr-handling i110/fix-leaked-redis-context i110/fix-libuv-bindinng i110/fix-mime-settypes i110/fix-mruby-keepalive i110/fix-mruby-lineno i110/fix-mruby-require i110/fix-mruby-sleep-memory-issue i110/fix-mruby-unexpectedly-release-http-request-context i110/fix-path-info i110/fix-plackup-option i110/fix-proxy-test-degration i110/fix-sock-bytes-written i110/fix-test-issues i110/forbid-empty-path i110/forward-date-request-header i110/forward-early-hints i110/gunzip i110/h2o_gettimeofday i110/header-flags i110/http-request-with-no-content-response i110/http2client-tests i110/http2client i110/httpclient-misc-changes i110/i110/fix-internal-redirect i110/i110/forward-content-length i110/ic7 i110/improve-server-timing i110/informational-doc i110/invalid-transfer-encoding i110/misc-test-issues i110/more-ssl-stats i110/mruby-cache i110/mruby-consistent-fiber-handling i110/mruby-embed-code i110/mruby-fix-preload-require-path i110/mruby-http-request-timeout-error i110/mruby-invalid-response i110/mruby-optional-preloads i110/mruby-output-filter i110/mruby-path-info-undecoded i110/mruby-preload-error-message i110/mruby-preloads-error i110/mruby-redis i110/mruby-sleep i110/mruby-socket i110/mruby-time-ext i110/mruby-update-input-stream i110/mruby-update i110/no-remove-session-cache i110/our-h2spec i110/process-existing-streams-after-goaway i110/prometheus-middleware i110/protocol-http2-module i110/rc i110/redis-session-resumption i110/reject-empty-path i110/remove-chunked-filter i110/remove-duplicate-date-headers i110/remove-generator i110/send-headers-immediately i110/send-informational i110/send-rst-stream-for-incomplete-body i110/server-timing-doc i110/server-timing i110/stop-applying-filter-multiple-times i110/stop-opening-new-push-streams-after-goaway i110/stop-wars i110/suppress-conversion-warnings i110/temp-buffer-threshold i110/test i110/travisci-in-osx-test i110/travisci-in-osx i110/update-deployment-target i110/update-h2get i110/update-h2spec i110/update-hiredis i110/update-mruby i110/upstream-timings i110/versioned-share-dir i110/wait-debugger i110/websockets-h2 i110/with-git-revision kazuho/accept-sigterm-in-main-thread kazuho/add-http11-to-npn kazuho/add-missing-extern-to-globals kazuho/allow-cmake-2.8.11 kazuho/amend-603 kazuho/amend-1031 kazuho/amend-1582 kazuho/amend-pr-1559 kazuho/append-slash-in-file-handler kazuho/apply-file-custom-handler-before-hosts-or-paths kazuho/apply-hostconf-to-fallback-path kazuho/armv8a kazuho/async-lookup kazuho/async-lookup2 kazuho/backtrace-logging-on-freebsd kazuho/backtrace-on-segv kazuho/bench/token_lookup kazuho/better-fatal kazuho/bigger-receive-window kazuho/bind-to-localhost kazuho/boringssl-compatibility kazuho/brotli-error-on-multivector-send kazuho/build-without-libs kazuho/bundle-libressl kazuho/bundle-libyaml kazuho/bundle-server-starter kazuho/cache-aware-push-2 kazuho/cache-aware-push kazuho/cache-digest-truncate kazuho/cache-rwlock kazuho/cache kazuho/casper-amendments kazuho/casper/disable-if-proxy-is-used kazuho/certbot kazuho/cgi kazuho/change-sig-of-h2o_config_register_path kazuho/check-avialability-of-correct-address kazuho/clang-format/sort-includes kazuho/clear-memory-of-deps kazuho/client-protocol-abstraction kazuho/cloexec-wrapper kazuho/close-connection-on-cancellation kazuho/cmake-extra-libs kazuho/concat-set-cookie kazuho/concurrent-collection-of-request-stats kazuho/conditionally-link-to-the-mruby-handler kazuho/configurable-mime-attributes kazuho/configure-tls-max-ver kazuho/constants-as-const-arrays kazuho/constify-write-vec kazuho/corrupt-json-status kazuho/custom-error-page kazuho/cve-2015-5638/doc kazuho/daemonize kazuho/deadline-for-internal-session-cache kazuho/default-enable-neverbleed kazuho/default-mimetypes kazuho/default-to-openssl-if-1.0.2 kazuho/depth-first-callback-for-timeouts kazuho/directive-docs kazuho/directive-to-disable-push kazuho/dirlisting kazuho/disallow-duplicate-host-entry kazuho/doc-borders kazuho/doc-ticket-encryption-key-format kazuho/doc/handshake-timeout kazuho/docker-ci-simplify kazuho/docker-ci kazuho/docker-enter kazuho/docs kazuho/dont-bump-max_open-for-priority-frames kazuho/dont-exit-if-failing-to-set-tcp-fastopen kazuho/double-buffer kazuho/draft-16 kazuho/drop-response-to-head-in-protocol-parser kazuho/duplicate-header-token kazuho/dynamic-socketpool kazuho/earlier-push kazuho/early-data-header kazuho/emit-json-quotes kazuho/enable-backtrace-on-bsd kazuho/enable-tcp-latopt-by-default kazuho/error-in-access-log kazuho/experiments/libuv-network-and-file kazuho/experiments/libuv-network-only kazuho/experiments/no-libuv kazuho/expose-hpack-primitives kazuho/expr/chunked-decoder kazuho/expr/connect kazuho/expr/dual-life kazuho/expr/e2e-test kazuho/expr/fix-travis-revproxy kazuho/expr/hpack-using-index kazuho/expr/http2-by-default kazuho/expr/http2-priority kazuho/expr/inbuf-initial-size kazuho/expr/ipv6 kazuho/expr/libdl kazuho/expr/libuv-network-only/1.0.0 kazuho/expr/loopback-testing kazuho/expr/max-connections kazuho/expr/mime-types-as-part-of-file kazuho/expr/path-based-config kazuho/expr/proxy-keepalive kazuho/expr/proxy/chunked-decoder kazuho/expr/pulling-generator kazuho/expr/revproxy kazuho/expr/sni kazuho/expr/travis-libuv kazuho/expr/travis/install-nghttp2 kazuho/extension-based-handlers kazuho/extract-buffering-send-func kazuho/fastcgi-amendments kazuho/fastcgi-cgi-verbose-mode kazuho/fastcgi-cgi kazuho/fastcgi-document-root kazuho/fastcgi-drop-special-headers kazuho/fastcgi-env kazuho/fastcgi-login-issue kazuho/fastcgi_spawn-with-setuid kazuho/fastcgi kazuho/faster-travis kazuho/fiber-switch-in-constructor kazuho/file-specific-sender kazuho/fix-conflict-with-oniguruma-installed kazuho/fix-crash-if-upgrade-to-http2-fails kazuho/fix-crash-in-recycling-allocator kazuho/fix-crash-when-status-code-is-not-a-number kazuho/fix-direct-access-to-cb_write kazuho/fix-dubious-if kazuho/fix-example-server-using-evloop kazuho/fix-fd-leaks kazuho/fix-freebsd-timeout-in-t50reverse-proxy.t kazuho/fix-h2o_url_stringify kazuho/fix-ignored-header-names-in-log kazuho/fix-leaks-on-destroy kazuho/fix-leaks kazuho/fix-memory-leak-in-poll-backend kazuho/fix-netbsd-crash-on-upstream-keepalive kazuho/fix-potential-leak-when-destroying-proxy-handler-using-defaults kazuho/fix-race-in-50internal-redirect.t kazuho/fix-race-in-50r-p-c-t-2.t kazuho/fix-race-in-test kazuho/fix-reverse-proxy kazuho/fix-stall-if-only-prio257-stream-exists kazuho/fix-test-stall-when-h2get-is-missing kazuho/fix-too-many-streams-error-with-h2load kazuho/fix-use-after-free-in-hostinfo kazuho/flatten-t-dir kazuho/freeaddrinfo kazuho/fuzzer-macosx-fixes kazuho/graceful-restart kazuho/graceful-shutdown kazuho/guard-mrb_str_new kazuho/gzip-on-the-fly kazuho/h1-header-validation kazuho/h2-negative-window kazuho/h2o_http2_scheduler_relocate kazuho/h2o_spawnp kazuho/h2spec-0.08 kazuho/h2spec-1.2.0 kazuho/h2spec-v0.0.6 kazuho/h2spec kazuho/header-flags kazuho/headers-in-lowercase kazuho/headers-on-304 kazuho/hpack-encoder-crash-on-token-wo-hpack-index kazuho/hpack-parse-resp-headers-init-outargs kazuho/hpack-push-optimizations kazuho/hpack/copyless-encode kazuho/hpack/dynamic-name-index kazuho/htpasswd kazuho/http2-dependency-2 kazuho/http2-is-done kazuho/http2-send-content-length kazuho/http2-timeout kazuho/http2/always-send-257 kazuho/http2/cache-digests kazuho/http2/cache-fingerprint kazuho/http2client-merge-master kazuho/http2client-reduce-timers kazuho/http2/dependency kazuho/http2/disallow-push-from-push kazuho/http2/dont-send-push-promise-when-cancelling-sync-handler kazuho/http2/eager-write-after-read kazuho/http2/emit-push-status kazuho/http2/entire-payload-for-flow-control kazuho/http2/fix-streaming-request-stall kazuho/http2/ignore-reserved-bit-of-frame-header kazuho/http2/invalid-preface kazuho/http2/max-conc-reqs-per-conn-vs-stall kazuho/http2/minimize-latency-take-two kazuho/http2/minimize-latency kazuho/http2/no-etag-in-casper kazuho/http2/optimize-locality kazuho/http2/push-indication-using-1xx kazuho/http2/push-memo kazuho/http2/reprioritize-by-default kazuho/include-pid-in-backtrace kazuho/incomplete-definition-of-phr-header kazuho/inflight-stream-window-size-on-settings-frame kazuho/initialize-all-fields-of-client kazuho/integrate-doc-make kazuho/internal-redirect-reproxy kazuho/internal-redirect-split-input-attributes kazuho/internal-redirect kazuho/interthread-messaging kazuho/io-error-in-head kazuho/issue/1215 kazuho/issues/%U-must-be-path kazuho/issues/busy-epoll kazuho/issues/crash-on-large-post kazuho/issues/fastcgi.spawn-backlog kazuho/issues/faster-post kazuho/issues/fix-git-access-on-build kazuho/issues/header-added-twice kazuho/issues/malloc-used-in-signal-handler kazuho/issues/no-handler-vs-h2-post kazuho/issues/pr-101-segv kazuho/issues/test-timeout kazuho/issues/61-reopen kazuho/issues/61 kazuho/issues/65 kazuho/issues/93 kazuho/issues/105 kazuho/issues/128 kazuho/issues/132 kazuho/issues/135-first-shot kazuho/issues/135-take-two kazuho/issues/135 kazuho/issues/141 kazuho/issues/146 kazuho/issues/173 kazuho/issues/185 kazuho/issues/192 kazuho/issues/218 kazuho/issues/225 kazuho/issues/266 kazuho/issues/274 kazuho/issues/288 kazuho/issues/293 kazuho/issues/300 kazuho/issues/301 kazuho/issues/316 kazuho/issues/341 kazuho/issues/371 kazuho/issues/395-amendments kazuho/issues/397 kazuho/issues/412 kazuho/issues/462 kazuho/issues/464 kazuho/issues/511 kazuho/issues/524 kazuho/issues/538 kazuho/issues/542 kazuho/issues/560 kazuho/issues/567 kazuho/issues/579 kazuho/issues/598 kazuho/issues/611 kazuho/issues/627 kazuho/issues/681 kazuho/issues/682 kazuho/issues/689 kazuho/issues/690 kazuho/issues/699 kazuho/issues/704 kazuho/issues/705 kazuho/issues/715 kazuho/issues/717 kazuho/issues/718-2 kazuho/issues/718-3 kazuho/issues/718 kazuho/issues/724 kazuho/issues/726 kazuho/issues/729 kazuho/issues/730 kazuho/issues/762 kazuho/issues/778 kazuho/issues/819 kazuho/issues/821 kazuho/issues/852 kazuho/issues/860 kazuho/issues/883 kazuho/issues/900 kazuho/issues/902 kazuho/issues/909 kazuho/issues/940 kazuho/issues/951 kazuho/issues/966 kazuho/issues/1007 kazuho/issues/1061 kazuho/issues/1070 kazuho/issues/1088 kazuho/issues/1089 kazuho/issues/1102 kazuho/issues/1174 kazuho/issues/1249 kazuho/issues/1267 kazuho/issues/1274 kazuho/issues/1375 kazuho/issues/1447 kazuho/issues/1474-2 kazuho/issues/1535 kazuho/issues/1560 kazuho/issues/1595 kazuho/issues/1615 kazuho/js-as-compressible kazuho/json-log-magic-quotes kazuho/json-logging kazuho/keep-alive-on-redirect kazuho/kill-fastcgi-procs-on-ctrl-c kazuho/kill-on-close-not-found kazuho/lb-vs-non-keep-alive kazuho/libgkc-eliminate-gccext kazuho/libressl-2.2.2 kazuho/libressl-2.2.4 kazuho/libressl-2.2.6 kazuho/libressl-2.2.7 kazuho/libressl-2.6.3 kazuho/libressl-on-arm kazuho/libyaml-0.1.7 kazuho/limit-max-internal-redirect kazuho/limit-ocsp-updater-concurrency kazuho/link-preload-critical kazuho/local-address kazuho/log-non-requests kazuho/log-original-response kazuho/log-protocol-specific-values kazuho/log-remote-port kazuho/log-timings kazuho/mapping-parser kazuho/memcached-session-resumption-1.4-libyrmcds kazuho/memcached-session-resumption-1.4 kazuho/memcached/text-protocol kazuho/memgrind kazuho/mime-type-attributes kazuho/mkhufftbl.py-as-part-of-regen kazuho/mod_status kazuho/more-compressible-types kazuho/more-logging-directives kazuho/mrb-int-as-ssize_t kazuho/mruby-1.4.1 kazuho/mruby-fiber-cleanup kazuho/mruby-fiber-refinements kazuho/mruby-fiber-resume-direct kazuho/mruby-fiber kazuho/mruby-file-stat/update-to-922840d kazuho/mruby-h2o_root kazuho/mruby-json/59493de kazuho/mruby-mattn-json-update kazuho/mruby-more-gems kazuho/mruby-reprocess-relative-url kazuho/mruby-update-2.1 kazuho/mruby-update-for-2.1-take-two kazuho/mruby/accept-file-as-body kazuho/mruby/async-delegate kazuho/mruby/async-http kazuho/mruby/body.close-must-be-called kazuho/mruby/bsd-compat kazuho/mruby/bundle-mruby-and-gems kazuho/mruby/cant-call-acl kazuho/mruby/change-sig-of-http_request kazuho/mruby/dont-send-response-more-than-once kazuho/mruby/dump-source-at-error kazuho/mruby/errno kazuho/mruby/fast-path-for-http_request kazuho/mruby/fix-crash-in-mruby_str_to_str kazuho/mruby/http-request-header-tests kazuho/mruby/inline-configuration kazuho/mruby/input-stream-as-str kazuho/mruby/load-path kazuho/mruby/make-error-if-mkmf-not-found kazuho/mruby/mattn-json kazuho/mruby/more-gems kazuho/mruby/multi-line-headers kazuho/mruby/preserve-link-preload-header kazuho/mruby/progressive-response kazuho/mruby/rack-style kazuho/mruby/raise-error-when-reading-from-a-closed-rack-input kazuho/mruby/refactor-chunked-sender kazuho/mruby/reprocess-relative-url kazuho/mruby/request-header-concat kazuho/mruby/resolve-issues-using-mruby kazuho/mruby/retain-order-of-1#-headers kazuho/mruby/send-content-length-when-possible kazuho/mruby/server-push kazuho/mruby/server_software kazuho/mruby/set-remote-user kazuho/mruby/sha256 kazuho/mruby/unify-directive-name-and-application-order kazuho/mruby/update-to-20ebe9c kazuho/mt-cache kazuho/multiple-cookie-headers-in-http2 kazuho/netbsd-kqueue kazuho/neverbleed kazuho/no-side-effect-on-dry-run kazuho/no-targets-in-req kazuho/no-vary-if-msie kazuho/note-php-cgi-version kazuho/nvlist-parser kazuho/ocsp kazuho/oops1 kazuho/open-file-cache-negative-cache kazuho/open-file-cache kazuho/openindiana kazuho/openssl-1.1.0 kazuho/optimize-travis-bootstrap kazuho/osx-libressl-build-error kazuho/osx-posix_spawnp-ebadf-fix kazuho/parse-if-modified-since kazuho/parse-mapping kazuho/parse_authority_from_url kazuho/pedantic kazuho/perl-path kazuho/perlify-setuidgid kazuho/picotls-ecdsa-certs-using-long-curves kazuho/picotls-openssl110-compatibility kazuho/picotls-sslkeylogfile kazuho/picotls-update kazuho/picotls kazuho/pid-file kazuho/piped-log-vs-linux kazuho/poll-backend kazuho/post-size-limit kazuho/pr/45 kazuho/pr/250 kazuho/pr/252 kazuho/pr/335 kazuho/pr/345 kazuho/pr/443 kazuho/pr/515 kazuho/pr/571 kazuho/pr/670 kazuho/pr/1152 kazuho/pr/1361 kazuho/pr/1366 kazuho/pr/1444 kazuho/pr/1605 kazuho/pr/1624 kazuho/pr/1709 kazuho/pr/1716 kazuho/pr/1781 kazuho/pr/1807 kazuho/pr/1865 kazuho/pr/1905 kazuho/preserve-overrides-if-authority-unchanged kazuho/proxy-protocol kazuho/proxy-response-parser-fix-internal-corruption kazuho/proxy-ssl-timeout kazuho/proxy-unix-socket kazuho/proxy/detect-upstream-close kazuho/proxy/optimize-header-concat kazuho/proxy/truncation-bug-on-non-persistent-conn kazuho/proxy/399-response kazuho/pthread-option kazuho/pull/618/fix-regress-on-freebsd kazuho/pull/927 kazuho/pull/936 kazuho/pull/950 kazuho/pull/1100 kazuho/pull/1126 kazuho/pull/1169 kazuho/pull/1175 kazuho/pull/1366 kazuho/pull/1427 kazuho/pull/1463 kazuho/push kazuho/quic kazuho/readdir-take-two kazuho/redo/1300 kazuho/refactor-http2-error-handling kazuho/refactor-lb kazuho/refactor-proxy-test-bootstrap kazuho/refactor-ssl-write kazuho/refactor-streaming-body-2 kazuho/refactor-streaming-body kazuho/refactor-travis-yml-upgrade-nghttp2 kazuho/refactor-travis-yml kazuho/refactor/config kazuho/refactor/hpack-encoder kazuho/refactor/hpack kazuho/refactor/http1client/reduce-copy kazuho/refactor/no-abstraction-for-openssl kazuho/refactor/url-rebase kazuho/refactor/url-rewrite kazuho/regexp kazuho/remove-chunked-filter-2 kazuho/remove-chunked-filter kazuho/remove-expired-ticket-secrets-on-memcached kazuho/replay-identifier kazuho/reprioritize-blocking-assets kazuho/reproxy-preserve-method kazuho/respect-H2O_PERL-in-setuidgid kazuho/responsiveness kazuho/restore-1221-doc kazuho/reverse-proxy/send-proxy-protocol kazuho/rewrite-location-caseless-hostmatch kazuho/rfc8446 kazuho/run-http1-and-http2-tests-using-curl kazuho/run-root-tests-on-travis kazuho/secure-casper-cookies kazuho/send-brotli kazuho/send-via-to-upstream kazuho/server-push-in-fastcgi kazuho/server-starter kazuho/serverpref kazuho/session-resumption-libyrmcds kazuho/session-resumption kazuho/session-ticket kazuho/set-priorities-of-old-streams kazuho/setenv-to-override-http-headers kazuho/setuid-nobody-if-run-as-root-wo-user-directive kazuho/setuidgid kazuho/simplify-build-request kazuho/simplify-proxy-config kazuho/skip-libh2o-if-openssl-not-found kazuho/sockname-in-log kazuho/solaris-test-failures kazuho/split-configurator kazuho/split-external-ver-and-lib-ver kazuho/split-unit-tests kazuho/sslctx-part-of-socketpool kazuho/strftime-in-log kazuho/stronger-ecdh-curves kazuho/struct-initialization kazuho/suppress-warnings-on-xcode kazuho/suppress-warnings kazuho/temp-buffer-path kazuho/test-issues kazuho/test kazuho/timerwheel kazuho/tls-client kazuho/tls/memcached-session-memory-leak kazuho/tls13-26 kazuho/tls13-assertion-failure-is_allocated-take-two kazuho/tls13-assertion-failure-is_allocated kazuho/tls13-cipher-suites kazuho/tls13-key-update kazuho/tls13-replay kazuho/tls13draft22 kazuho/tmp/last-libuv kazuho/tmp027 kazuho/tmp074 kazuho/too-many-priority-frames kazuho/travis-container-based kazuho/travis-update-nghttp2 kazuho/travis-upgrade-to-nghttp2-0.7.5 kazuho/travis/1 kazuho/travis/2 kazuho/tweak-headers kazuho/unbundle-libressl-all-usr-local kazuho/unbundle-libressl kazuho/update-brotli kazuho/update-iijson kazuho/update-mruby-2 kazuho/update-mruby-io kazuho/update-mruby-onig-regexp kazuho/update-picotls-2 kazuho/update-picotls-neverbleed kazuho/update-picotls kazuho/update-server-starter-to-0.30 kazuho/upgrade-nghttp2 kazuho/url-handling-functions kazuho/url_resolve_path kazuho/use-pkgconfig kazuho/use-tail-call kazuho/v2.2.x-issues/1560 kazuho/v2.2.x-libressl-2.6.3 kazuho/v2.2.x-mruby-stack-length kazuho/v2.2.x-pr1489 kazuho/valgrind-fixes kazuho/vuln201612/v2.0.x kazuho/vuln201612/v2.1.x kazuho/websocket-proxy kazuho/wildcard-host kazuho/wip/picotls kazuho/wordpress-url-rewrite kazuho/writer-preferred-rwlock kazuho/x-sendfile kazuho/yaml-error-lineno kazuho/yaml-merge kazuho/yoml-with-filename kazuho/210doc kazuho/973-take-two master naritta/parallel-http-join publish-docs rel/v0.9.0 rel/v0.9.1 rel/v1.0.0 tmp008 tmp016 tmp9901 v1.4.x v1.5.x v1.6.x v1.7.x v2.0.x v2.1.x v2.2.x v2.3.x
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
620 lines (533 sloc) 20.8 KB
/* The MIT License
Copyright (c) 2008, 2009, 2011 by Attractive Chaos <attractor@live.co.uk>
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
/*
An example:
#include "khash.h"
KHASH_MAP_INIT_INT(32, char)
int main() {
int ret, is_missing;
khiter_t k;
khash_t(32) *h = kh_init(32);
k = kh_put(32, h, 5, &ret);
kh_value(h, k) = 10;
k = kh_get(32, h, 10);
is_missing = (k == kh_end(h));
k = kh_get(32, h, 5);
kh_del(32, h, k);
for (k = kh_begin(h); k != kh_end(h); ++k)
if (kh_exist(h, k)) kh_value(h, k) = 1;
kh_destroy(32, h);
return 0;
}
*/
/*
2013-05-02 (0.2.8):
* Use quadratic probing. When the capacity is power of 2, stepping function
i*(i+1)/2 guarantees to traverse each bucket. It is better than double
hashing on cache performance and is more robust than linear probing.
In theory, double hashing should be more robust than quadratic probing.
However, my implementation is probably not for large hash tables, because
the second hash function is closely tied to the first hash function,
which reduce the effectiveness of double hashing.
Reference: http://research.cs.vt.edu/AVresearch/hashing/quadratic.php
2011-12-29 (0.2.7):
* Minor code clean up; no actual effect.
2011-09-16 (0.2.6):
* The capacity is a power of 2. This seems to dramatically improve the
speed for simple keys. Thank Zilong Tan for the suggestion. Reference:
- http://code.google.com/p/ulib/
- http://nothings.org/computer/judy/
* Allow to optionally use linear probing which usually has better
performance for random input. Double hashing is still the default as it
is more robust to certain non-random input.
* Added Wang's integer hash function (not used by default). This hash
function is more robust to certain non-random input.
2011-02-14 (0.2.5):
* Allow to declare global functions.
2009-09-26 (0.2.4):
* Improve portability
2008-09-19 (0.2.3):
* Corrected the example
* Improved interfaces
2008-09-11 (0.2.2):
* Improved speed a little in kh_put()
2008-09-10 (0.2.1):
* Added kh_clear()
* Fixed a compiling error
2008-09-02 (0.2.0):
* Changed to token concatenation which increases flexibility.
2008-08-31 (0.1.2):
* Fixed a bug in kh_get(), which has not been tested previously.
2008-08-31 (0.1.1):
* Added destructor
*/
#ifndef __AC_KHASH_H
#define __AC_KHASH_H
/*!
@header
Generic hash table library.
*/
#define AC_VERSION_KHASH_H "0.2.8"
#include <stdlib.h>
#include <string.h>
#include <limits.h>
/* compiler specific configuration */
#if UINT_MAX == 0xffffffffu
typedef unsigned int khint32_t;
#elif ULONG_MAX == 0xffffffffu
typedef unsigned long khint32_t;
#endif
#if ULONG_MAX == ULLONG_MAX
typedef unsigned long khint64_t;
#else
typedef unsigned long long khint64_t;
#endif
#ifndef kh_inline
#ifdef _MSC_VER
#define kh_inline __inline
#else
#define kh_inline inline
#endif
#endif /* kh_inline */
typedef khint32_t khint_t;
typedef khint_t khiter_t;
#define __ac_isempty(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&2)
#define __ac_isdel(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&1)
#define __ac_iseither(flag, i) ((flag[i>>4]>>((i&0xfU)<<1))&3)
#define __ac_set_isdel_false(flag, i) (flag[i>>4]&=~(1ul<<((i&0xfU)<<1)))
#define __ac_set_isempty_false(flag, i) (flag[i>>4]&=~(2ul<<((i&0xfU)<<1)))
#define __ac_set_isboth_false(flag, i) (flag[i>>4]&=~(3ul<<((i&0xfU)<<1)))
#define __ac_set_isdel_true(flag, i) (flag[i>>4]|=1ul<<((i&0xfU)<<1))
#define __ac_fsize(m) ((m) < 16? 1 : (m)>>4)
#ifndef kroundup32
#define kroundup32(x) (--(x), (x)|=(x)>>1, (x)|=(x)>>2, (x)|=(x)>>4, (x)|=(x)>>8, (x)|=(x)>>16, ++(x))
#endif
#ifndef kcalloc
#define kcalloc(N,Z) calloc(N,Z)
#endif
#ifndef kmalloc
#define kmalloc(Z) malloc(Z)
#endif
#ifndef krealloc
#define krealloc(P,Z) realloc(P,Z)
#endif
#ifndef kfree
#define kfree(P) free(P)
#endif
static const double __ac_HASH_UPPER = 0.77;
#define __KHASH_TYPE(name, khkey_t, khval_t) \
typedef struct kh_##name##_s { \
khint_t n_buckets, size, n_occupied, upper_bound; \
khint32_t *flags; \
khkey_t *keys; \
khval_t *vals; \
} kh_##name##_t;
#define __KHASH_PROTOTYPES(name, khkey_t, khval_t) \
extern kh_##name##_t *kh_init_##name(void); \
extern void kh_destroy_##name(kh_##name##_t *h); \
extern void kh_clear_##name(kh_##name##_t *h); \
extern khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key); \
extern int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets); \
extern khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret); \
extern void kh_del_##name(kh_##name##_t *h, khint_t x);
#define __KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
SCOPE kh_##name##_t *kh_init_##name(void) { \
return (kh_##name##_t*)kcalloc(1, sizeof(kh_##name##_t)); \
} \
SCOPE void kh_destroy_##name(kh_##name##_t *h) \
{ \
if (h) { \
kfree((void *)h->keys); kfree(h->flags); \
kfree((void *)h->vals); \
kfree(h); \
} \
} \
SCOPE void kh_clear_##name(kh_##name##_t *h) \
{ \
if (h && h->flags) { \
memset(h->flags, 0xaa, __ac_fsize(h->n_buckets) * sizeof(khint32_t)); \
h->size = h->n_occupied = 0; \
} \
} \
SCOPE khint_t kh_get_##name(const kh_##name##_t *h, khkey_t key) \
{ \
if (h->n_buckets) { \
khint_t k, i, last, mask, step = 0; \
mask = h->n_buckets - 1; \
k = __hash_func(key); i = k & mask; \
last = i; \
while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
i = (i + (++step)) & mask; \
if (i == last) return h->n_buckets; \
} \
return __ac_iseither(h->flags, i)? h->n_buckets : i; \
} else return 0; \
} \
SCOPE int kh_resize_##name(kh_##name##_t *h, khint_t new_n_buckets) \
{ /* This function uses 0.25*n_buckets bytes of working space instead of [sizeof(key_t+val_t)+.25]*n_buckets. */ \
khint32_t *new_flags = 0; \
khint_t j = 1; \
{ \
kroundup32(new_n_buckets); \
if (new_n_buckets < 4) new_n_buckets = 4; \
if (h->size >= (khint_t)(new_n_buckets * __ac_HASH_UPPER + 0.5)) j = 0; /* requested size is too small */ \
else { /* hash table size to be changed (shrink or expand); rehash */ \
new_flags = (khint32_t*)kmalloc(__ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
if (!new_flags) return -1; \
memset(new_flags, 0xaa, __ac_fsize(new_n_buckets) * sizeof(khint32_t)); \
if (h->n_buckets < new_n_buckets) { /* expand */ \
khkey_t *new_keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
if (!new_keys) { kfree(new_flags); return -1; } \
h->keys = new_keys; \
if (kh_is_map) { \
khval_t *new_vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
if (!new_vals) { kfree(new_flags); return -1; } \
h->vals = new_vals; \
} \
} /* otherwise shrink */ \
} \
} \
if (j) { /* rehashing is needed */ \
for (j = 0; j != h->n_buckets; ++j) { \
if (__ac_iseither(h->flags, j) == 0) { \
khkey_t key = h->keys[j]; \
khval_t val; \
khint_t new_mask; \
new_mask = new_n_buckets - 1; \
if (kh_is_map) val = h->vals[j]; \
__ac_set_isdel_true(h->flags, j); \
while (1) { /* kick-out process; sort of like in Cuckoo hashing */ \
khint_t k, i, step = 0; \
k = __hash_func(key); \
i = k & new_mask; \
while (!__ac_isempty(new_flags, i)) i = (i + (++step)) & new_mask; \
__ac_set_isempty_false(new_flags, i); \
if (i < h->n_buckets && __ac_iseither(h->flags, i) == 0) { /* kick out the existing element */ \
{ khkey_t tmp = h->keys[i]; h->keys[i] = key; key = tmp; } \
if (kh_is_map) { khval_t tmp = h->vals[i]; h->vals[i] = val; val = tmp; } \
__ac_set_isdel_true(h->flags, i); /* mark it as deleted in the old hash table */ \
} else { /* write the element and jump out of the loop */ \
h->keys[i] = key; \
if (kh_is_map) h->vals[i] = val; \
break; \
} \
} \
} \
} \
if (h->n_buckets > new_n_buckets) { /* shrink the hash table */ \
h->keys = (khkey_t*)krealloc((void *)h->keys, new_n_buckets * sizeof(khkey_t)); \
if (kh_is_map) h->vals = (khval_t*)krealloc((void *)h->vals, new_n_buckets * sizeof(khval_t)); \
} \
kfree(h->flags); /* free the working space */ \
h->flags = new_flags; \
h->n_buckets = new_n_buckets; \
h->n_occupied = h->size; \
h->upper_bound = (khint_t)(h->n_buckets * __ac_HASH_UPPER + 0.5); \
} \
return 0; \
} \
SCOPE khint_t kh_put_##name(kh_##name##_t *h, khkey_t key, int *ret) \
{ \
khint_t x; \
if (h->n_occupied >= h->upper_bound) { /* update the hash table */ \
if (h->n_buckets > (h->size<<1)) { \
if (kh_resize_##name(h, h->n_buckets - 1) < 0) { /* clear "deleted" elements */ \
*ret = -1; return h->n_buckets; \
} \
} else if (kh_resize_##name(h, h->n_buckets + 1) < 0) { /* expand the hash table */ \
*ret = -1; return h->n_buckets; \
} \
} /* TODO: to implement automatically shrinking; resize() already support shrinking */ \
{ \
khint_t k, i, site, last, mask = h->n_buckets - 1, step = 0; \
x = site = h->n_buckets; k = __hash_func(key); i = k & mask; \
if (__ac_isempty(h->flags, i)) x = i; /* for speed up */ \
else { \
last = i; \
while (!__ac_isempty(h->flags, i) && (__ac_isdel(h->flags, i) || !__hash_equal(h->keys[i], key))) { \
if (__ac_isdel(h->flags, i)) site = i; \
i = (i + (++step)) & mask; \
if (i == last) { x = site; break; } \
} \
if (x == h->n_buckets) { \
if (__ac_isempty(h->flags, i) && site != h->n_buckets) x = site; \
else x = i; \
} \
} \
} \
if (__ac_isempty(h->flags, x)) { /* not present at all */ \
h->keys[x] = key; \
__ac_set_isboth_false(h->flags, x); \
++h->size; ++h->n_occupied; \
*ret = 1; \
} else if (__ac_isdel(h->flags, x)) { /* deleted */ \
h->keys[x] = key; \
__ac_set_isboth_false(h->flags, x); \
++h->size; \
*ret = 2; \
} else *ret = 0; /* Don't touch h->keys[x] if present and not deleted */ \
return x; \
} \
SCOPE void kh_del_##name(kh_##name##_t *h, khint_t x) \
{ \
if (x != h->n_buckets && !__ac_iseither(h->flags, x)) { \
__ac_set_isdel_true(h->flags, x); \
--h->size; \
} \
}
#define KHASH_DECLARE(name, khkey_t, khval_t) \
__KHASH_TYPE(name, khkey_t, khval_t) \
__KHASH_PROTOTYPES(name, khkey_t, khval_t)
#define KHASH_INIT2(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
__KHASH_TYPE(name, khkey_t, khval_t) \
__KHASH_IMPL(name, SCOPE, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
#define KHASH_INIT(name, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal) \
KHASH_INIT2(name, static kh_inline, khkey_t, khval_t, kh_is_map, __hash_func, __hash_equal)
/* --- BEGIN OF HASH FUNCTIONS --- */
/*! @function
@abstract Integer hash function
@param key The integer [khint32_t]
@return The hash value [khint_t]
*/
#define kh_int_hash_func(key) (khint32_t)(key)
/*! @function
@abstract Integer comparison function
*/
#define kh_int_hash_equal(a, b) ((a) == (b))
/*! @function
@abstract 64-bit integer hash function
@param key The integer [khint64_t]
@return The hash value [khint_t]
*/
#define kh_int64_hash_func(key) (khint32_t)((key)>>33^(key)^(key)<<11)
/*! @function
@abstract 64-bit integer comparison function
*/
#define kh_int64_hash_equal(a, b) ((a) == (b))
/*! @function
@abstract const char* hash function
@param s Pointer to a null terminated string
@return The hash value
*/
static kh_inline khint_t __ac_X31_hash_string(const char *s)
{
khint_t h = (khint_t)*s;
if (h) for (++s ; *s; ++s) h = (h << 5) - h + (khint_t)*s;
return h;
}
/*! @function
@abstract Another interface to const char* hash function
@param key Pointer to a null terminated string [const char*]
@return The hash value [khint_t]
*/
#define kh_str_hash_func(key) __ac_X31_hash_string(key)
/*! @function
@abstract Const char* comparison function
*/
#define kh_str_hash_equal(a, b) (strcmp(a, b) == 0)
static kh_inline khint_t __ac_Wang_hash(khint_t key)
{
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
#define kh_int_hash_func2(k) __ac_Wang_hash((khint_t)key)
/* --- END OF HASH FUNCTIONS --- */
/* Other convenient macros... */
/*!
@abstract Type of the hash table.
@param name Name of the hash table [symbol]
*/
#define khash_t(name) kh_##name##_t
/*! @function
@abstract Initiate a hash table.
@param name Name of the hash table [symbol]
@return Pointer to the hash table [khash_t(name)*]
*/
#define kh_init(name) kh_init_##name()
/*! @function
@abstract Destroy a hash table.
@param name Name of the hash table [symbol]
@param h Pointer to the hash table [khash_t(name)*]
*/
#define kh_destroy(name, h) kh_destroy_##name(h)
/*! @function
@abstract Reset a hash table without deallocating memory.
@param name Name of the hash table [symbol]
@param h Pointer to the hash table [khash_t(name)*]
*/
#define kh_clear(name, h) kh_clear_##name(h)
/*! @function
@abstract Resize a hash table.
@param name Name of the hash table [symbol]
@param h Pointer to the hash table [khash_t(name)*]
@param s New size [khint_t]
*/
#define kh_resize(name, h, s) kh_resize_##name(h, s)
/*! @function
@abstract Insert a key to the hash table.
@param name Name of the hash table [symbol]
@param h Pointer to the hash table [khash_t(name)*]
@param k Key [type of keys]
@param r Extra return code: -1 if the operation failed;
0 if the key is present in the hash table;
1 if the bucket is empty (never used); 2 if the element in
the bucket has been deleted [int*]
@return Iterator to the inserted element [khint_t]
*/
#define kh_put(name, h, k, r) kh_put_##name(h, k, r)
/*! @function
@abstract Retrieve a key from the hash table.
@param name Name of the hash table [symbol]
@param h Pointer to the hash table [khash_t(name)*]
@param k Key [type of keys]
@return Iterator to the found element, or kh_end(h) if the element is absent [khint_t]
*/
#define kh_get(name, h, k) kh_get_##name(h, k)
/*! @function
@abstract Remove a key from the hash table.
@param name Name of the hash table [symbol]
@param h Pointer to the hash table [khash_t(name)*]
@param k Iterator to the element to be deleted [khint_t]
*/
#define kh_del(name, h, k) kh_del_##name(h, k)
/*! @function
@abstract Test whether a bucket contains data.
@param h Pointer to the hash table [khash_t(name)*]
@param x Iterator to the bucket [khint_t]
@return 1 if containing data; 0 otherwise [int]
*/
#define kh_exist(h, x) (!__ac_iseither((h)->flags, (x)))
/*! @function
@abstract Get key given an iterator
@param h Pointer to the hash table [khash_t(name)*]
@param x Iterator to the bucket [khint_t]
@return Key [type of keys]
*/
#define kh_key(h, x) ((h)->keys[x])
/*! @function
@abstract Get value given an iterator
@param h Pointer to the hash table [khash_t(name)*]
@param x Iterator to the bucket [khint_t]
@return Value [type of values]
@discussion For hash sets, calling this results in segfault.
*/
#define kh_val(h, x) ((h)->vals[x])
/*! @function
@abstract Alias of kh_val()
*/
#define kh_value(h, x) ((h)->vals[x])
/*! @function
@abstract Get the start iterator
@param h Pointer to the hash table [khash_t(name)*]
@return The start iterator [khint_t]
*/
#define kh_begin(h) (khint_t)(0)
/*! @function
@abstract Get the end iterator
@param h Pointer to the hash table [khash_t(name)*]
@return The end iterator [khint_t]
*/
#define kh_end(h) ((h)->n_buckets)
/*! @function
@abstract Get the number of elements in the hash table
@param h Pointer to the hash table [khash_t(name)*]
@return Number of elements in the hash table [khint_t]
*/
#define kh_size(h) ((h)->size)
/*! @function
@abstract Get the number of buckets in the hash table
@param h Pointer to the hash table [khash_t(name)*]
@return Number of buckets in the hash table [khint_t]
*/
#define kh_n_buckets(h) ((h)->n_buckets)
/*! @function
@abstract Iterate over the entries in the hash table
@param h Pointer to the hash table [khash_t(name)*]
@param kvar Variable to which key will be assigned
@param vvar Variable to which value will be assigned
@param code Block of code to execute
*/
#define kh_foreach(h, kvar, vvar, code) { khint_t __i; \
for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
if (!kh_exist(h,__i)) continue; \
(kvar) = kh_key(h,__i); \
(vvar) = kh_val(h,__i); \
code; \
} }
/*! @function
@abstract Iterate over the values in the hash table
@param h Pointer to the hash table [khash_t(name)*]
@param vvar Variable to which value will be assigned
@param code Block of code to execute
*/
#define kh_foreach_value(h, vvar, code) { khint_t __i; \
for (__i = kh_begin(h); __i != kh_end(h); ++__i) { \
if (!kh_exist(h,__i)) continue; \
(vvar) = kh_val(h,__i); \
code; \
} }
/* More conenient interfaces */
/*! @function
@abstract Instantiate a hash set containing integer keys
@param name Name of the hash table [symbol]
*/
#define KHASH_SET_INIT_INT(name) \
KHASH_INIT(name, khint32_t, char, 0, kh_int_hash_func, kh_int_hash_equal)
/*! @function
@abstract Instantiate a hash map containing integer keys
@param name Name of the hash table [symbol]
@param khval_t Type of values [type]
*/
#define KHASH_MAP_INIT_INT(name, khval_t) \
KHASH_INIT(name, khint32_t, khval_t, 1, kh_int_hash_func, kh_int_hash_equal)
/*! @function
@abstract Instantiate a hash map containing 64-bit integer keys
@param name Name of the hash table [symbol]
*/
#define KHASH_SET_INIT_INT64(name) \
KHASH_INIT(name, khint64_t, char, 0, kh_int64_hash_func, kh_int64_hash_equal)
/*! @function
@abstract Instantiate a hash map containing 64-bit integer keys
@param name Name of the hash table [symbol]
@param khval_t Type of values [type]
*/
#define KHASH_MAP_INIT_INT64(name, khval_t) \
KHASH_INIT(name, khint64_t, khval_t, 1, kh_int64_hash_func, kh_int64_hash_equal)
typedef const char *kh_cstr_t;
/*! @function
@abstract Instantiate a hash map containing const char* keys
@param name Name of the hash table [symbol]
*/
#define KHASH_SET_INIT_STR(name) \
KHASH_INIT(name, kh_cstr_t, char, 0, kh_str_hash_func, kh_str_hash_equal)
/*! @function
@abstract Instantiate a hash map containing const char* keys
@param name Name of the hash table [symbol]
@param khval_t Type of values [type]
*/
#define KHASH_MAP_INIT_STR(name, khval_t) \
KHASH_INIT(name, kh_cstr_t, khval_t, 1, kh_str_hash_func, kh_str_hash_equal)
#endif /* __AC_KHASH_H */