# HG changeset patch # User June Park # Date 1766982862 28800 # Node ID 75de5903355c8bec826fa35ae8a96bfa4b291396 # Parent 4bc56e88e1f30149566eabb06a5391f8f96bb3e8 Giagantic changes that update Dowa library to be more align with stb style array and hashmap. Updated Seobeo to be caching on server side instead of file level caching. Deleted bunch of things I don't really use. diff -r 4bc56e88e1f3 -r 75de5903355c .bazelignore --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/.bazelignore Sun Dec 28 20:34:22 2025 -0800 @@ -0,0 +1,1 @@ +bazel-mono diff -r 4bc56e88e1f3 -r 75de5903355c BUILD diff -r 4bc56e88e1f3 -r 75de5903355c MODULE.bazel --- a/MODULE.bazel Thu Dec 25 20:10:46 2025 -0800 +++ b/MODULE.bazel Sun Dec 28 20:34:22 2025 -0800 @@ -1,11 +1,13 @@ bazel_dep(name = "rules_cc", version = "0.2.14") -bazel_dep(name = "platforms", version = "0.0.11") +bazel_dep(name = "platforms", version = "1.0.0") bazel_dep(name = "bazel_skylib", version = "1.8.2") +bazel_dep(name = "rules_shell", version = "0.6.1") bazel_dep(name = "openssl", version = "3.3.1.bcr.7") -bazel_dep(name = "rules_python", version = "1.7.0") -bazel_dep(name = "rules_android", version = "0.6.6") + +http_file = use_repo_rule("@bazel_tools//tools/build_defs/repo:http.bzl", "http_file") # Android stuff +bazel_dep(name = "rules_android", version = "0.6.6") remote_android_extensions = use_extension( "@rules_android//bzlmod_extensions:android_extensions.bzl", "remote_android_tools_extensions") @@ -14,9 +16,6 @@ android_sdk_repository_extension = use_extension("@rules_android//rules/android_sdk_repository:rule.bzl", "android_sdk_repository_extension") use_repo(android_sdk_repository_extension, "androidsdk") - -http_file = use_repo_rule("@bazel_tools//tools/build_defs/repo:http.bzl", "http_file") - # Bun http_file( name = "bun_darwin_arm64_zip", @@ -35,11 +34,12 @@ ) # Bring in pip support -use_extension("@rules_python//python/extensions:pip.bzl", "pip") -pip = use_extension("@rules_python//python/extensions:pip.bzl", "pip") +# bazel_dep(name = "rules_python", version = "1.7.0") +# use_extension("@rules_python//python/extensions:pip.bzl", "pip") +# pip = use_extension("@rules_python//python/extensions:pip.bzl", "pip") # Point to your requirements file -pip.install(requirements = "//:requirements.txt") +# pip.install(requirements = "//:requirements.txt") # Register the pip repo so you can depend on it -use_repo(pip, "pip_deps") +# use_repo(pip, "pip_deps") diff -r 4bc56e88e1f3 -r 75de5903355c MODULE.bazel.lock --- a/MODULE.bazel.lock Thu Dec 25 20:10:46 2025 -0800 +++ b/MODULE.bazel.lock Sun Dec 28 20:34:22 2025 -0800 @@ -121,7 +121,6 @@ "https://bcr.bazel.build/modules/rules_cc/0.0.8/MODULE.bazel": "964c85c82cfeb6f3855e6a07054fdb159aced38e99a5eecf7bce9d53990afa3e", "https://bcr.bazel.build/modules/rules_cc/0.0.9/MODULE.bazel": "836e76439f354b89afe6a911a7adf59a6b2518fafb174483ad78a2a2fde7b1c5", "https://bcr.bazel.build/modules/rules_cc/0.1.1/MODULE.bazel": "2f0222a6f229f0bf44cd711dc13c858dad98c62d52bd51d8fc3a764a83125513", - "https://bcr.bazel.build/modules/rules_cc/0.1.5/MODULE.bazel": "88dfc9361e8b5ae1008ac38f7cdfd45ad738e4fa676a3ad67d19204f045a1fd8", "https://bcr.bazel.build/modules/rules_cc/0.2.14/MODULE.bazel": "353c99ed148887ee89c54a17d4100ae7e7e436593d104b668476019023b58df8", "https://bcr.bazel.build/modules/rules_cc/0.2.14/source.json": "55d0a4587c5592fad350f6e698530f4faf0e7dd15e69d43f8d87e220c78bea54", "https://bcr.bazel.build/modules/rules_cc/0.2.4/MODULE.bazel": "1ff1223dfd24f3ecf8f028446d4a27608aa43c3f41e346d22838a4223980b8cc", @@ -194,15 +193,15 @@ "https://bcr.bazel.build/modules/rules_python/0.4.0/MODULE.bazel": "9208ee05fd48bf09ac60ed269791cf17fb343db56c8226a720fbb1cdf467166c", "https://bcr.bazel.build/modules/rules_python/0.40.0/MODULE.bazel": "9d1a3cd88ed7d8e39583d9ffe56ae8a244f67783ae89b60caafc9f5cf318ada7", "https://bcr.bazel.build/modules/rules_python/1.0.0/MODULE.bazel": "898a3d999c22caa585eb062b600f88654bf92efb204fa346fb55f6f8edffca43", - "https://bcr.bazel.build/modules/rules_python/1.7.0/MODULE.bazel": "d01f995ecd137abf30238ad9ce97f8fc3ac57289c8b24bd0bf53324d937a14f8", - "https://bcr.bazel.build/modules/rules_python/1.7.0/source.json": "028a084b65dcf8f4dc4f82f8778dbe65df133f234b316828a82e060d81bdce32", + "https://bcr.bazel.build/modules/rules_python/1.0.0/source.json": "b0162a65c6312e45e7912e39abd1a7f8856c2c7e41ecc9b6dc688a6f6400a917", "https://bcr.bazel.build/modules/rules_robolectric/4.14.1.2/MODULE.bazel": "d44fec647d0aeb67b9f3b980cf68ba634976f3ae7ccd6c07d790b59b87a4f251", "https://bcr.bazel.build/modules/rules_robolectric/4.14.1.2/source.json": "37c10335f2361c337c5c1f34ed36d2da70534c23088062b33a8bdaab68aa9dea", "https://bcr.bazel.build/modules/rules_shell/0.1.2/MODULE.bazel": "66e4ca3ce084b04af0b9ff05ff14cab4e5df7503973818bb91cbc6cda08d32fc", "https://bcr.bazel.build/modules/rules_shell/0.2.0/MODULE.bazel": "fda8a652ab3c7d8fee214de05e7a9916d8b28082234e8d2c0094505c5268ed3c", "https://bcr.bazel.build/modules/rules_shell/0.3.0/MODULE.bazel": "de4402cd12f4cc8fda2354fce179fdb068c0b9ca1ec2d2b17b3e21b24c1a937b", "https://bcr.bazel.build/modules/rules_shell/0.4.0/MODULE.bazel": "0f8f11bb3cd11755f0b48c1de0bbcf62b4b34421023aa41a2fc74ef68d9584f0", - "https://bcr.bazel.build/modules/rules_shell/0.4.0/source.json": "1d7fa7f941cd41dc2704ba5b4edc2e2230eea1cc600d80bd2b65838204c50b95", + "https://bcr.bazel.build/modules/rules_shell/0.6.1/MODULE.bazel": "72e76b0eea4e81611ef5452aa82b3da34caca0c8b7b5c0c9584338aa93bae26b", + "https://bcr.bazel.build/modules/rules_shell/0.6.1/source.json": "20ec05cd5e592055e214b2da8ccb283c7f2a421ea0dc2acbf1aa792e11c03d0c", "https://bcr.bazel.build/modules/rules_swift/1.16.0/MODULE.bazel": "4a09f199545a60d09895e8281362b1ff3bb08bbde69c6fc87aff5b92fcc916ca", "https://bcr.bazel.build/modules/rules_swift/2.1.1/MODULE.bazel": "494900a80f944fc7aa61500c2073d9729dff0b764f0e89b824eb746959bc1046", "https://bcr.bazel.build/modules/rules_swift/2.1.1/source.json": "40fc69dfaac64deddbb75bd99cdac55f4427d9ca0afbe408576a65428427a186", @@ -336,282 +335,6 @@ ] ] } - }, - "@@rules_python+//python/extensions:config.bzl%config": { - "general": { - "bzlTransitiveDigest": "xaCns8Qt+8bJqVLy8r6nc/eL2AjEIX/vOdjqoh5xYac=", - "usagesDigest": "ZVSXMAGpD+xzVNPuvF1IoLBkty7TROO0+akMapt1pAg=", - "recordedFileInputs": {}, - "recordedDirentsInputs": {}, - "envVariables": {}, - "generatedRepoSpecs": { - "rules_python_internal": { - "repoRuleId": "@@rules_python+//python/private:internal_config_repo.bzl%internal_config_repo", - "attributes": { - "transition_setting_generators": {}, - "transition_settings": [] - } - }, - "pypi__build": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/e2/03/f3c8ba0a6b6e30d7d18c40faab90807c9bb5e9a1e3b2fe2008af624a9c97/build-1.2.1-py3-none-any.whl", - "sha256": "75e10f767a433d9a86e50d83f418e83efc18ede923ee5ff7df93b6cb0306c5d4", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__click": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/00/2e/d53fa4befbf2cfa713304affc7ca780ce4fc1fd8710527771b58311a3229/click-8.1.7-py3-none-any.whl", - "sha256": "ae74fb96c20a0277a1d615f1e4d73c8414f5a98db8b799a7931d1582f3390c28", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__colorama": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/d1/d6/3965ed04c63042e047cb6a3e6ed1a63a35087b6a609aa3a15ed8ac56c221/colorama-0.4.6-py2.py3-none-any.whl", - "sha256": "4f1d9991f5acc0ca119f9d443620b77f9d6b33703e51011c16baf57afb285fc6", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__importlib_metadata": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/2d/0a/679461c511447ffaf176567d5c496d1de27cbe34a87df6677d7171b2fbd4/importlib_metadata-7.1.0-py3-none-any.whl", - "sha256": "30962b96c0c223483ed6cc7280e7f0199feb01a0e40cfae4d4450fc6fab1f570", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__installer": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/e5/ca/1172b6638d52f2d6caa2dd262ec4c811ba59eee96d54a7701930726bce18/installer-0.7.0-py3-none-any.whl", - "sha256": "05d1933f0a5ba7d8d6296bb6d5018e7c94fa473ceb10cf198a92ccea19c27b53", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__more_itertools": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/50/e2/8e10e465ee3987bb7c9ab69efb91d867d93959095f4807db102d07995d94/more_itertools-10.2.0-py3-none-any.whl", - "sha256": "686b06abe565edfab151cb8fd385a05651e1fdf8f0a14191e4439283421f8684", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__packaging": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/49/df/1fceb2f8900f8639e278b056416d49134fb8d84c5942ffaa01ad34782422/packaging-24.0-py3-none-any.whl", - "sha256": "2ddfb553fdf02fb784c234c7ba6ccc288296ceabec964ad2eae3777778130bc5", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__pep517": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/25/6e/ca4a5434eb0e502210f591b97537d322546e4833dcb4d470a48c375c5540/pep517-0.13.1-py3-none-any.whl", - "sha256": "31b206f67165b3536dd577c5c3f1518e8fbaf38cbc57efff8369a392feff1721", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__pip": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/8a/6a/19e9fe04fca059ccf770861c7d5721ab4c2aebc539889e97c7977528a53b/pip-24.0-py3-none-any.whl", - "sha256": "ba0d021a166865d2265246961bec0152ff124de910c5cc39f1156ce3fa7c69dc", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__pip_tools": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/0d/dc/38f4ce065e92c66f058ea7a368a9c5de4e702272b479c0992059f7693941/pip_tools-7.4.1-py3-none-any.whl", - "sha256": "4c690e5fbae2f21e87843e89c26191f0d9454f362d8acdbd695716493ec8b3a9", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__pyproject_hooks": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/ae/f3/431b9d5fe7d14af7a32340792ef43b8a714e7726f1d7b69cc4e8e7a3f1d7/pyproject_hooks-1.1.0-py3-none-any.whl", - "sha256": "7ceeefe9aec63a1064c18d939bdc3adf2d8aa1988a510afec15151578b232aa2", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__setuptools": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/90/99/158ad0609729111163fc1f674a5a42f2605371a4cf036d0441070e2f7455/setuptools-78.1.1-py3-none-any.whl", - "sha256": "c3a9c4211ff4c309edb8b8c4f1cbfa7ae324c4ba9f91ff254e3d305b9fd54561", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__tomli": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/97/75/10a9ebee3fd790d20926a90a2547f0bf78f371b2f13aa822c759680ca7b9/tomli-2.0.1-py3-none-any.whl", - "sha256": "939de3e7a6161af0c887ef91b7d41a53e7c5a1ca976325f429cb46ea9bc30ecc", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__wheel": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/7d/cd/d7460c9a869b16c3dd4e1e403cce337df165368c71d6af229a74699622ce/wheel-0.43.0-py3-none-any.whl", - "sha256": "55c570405f142630c6b9f72fe09d9b67cf1477fcf543ae5b8dcb1f5b7377da81", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - }, - "pypi__zipp": { - "repoRuleId": "@@bazel_tools//tools/build_defs/repo:http.bzl%http_archive", - "attributes": { - "url": "https://files.pythonhosted.org/packages/da/55/a03fd7240714916507e1fcf7ae355bd9d9ed2e6db492595f1a67f61681be/zipp-3.18.2-py3-none-any.whl", - "sha256": "dce197b859eb796242b0622af1b8beb0a722d52aa2f57133ead08edd5bf5374e", - "type": "zip", - "build_file_content": "package(default_visibility = [\"//visibility:public\"])\n\nload(\"@rules_python//python:py_library.bzl\", \"py_library\")\n\npy_library(\n name = \"lib\",\n srcs = glob([\"**/*.py\"]),\n data = glob([\"**/*\"], exclude=[\n # These entries include those put into user-installed dependencies by\n # data_exclude to avoid non-determinism.\n \"**/*.py\",\n \"**/*.pyc\",\n \"**/*.pyc.*\", # During pyc creation, temp files named *.pyc.NNN are created\n \"**/*.dist-info/RECORD\",\n \"BUILD\",\n \"WORKSPACE\",\n ]),\n # This makes this directory a top-level in the python import\n # search path for anything that depends on this.\n imports = [\".\"],\n)\n" - } - } - }, - "recordedRepoMappingEntries": [ - [ - "rules_python+", - "bazel_tools", - "bazel_tools" - ], - [ - "rules_python+", - "pypi__build", - "rules_python++config+pypi__build" - ], - [ - "rules_python+", - "pypi__click", - "rules_python++config+pypi__click" - ], - [ - "rules_python+", - "pypi__colorama", - "rules_python++config+pypi__colorama" - ], - [ - "rules_python+", - "pypi__importlib_metadata", - "rules_python++config+pypi__importlib_metadata" - ], - [ - "rules_python+", - "pypi__installer", - "rules_python++config+pypi__installer" - ], - [ - "rules_python+", - "pypi__more_itertools", - "rules_python++config+pypi__more_itertools" - ], - [ - "rules_python+", - "pypi__packaging", - "rules_python++config+pypi__packaging" - ], - [ - "rules_python+", - "pypi__pep517", - "rules_python++config+pypi__pep517" - ], - [ - "rules_python+", - "pypi__pip", - "rules_python++config+pypi__pip" - ], - [ - "rules_python+", - "pypi__pip_tools", - "rules_python++config+pypi__pip_tools" - ], - [ - "rules_python+", - "pypi__pyproject_hooks", - "rules_python++config+pypi__pyproject_hooks" - ], - [ - "rules_python+", - "pypi__setuptools", - "rules_python++config+pypi__setuptools" - ], - [ - "rules_python+", - "pypi__tomli", - "rules_python++config+pypi__tomli" - ], - [ - "rules_python+", - "pypi__wheel", - "rules_python++config+pypi__wheel" - ], - [ - "rules_python+", - "pypi__zipp", - "rules_python++config+pypi__zipp" - ] - ] - } - }, - "@@rules_python+//python/uv:uv.bzl%uv": { - "general": { - "bzlTransitiveDigest": "N8SCcKcL6KnzBLApxvY2jR9vhXjA2VCBZMLZfY3sDRA=", - "usagesDigest": "H8dQoNZcoqP+Mu0tHZTi4KHATzvNkM5ePuEqoQdklIU=", - "recordedFileInputs": {}, - "recordedDirentsInputs": {}, - "envVariables": {}, - "generatedRepoSpecs": { - "uv": { - "repoRuleId": "@@rules_python+//python/uv/private:uv_toolchains_repo.bzl%uv_toolchains_repo", - "attributes": { - "toolchain_type": "'@@rules_python+//python/uv:uv_toolchain_type'", - "toolchain_names": [ - "none" - ], - "toolchain_implementations": { - "none": "'@@rules_python+//python:none'" - }, - "toolchain_compatible_with": { - "none": [ - "@platforms//:incompatible" - ] - }, - "toolchain_target_settings": {} - } - } - }, - "recordedRepoMappingEntries": [ - [ - "rules_python+", - "bazel_tools", - "bazel_tools" - ], - [ - "rules_python+", - "platforms", - "platforms" - ] - ] - } } } } diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/LRU.py --- a/async_multi_threads/LRU.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -from typing import Optional - - -class Node: - def __init__(self, key, value): - self.key = key - self.value = value - self.next: Optional[Node] = None - self.prev: Optional[Node] = None - -class LRUCache: - - def __init__(self, capacity: int): - self.capacity = capacity - self.map = {} - self.head = Node(-1, -1) - self.tail = Node(-1, -1) - self.head.next, self.tail.prev = self.tail, self.head - - def get(self, key: int) -> int: - if not key in self.map: - return -1 - node = self.map[key] - self._deleteAndAdd(node) - return node.value - - def put(self, key: int, value: int) -> None: - newNode = Node(key, value) - if key in self.map: - self._delete(self.map[key]) - else: - if len(self.map.keys())+1 > self.capacity: - del self.map[self.head.next.key] - self._delete(self.head.next) - self._add(newNode) - self.map[key] = newNode - - def _deleteAndAdd(self, node): - self._delete(node) - self._add(node) - - def _delete(self, node): - node.prev.next, node.next.prev = node.next, node.prev - - def _add(self, node): - node.prev, node.next, self.tail.prev.next, self.tail.prev = self.tail.prev, self.tail, node, node diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/README.md --- a/async_multi_threads/README.md Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,43 +0,0 @@ -# Distributed Cache (Focus: Hashing & System Logic) - -- Question: Implement a Cache Router - - Level 1 (Easy - Modulo Hashing): Write a function that maps a key (string) to one of N servers. - - Task: Implement getServerIndex(key, serverCount). - - Expected Logic: Simple hash modulo: hash(key) % serverCount. - - Critique: The interviewer will ask, "What happens to the existing keys if we add one server (change N to N+1)?" (Answer: Almost all keys get remapped, causing a massive cache miss storm). - - Level 2 (Medium - Consistent Hashing): Solve the remapping problem. Implement a ConsistentHash class. - - Task: Map servers to points on a circle (0 to 360 degrees or a large integer range). Map keys to the same circle. A key belongs to the first server it encounters moving clockwise. - - Goal: Prove that adding a server only requires remapping the keys that fall between the new server and its predecessor. - - Level 3 (Hard - Virtual Nodes): The servers have uneven capacity, or the data distribution is skewed (some segments of the ring have way more keys). - - Task: Modify the class so that each physical server exists at multiple points on the ring (e.g., "Server A" is at positions 10, 150, and 290). - - Goal: Distribute load more evenly and handle "hot spots" better. - ---- - -Questions: - - - Async - - Threads - - DB - - Cache - - KV - - Distribution - - ---- - -FE - - - Fetching URL - - Storing it as useMemo and what not. - diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/alphabet_search.py --- a/async_multi_threads/alphabet_search.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,56 +0,0 @@ -# Given an m x n grid of characters board and a string word, return true if word exists in the grid. -# -# The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. -# -# -# -# Example 1: -# -# -# Input: board = [ -# ["A","B","C","E"], -# ["S","F","C","S"], -# ["A","D","E","E"] -# ], word = "ABCCED" -# Output: true - -def main(board, word): - ROWS = len(board) - COLS = len(board[0]) - - pos = 0 - - directions = [ - (0, 1), - (1, 0), - (0, -1), - (-1, 0), - ] - def dfs(row, col, pos): - # import pdb; pdb.set_trace() - if pos == len(word): - return True - - if (row < 0 or row >= ROWS) or (col < 0 or col >= COLS) or board[row][col] == "#": - return False - - letter = board[row][col] - if letter == word[pos]: - pos += 1 - board[row][col] = "#" - for direction in directions: - if dfs(row + direction[0], col + direction[1], pos): - return True - board[row][col] = letter - - for r in range(ROWS): - for c in range(COLS): - if dfs(r, c, 0): - return True - return False - - -board = [["b"],["a"],["b"],["b"],["a"]] -word = "baa" - -print(main(board, word)) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/async.py --- a/async_multi_threads/async.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ - -# 1. asynciously down list of urls -# 2. retries - - - -import asyncio -from concurrent.futures import ThreadPoolExecutor -import random -from typing import List -import time - -async def interface_download_url(url: str, retry_number = 0): - curr = time.time() - success = False - try: - res = await func_download_url(url) - success = True - except: - res = await interface_download_url(url, retry_number + 1) - res = None - long = curr - time.time() - return success, res, url, long - -async def func_download_url(url: str): - await asyncio.sleep(random.randint(1, 10)) - -ALLOWED_BATCH_SIZE = 10 -ALLOWED_RETRY_SIZE = 3 -async def download_multi_urls(urls: List[str], retry_num = 0): - if retry_num > ALLOWED_RETRY_SIZE: - return - - number_of_batch = len(urls) // ALLOWED_BATCH_SIZE + 1 - - errors = [] - for batch_num in range(number_of_batch): - download_urls = urls[batch_num * ALLOWED_BATCH_SIZE:(batch_num + 1) * ALLOWED_BATCH_SIZE] - for download_url in download_urls: - asyncio.run(asyncio.create_task(interface_download_url(download_url))) - results = await asyncio.gather(*tasks) - for task in tasks - asyncio.run() - for result in results: - if not result[0]: - errors.append(result[2]) - - await download_multi_urls(errors, retry_num+1) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/binary_search.py --- a/async_multi_threads/binary_search.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,18 +0,0 @@ - -x = [1,2,3,4,5,9,20,25,33,99] -# | | - -target = 18 -left = 0 -right = len(x) - -while left < right: - mid = (left + right)//2 - if x[mid] == target: - break - elif x[mid] < target: - left = mid + 1 - else: - right = mid - -print(x[mid]) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/bucket_try_2.py --- a/async_multi_threads/bucket_try_2.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,65 +0,0 @@ -# Context -# -# Please implement two functions: refillTokenBucket and useTokens. Two classes are already defined: DistributedCache and TokenBucket. -# -# refillTokenBucket(user_id): Refill tokens for the specified user's bucket. -# -# useTokens(user_id, tokens): Check if there are enough tokens in the specified user's token bucket. If so, update the remaining token count and return true; otherwise, return false. You are required to use instances of the existing classes to implement these functions. - -import asyncio -from typing import Dict - - -class DistributedCache: - - def __init__(self): - self._hashmap: Dict[str, TokenBucket] = {} - - def add_user(self, user_id: str): - self._hashmap[user_id] = TokenBucket() - - def get_token_bucket(self, user_id: str): - return self._hashmap[user_id] - -class TokenBucket: - - def __init__(self, initial_token_value: int = 100): - self._tokens = initial_token_value - self.initial_token_value = initial_token_value - self._lock = asyncio.Lock() - - async def consume(self, token: int): - async with self._lock: - tokens = self.get_token() - await asyncio.sleep(0.1) - if tokens < token: - return False - tokens -= token - self.set_token(tokens) - return True - - async def refill(self): - async with self._lock: - self._tokens = self.initial_token_value - - def get_token(self): - return self._tokens - - def set_token(self, token: int): - self._tokens = token - -distCache = DistributedCache() -distCache.add_user("june") - -async def refillTokenBucket(user_id: str): - await distCache.get_token_bucket(user_id).refill() - -async def useTokens(user_id: str, token: int): - return await distCache.get_token_bucket(user_id).consume(token) - -async def main(): - await asyncio.gather(useTokens("june", 10), useTokens("june", 10), useTokens("june", 10)) - print(distCache.get_token_bucket("june").get_token()) - -asyncio.run(main()) - diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/choice.py --- a/async_multi_threads/choice.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ -import random - -print(random.choice([ - 'Bucket questions', - 'Inference Questions', - 'Bank Account', - 'Job Schedular', - 'Alphabet Word Search II', - 'Least Recently Used (LRU) Cache Implementation', - 'In-Memory Key-Value Store with Nested Transactions', -])) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/consistent_hash.py --- a/async_multi_threads/consistent_hash.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,32 +0,0 @@ -# Write a function taht maps -# Key string to one of N servers -from bisect import bisect_left -from hashlib import sha256 - -class Server: - - def __init__(self): - self.id = str(sha256()) - -class ConsistentHash: - def __init__(self): - self.server = [] - self.hash_key_to_server = {} - self.hash_range = 10000 - - def get_hash_pos(self, key: str) -> int: - x = sha256(bytes(key, "utf-8")) - return int.from_bytes(x.digest()[:8]) % self.hash_range - - def add_server(self, server: Server): - self.server.append(server) - for i in range(len(self.server) + 1): - hash_key = self.get_hash_pos(server.id) - self.hash_key_to_server[hash_key] = i - - def get_server(self, key): - hash_key = self.get_hash_pos(key) - return self.server[bisect_left(list(self.hash_key_to_server.keys()), hash_key)] - - def remove_server(self, server): - hash_key = self.get_hash_pos(server.id) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/inference.py --- a/async_multi_threads/inference.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,146 +0,0 @@ -import asyncio -import time -from typing import List, Dict, Any, Optional -import uuid -from dataclasses import dataclass, field - -@dataclass -class InferenceRequest: - prompt: str - request_id: str = field(default_factory=lambda: str(uuid.uuid4())) - max_tokens: int = 128 - created_at: float = field(default_factory=time.time) - -@dataclass -class TokenOutput: - token: str - request_id: str - token_index: int # position in this request's generation - is_complete: bool = False - -class BatchInferenceEngine: - - def __init__(self, batch_size: int = 8, timeout: float = 0.1): - """ - Args: - batch_size: Maximum number of requests to process in one inference call - timeout: Max time to wait for batch to fill before processing (in seconds) - """ - self.batch_size = batch_size - self.timeout = timeout - - self.queue: List[InferenceRequest] = [] - self.pending_requests: Dict[str, List[str]] = {} # request_id -> list of generated tokens - self.completion_futures: Dict[str, asyncio.Future] = {} - - self._lock = asyncio.Lock() - self._batch_ready_event = asyncio.Event() - - async def submit_request(self, prompt: str, max_tokens: int = 128) -> asyncio.Future[str]: - """ - Submit a new inference request and return a Future that resolves to the generated text. - """ - request = InferenceRequest(prompt=prompt, max_tokens=max_tokens) - - future = asyncio.get_event_loop().create_future() - - async with self._lock: - self.queue.append(request) - self.pending_requests[request.request_id] = [] - self.completion_futures[request.request_id] = future - - # Trigger batch processing if we've reached batch size - if len(self.queue) >= self.batch_size: - self._batch_ready_event.set() - - # Start background worker if not already running - asyncio.create_task(self._worker()) - - return future - - async def _worker(self): - """Background task that processes batches when ready""" - while True: - # Wait until we have requests or timeout triggers - try: - await asyncio.wait_for(self._batch_ready_event.wait(), timeout=self.timeout) - except asyncio.TimeoutError: - pass - - async with self._lock: - if not self.queue: - self._batch_ready_event.clear() - continue - - # Take up to batch_size requests - current_batch = self.queue[:self.batch_size] - self.queue = self.queue[self.batch_size:] - - # Reset event if queue is now empty - if not self.queue: - self._batch_ready_event.clear() - - # Simulate batched LLM inference - token_outputs: List[TokenOutput] = self._simulate_batched_inference(current_batch) - - # Distribute tokens back to individual requests - async with self._lock: - for token_out in token_outputs: - req_id = token_out.request_id - self.pending_requests[req_id].append(token_out.token) - - # Check if this request is complete - if token_out.is_complete: - full_text = ''.join(self.pending_requests[req_id]) - future = self.completion_futures.pop(req_id) - future.set_result(full_text) - del self.pending_requests[req_id] - - def _simulate_batched_inference(self, batch: List[InferenceRequest]) -> List[TokenOutput]: - """ - Simulates a real LLM forward pass on a batch. - In real implementation, this would call model.generate() with padded batch. - """ - outputs: List[TokenOutput] = [] - - for req in batch: - prompt_len = len(req.prompt.split()) # rough estimate - num_tokens_to_generate = min(req.max_tokens, 50 + hash(req.request_id) % 30) - - # Simulate token-by-token generation - token_str = f"{req.prompt}" - is_complete = (i == num_tokens_to_generate - 1) - - outputs.append(TokenOutput( - token=token_str, - request_id=req.request_id, - token_index=i, - is_complete=is_complete - )) - - # In streaming: could yield early here in real streaming setup - - return outputs - -# Example usage -async def main(): - engine = BatchInferenceEngine(batch_size=4, timeout=0.5) - - # Submit several requests - futures = [ - engine.submit_request("Tell me a joke about cats"), - engine.submit_request("Explain quantum computing in simple terms"), - engine.submit_request("Write a haiku about AI"), - engine.submit_request("What is the meaning of life?"), - ] - - print("Requests submitted, waiting for results...") - - # Wait for all to complete - results = await asyncio.gather(*futures) - - for i, text in enumerate(results): - print(f"Request {i}: {text.result()}\n\n\n") - -if __name__ == "__main__": - asyncio.run(main()) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/inference_my_version.py --- a/async_multi_threads/inference_my_version.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,75 +0,0 @@ -""" -Inference Questions - -Context - -You are tasked with building a simplified inference engine component responsible for handling incoming user requests for a large language model (LLM). To optimize throughput and GPU utilization, the engine must batch multiple requests together, run the inference call once per batch, and then deconstruct the results to return token-level output to the individual users. - -Objective - -Complete the provided Python class, BatchInferenceEngine by implementing the methods necessary to: - -Queue incoming user requests. - -Process a batch when the queue reaches a defined batch size. -Simulate the token-level output from an LLM and correctly associate each generated token with its original request. -""" - -import asyncio -from dataclasses import dataclass, field -from time import time -from typing import Dict, List -import uuid - -@dataclass -class UserRequest: - prompt: str - id: str = field(default_factory=lambda: str(uuid.uuid4())) - created_at: float = field(default_factory=time) - - -@dataclass -class TokenOutput: - request_id: str - token: bytes - -class BatchInferenceEngine: - - def __init__(self, batch_sizes: int = 8): - self.queue = [] - self.request_token_map: Dict[str, str] = {} - self.batch_sizes = batch_sizes - - self._lock = asyncio.Lock() - self._batch_event = asyncio.Event() - - async def add_to_queue(self, request: UserRequest): - async with self._lock: - self.queue.append(request) - - if len(self.queue) > self.batch_sizes: - self._batch_event.set() - - task = asyncio.create_task(self._batch()) - return task - - async def _batch(self): - while True: - try: - await asyncio.wait_for(self._batch_event.wait(), timeout=0.05) - except: - raise Exception("Timed out") - - async with self._lock: - if not self.queue: - self._batch_event.clear() - continue - - batch = self.queue[:self.batch_sizes] - tokens = await self._handle_prompt_to_token(batch) - - return tokens - - - async def _handle_prompt_to_token(self, batch: List[UserRequest]): - pass diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/job_scheduler.py --- a/async_multi_threads/job_scheduler.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,43 +0,0 @@ -# Job Schedular -# -# Implement a concurrent job scheduler that can schedule multiple workers to complete job tasks. The scheduler must handle asynchronous tasks and be able to dynamically increase or decrease the number of workers. It must handle task execution failures, for example, by retrying or logging. Provide examples with at least three different tasks and examples of scheduling strategies. - -import asyncio -from asyncio import Task -import random - -# Rename to match standard library function -async def job(name: str, delay: int = 1): - # Use asyncio.sleep - await asyncio.sleep(delay) - val = random.randint(1, 10) - if val > 5: - raise Exception("Something went wrong") - else: - print(name) - -class JobScheduler: - def __init__(self): - self._jobs: list[Task] = [] - - def add_task(self, task: Task): - self._jobs.append(task) - print(f"Added job: {task.get_name()}") # Added for debugging - - async def run(self): - print("Starting concurrent jobs...") - await asyncio.gather(*self._jobs, return_exceptions=True) - print("All jobs completed.") - -async def main(): - job_scheduler = JobScheduler() - # Use asyncio.create_task and provide a name - job_scheduler.add_task(asyncio.create_task(job("JUNE", 3), name="JUNE_JOB")) - job_scheduler.add_task(asyncio.create_task(job("PARK", 2), name="PARK_JOB")) - job_scheduler.add_task(asyncio.create_task(job("HELLO", 1), name="HELLO_JOB")) - await job_scheduler.run() - - -if __name__ == "__main__": - # Run the main asynchronous entry point - asyncio.run(main()) diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/lru_version2.py --- a/async_multi_threads/lru_version2.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,75 +0,0 @@ -# -# Question: Least Recently Used (LRU) Cache Implementation -# -# Design and implement a Least Recently Used (LRU) cache. The cache should be initialized with a positive integer capacity. -# -# Your implementation must support the following operations with $O(1)$ time complexity for both: -# -# get(key): Retrieve the value of the item identified by key. If the key exists, return its value. If it doesn't, return $-1$. This operation also marks the key as the most recently used. -# -# put(key, value): Insert or update an item. If the key already exists, update its value and mark it as the most recently used. If the key does not exist, insert the new item. When the cache reaches its capacity, it must evict the least recently used item before inserting the new one. -# -# You must use a Hash Map and a Doubly Linked List for the implementation. - -# Cache , limit 3 - -from typing import Dict - -# tail.prev.next = node, node.left = tails.prev, tails.prev = Node, node.next = tail - -# Head <-> Tail -# Head -> Node <-> Tail , -# Head <-> Node <-> Node1 <-> Tail, -# node.prev.next = node.next, node.next.prev = node.prev - -class Node: - - def __init__(self, key: str, value: str): - self.next: Node | None = None - self.prev: Node | None = None - self.key = key - self.value = value - -class LRU: - - def __init__(self, capacity: int = 2): - self.db: Dict[str, Node] = {} - self.capacity = capacity - - self.head = Node("-1", "-1") - self.tail = Node("-1", "-1") - self.head.next, self.tail.prev = self.tail, self.head - - def get(self, key: str): - node = self.db[key] - self._remove(node) - self._add_to_tail(node) - return node.value - - def put(self, key: str, value: str): - if len(self.db) < self.capacity or key in self.db: - new_node = Node(key, value) - self._add_to_tail(new_node) - self.db[key] = new_node - else: - least_recently_used_node = self.head.next - self._remove(least_recently_used_node) - del self.db[least_recently_used_node.key] - - new_node = Node(key, value) - self._add_to_tail(new_node) - self.db[key] = new_node - - def _remove(self, node: Node): - node.prev.next, node.next.prev = node.next, node.prev - - def _add_to_tail(self, node): - self.tail.prev.next, node.prev, self.tail.prev, node.next = node, self.tail.prev, node, self.tail - -lru = LRU() -lru.put("june", "park") -lru.put("victor", "sun") -lru.get("june") -lru.put("bowen", "sun") - - diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/main.py --- a/async_multi_threads/main.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,51 +0,0 @@ -# You are required to implement a production-level code live, using concurrency. Complete within 60 minutes. Suppose you are developing a simple concurrent counter that can correctly update the count in a multi-threaded environment. The initial count value is 0. Ensure it executes in 100 threads, where each thread increments the counter by 1 every second for 10 seconds. Calculate the final count after parallel execution. -# -# Input: None -# -# Output: An integer representing the final count. -# -# Constraints: -# -# The code must use multi-threading or multi-processing techniques. -# Ensure thread safety. - - -# - 100 threads -# - each tread update counter by 1 everyseconds by 10 seconds -from threading import Lock -from time import sleep -from concurrent.futures import ThreadPoolExecutor - - -SLEEP_IN_SECONDS = 1 -EXECUTION_TIME_IN_SECONDS = 3 -NUMS_THREADS = 100 - -class Counter: - - def __init__(self): - self._value = 0 - self.lock = Lock() - - def get(self): - return self._value - - def increment(self): - with self.lock: - value = self.get() - sleep(0.01) - self._value = value + 1 - -def worker(counter: Counter): - for _ in range(EXECUTION_TIME_IN_SECONDS): - counter.increment() - sleep(SLEEP_IN_SECONDS) - -def main(): - counter = Counter() - with ThreadPoolExecutor(max_workers=NUMS_THREADS) as executor: - for _ in range(NUMS_THREADS): - executor.submit(worker, counter) - print(counter.get()) - -main() diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/merge_sort.py --- a/async_multi_threads/merge_sort.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -from concurrent.futures import ProcessPoolExecutor -import random -from typing import List - -def merge_sort(lst: List[int]) -> List[int]: # no executor parameter! - if len(lst) <= 1: - return lst - middle = len(lst) // 2 - # These run in separate processes → no shared thread pool problem - left = merge_sort(lst[:middle]) - right = merge_sort(lst[middle:]) - return merge(left, right) - -def merge(left: List[int], right: List[int]) -> List[int]: - res = [] - i = j = 0 - while i < len(left) and j < len(right): - if left[i] <= right[j]: - res.append(left[i]) - i += 1 - else: - res.append(right[j]) - j += 1 - res.extend(left[i:]) - res.extend(right[j:]) - return res - -RANGE = 10_000 -cpu_num = 10 -def main(): - data = [random.randint(0, 100) for _ in range(RANGE)] - sorted_data = [] - ranges = [i for i in range(RANGE // cpu_num, RANGE, RANGE // 100)] - with ProcessPoolExecutor() as executor: - for pos_range in ranges: - sorted_data.append(executor.submit(merge_sort, data[:pos_range]).result()) - - while len(sorted_data) > 1: - new_sorted_data = [] - for i in range(0, len(sorted_data), 2): - if - res = merge(sorted_data[i], sorted_data[i+1]) - new_sorted_data.append(res) - - print(len(sorted_data)) - -if __name__ == "__main__": # important on Windows/macOS - main() diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/test.py --- a/async_multi_threads/test.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,36 +0,0 @@ -import asyncio -import random - - -class database: - def __init__(self): - self.values = 0 - self._lock = asyncio.Lock() - - def get(self): - return self.values - - def set(self, values): - self.values = values - - -async def add(number, db: database, random_wait: int): - async with db._lock: - current = db.get() - await asyncio.sleep(random.random() * 0.05) - db.set(current + number) - - -async def main(): - db = database() - tasks = [] - for i in range(100): - tasks.append(asyncio.create_task( - add(i, db, random.randint(1, 5)) - )) - await asyncio.gather(*tasks) - print(db.get()) - print(sum([i for i in range(100)])) - -asyncio.run(main()) - diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/thread.py --- a/async_multi_threads/thread.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,32 +0,0 @@ -# 1. data struture {} -# - multiple threads can access it -# - multiple threads can edit it if it is editable. (mutex) - - -from hashlib import sha256 -from threading import Lock - -class Subscribers: - def __init__(self): - self.id = sha256() - - def on_event(self, event): - pass - -class Publisher: - def __init__(self): - self._subscritions = {} - self.lock = Lock() - - def publish_event(self, event): - for subscriber_id, subscriber in enumerate(self._subscritions): - subscriber.on_event(event) - - def add_subscribers(self, subscriber: Subscribers): - with self.lock: - self._subscritions[subscriber.id] = subscriber - - def remove_subscribers(self, subscriber: Subscribers): - with self.lock: - del self._subscritions[subscriber.id] - diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/transaction.py --- a/async_multi_threads/transaction.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,57 +0,0 @@ -# Question: In-Memory Key-Value Store with Nested Transactions -# -# Design an in-memory key-value database that supports the following commands and fully handles nested transactions. -# Core Operations: - -# SET : Sets the value for a key. - -# GET : Returns the value for a key. - -# UNSET : Removes the key and its value. -# -# Transaction Operations: - -# BEGIN: Starts a new transaction scope. If a transaction is already active, this starts a nested transaction. - -# COMMIT: Applies all changes made in the current transaction scope and all its active nested transactions to the parent scope (or to the main database state if no parent exists). After a successful commit, the transaction scope is closed. - -# ROLLBACK: Discards all changes made in the current transaction scope and all its active nested transactions, restoring the state to what it was when the BEGIN command was issued for the current scope. After a successful rollback, the transaction scope is closed. - -# Implementation Goal: -# Design the primary data structures and outline the logic for SET, COMMIT, and ROLLBACK to ensure nested transactions operate correctly. Explain how the state of the database is managed across multiple transaction layers. - - -class Database: - def __init__(self): - self.global_db = {} - self.queue = [] - - def commit(self): - copy_db = self.queue.pop() - if self.queue: - self.queue[-1].merge(copy_db) - else: - self.global_db |= copy_db - - def set(self, key, value): - if self.queue: - curr_db = self.queue[-1] - curr_db[key] = value - else: - self.global_db[key] = value - - def get(self, key): - if self.queue: - for copy_db in reversed(self.queue): - if key in copy_db: - return copy_db[key] - - return self.global_db[key] - - def unset(self, key): - if self.queue: - curr_db = self.queue[-1] - del curr_db[key] - else: - del self.global_db[key] - diff -r 4bc56e88e1f3 -r 75de5903355c async_multi_threads/tries.py --- a/async_multi_threads/tries.py Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,95 +0,0 @@ -# Question: Alphabet Word Search II -# -# You are given an M x N board of characters and a list of strings called dictionary. Find all unique words in the dictionary that can be found in the board. -# -# A word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are those horizontally, vertically, or diagonally neighboring. The same letter cell may not be used more than once in a single word. -# -# Implement a function findWords(board, dictionary) that returns a list of all unique words found. -# -# Example: -# -# Board: -# -# [['o', 'a', 'b', 'n'], -# ['o', 't', 'a', 'e'], -# ['a', 'h', 'k', 'r'], -# ['a', 'f', 'l', 'v']] -# - -# Dictionary: ["oath", "pea", "eat", "rain", "hobo", "oats"] -# -# Expected Output: ["oath", "eat", "hobo", "oats"] -# -# Constraints & Requirements: - -# The search should be optimized for large dictionaries. - -# Clearly explain your chosen data structure and algorithm for prefix matching and path finding. - -from collections import deque -from os import wait -from typing import List - - -board = [ - ['o', 'a', 'b', 'n'], - ['o', 't', 'a', 'e'], - ['a', 'h', 'k', 'r'], - ['a', 'f', 'l', 'v'] -] -dictionary = ["oath", "pea", "eat", "rain", "hobo", "oats"] -directions = [ - (0, 1), - (0, -1), - (1, 0), - (-1, 0), - (1, 1), - (-1, -1), - (1, -1), - (-1, 1), -] - -def find_words(board: List[List[str]], dictionary: List[str]): - tree = {} - for row in range(len(board)): - for col in range(len(board)): - dfs(row, col, tree) - - ans = [] - for word in dictionary: - curr = tree - possible = True - for letter in word: - if letter not in curr: - possible = False - break - curr = curr[letter] - if possible: - ans.append(word) - - return ans - - -def dfs(row, col, tree): - if not (row >= 0 and row < len(board)\ - and col >= 0 and col < len(board[0])): - return {} - - if board[row][col] == "#": - return {} - - letter = board[row][col] - children = {} - board[row][col] = "#" - - for direction in directions: - new_row, new_col = row + direction[0], col + direction[1] - child_node = dfs(new_row, new_col, tree[letter]) - if child_node: - children.update(child_node) - - board[row][col] = letter - - return { letter: children } - -print(find_words(board, dictionary)) diff -r 4bc56e88e1f3 -r 75de5903355c color_game/BUILD --- a/color_game/BUILD Thu Dec 25 20:10:46 2025 -0800 +++ b/color_game/BUILD Sun Dec 28 20:34:22 2025 -0800 @@ -5,7 +5,6 @@ srcs = ["main.c"], deps = [ "//third_party/raylib:raylib", - # "//dowa:dowa", // TODO Fix for windows ], static = True ) diff -r 4bc56e88e1f3 -r 75de5903355c config/BUILD --- a/config/BUILD Thu Dec 25 20:10:46 2025 -0800 +++ b/config/BUILD Sun Dec 28 20:34:22 2025 -0800 @@ -1,6 +1,6 @@ config_setting( name = "macos", - constraint_values = ["@platforms//os:osx"], + constraint_values = ["@platforms//os:macos"], ) config_setting( diff -r 4bc56e88e1f3 -r 75de5903355c dowa/BUILD --- a/dowa/BUILD Thu Dec 25 20:10:46 2025 -0800 +++ b/dowa/BUILD Sun Dec 28 20:34:22 2025 -0800 @@ -1,6 +1,13 @@ load("@rules_cc//cc:cc_library.bzl", "cc_library") +load("@rules_cc//cc:cc_binary.bzl", "cc_binary") load("@rules_cc//cc:cc_test.bzl", "cc_test") +cc_library( + name = "stb_ds", + hdrs = ["stb_ds.h"], + visibility = ["//visibility:public"], +) + # TODO: Fix so that we can just define in the header instead of defining in the cc_library because this is ass. cc_library( name = "dowa_generic", @@ -10,7 +17,8 @@ ], hdrs = [ "dowa.h", - "dowa_internal.h" + "dowa_internal.h", + "stb_ds.h" ], visibility = ["//visibility:public"], ) @@ -23,7 +31,7 @@ ], hdrs = [ "dowa.h", - "dowa_internal.h" + "dowa_internal.h", ], copts = ["-DDIRECTORY"], visibility = ["//visibility:public"], @@ -37,6 +45,7 @@ data = glob([ "test_folder/**", ]), - copts = ["-fsanitize=address", "-g"], - linkopts = ["-fsanitize=address"], + # TODO: Fix this lmao? + # copts = ["-fsanitize=address", "-g"], + # linkopts = ["-fsanitize=address"], ) diff -r 4bc56e88e1f3 -r 75de5903355c dowa/d_memory.c --- a/dowa/d_memory.c Thu Dec 25 20:10:46 2025 -0800 +++ b/dowa/d_memory.c Sun Dec 28 20:34:22 2025 -0800 @@ -23,16 +23,7 @@ void *Dowa_Arena_Allocate(Dowa_Arena *p_arena, size_t size) { - if (!p_arena || !p_arena->buffer || size == 0) - return NULL; - - if (p_arena->offset + size > p_arena->capacity) - { - return NULL; - } - void *currnet_ptr = p_arena->buffer + p_arena->offset; - p_arena->offset += size; - return currnet_ptr; + return Dowa_Arena_Allocate_Aligned(p_arena, size, sizeof(void*) * 2); } void Dowa_Arena_Destroy(Dowa_Arena *p_arena) @@ -75,7 +66,576 @@ return p_arena->capacity - p_arena->offset; } -// --- HashMap --- // +void *Dowa_Arena_Allocate_Aligned(Dowa_Arena *p_arena, size_t size, size_t alignment) +{ + if (!p_arena || !p_arena->buffer || size == 0 || alignment == 0) + return NULL; + + size_t current_address = (size_t)(p_arena->buffer + p_arena->offset); + size_t aligned_address = (current_address + alignment - 1) & ~(alignment - 1); + size_t padding = aligned_address - current_address; + + if (p_arena->offset + padding + size > p_arena->capacity) + return NULL; + + p_arena->offset += padding; + void *p_result = p_arena->buffer + p_arena->offset; + p_arena->offset += size; + return p_result; +} + +// --- NEW stb_ds-style Array Implementation --- // + +void* dowa__array_grow(void* p_array, size_t element_size, size_t minimum_capacity, Dowa_Arena* p_arena) +{ + Dowa_Array_Header* p_header; + size_t new_capacity; + size_t current_capacity; + + if (p_array) + { + p_header = dowa__header(p_array); + current_capacity = p_header->capacity; + + if (p_header->allocator_type == DOWA_ALLOCATOR_ARENA && p_header->p_arena != p_arena) + { + fprintf(stderr, "Error: Cannot mix arena allocators\n"); + return p_array; + } + } + else + { + current_capacity = 0; + } + + if (current_capacity >= minimum_capacity && p_array != NULL) + return p_array; + + new_capacity = current_capacity * 2; + if (new_capacity < 4) + new_capacity = 4; + if (new_capacity < minimum_capacity) + new_capacity = minimum_capacity; + + size_t total_size = sizeof(Dowa_Array_Header) + (element_size * new_capacity); + + if (p_arena) + { + // Array header and data must be properly aligned + size_t alignment = element_size >= 16 ? 16 : (element_size >= 8 ? 8 : element_size); + Dowa_Array_Header* p_new_header = (Dowa_Array_Header*)Dowa_Arena_Allocate_Aligned(p_arena, total_size, alignment); + if (!p_new_header) + return p_array; + + void* p_new_array = (char*)p_new_header + sizeof(Dowa_Array_Header); + + if (p_array) + { + memcpy(p_new_array, p_array, element_size * p_header->length); + p_new_header->length = p_header->length; + } + else + { + p_new_header->length = 0; + } + + p_new_header->capacity = new_capacity; + p_new_header->allocator_type = DOWA_ALLOCATOR_ARENA; + p_new_header->p_arena = p_arena; + p_new_header->p_hash = p_array ? p_header->p_hash : NULL; + + return p_new_array; + } + else + { + Dowa_Array_Header* p_new_header; + + if (p_array) + { + p_header = dowa__header(p_array); + p_new_header = (Dowa_Array_Header*)realloc(p_header, total_size); + } + else + { + p_new_header = (Dowa_Array_Header*)malloc(total_size); + if (p_new_header) + p_new_header->length = 0; + } + + if (!p_new_header) + return p_array; + + p_new_header->capacity = new_capacity; + p_new_header->allocator_type = DOWA_ALLOCATOR_MALLOC; + p_new_header->p_arena = NULL; + p_new_header->p_hash = NULL; + + return (char*)p_new_header + sizeof(Dowa_Array_Header); + } +} + +void dowa__array_free(void* p_array) +{ + if (!p_array) + return; + + Dowa_Array_Header* p_header = dowa__header(p_array); + + if (p_header->allocator_type == DOWA_ALLOCATOR_MALLOC) + free(p_header); +} + +// --- NEW stb_ds-style HashMap Implementation --- // + +#define DOWA_HASH_EMPTY 0xFFFFFFFF +#define DOWA_HASH_TOMBSTONE 0xFFFFFFFE + +uint32 dowa__hash_bytes(void* p_key, size_t key_size) +{ + uint32 hash = HASH_KEY_NUMBER; + uint8* p_bytes = (uint8*)p_key; + + for (size_t i = 0; i < key_size; i++) + hash = ((hash << 5) + hash) + p_bytes[i]; + + if (hash == DOWA_HASH_EMPTY || hash == DOWA_HASH_TOMBSTONE) + hash = HASH_KEY_NUMBER; + + return hash; +} + +static Dowa_Hash_Index* dowa__hashmap_get_index(void* p_map) +{ + if (!p_map) + return NULL; + + Dowa_Array_Header* p_header = dowa__header(p_map); + return (Dowa_Hash_Index*)p_header->p_hash; +} + +static void* dowa__hashmap_find_slot(void* p_map, size_t element_size, void* p_key, size_t key_size, uint32 hash, boolean* p_found) +{ + Dowa_Hash_Index* p_index = dowa__hashmap_get_index(p_map); + if (!p_index || !p_index->p_buckets) + { + *p_found = FALSE; + return NULL; + } + + size_t bucket_mask = p_index->bucket_count - 1; + size_t bucket_index = hash & bucket_mask; + size_t probe_step = 0; + + while (1) + { + Dowa_Hash_Bucket* p_bucket = &p_index->p_buckets[bucket_index]; + + for (size_t i = 0; i < DOWA_HASH_BUCKET_SIZE; i++) + { + if (p_bucket->hash[i] == DOWA_HASH_EMPTY) + { + *p_found = FALSE; + return NULL; + } + + if (p_bucket->hash[i] == hash && p_bucket->index[i] != DOWA_HASH_TOMBSTONE) + { + uint32 array_index = p_bucket->index[i]; + char* p_element = (char*)p_map + (array_index * element_size); + + char** p_stored_key_ptr = (char**)p_element; + char* p_stored_key = *p_stored_key_ptr; + char* p_search_key = (char*)p_key; + + if (memcmp(p_stored_key, p_search_key, key_size) == 0) + { + *p_found = TRUE; + return p_element; + } + } + } + + probe_step++; + bucket_index = (hash + (probe_step * probe_step)) & bucket_mask; + + if (probe_step > p_index->bucket_count) + break; + } + + *p_found = FALSE; + return NULL; +} + +void* dowa__hashmap_get_ptr(void* p_map, size_t element_size, void* p_key, size_t key_size) +{ + if (!p_map) + return NULL; + + uint32 hash = dowa__hash_bytes(p_key, key_size); + boolean found = FALSE; + void* p_result = dowa__hashmap_find_slot(p_map, element_size, p_key, key_size, hash, &found); + + return found ? p_result : NULL; +} + +void* dowa__hashmap_get(void* p_map, size_t element_size, void* p_key, size_t key_size) +{ + void* p_kv = dowa__hashmap_get_ptr(p_map, element_size, p_key, key_size); + if (!p_kv) + return NULL; + + return (char*)p_kv + key_size; +} + +boolean dowa__hashmap_has_key(void* p_map, size_t element_size, void* p_key, size_t key_size) +{ + return dowa__hashmap_get_ptr(p_map, element_size, p_key, key_size) != NULL; +} + +static void* dowa__hashmap_rehash(void* p_map, size_t element_size, size_t new_bucket_count, Dowa_Arena* p_arena) +{ + Dowa_Hash_Index* p_old_index = dowa__hashmap_get_index(p_map); + if (!p_old_index) + return p_map; + + size_t bucket_alloc_size = sizeof(Dowa_Hash_Bucket) * new_bucket_count; + Dowa_Hash_Bucket* p_new_buckets; + + if (p_arena) + { + p_new_buckets = (Dowa_Hash_Bucket*)Dowa_Arena_Allocate_Aligned(p_arena, bucket_alloc_size, DOWA_HASH_CACHE_LINE_SIZE); + } + else + { + if (posix_memalign((void**)&p_new_buckets, DOWA_HASH_CACHE_LINE_SIZE, bucket_alloc_size) != 0) + p_new_buckets = NULL; + } + + if (!p_new_buckets) + return p_map; + + for (size_t i = 0; i < new_bucket_count; i++) + { + for (size_t j = 0; j < DOWA_HASH_BUCKET_SIZE; j++) + { + p_new_buckets[i].hash[j] = DOWA_HASH_EMPTY; + p_new_buckets[i].index[j] = DOWA_HASH_EMPTY; + } + } + + Dowa_Hash_Index* p_new_index; + if (p_arena) + p_new_index = (Dowa_Hash_Index*)Dowa_Arena_Allocate_Aligned(p_arena, sizeof(Dowa_Hash_Index), 16); + else + p_new_index = (Dowa_Hash_Index*)malloc(sizeof(Dowa_Hash_Index)); + + if (!p_new_index) + { + if (!p_arena) + free(p_new_buckets); + return p_map; + } + + p_new_index->bucket_count = new_bucket_count; + p_new_index->item_count = 0; + p_new_index->tombstone_count = 0; + p_new_index->allocator_type = p_arena ? DOWA_ALLOCATOR_ARENA : DOWA_ALLOCATOR_MALLOC; + p_new_index->p_arena = p_arena; + p_new_index->p_buckets = p_new_buckets; + + size_t map_length = Dowa_Array_Length(p_map); + for (size_t i = 0; i < map_length; i++) + { + char* p_element = (char*)p_map + (i * element_size); + char** p_key_ptr = (char**)p_element; + char* p_key_data = *p_key_ptr; + uint32 hash = dowa__hash_bytes(p_key_data, strlen(p_key_data) + 1); + + size_t bucket_mask = new_bucket_count - 1; + size_t bucket_index = hash & bucket_mask; + size_t probe_step = 0; + boolean inserted = FALSE; + + while (!inserted && probe_step <= new_bucket_count) + { + Dowa_Hash_Bucket* p_bucket = &p_new_buckets[bucket_index]; + + for (size_t j = 0; j < DOWA_HASH_BUCKET_SIZE; j++) + { + if (p_bucket->hash[j] == DOWA_HASH_EMPTY) + { + p_bucket->hash[j] = hash; + p_bucket->index[j] = (uint32)i; + p_new_index->item_count++; + inserted = TRUE; + break; + } + } + + if (!inserted) + { + probe_step++; + bucket_index = (hash + (probe_step * probe_step)) & bucket_mask; + } + } + } + + if (p_old_index->allocator_type == DOWA_ALLOCATOR_MALLOC) + { + if (p_old_index->p_buckets) + free(p_old_index->p_buckets); + free(p_old_index); + } + + dowa__header(p_map)->p_hash = p_new_index; + return p_map; +} + +void* dowa__hashmap_push(void* p_map, size_t element_size, void* p_key, size_t key_size, Dowa_Arena* p_arena) +{ + uint32 hash = dowa__hash_bytes(p_key, key_size); + + if (p_map) + { + boolean found = FALSE; + dowa__hashmap_find_slot(p_map, element_size, p_key, key_size, hash, &found); + if (found) + return p_map; + } + + p_map = dowa__array_grow(p_map, element_size, 0, p_arena); + + Dowa_Hash_Index* p_index = dowa__hashmap_get_index(p_map); + if (!p_index) + { + size_t initial_bucket_count = 4; + size_t bucket_alloc_size = sizeof(Dowa_Hash_Bucket) * initial_bucket_count; + Dowa_Hash_Bucket* p_buckets; + + if (p_arena) + { + p_buckets = (Dowa_Hash_Bucket*)Dowa_Arena_Allocate_Aligned(p_arena, bucket_alloc_size, DOWA_HASH_CACHE_LINE_SIZE); + } + else + { + if (posix_memalign((void**)&p_buckets, DOWA_HASH_CACHE_LINE_SIZE, bucket_alloc_size) != 0) + p_buckets = NULL; + } + + if (!p_buckets) + return p_map; + + for (size_t i = 0; i < initial_bucket_count; i++) + { + for (size_t j = 0; j < DOWA_HASH_BUCKET_SIZE; j++) + { + p_buckets[i].hash[j] = DOWA_HASH_EMPTY; + p_buckets[i].index[j] = DOWA_HASH_EMPTY; + } + } + + if (p_arena) + p_index = (Dowa_Hash_Index*)Dowa_Arena_Allocate_Aligned(p_arena, sizeof(Dowa_Hash_Index), 16); + else + p_index = (Dowa_Hash_Index*)malloc(sizeof(Dowa_Hash_Index)); + + if (!p_index) + { + if (!p_arena) + free(p_buckets); + return p_map; + } + + p_index->bucket_count = initial_bucket_count; + p_index->item_count = 0; + p_index->tombstone_count = 0; + p_index->allocator_type = p_arena ? DOWA_ALLOCATOR_ARENA : DOWA_ALLOCATOR_MALLOC; + p_index->p_arena = p_arena; + p_index->p_buckets = p_buckets; + + dowa__header(p_map)->p_hash = p_index; + } + + // Rehash when load factor exceeds ~50% (bucket_count * BUCKET_SIZE * 0.5) + // This ensures we rehash before probe chains get too long + if (p_index->item_count + p_index->tombstone_count >= p_index->bucket_count * 4) + p_map = dowa__hashmap_rehash(p_map, element_size, p_index->bucket_count * 2, p_arena); + + p_index = dowa__hashmap_get_index(p_map); + + Dowa_Array_Header* p_header = dowa__header(p_map); + uint32 new_index = (uint32)p_header->length; + char* p_new_element = (char*)p_map + (new_index * element_size); + + char* p_key_copy; + if (p_arena) + p_key_copy = (char*)Dowa_Arena_Allocate(p_arena, key_size); + else + p_key_copy = (char*)malloc(key_size); + + if (!p_key_copy) + return p_map; + + memcpy(p_key_copy, p_key, key_size); + + memcpy(p_new_element, &p_key_copy, sizeof(char*)); + p_header->length++; + + // Try to insert into hash table - if it fails, rehash and retry + boolean inserted = FALSE; + for (int attempt = 0; attempt < 2 && !inserted; attempt++) + { + if (attempt == 1) + { + // First attempt failed - rehash to make more room + p_header->length--; // Undo the array length increment temporarily + p_map = dowa__hashmap_rehash(p_map, element_size, p_index->bucket_count * 2, p_arena); + p_index = dowa__hashmap_get_index(p_map); + p_header = dowa__header(p_map); + + // Restore array state + new_index = (uint32)p_header->length; + p_new_element = (char*)p_map + (new_index * element_size); + memcpy(p_new_element, &p_key_copy, sizeof(char*)); + p_header->length++; + } + + size_t bucket_mask = p_index->bucket_count - 1; + size_t bucket_index = hash & bucket_mask; + size_t probe_step = 0; + + while (!inserted && probe_step <= p_index->bucket_count) + { + Dowa_Hash_Bucket* p_bucket = &p_index->p_buckets[bucket_index]; + + for (size_t i = 0; i < DOWA_HASH_BUCKET_SIZE; i++) + { + if (p_bucket->hash[i] == DOWA_HASH_EMPTY || p_bucket->hash[i] == DOWA_HASH_TOMBSTONE) + { + if (p_bucket->hash[i] == DOWA_HASH_TOMBSTONE) + p_index->tombstone_count--; + + p_bucket->hash[i] = hash; + p_bucket->index[i] = new_index; + p_index->item_count++; + inserted = TRUE; + break; + } + } + + if (!inserted) + { + probe_step++; + bucket_index = (hash + (probe_step * probe_step)) & bucket_mask; + } + } + } + + return p_map; +} + +void dowa__hashmap_delete(void* p_map, size_t element_size, void* p_key, size_t key_size) +{ + if (!p_map) + return; + + Dowa_Hash_Index* p_index = dowa__hashmap_get_index(p_map); + if (!p_index || !p_index->p_buckets) + return; + + uint32 hash = dowa__hash_bytes(p_key, key_size); + size_t bucket_mask = p_index->bucket_count - 1; + size_t bucket_index = hash & bucket_mask; + size_t probe_step = 0; + + while (probe_step <= p_index->bucket_count) + { + Dowa_Hash_Bucket* p_bucket = &p_index->p_buckets[bucket_index]; + + for (size_t i = 0; i < DOWA_HASH_BUCKET_SIZE; i++) + { + if (p_bucket->hash[i] == DOWA_HASH_EMPTY) + return; + + if (p_bucket->hash[i] == hash && p_bucket->index[i] != DOWA_HASH_TOMBSTONE) + { + uint32 array_index = p_bucket->index[i]; + char* p_element = (char*)p_map + (array_index * element_size); + + char** p_stored_key_ptr = (char**)p_element; + char* p_stored_key = *p_stored_key_ptr; + char* p_search_key = (char*)p_key; + + if (memcmp(p_stored_key, p_search_key, key_size) == 0) + { + if (dowa__header(p_map)->allocator_type == DOWA_ALLOCATOR_MALLOC) + free(p_stored_key); + + p_bucket->hash[i] = DOWA_HASH_TOMBSTONE; + p_bucket->index[i] = DOWA_HASH_TOMBSTONE; + p_index->item_count--; + p_index->tombstone_count++; + return; + } + } + } + + probe_step++; + bucket_index = (hash + (probe_step * probe_step)) & bucket_mask; + } +} + +void dowa__hashmap_clear(void* p_map, size_t element_size) +{ + if (!p_map) + return; + + Dowa_Array_Header* p_header = dowa__header(p_map); + p_header->length = 0; + + Dowa_Hash_Index* p_index = dowa__hashmap_get_index(p_map); + if (p_index && p_index->p_buckets) + { + for (size_t i = 0; i < p_index->bucket_count; i++) + { + for (size_t j = 0; j < DOWA_HASH_BUCKET_SIZE; j++) + { + p_index->p_buckets[i].hash[j] = DOWA_HASH_EMPTY; + p_index->p_buckets[i].index[j] = DOWA_HASH_EMPTY; + } + } + p_index->item_count = 0; + p_index->tombstone_count = 0; + } +} + +void dowa__hashmap_free(void* p_map) +{ + if (!p_map) + return; + + Dowa_Hash_Index* p_index = dowa__hashmap_get_index(p_map); + if (p_index && p_index->allocator_type == DOWA_ALLOCATOR_MALLOC) + { + if (p_index->p_buckets) + free(p_index->p_buckets); + free(p_index); + } + + dowa__array_free(p_map); +} + +size_t dowa__hashmap_count(void* p_map) +{ + if (!p_map) + return 0; + + Dowa_Hash_Index* p_index = dowa__hashmap_get_index(p_map); + return p_index ? p_index->item_count : 0; +} + +/* +// --- OLD HashMap Implementation (Commented out for migration) --- // Dowa_HashMap *Dowa_HashMap_Create(size_t capacity) { Dowa_HashMap *p_hash_map; @@ -214,24 +774,6 @@ entry = entry->next; } - // Overriding doesn't really make sense? when copying over - // as we need to free it. - // - //while (entry) - //{ - // if (strcmp(entry->key, key) == 0) - // { - // if (!p_hash_map->p_arena && entry->buffer) - // Dowa_Free(entry->buffer); - // entry->buffer = value; - // entry->capacity = value_size; - // entry->type = type; - // return 0; - // } - // prev = entry; - // entry = entry->next; - //} - // New Key entry = p_hash_map->p_arena ? Dowa_Arena_Allocate(p_hash_map->p_arena, sizeof(Dowa_HashEntry)) : @@ -239,7 +781,7 @@ if (!entry) { perror("malloc or arena alloc"); return -1; } entry->key = p_hash_map->p_arena ? - Dowa_Arena_Copy(p_hash_map->p_arena, key, strlen(key) + 1 /* \0 */) : + Dowa_Arena_Copy(p_hash_map->p_arena, key, strlen(key) + 1) : strdup(key); if (!entry->key) { @@ -301,7 +843,7 @@ if (!entry) { perror("malloc or arena alloc"); return -1; } entry->key = p_hash_map->p_arena ? - Dowa_Arena_Copy(p_hash_map->p_arena, key, strlen(key) + 1 /* \0 */) : + Dowa_Arena_Copy(p_hash_map->p_arena, key, strlen(key) + 1) : strdup(key); if (!entry->key) { perror("strdup"); return -1; } @@ -474,6 +1016,46 @@ printf("-----------\n"); } +// -- Array --// +Dowa_Array *Dowa_Array_Init() +{ + Dowa_Array *dowa_array = malloc(sizeof(Dowa_Array)); + if (dowa_array == NULL) + { + return NULL; + } + + dowa_array->capacity = DOWA_ARRAY_DEFAULT_CAPACITY; + dowa_array->items = (Dowa_Array_Item *)malloc(sizeof(Dowa_Array_Item) * DOWA_ARRAY_DEFAULT_CAPACITY); + if (dowa_array->items == NULL) + { + return NULL; + } + + dowa_array->current_length = 0; + return dowa_array; +} + +// void Dowa_Array_Push_Value(Dowa_Array *dowa_array, void *buffer, uint32 length) +// { +// if (dowa_array->current_length == dowa_array->capacity) +// { +// dowa_array->items = realloc(dowa_array->items, sizeof(Dowa_Array_Item) * dowa_array->capacity * 2); +// dowa_array->capacity = dowa_array->capacity * 2; +// } +// Dowa_Array_Item *item = &(dowa_array->items[dowa_array->current_length]); +// item->value = malloc(length); +// if (item->value == NULL) +// { +// // didn't alloc should raise an error. +// return; +// } +// memcpy(item->value, buffer, length); +// item->length = length; +// dowa_array->current_length += 1; +// } + + #ifdef DIRECTORY int Dowa_HashMap_Cache_Folder(Dowa_HashMap *p_hash_map, const char *folder_path) { @@ -552,3 +1134,4 @@ return 0; } #endif +*/ diff -r 4bc56e88e1f3 -r 75de5903355c dowa/d_string.c --- a/dowa/d_string.c Thu Dec 25 20:10:46 2025 -0800 +++ b/dowa/d_string.c Sun Dec 28 20:34:22 2025 -0800 @@ -17,5 +17,88 @@ return buffer; } +int32 Dowa_String_Pos_Find(const char *from, const char *value, const size_t from_length, const size_t value_length) +{ + if (value == NULL || from == NULL) + return -1; + for (int32 i = 0; i < from_length - value_length; i++) + { + if (from[i] == value[0]) + { + int32 j = 0; + while (j < value_length && value[j] == from[i+j]) + j++; + if (j == value_length) + return i; + } + } + return -1; +} + +char *Dowa_String_Find(const char *from, const char *value, const size_t from_length, const size_t value_length) +{ + if (value == NULL || from == NULL) + return NULL; + + for (int32 i = 0; i < from_length - value_length; i++) + { + if (from[i] == value[0]) + { + int32 j = 0; + while (j < value_length && value[j] == from[i+j]) + j++; + + if (j == value_length) + return &from[i]; + } + } + return NULL; +} + +int32 Dowa_String_Pos_Find_Char(const char *from, int c, int32 from_len) +{ + if (!from || from_len == 0) + return -1; + + for (int32 i = 0; i < from_len; i++) + { + if ((int)from[i] == c) + return i; + } + return -1; +} + +char *Dowa_String_Find_Char(const char *from, int c, int32 from_len) +{ + if (!from || from_len == 0) + return NULL; + + for (int32 i = 0; i < from_len; i++) + { + if ((int)from[i] == c) + return &from[i]; + } + return NULL ; +} + +// char **Dowa_String_Split(char *from, char *split_token, int32 from_length, int32 split_token_length) +// { +// char *current_from = from; +// int32 moved = 0; +// while (1) +// { +// int32 next_token = Dowa_String_Pos_Find( +// current_from, split_token, from_length - moved, split_token_length +// ); +// +// if (next_token == -1) +// { +// break; +// } +// char *curr = malloc(sizeof(char) * next_token); +// while (i < next_token) +// curr[i++] = from[i]; +// } +// } diff -r 4bc56e88e1f3 -r 75de5903355c dowa/dowa.h --- a/dowa/dowa.h Thu Dec 25 20:10:46 2025 -0800 +++ b/dowa/dowa.h Sun Dec 28 20:34:22 2025 -0800 @@ -2,12 +2,13 @@ #define DOWA #include -#include // stdup -#include // only for malloc, free, stuff +#include // strdup, strlen, memcmp, memcpy +#include // malloc, free, realloc #include // mostly for TODO +#include // size_t #ifdef DIRECTORY -// Only for linux and mac since window do not support. +// Only for linux and mac since window do not support. // Maybe move this into seobeo file directly? #include // some functions loop through files #endif @@ -19,10 +20,25 @@ #include "dowa_internal.h" -#define HASH_KEY_NUMBER 5381 // DJD hash number +// DLAPI macro for DLL export/import +#ifndef DLAPI + #ifdef _WIN32 + #ifdef DOWA_EXPORTS + #define DLAPI __declspec(dllexport) + #else + #define DLAPI __declspec(dllimport) + #endif + #else + #define DLAPI extern + #endif +#endif + +#define HASH_KEY_NUMBER 5381 #define ONE_MEGA_BYTE 1048576 #define TRUE 1 #define FALSE 0 +#define DOWA_HASH_BUCKET_SIZE 8 +#define DOWA_HASH_CACHE_LINE_SIZE 64 #define Dowa_Free(p) do { \ if (p) { \ @@ -32,13 +48,13 @@ } while (0) // Fixed-width integer types -typedef unsigned int uint32; // 32-bit unsigned integer -typedef int int32; // 32-bit signed integer -typedef unsigned short uint16; // 16-bit unsigned integer -typedef short int16; // 16-bit signed integer -typedef unsigned char uint8; // 8-bit unsigned integer -typedef char int8; // 8-bit signed integer -typedef char boolean; // Boolean type (0 = false, nonzero = true) +typedef unsigned int uint32; +typedef int int32; +typedef unsigned short uint16; +typedef short int16; +typedef unsigned char uint8; +typedef char int8; +typedef char boolean; // --- Arena Allocator --- // typedef struct { @@ -47,28 +63,164 @@ size_t capacity; } Dowa_Arena; -/* Creates a new arena with the specified capacity (in bytes). Returns a pointer to the arena, or NULL on failure. */ -extern Dowa_Arena *Dowa_Arena_Create(size_t capacity); -/* Allocates a block of memory of the given size from the arena. Returns pointer to the allocated memory, or NULL if there is insufficient space. */ -extern void *Dowa_Arena_Allocate(Dowa_Arena *arena, size_t size); -/* Destroys the arena and frees its underlying memory block.*/ -extern void Dowa_Arena_Destroy(Dowa_Arena *arena); -/* Strdup but saves within the arena */ -extern void *Dowa_Arena_Copy(Dowa_Arena *p_arena, const void *src, size_t size); -/* Resets the arena offset to 0, allowing reuse without freeing */ -extern void Dowa_Arena_Reset(Dowa_Arena *p_arena); -/* Returns the current number of bytes allocated in the arena */ -extern size_t Dowa_Arena_Get_Used(Dowa_Arena *p_arena); -/* Returns the remaining capacity in bytes */ -extern size_t Dowa_Arena_Get_Remaining(Dowa_Arena *p_arena); +DLAPI Dowa_Arena *Dowa_Arena_Create(size_t capacity); +DLAPI void *Dowa_Arena_Allocate(Dowa_Arena *p_arena, size_t size); +DLAPI void *Dowa_Arena_Allocate_Aligned(Dowa_Arena *p_arena, size_t size, size_t alignment); +DLAPI void Dowa_Arena_Destroy(Dowa_Arena *p_arena); +DLAPI void *Dowa_Arena_Copy(Dowa_Arena *p_arena, const void *p_src, size_t size); +DLAPI void Dowa_Arena_Reset(Dowa_Arena *p_arena); +DLAPI size_t Dowa_Arena_Get_Used(Dowa_Arena *p_arena); +DLAPI size_t Dowa_Arena_Get_Remaining(Dowa_Arena *p_arena); + +// --- New stb_ds-style Data Structures --- // + +// Allocator type enum +typedef enum { + DOWA_ALLOCATOR_MALLOC = 0, + DOWA_ALLOCATOR_ARENA = 1 +} Dowa_Allocator_Type; + +// Array header (prefix to actual array data) +typedef struct { + size_t length; + size_t capacity; + uint8 allocator_type; + Dowa_Arena* p_arena; + void* p_hash; +} Dowa_Array_Header; + +// Hash bucket (64 bytes for cache line alignment) +typedef struct { + uint32 hash[DOWA_HASH_BUCKET_SIZE]; + uint32 index[DOWA_HASH_BUCKET_SIZE]; +} Dowa_Hash_Bucket; + +// Hash index structure (separate from value array) +typedef struct { + size_t bucket_count; + size_t item_count; + size_t tombstone_count; + uint8 allocator_type; + Dowa_Arena* p_arena; + Dowa_Hash_Bucket* p_buckets; +} Dowa_Hash_Index; + +// Key-Value pair declaration macro +#define Dowa_KV(K, V) struct { K key; V value; } + +// Internal header accessor +#define dowa__header(a) ((Dowa_Array_Header*)(a) - 1) + +// --- Array Macros --- // + +#define Dowa_Array_Length(a) ((a) ? dowa__header(a)->length : 0) +#define Dowa_Array_Capacity(a) ((a) ? dowa__header(a)->capacity : 0) + +#define Dowa_Array_Push(a, v) \ + ((a) = dowa__array_grow((a), sizeof(*(a)), 0, NULL), \ + (a)[dowa__header(a)->length++] = (v)) + +#define Dowa_Array_Push_Arena(a, v, arena) \ + ((a) = dowa__array_grow((a), sizeof(*(a)), 0, (arena)), \ + (a)[dowa__header(a)->length++] = (v)) + +#define Dowa_Array_Pop(a) ((a)[--dowa__header(a)->length]) + +#define Dowa_Array_Clear(a) ((a) ? (dowa__header(a)->length = 0) : 0) + +#define Dowa_Array_Free(a) ((a) ? (dowa__array_free((a)), (a) = NULL) : 0) + +#define Dowa_Array_Reserve(a, n) \ + ((a) = dowa__array_grow((a), sizeof(*(a)), (n), NULL)) + +#define Dowa_Array_Reserve_Arena(a, n, arena) \ + ((a) = dowa__array_grow((a), sizeof(*(a)), (n), (arena))) + +// --- HashMap Macros --- // + +#define Dowa_HashMap_Get(m, k) \ + dowa__hashmap_get((m), sizeof(*(m)), (k), strlen(k) + 1) + +#define Dowa_HashMap_Get_Ptr(m, k) \ + dowa__hashmap_get_ptr((m), sizeof(*(m)), (k), strlen(k) + 1) + +#define Dowa_HashMap_Push(m, k, v) \ + do { \ + (m) = dowa__hashmap_push((m), sizeof(*(m)), (k), strlen(k) + 1, NULL); \ + void* p_kv_temp = dowa__hashmap_get_ptr((m), sizeof(*(m)), (k), strlen(k) + 1); \ + if (p_kv_temp) \ + ((typeof(m))p_kv_temp)->value = (v); \ + } while (0) + +#define Dowa_HashMap_Push_Arena(m, k, v, arena) \ + do { \ + (m) = dowa__hashmap_push((m), sizeof(*(m)), (k), strlen(k) + 1, (arena)); \ + void* p_kv_temp = dowa__hashmap_get_ptr((m), sizeof(*(m)), (k), strlen(k) + 1); \ + if (p_kv_temp) \ + ((typeof(m))p_kv_temp)->value = (v); \ + } while (0) + +#define Dowa_HashMap_Has_Key(m, k) \ + dowa__hashmap_has_key((m), sizeof(*(m)), (k), strlen(k) + 1) + +#define Dowa_HashMap_Delete(m, k) \ + dowa__hashmap_delete((m), sizeof(*(m)), (k), strlen(k) + 1) + +#define Dowa_HashMap_Clear(m) dowa__hashmap_clear((m), sizeof(*(m))) + +#define Dowa_HashMap_Free(m) ((m) ? (dowa__hashmap_free((m)), (m) = NULL) : 0) + +#define Dowa_HashMap_Count(m) dowa__hashmap_count(m) + +#define Dowa_HashMap_Get_Binary(m, k, ksize) \ + dowa__hashmap_get((m), sizeof(*(m)), (k), (ksize)) + +#define Dowa_HashMap_Get_Ptr_Binary(m, k, ksize) \ + dowa__hashmap_get_ptr((m), sizeof(*(m)), (k), (ksize)) + +#define Dowa_HashMap_Push_Binary(m, k, ksize, v) \ + do { \ + (m) = dowa__hashmap_push((m), sizeof(*(m)), (k), (ksize), NULL); \ + void* p_kv_temp = dowa__hashmap_get_ptr((m), sizeof(*(m)), (k), (ksize)); \ + if (p_kv_temp) \ + ((typeof(m))p_kv_temp)->value = (v); \ + } while (0) + +#define Dowa_HashMap_Push_Binary_Arena(m, k, ksize, v, arena) \ + do { \ + (m) = dowa__hashmap_push((m), sizeof(*(m)), (k), (ksize), (arena)); \ + void* p_kv_temp = dowa__hashmap_get_ptr((m), sizeof(*(m)), (k), (ksize)); \ + if (p_kv_temp) \ + ((typeof(m))p_kv_temp)->value = (v); \ + } while (0) + +// --- Array Core Functions --- // + +DLAPI void* dowa__array_grow(void* p_array, size_t element_size, size_t minimum_capacity, Dowa_Arena* p_arena); +DLAPI void dowa__array_free(void* p_array); + +// --- HashMap Core Functions --- // + +DLAPI uint32 dowa__hash_bytes(void* p_key, size_t key_size); +DLAPI void* dowa__hashmap_get(void* p_map, size_t element_size, void* p_key, size_t key_size); +DLAPI void* dowa__hashmap_get_ptr(void* p_map, size_t element_size, void* p_key, size_t key_size); +DLAPI void* dowa__hashmap_push(void* p_map, size_t element_size, void* p_key, size_t key_size, Dowa_Arena* p_arena); +DLAPI boolean dowa__hashmap_has_key(void* p_map, size_t element_size, void* p_key, size_t key_size); +DLAPI void dowa__hashmap_delete(void* p_map, size_t element_size, void* p_key, size_t key_size); +DLAPI void dowa__hashmap_clear(void* p_map, size_t element_size); +DLAPI void dowa__hashmap_free(void* p_map); +DLAPI size_t dowa__hashmap_count(void* p_map); + +// --- OLD API (kept for reference, will be removed after migration) --- // +/* -// --- HashMap --- // +OLD HashMap API - Commented out for migration typedef enum { - DOWA_HASH_MAP_TYPE_BUFFER, // Raw byte buffer - DOWA_HASH_MAP_TYPE_STRING, // Null-terminated string - DOWA_HASH_MAP_TYPE_HASHMAP, // Nested hashmap - DOWA_HASH_MAP_TYPE_INT // Integer value + DOWA_HASH_MAP_TYPE_BUFFER, + DOWA_HASH_MAP_TYPE_STRING, + DOWA_HASH_MAP_TYPE_HASHMAP, + DOWA_HASH_MAP_TYPE_INT } Dowa_HashMap_ValueType; typedef struct Dowa_HashEntry { @@ -76,7 +228,7 @@ void *buffer; size_t capacity; Dowa_HashMap_ValueType type; - struct Dowa_HashEntry *next; + struct Dowa_HashEntry *next; } Dowa_HashEntry; typedef struct { @@ -86,44 +238,49 @@ Dowa_Arena *p_arena; } Dowa_HashMap; -/* Creates a new hashmap with the given initial capacity. Returns pointer to the hashmap, or NULL on failure. */ extern Dowa_HashMap *Dowa_HashMap_Create(size_t capacity); -/* Creates a new hashmap with the given initial capacity, using the provided arena for all internal allocations. Returns pointer to the hashmap, or NULL on failure. */ extern Dowa_HashMap *Dowa_HashMap_Create_With_Arena(size_t capacity, Dowa_Arena *arena); -/* Destroys the hashmap and frees all associated memory */ extern void Dowa_HashMap_Destroy(Dowa_HashMap *p_hash_map); -/* Returns the index of the entry for the specified key, or -1 if the key is not found. */ extern int32 Dowa_HashMap_Get_Position(Dowa_HashMap *p_hash_map, const char *key); -/* Retrieves the value buffer for the specified key, or NULL if the key does not exist. */ extern void *Dowa_HashMap_Get(Dowa_HashMap *p_hash_map, const char *key); -/* Inserts a copy of the given value into the hashmap under the specified key. Uses DOWA_HASH_MAP_TYPE_BUFFER as the entry type. */ extern void Dowa_HashMap_Push_Value(Dowa_HashMap *p_hash_map, const char *key, void *value, size_t value_size); -/* Inserts a copy of the given value with the specified type into the hashmap under the key. Returns the index of the new entry, or -1 on failure. */ extern int32 Dowa_HashMap_Push_Value_With_Type(Dowa_HashMap *p_hash_map, const char *key, void *value, size_t value_size, Dowa_HashMap_ValueType type); -/* Inserts a value pointer into the hashmap under the specified key without copying data. The caller retains ownership of the pointer. Returns the entry index, or -1 on failure. */ extern int32 Dowa_HashMap_Push_Value_With_Type_NoCopy(Dowa_HashMap *p_hash_map, const char *key, void *value, size_t value_size, Dowa_HashMap_ValueType type); -/* Removes the entry with the specified key from the hashmap and frees its data if owned. */ extern void Dowa_HashMap_Pop_Key(Dowa_HashMap *p_hash_map, const char *key); -/* Returns TRUE if the key exists in the hashmap, FALSE otherwise. */ extern boolean Dowa_HashMap_Has_Key(Dowa_HashMap *p_hash_map, const char *key); -/* Removes all entries from the hashmap without destroying it. */ extern void Dowa_HashMap_Clear(Dowa_HashMap *p_hash_map); -/* Returns the number of entries currently in the hashmap. */ extern uint32 Dowa_HashMap_Get_Count(Dowa_HashMap *p_hash_map); -// --- String manipuliation -- // -// Splice string from start to end -const char *Dowa_String_Slice(const char *from, size_t start, size_t end); -// --- Miscellaneous --- // -char *Dowa_Int32ToString(uint32 value, char *buffer); /* Just use atoid lmao*/ +OLD Array API - Commented out for migration +#define DOWA_ARRAY_DEFAULT_CAPACITY 256 + +typedef struct { + void *value; + uint32 length; +} Dowa_Array_Item; + +typedef struct { + uint32 capacity; + uint32 current_length; + Dowa_Array_Item *items; +} Dowa_Array; -// --- Utility Functions --- // -/* Prints all entries in the hashmap to stdout for debugging purposes. */ -extern void Dowa_HashMap_Print(Dowa_HashMap *map); -#ifdef DIRECTORY -/* Loads all files from the specified folder into the hashmap. Uses file names as keys and file contents as values. Returns 0 on success, or -1 on failure. */ -extern int Dowa_HashMap_Cache_Folder(Dowa_HashMap *map, const char *folder_path); -#endif +#define Dowa_Array_Push_Value(dowa_array, buffer, length) ... +Dowa_Array *Dowa_Array_Init(); + +OLD Utility Functions - Will be migrated +extern void Dowa_HashMap_Print(Dowa_HashMap *map); +extern int Dowa_HashMap_Cache_Folder(Dowa_HashMap *map, const char *folder_path); +*/ + +// --- String Manipulation --- // + +DLAPI const char *Dowa_String_Slice(const char *p_from, size_t start, size_t end); +DLAPI int32 Dowa_String_Pos_Find(const char *p_from, const char *p_value, const size_t from_length, const size_t value_length); +DLAPI char *Dowa_String_Find(const char *p_from, const char *p_value, const size_t from_length, const size_t value_length); +DLAPI int32 Dowa_String_Pos_Find_Char(const char *p_from, int c, int32 from_len); +DLAPI char *Dowa_String_Find_Char(const char *p_from, int c, int32 from_len); +DLAPI char *Dowa_Int32ToString(uint32 value, char *p_buffer); #endif diff -r 4bc56e88e1f3 -r 75de5903355c dowa/dowa_test.c --- a/dowa/dowa_test.c Thu Dec 25 20:10:46 2025 -0800 +++ b/dowa/dowa_test.c Sun Dec 28 20:34:22 2025 -0800 @@ -7,116 +7,211 @@ int main(void) { - // --- Test Arena Allocator --- - Dowa_Arena *arena = Dowa_Arena_Create(64); - assert(arena && "Arena creation failed"); + printf("=== Testing NEW dowa API (stb_ds style) ===\n\n"); - char *arena_mem1 = (char *)Dowa_Arena_Allocate(arena, 16); - assert(arena_mem1 && "Arena allocation #1 failed"); - strcpy(arena_mem1, "hello arena"); - printf("[Arena Allocate] mem1 = \"%s\"\n", arena_mem1); + // --- Test Arena Allocator --- + printf("Testing Arena Allocator...\n"); + Dowa_Arena *p_arena = Dowa_Arena_Create(64); + assert(p_arena && "Arena creation failed"); - char *arena_mem2 = (char *)Dowa_Arena_Allocate(arena, 8); - assert(arena_mem2 && "Arena allocation #2 failed"); - strcpy(arena_mem2, "data"); - printf("[Arena Allocate] mem2 = \"%s\"\n", arena_mem2); + char *p_arena_mem1 = (char *)Dowa_Arena_Allocate(p_arena, 16); + assert(p_arena_mem1 && "Arena allocation #1 failed"); + strcpy(p_arena_mem1, "hello arena"); + printf(" [Arena Allocate] mem1 = \"%s\"\n", p_arena_mem1); - Dowa_Arena_Destroy(arena); - printf("[Arena] destroyed\n\n"); + char *p_arena_mem2 = (char *)Dowa_Arena_Allocate(p_arena, 8); + assert(p_arena_mem2 && "Arena allocation #2 failed"); + strcpy(p_arena_mem2, "data"); + printf(" [Arena Allocate] mem2 = \"%s\"\n", p_arena_mem2); - // --- Test HashMap Basic Operations --- - Dowa_HashMap *map = Dowa_HashMap_Create(8); - assert(map && "HashMap_Create failed"); + Dowa_Arena_Destroy(p_arena); + printf(" [Arena] destroyed\n\n"); - // Push raw buffer (default type: BUFFER) - const char raw_buf[] = {0x01, 0x02, 0x03, 0x04}; - Dowa_HashMap_Push_Value(map, "raw", raw_buf, sizeof(raw_buf)); + // --- Test Array Operations --- + printf("Testing Array Operations...\n"); + int32* p_numbers = NULL; - // Push string with explicit STRING type - const char *hello = "hello, world"; - Dowa_HashMap_Push_Value_With_Type(map, "greeting", hello, strlen(hello) + 1, DOWA_HASH_MAP_TYPE_STRING); + Dowa_Array_Push(p_numbers, 10); + Dowa_Array_Push(p_numbers, 20); + Dowa_Array_Push(p_numbers, 30); + Dowa_Array_Push(p_numbers, 40); - // Push nested hashmap (no copy) - Dowa_HashMap *inner = Dowa_HashMap_Create(4); - Dowa_HashMap_Push_Value(inner, "inner_key", "inner_val", strlen("inner_val") + 1); - Dowa_HashMap_Push_Value_With_Type_NoCopy(map, "nested", inner, sizeof(inner), DOWA_HASH_MAP_TYPE_HASHMAP); + printf(" Array length: %zu\n", Dowa_Array_Length(p_numbers)); + printf(" Array capacity: %zu\n", Dowa_Array_Capacity(p_numbers)); + printf(" Array contents:"); + for (size_t i = 0; i < Dowa_Array_Length(p_numbers); i++) + printf(" %d", p_numbers[i]); + printf("\n"); + + int32 popped = Dowa_Array_Pop(p_numbers); + printf(" Popped value: %d\n", popped); + printf(" Array length after pop: %zu\n", Dowa_Array_Length(p_numbers)); + + Dowa_Array_Clear(p_numbers); + printf(" Array length after clear: %zu\n", Dowa_Array_Length(p_numbers)); - // Push integer with INT type - int32 number = 42; - Dowa_HashMap_Push_Value_With_Type(map, "answer", &number, sizeof(number), DOWA_HASH_MAP_TYPE_INT); + Dowa_Array_Free(p_numbers); + printf(" Array freed\n\n"); + + // --- Test HashMap Basic Operations (String Keys) --- + printf("Testing HashMap with String Keys...\n"); + Dowa_KV(char*, char*)* p_map = NULL; - // Print full map - printf("=== Map After Inserts ===\n"); - Dowa_HashMap_Print(map); + Dowa_HashMap_Push(p_map, "name", "John"); + Dowa_HashMap_Push(p_map, "city", "New York"); + Dowa_HashMap_Push(p_map, "country", "USA"); - // Retrieve and validate values + printf(" HashMap count: %zu\n", Dowa_HashMap_Count(p_map)); + + void* p_kv = Dowa_HashMap_Get_Ptr(p_map, "name"); + if (p_kv) { - // raw buffer - uint8 *r = Dowa_HashMap_Get(map, "raw"); - printf("[Get raw] bytes:"); - for (size_t i = 0; i < sizeof(raw_buf); ++i) { - printf(" %02X", r[i]); - } - printf("\n"); + Dowa_KV(char*, char*)* p_pair = (Dowa_KV(char*, char*)*)p_kv; + printf(" HashMap['name']: %s\n", p_pair->value); + } - // greeting - char *g = Dowa_HashMap_Get(map, "greeting"); - printf("[Get greeting] \"%s\"\n", g); - - // nested hashmap - Dowa_HashMap *ni = Dowa_HashMap_Get(map, "nested"); - printf("[Get nested] Inner map contents:\n"); - Dowa_HashMap_Print(ni); - - // answer - int32 *ans = Dowa_HashMap_Get(map, "answer"); - printf("[Get answer] %d\n", *ans); + p_kv = Dowa_HashMap_Get_Ptr(p_map, "city"); + if (p_kv) + { + Dowa_KV(char*, char*)* p_pair = (Dowa_KV(char*, char*)*)p_kv; + printf(" HashMap['city']: %s\n", p_pair->value); } - // Test Get_Position - printf("[Get_Position] 'greeting' at index %d\n", - Dowa_HashMap_Get_Position(map, "greeting")); - printf("[Get_Position] 'missing' at index %d\n", - Dowa_HashMap_Get_Position(map, "missing")); + boolean has_name = Dowa_HashMap_Has_Key(p_map, "name"); + printf(" Has key 'name': %d\n", has_name); + + boolean has_missing = Dowa_HashMap_Has_Key(p_map, "missing"); + printf(" Has key 'missing': %d\n", has_missing); + + printf(" Iterating over HashMap:\n"); + size_t map_length = Dowa_Array_Length(p_map); + for (size_t i = 0; i < map_length; i++) + printf(" [%zu] '%s' => '%s'\n", i, p_map[i].key, p_map[i].value); + + Dowa_HashMap_Delete(p_map, "city"); + printf(" After deleting 'city', count: %zu\n", Dowa_HashMap_Count(p_map)); + + Dowa_HashMap_Clear(p_map); + printf(" After clear, count: %zu\n", Dowa_HashMap_Count(p_map)); + + Dowa_HashMap_Free(p_map); + printf(" HashMap freed\n\n"); + + // --- Test HashMap with Int Keys (Binary) --- + printf("Testing HashMap with Int Keys...\n"); + Dowa_KV(int32, char*)* p_int_map = NULL; + + int32 key1 = 1; + int32 key2 = 2; + int32 key3 = 3; - // Pop a key - Dowa_HashMap_Pop_Key(map, "raw"); - printf("=== Map After Pop 'raw' ===\n"); - Dowa_HashMap_Print(map); + Dowa_HashMap_Push_Binary(p_int_map, &key1, sizeof(int32), "one"); + Dowa_HashMap_Push_Binary(p_int_map, &key2, sizeof(int32), "two"); + Dowa_HashMap_Push_Binary(p_int_map, &key3, sizeof(int32), "three"); + + printf(" Int map count: %zu\n", Dowa_HashMap_Count(p_int_map)); + + p_kv = Dowa_HashMap_Get_Ptr_Binary(p_int_map, &key1, sizeof(int32)); + if (p_kv) + { + Dowa_KV(int32, char*)* p_pair = (Dowa_KV(int32, char*)*)p_kv; + printf(" Int map[1]: '%s'\n", p_pair->value); + } + + p_kv = Dowa_HashMap_Get_Ptr_Binary(p_int_map, &key2, sizeof(int32)); + if (p_kv) + { + Dowa_KV(int32, char*)* p_pair = (Dowa_KV(int32, char*)*)p_kv; + printf(" Int map[2]: '%s'\n", p_pair->value); + } + + printf(" Iterating over Int HashMap:\n"); + map_length = Dowa_Array_Length(p_int_map); + for (size_t i = 0; i < map_length; i++) + printf(" [%zu] %d => '%s'\n", i, p_int_map[i].key, p_int_map[i].value); + + Dowa_HashMap_Free(p_int_map); + printf(" Int map freed\n\n"); // --- Test HashMap with Arena --- - Dowa_Arena *mapArena = Dowa_Arena_Create(256); - Dowa_HashMap *map2 = Dowa_HashMap_Create_With_Arena(8, mapArena); - assert(map2 && "HashMap_Create_With_Arena failed"); - char *test = "bar"; + printf("Testing HashMap with Arena...\n"); + Dowa_Arena *p_map_arena = Dowa_Arena_Create(1024); + Dowa_KV(char*, int32) *p_arena_map = NULL; - Dowa_HashMap_Push_Value_With_Type(map2, "foo", test, 4, DOWA_HASH_MAP_TYPE_STRING); - Dowa_HashMap_Push_Value_With_Type(map2, "num", &number, sizeof(number), DOWA_HASH_MAP_TYPE_INT); + Dowa_HashMap_Push_Arena(p_arena_map, "x", 100, p_map_arena); + Dowa_HashMap_Push_Arena(p_arena_map, "y", 200, p_map_arena); + Dowa_HashMap_Push_Arena(p_arena_map, "z", 300, p_map_arena); - printf("=== Map2 (with arena) ===\n"); - Dowa_HashMap_Print(map2); + printf(" Arena map count: %zu\n", Dowa_HashMap_Count(p_arena_map)); - Dowa_HashMap_Destroy(map2); - printf("[Map2] destroyed (no change)\n\n"); - Dowa_Arena_Destroy(mapArena); - printf("[Arena] destroyed (all null)\n\n"); + p_kv = Dowa_HashMap_Get_Ptr(p_arena_map, "x"); + if (p_kv) + { + Dowa_KV(char*, int32)* p_pair = (Dowa_KV(char*, int32)*)p_kv; + printf(" Arena map['x']: %d\n", p_pair->value); + } - // --- Test Cache_Folder --- - // Ensure there is a directory "./dowa/test_folder" with some files for this test to succeed. - int cache_result = Dowa_HashMap_Cache_Folder(map, "dowa/test_folder"); - printf("[Cache_Folder] returned %d\n", cache_result); - if (cache_result == 0) + p_kv = Dowa_HashMap_Get_Ptr(p_arena_map, "y"); + if (p_kv) { - printf("=== Map After Caching 'dowa/test_folder' ===\n"); - Dowa_HashMap_Print(map); - }else - { - printf("Cache_Folder failed (ensure 'dowa/test_folder' exists with files)\n"); + Dowa_KV(char*, int32)* p_pair = (Dowa_KV(char*, int32)*)p_kv; + printf(" Arena map['y']: %d\n", p_pair->value); } - // Cleanup - Dowa_HashMap_Destroy(map); - printf("[Map] destroyed\n"); + printf(" Iterating over Arena HashMap:\n"); + map_length = Dowa_Array_Length(p_arena_map); + for (size_t i = 0; i < map_length; i++) + printf(" [%zu] '%s' => %d\n", i, p_arena_map[i].key, p_arena_map[i].value); + + Dowa_Arena_Destroy(p_map_arena); + printf(" Arena destroyed (including map)\n\n"); + + // --- Test Array with Arena --- + printf("Testing Array with Arena...\n"); + Dowa_Arena *p_array_arena = Dowa_Arena_Create(1024); + int32* p_arena_numbers = NULL; + + Dowa_Array_Push_Arena(p_arena_numbers, 5, p_array_arena); + Dowa_Array_Push_Arena(p_arena_numbers, 10, p_array_arena); + Dowa_Array_Push_Arena(p_arena_numbers, 15, p_array_arena); + + printf(" Arena array length: %zu\n", Dowa_Array_Length(p_arena_numbers)); + printf(" Arena array contents:"); + for (size_t i = 0; i < Dowa_Array_Length(p_arena_numbers); i++) + printf(" %d", p_arena_numbers[i]); + printf("\n"); + + Dowa_Arena_Destroy(p_array_arena); + printf(" Arena destroyed (including array)\n\n"); + // --- Test Medium HashMap (Stress Test) --- + printf("Testing Medium HashMap (Stress Test)...\n"); + Dowa_KV(char*, int32)* p_large_map = NULL; + + char key_buffer[32]; + for (int32 i = 0; i < 100; i++) + { + sprintf(key_buffer, "key_%d", i); + Dowa_HashMap_Push(p_large_map, key_buffer, i * 10); + } + + printf(" Medium map count: %zu\n", Dowa_HashMap_Count(p_large_map)); + + sprintf(key_buffer, "key_50"); + p_kv = Dowa_HashMap_Get_Ptr(p_large_map, key_buffer); + if (p_kv) + { + Dowa_KV(char*, int32)* p_pair = (Dowa_KV(char*, int32)*)p_kv; + printf(" Medium map['key_50']: %d\n", p_pair->value); + } + + sprintf(key_buffer, "key_99"); + boolean has_99 = Dowa_HashMap_Has_Key(p_large_map, key_buffer); + printf(" Has key 'key_99': %d\n", has_99); + + Dowa_HashMap_Free(p_large_map); + printf(" Medium map freed\n\n"); + + printf("=== All tests passed! ===\n"); return 0; } diff -r 4bc56e88e1f3 -r 75de5903355c dowa/stb_ds.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/dowa/stb_ds.h Sun Dec 28 20:34:22 2025 -0800 @@ -0,0 +1,1895 @@ +/* stb_ds.h - v0.67 - public domain data structures - Sean Barrett 2019 + + This is a single-header-file library that provides easy-to-use + dynamic arrays and hash tables for C (also works in C++). + + For a gentle introduction: + http://nothings.org/stb_ds + + To use this library, do this in *one* C or C++ file: + #define STB_DS_IMPLEMENTATION + #include "stb_ds.h" + +TABLE OF CONTENTS + + Table of Contents + Compile-time options + License + Documentation + Notes + Notes - Dynamic arrays + Notes - Hash maps + Credits + +COMPILE-TIME OPTIONS + + #define STBDS_NO_SHORT_NAMES + + This flag needs to be set globally. + + By default stb_ds exposes shorter function names that are not qualified + with the "stbds_" prefix. If these names conflict with the names in your + code, define this flag. + + #define STBDS_SIPHASH_2_4 + + This flag only needs to be set in the file containing #define STB_DS_IMPLEMENTATION. + + By default stb_ds.h hashes using a weaker variant of SipHash and a custom hash for + 4- and 8-byte keys. On 64-bit platforms, you can define the above flag to force + stb_ds.h to use specification-compliant SipHash-2-4 for all keys. Doing so makes + hash table insertion about 20% slower on 4- and 8-byte keys, 5% slower on + 64-byte keys, and 10% slower on 256-byte keys on my test computer. + + #define STBDS_REALLOC(context,ptr,size) better_realloc + #define STBDS_FREE(context,ptr) better_free + + These defines only need to be set in the file containing #define STB_DS_IMPLEMENTATION. + + By default stb_ds uses stdlib realloc() and free() for memory management. You can + substitute your own functions instead by defining these symbols. You must either + define both, or neither. Note that at the moment, 'context' will always be NULL. + @TODO add an array/hash initialization function that takes a memory context pointer. + + #define STBDS_UNIT_TESTS + + Defines a function stbds_unit_tests() that checks the functioning of the data structures. + + Note that on older versions of gcc (e.g. 5.x.x) you may need to build with '-std=c++0x' + (or equivalentally '-std=c++11') when using anonymous structures as seen on the web + page or in STBDS_UNIT_TESTS. + +LICENSE + + Placed in the public domain and also MIT licensed. + See end of file for detailed license information. + +DOCUMENTATION + + Dynamic Arrays + + Non-function interface: + + Declare an empty dynamic array of type T + T* foo = NULL; + + Access the i'th item of a dynamic array 'foo' of type T, T* foo: + foo[i] + + Functions (actually macros) + + arrfree: + void arrfree(T*); + Frees the array. + + arrlen: + ptrdiff_t arrlen(T*); + Returns the number of elements in the array. + + arrlenu: + size_t arrlenu(T*); + Returns the number of elements in the array as an unsigned type. + + arrpop: + T arrpop(T* a) + Removes the final element of the array and returns it. + + arrput: + T arrput(T* a, T b); + Appends the item b to the end of array a. Returns b. + + arrins: + T arrins(T* a, int p, T b); + Inserts the item b into the middle of array a, into a[p], + moving the rest of the array over. Returns b. + + arrinsn: + void arrinsn(T* a, int p, int n); + Inserts n uninitialized items into array a starting at a[p], + moving the rest of the array over. + + arraddnptr: + T* arraddnptr(T* a, int n) + Appends n uninitialized items onto array at the end. + Returns a pointer to the first uninitialized item added. + + arraddnindex: + size_t arraddnindex(T* a, int n) + Appends n uninitialized items onto array at the end. + Returns the index of the first uninitialized item added. + + arrdel: + void arrdel(T* a, int p); + Deletes the element at a[p], moving the rest of the array over. + + arrdeln: + void arrdeln(T* a, int p, int n); + Deletes n elements starting at a[p], moving the rest of the array over. + + arrdelswap: + void arrdelswap(T* a, int p); + Deletes the element at a[p], replacing it with the element from + the end of the array. O(1) performance. + + arrsetlen: + void arrsetlen(T* a, int n); + Changes the length of the array to n. Allocates uninitialized + slots at the end if necessary. + + arrsetcap: + size_t arrsetcap(T* a, int n); + Sets the length of allocated storage to at least n. It will not + change the length of the array. + + arrcap: + size_t arrcap(T* a); + Returns the number of total elements the array can contain without + needing to be reallocated. + + Hash maps & String hash maps + + Given T is a structure type: struct { TK key; TV value; }. Note that some + functions do not require TV value and can have other fields. For string + hash maps, TK must be 'char *'. + + Special interface: + + stbds_rand_seed: + void stbds_rand_seed(size_t seed); + For security against adversarially chosen data, you should seed the + library with a strong random number. Or at least seed it with time(). + + stbds_hash_string: + size_t stbds_hash_string(char *str, size_t seed); + Returns a hash value for a string. + + stbds_hash_bytes: + size_t stbds_hash_bytes(void *p, size_t len, size_t seed); + These functions hash an arbitrary number of bytes. The function + uses a custom hash for 4- and 8-byte data, and a weakened version + of SipHash for everything else. On 64-bit platforms you can get + specification-compliant SipHash-2-4 on all data by defining + STBDS_SIPHASH_2_4, at a significant cost in speed. + + Non-function interface: + + Declare an empty hash map of type T + T* foo = NULL; + + Access the i'th entry in a hash table T* foo: + foo[i] + + Function interface (actually macros): + + hmfree + shfree + void hmfree(T*); + void shfree(T*); + Frees the hashmap and sets the pointer to NULL. + + hmlen + shlen + ptrdiff_t hmlen(T*) + ptrdiff_t shlen(T*) + Returns the number of elements in the hashmap. + + hmlenu + shlenu + size_t hmlenu(T*) + size_t shlenu(T*) + Returns the number of elements in the hashmap. + + hmgeti + shgeti + hmgeti_ts + ptrdiff_t hmgeti(T*, TK key) + ptrdiff_t shgeti(T*, char* key) + ptrdiff_t hmgeti_ts(T*, TK key, ptrdiff_t tempvar) + Returns the index in the hashmap which has the key 'key', or -1 + if the key is not present. + + hmget + hmget_ts + shget + TV hmget(T*, TK key) + TV shget(T*, char* key) + TV hmget_ts(T*, TK key, ptrdiff_t tempvar) + Returns the value corresponding to 'key' in the hashmap. + The structure must have a 'value' field + + hmgets + shgets + T hmgets(T*, TK key) + T shgets(T*, char* key) + Returns the structure corresponding to 'key' in the hashmap. + + hmgetp + shgetp + hmgetp_ts + hmgetp_null + shgetp_null + T* hmgetp(T*, TK key) + T* shgetp(T*, char* key) + T* hmgetp_ts(T*, TK key, ptrdiff_t tempvar) + T* hmgetp_null(T*, TK key) + T* shgetp_null(T*, char *key) + Returns a pointer to the structure corresponding to 'key' in + the hashmap. Functions ending in "_null" return NULL if the key + is not present in the hashmap; the others return a pointer to a + structure holding the default value (but not the searched-for key). + + hmdefault + shdefault + TV hmdefault(T*, TV value) + TV shdefault(T*, TV value) + Sets the default value for the hashmap, the value which will be + returned by hmget/shget if the key is not present. + + hmdefaults + shdefaults + TV hmdefaults(T*, T item) + TV shdefaults(T*, T item) + Sets the default struct for the hashmap, the contents which will be + returned by hmgets/shgets if the key is not present. + + hmput + shput + TV hmput(T*, TK key, TV value) + TV shput(T*, char* key, TV value) + Inserts a pair into the hashmap. If the key is already + present in the hashmap, updates its value. + + hmputs + shputs + T hmputs(T*, T item) + T shputs(T*, T item) + Inserts a struct with T.key into the hashmap. If the struct is already + present in the hashmap, updates it. + + hmdel + shdel + int hmdel(T*, TK key) + int shdel(T*, char* key) + If 'key' is in the hashmap, deletes its entry and returns 1. + Otherwise returns 0. + + Function interface (actually macros) for strings only: + + sh_new_strdup + void sh_new_strdup(T*); + Overwrites the existing pointer with a newly allocated + string hashmap which will automatically allocate and free + each string key using realloc/free + + sh_new_arena + void sh_new_arena(T*); + Overwrites the existing pointer with a newly allocated + string hashmap which will automatically allocate each string + key to a string arena. Every string key ever used by this + hash table remains in the arena until the arena is freed. + Additionally, any key which is deleted and reinserted will + be allocated multiple times in the string arena. + +NOTES + + * These data structures are realloc'd when they grow, and the macro + "functions" write to the provided pointer. This means: (a) the pointer + must be an lvalue, and (b) the pointer to the data structure is not + stable, and you must maintain it the same as you would a realloc'd + pointer. For example, if you pass a pointer to a dynamic array to a + function which updates it, the function must return back the new + pointer to the caller. This is the price of trying to do this in C. + + * The following are the only functions that are thread-safe on a single data + structure, i.e. can be run in multiple threads simultaneously on the same + data structure + hmlen shlen + hmlenu shlenu + hmget_ts shget_ts + hmgeti_ts shgeti_ts + hmgets_ts shgets_ts + + * You iterate over the contents of a dynamic array and a hashmap in exactly + the same way, using arrlen/hmlen/shlen: + + for (i=0; i < arrlen(foo); ++i) + ... foo[i] ... + + * All operations except arrins/arrdel are O(1) amortized, but individual + operations can be slow, so these data structures may not be suitable + for real time use. Dynamic arrays double in capacity as needed, so + elements are copied an average of once. Hash tables double/halve + their size as needed, with appropriate hysteresis to maintain O(1) + performance. + +NOTES - DYNAMIC ARRAY + + * If you know how long a dynamic array is going to be in advance, you can avoid + extra memory allocations by using arrsetlen to allocate it to that length in + advance and use foo[n] while filling it out, or arrsetcap to allocate the memory + for that length and use arrput/arrpush as normal. + + * Unlike some other versions of the dynamic array, this version should + be safe to use with strict-aliasing optimizations. + +NOTES - HASH MAP + + * For compilers other than GCC and clang (e.g. Visual Studio), for hmput/hmget/hmdel + and variants, the key must be an lvalue (so the macro can take the address of it). + Extensions are used that eliminate this requirement if you're using C99 and later + in GCC or clang, or if you're using C++ in GCC. But note that this can make your + code less portable. + + * To test for presence of a key in a hashmap, just do 'hmgeti(foo,key) >= 0'. + + * The iteration order of your data in the hashmap is determined solely by the + order of insertions and deletions. In particular, if you never delete, new + keys are always added at the end of the array. This will be consistent + across all platforms and versions of the library. However, you should not + attempt to serialize the internal hash table, as the hash is not consistent + between different platforms, and may change with future versions of the library. + + * Use sh_new_arena() for string hashmaps that you never delete from. Initialize + with NULL if you're managing the memory for your strings, or your strings are + never freed (at least until the hashmap is freed). Otherwise, use sh_new_strdup(). + @TODO: make an arena variant that garbage collects the strings with a trivial + copy collector into a new arena whenever the table shrinks / rebuilds. Since + current arena recommendation is to only use arena if it never deletes, then + this can just replace current arena implementation. + + * If adversarial input is a serious concern and you're on a 64-bit platform, + enable STBDS_SIPHASH_2_4 (see the 'Compile-time options' section), and pass + a strong random number to stbds_rand_seed. + + * The default value for the hash table is stored in foo[-1], so if you + use code like 'hmget(T,k)->value = 5' you can accidentally overwrite + the value stored by hmdefault if 'k' is not present. + +CREDITS + + Sean Barrett -- library, idea for dynamic array API/implementation + Per Vognsen -- idea for hash table API/implementation + Rafael Sachetto -- arrpop() + github:HeroicKatora -- arraddn() reworking + + Bugfixes: + Andy Durdin + Shane Liesegang + Vinh Truong + Andreas Molzer + github:hashitaku + github:srdjanstipic + Macoy Madson + Andreas Vennstrom + Tobias Mansfield-Williams +*/ + +#ifdef STBDS_UNIT_TESTS +#define _CRT_SECURE_NO_WARNINGS +#endif + +#ifndef INCLUDE_STB_DS_H +#define INCLUDE_STB_DS_H + +#include +#include + +#ifndef STBDS_NO_SHORT_NAMES +#define arrlen stbds_arrlen +#define arrlenu stbds_arrlenu +#define arrput stbds_arrput +#define arrpush stbds_arrput +#define arrpop stbds_arrpop +#define arrfree stbds_arrfree +#define arraddn stbds_arraddn // deprecated, use one of the following instead: +#define arraddnptr stbds_arraddnptr +#define arraddnindex stbds_arraddnindex +#define arrsetlen stbds_arrsetlen +#define arrlast stbds_arrlast +#define arrins stbds_arrins +#define arrinsn stbds_arrinsn +#define arrdel stbds_arrdel +#define arrdeln stbds_arrdeln +#define arrdelswap stbds_arrdelswap +#define arrcap stbds_arrcap +#define arrsetcap stbds_arrsetcap + +#define hmput stbds_hmput +#define hmputs stbds_hmputs +#define hmget stbds_hmget +#define hmget_ts stbds_hmget_ts +#define hmgets stbds_hmgets +#define hmgetp stbds_hmgetp +#define hmgetp_ts stbds_hmgetp_ts +#define hmgetp_null stbds_hmgetp_null +#define hmgeti stbds_hmgeti +#define hmgeti_ts stbds_hmgeti_ts +#define hmdel stbds_hmdel +#define hmlen stbds_hmlen +#define hmlenu stbds_hmlenu +#define hmfree stbds_hmfree +#define hmdefault stbds_hmdefault +#define hmdefaults stbds_hmdefaults + +#define shput stbds_shput +#define shputi stbds_shputi +#define shputs stbds_shputs +#define shget stbds_shget +#define shgeti stbds_shgeti +#define shgets stbds_shgets +#define shgetp stbds_shgetp +#define shgetp_null stbds_shgetp_null +#define shdel stbds_shdel +#define shlen stbds_shlen +#define shlenu stbds_shlenu +#define shfree stbds_shfree +#define shdefault stbds_shdefault +#define shdefaults stbds_shdefaults +#define sh_new_arena stbds_sh_new_arena +#define sh_new_strdup stbds_sh_new_strdup + +#define stralloc stbds_stralloc +#define strreset stbds_strreset +#endif + +#if defined(STBDS_REALLOC) && !defined(STBDS_FREE) || !defined(STBDS_REALLOC) && defined(STBDS_FREE) +#error "You must define both STBDS_REALLOC and STBDS_FREE, or neither." +#endif +#if !defined(STBDS_REALLOC) && !defined(STBDS_FREE) +#include +#define STBDS_REALLOC(c,p,s) realloc(p,s) +#define STBDS_FREE(c,p) free(p) +#endif + +#ifdef _MSC_VER +#define STBDS_NOTUSED(v) (void)(v) +#else +#define STBDS_NOTUSED(v) (void)sizeof(v) +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +// for security against attackers, seed the library with a random number, at least time() but stronger is better +extern void stbds_rand_seed(size_t seed); + +// these are the hash functions used internally if you want to test them or use them for other purposes +extern size_t stbds_hash_bytes(void *p, size_t len, size_t seed); +extern size_t stbds_hash_string(char *str, size_t seed); + +// this is a simple string arena allocator, initialize with e.g. 'stbds_string_arena my_arena={0}'. +typedef struct stbds_string_arena stbds_string_arena; +extern char * stbds_stralloc(stbds_string_arena *a, char *str); +extern void stbds_strreset(stbds_string_arena *a); + +// have to #define STBDS_UNIT_TESTS to call this +extern void stbds_unit_tests(void); + +/////////////// +// +// Everything below here is implementation details +// + +extern void * stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap); +extern void stbds_arrfreef(void *a); +extern void stbds_hmfree_func(void *p, size_t elemsize); +extern void * stbds_hmget_key(void *a, size_t elemsize, void *key, size_t keysize, int mode); +extern void * stbds_hmget_key_ts(void *a, size_t elemsize, void *key, size_t keysize, ptrdiff_t *temp, int mode); +extern void * stbds_hmput_default(void *a, size_t elemsize); +extern void * stbds_hmput_key(void *a, size_t elemsize, void *key, size_t keysize, int mode); +extern void * stbds_hmdel_key(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode); +extern void * stbds_shmode_func(size_t elemsize, int mode); + +#ifdef __cplusplus +} +#endif + +#if defined(__GNUC__) || defined(__clang__) +#define STBDS_HAS_TYPEOF +#ifdef __cplusplus +//#define STBDS_HAS_LITERAL_ARRAY // this is currently broken for clang +#endif +#endif + +#if !defined(__cplusplus) +#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L +#define STBDS_HAS_LITERAL_ARRAY +#endif +#endif + +// this macro takes the address of the argument, but on gcc/clang can accept rvalues +#if defined(STBDS_HAS_LITERAL_ARRAY) && defined(STBDS_HAS_TYPEOF) + #if __clang__ + #define STBDS_ADDRESSOF(typevar, value) ((__typeof__(typevar)[1]){value}) // literal array decays to pointer to value + #else + #define STBDS_ADDRESSOF(typevar, value) ((typeof(typevar)[1]){value}) // literal array decays to pointer to value + #endif +#else +#define STBDS_ADDRESSOF(typevar, value) &(value) +#endif + +#define STBDS_OFFSETOF(var,field) ((char *) &(var)->field - (char *) (var)) + +#define stbds_header(t) ((stbds_array_header *) (t) - 1) +#define stbds_temp(t) stbds_header(t)->temp +#define stbds_temp_key(t) (*(char **) stbds_header(t)->hash_table) + +#define stbds_arrsetcap(a,n) (stbds_arrgrow(a,0,n)) +#define stbds_arrsetlen(a,n) ((stbds_arrcap(a) < (size_t) (n) ? stbds_arrsetcap((a),(size_t)(n)),0 : 0), (a) ? stbds_header(a)->length = (size_t) (n) : 0) +#define stbds_arrcap(a) ((a) ? stbds_header(a)->capacity : 0) +#define stbds_arrlen(a) ((a) ? (ptrdiff_t) stbds_header(a)->length : 0) +#define stbds_arrlenu(a) ((a) ? stbds_header(a)->length : 0) +#define stbds_arrput(a,v) (stbds_arrmaybegrow(a,1), (a)[stbds_header(a)->length++] = (v)) +#define stbds_arrpush stbds_arrput // synonym +#define stbds_arrpop(a) (stbds_header(a)->length--, (a)[stbds_header(a)->length]) +#define stbds_arraddn(a,n) ((void)(stbds_arraddnindex(a, n))) // deprecated, use one of the following instead: +#define stbds_arraddnptr(a,n) (stbds_arrmaybegrow(a,n), (n) ? (stbds_header(a)->length += (n), &(a)[stbds_header(a)->length-(n)]) : (a)) +#define stbds_arraddnindex(a,n)(stbds_arrmaybegrow(a,n), (n) ? (stbds_header(a)->length += (n), stbds_header(a)->length-(n)) : stbds_arrlen(a)) +#define stbds_arraddnoff stbds_arraddnindex +#define stbds_arrlast(a) ((a)[stbds_header(a)->length-1]) +#define stbds_arrfree(a) ((void) ((a) ? STBDS_FREE(NULL,stbds_header(a)) : (void)0), (a)=NULL) +#define stbds_arrdel(a,i) stbds_arrdeln(a,i,1) +#define stbds_arrdeln(a,i,n) (memmove(&(a)[i], &(a)[(i)+(n)], sizeof *(a) * (stbds_header(a)->length-(n)-(i))), stbds_header(a)->length -= (n)) +#define stbds_arrdelswap(a,i) ((a)[i] = stbds_arrlast(a), stbds_header(a)->length -= 1) +#define stbds_arrinsn(a,i,n) (stbds_arraddn((a),(n)), memmove(&(a)[(i)+(n)], &(a)[i], sizeof *(a) * (stbds_header(a)->length-(n)-(i)))) +#define stbds_arrins(a,i,v) (stbds_arrinsn((a),(i),1), (a)[i]=(v)) + +#define stbds_arrmaybegrow(a,n) ((!(a) || stbds_header(a)->length + (n) > stbds_header(a)->capacity) \ + ? (stbds_arrgrow(a,n,0),0) : 0) + +#define stbds_arrgrow(a,b,c) ((a) = stbds_arrgrowf_wrapper((a), sizeof *(a), (b), (c))) + +#define stbds_hmput(t, k, v) \ + ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, 0), \ + (t)[stbds_temp((t)-1)].key = (k), \ + (t)[stbds_temp((t)-1)].value = (v)) + +#define stbds_hmputs(t, s) \ + ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), &(s).key, sizeof (s).key, STBDS_HM_BINARY), \ + (t)[stbds_temp((t)-1)] = (s)) + +#define stbds_hmgeti(t,k) \ + ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, STBDS_HM_BINARY), \ + stbds_temp((t)-1)) + +#define stbds_hmgeti_ts(t,k,temp) \ + ((t) = stbds_hmget_key_ts_wrapper((t), sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, &(temp), STBDS_HM_BINARY), \ + (temp)) + +#define stbds_hmgetp(t, k) \ + ((void) stbds_hmgeti(t,k), &(t)[stbds_temp((t)-1)]) + +#define stbds_hmgetp_ts(t, k, temp) \ + ((void) stbds_hmgeti_ts(t,k,temp), &(t)[temp]) + +#define stbds_hmdel(t,k) \ + (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) STBDS_ADDRESSOF((t)->key, (k)), sizeof (t)->key, STBDS_OFFSETOF((t),key), STBDS_HM_BINARY)),(t)?stbds_temp((t)-1):0) + +#define stbds_hmdefault(t, v) \ + ((t) = stbds_hmput_default_wrapper((t), sizeof *(t)), (t)[-1].value = (v)) + +#define stbds_hmdefaults(t, s) \ + ((t) = stbds_hmput_default_wrapper((t), sizeof *(t)), (t)[-1] = (s)) + +#define stbds_hmfree(p) \ + ((void) ((p) != NULL ? stbds_hmfree_func((p)-1,sizeof*(p)),0 : 0),(p)=NULL) + +#define stbds_hmgets(t, k) (*stbds_hmgetp(t,k)) +#define stbds_hmget(t, k) (stbds_hmgetp(t,k)->value) +#define stbds_hmget_ts(t, k, temp) (stbds_hmgetp_ts(t,k,temp)->value) +#define stbds_hmlen(t) ((t) ? (ptrdiff_t) stbds_header((t)-1)->length-1 : 0) +#define stbds_hmlenu(t) ((t) ? stbds_header((t)-1)->length-1 : 0) +#define stbds_hmgetp_null(t,k) (stbds_hmgeti(t,k) == -1 ? NULL : &(t)[stbds_temp((t)-1)]) + +#define stbds_shput(t, k, v) \ + ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \ + (t)[stbds_temp((t)-1)].value = (v)) + +#define stbds_shputi(t, k, v) \ + ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \ + (t)[stbds_temp((t)-1)].value = (v), stbds_temp((t)-1)) + +#define stbds_shputs(t, s) \ + ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (s).key, sizeof (s).key, STBDS_HM_STRING), \ + (t)[stbds_temp((t)-1)] = (s), \ + (t)[stbds_temp((t)-1)].key = stbds_temp_key((t)-1)) // above line overwrites whole structure, so must rewrite key here if it was allocated internally + +#define stbds_pshput(t, p) \ + ((t) = stbds_hmput_key_wrapper((t), sizeof *(t), (void*) (p)->key, sizeof (p)->key, STBDS_HM_PTR_TO_STRING), \ + (t)[stbds_temp((t)-1)] = (p)) + +#define stbds_shgeti(t,k) \ + ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_HM_STRING), \ + stbds_temp((t)-1)) + +#define stbds_pshgeti(t,k) \ + ((t) = stbds_hmget_key_wrapper((t), sizeof *(t), (void*) (k), sizeof (*(t))->key, STBDS_HM_PTR_TO_STRING), \ + stbds_temp((t)-1)) + +#define stbds_shgetp(t, k) \ + ((void) stbds_shgeti(t,k), &(t)[stbds_temp((t)-1)]) + +#define stbds_pshget(t, k) \ + ((void) stbds_pshgeti(t,k), (t)[stbds_temp((t)-1)]) + +#define stbds_shdel(t,k) \ + (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) (k), sizeof (t)->key, STBDS_OFFSETOF((t),key), STBDS_HM_STRING)),(t)?stbds_temp((t)-1):0) +#define stbds_pshdel(t,k) \ + (((t) = stbds_hmdel_key_wrapper((t),sizeof *(t), (void*) (k), sizeof (*(t))->key, STBDS_OFFSETOF(*(t),key), STBDS_HM_PTR_TO_STRING)),(t)?stbds_temp((t)-1):0) + +#define stbds_sh_new_arena(t) \ + ((t) = stbds_shmode_func_wrapper(t, sizeof *(t), STBDS_SH_ARENA)) +#define stbds_sh_new_strdup(t) \ + ((t) = stbds_shmode_func_wrapper(t, sizeof *(t), STBDS_SH_STRDUP)) + +#define stbds_shdefault(t, v) stbds_hmdefault(t,v) +#define stbds_shdefaults(t, s) stbds_hmdefaults(t,s) + +#define stbds_shfree stbds_hmfree +#define stbds_shlenu stbds_hmlenu + +#define stbds_shgets(t, k) (*stbds_shgetp(t,k)) +#define stbds_shget(t, k) (stbds_shgetp(t,k)->value) +#define stbds_shgetp_null(t,k) (stbds_shgeti(t,k) == -1 ? NULL : &(t)[stbds_temp((t)-1)]) +#define stbds_shlen stbds_hmlen + +typedef struct +{ + size_t length; + size_t capacity; + void * hash_table; + ptrdiff_t temp; +} stbds_array_header; + +typedef struct stbds_string_block +{ + struct stbds_string_block *next; + char storage[8]; +} stbds_string_block; + +struct stbds_string_arena +{ + stbds_string_block *storage; + size_t remaining; + unsigned char block; + unsigned char mode; // this isn't used by the string arena itself +}; + +#define STBDS_HM_BINARY 0 +#define STBDS_HM_STRING 1 + +enum +{ + STBDS_SH_NONE, + STBDS_SH_DEFAULT, + STBDS_SH_STRDUP, + STBDS_SH_ARENA +}; + +#ifdef __cplusplus +// in C we use implicit assignment from these void*-returning functions to T*. +// in C++ these templates make the same code work +template static T * stbds_arrgrowf_wrapper(T *a, size_t elemsize, size_t addlen, size_t min_cap) { + return (T*)stbds_arrgrowf((void *)a, elemsize, addlen, min_cap); +} +template static T * stbds_hmget_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, int mode) { + return (T*)stbds_hmget_key((void*)a, elemsize, key, keysize, mode); +} +template static T * stbds_hmget_key_ts_wrapper(T *a, size_t elemsize, void *key, size_t keysize, ptrdiff_t *temp, int mode) { + return (T*)stbds_hmget_key_ts((void*)a, elemsize, key, keysize, temp, mode); +} +template static T * stbds_hmput_default_wrapper(T *a, size_t elemsize) { + return (T*)stbds_hmput_default((void *)a, elemsize); +} +template static T * stbds_hmput_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, int mode) { + return (T*)stbds_hmput_key((void*)a, elemsize, key, keysize, mode); +} +template static T * stbds_hmdel_key_wrapper(T *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode){ + return (T*)stbds_hmdel_key((void*)a, elemsize, key, keysize, keyoffset, mode); +} +template static T * stbds_shmode_func_wrapper(T *, size_t elemsize, int mode) { + return (T*)stbds_shmode_func(elemsize, mode); +} +#else +#define stbds_arrgrowf_wrapper stbds_arrgrowf +#define stbds_hmget_key_wrapper stbds_hmget_key +#define stbds_hmget_key_ts_wrapper stbds_hmget_key_ts +#define stbds_hmput_default_wrapper stbds_hmput_default +#define stbds_hmput_key_wrapper stbds_hmput_key +#define stbds_hmdel_key_wrapper stbds_hmdel_key +#define stbds_shmode_func_wrapper(t,e,m) stbds_shmode_func(e,m) +#endif + +#endif // INCLUDE_STB_DS_H + + +////////////////////////////////////////////////////////////////////////////// +// +// IMPLEMENTATION +// + +#ifdef STB_DS_IMPLEMENTATION +#include +#include + +#ifndef STBDS_ASSERT +#define STBDS_ASSERT_WAS_UNDEFINED +#define STBDS_ASSERT(x) ((void) 0) +#endif + +#ifdef STBDS_STATISTICS +#define STBDS_STATS(x) x +size_t stbds_array_grow; +size_t stbds_hash_grow; +size_t stbds_hash_shrink; +size_t stbds_hash_rebuild; +size_t stbds_hash_probes; +size_t stbds_hash_alloc; +size_t stbds_rehash_probes; +size_t stbds_rehash_items; +#else +#define STBDS_STATS(x) +#endif + +// +// stbds_arr implementation +// + +//int *prev_allocs[65536]; +//int num_prev; + +void *stbds_arrgrowf(void *a, size_t elemsize, size_t addlen, size_t min_cap) +{ + stbds_array_header temp={0}; // force debugging + void *b; + size_t min_len = stbds_arrlen(a) + addlen; + (void) sizeof(temp); + + // compute the minimum capacity needed + if (min_len > min_cap) + min_cap = min_len; + + if (min_cap <= stbds_arrcap(a)) + return a; + + // increase needed capacity to guarantee O(1) amortized + if (min_cap < 2 * stbds_arrcap(a)) + min_cap = 2 * stbds_arrcap(a); + else if (min_cap < 4) + min_cap = 4; + + //if (num_prev < 65536) if (a) prev_allocs[num_prev++] = (int *) ((char *) a+1); + //if (num_prev == 2201) + // num_prev = num_prev; + b = STBDS_REALLOC(NULL, (a) ? stbds_header(a) : 0, elemsize * min_cap + sizeof(stbds_array_header)); + //if (num_prev < 65536) prev_allocs[num_prev++] = (int *) (char *) b; + b = (char *) b + sizeof(stbds_array_header); + if (a == NULL) { + stbds_header(b)->length = 0; + stbds_header(b)->hash_table = 0; + stbds_header(b)->temp = 0; + } else { + STBDS_STATS(++stbds_array_grow); + } + stbds_header(b)->capacity = min_cap; + + return b; +} + +void stbds_arrfreef(void *a) +{ + STBDS_FREE(NULL, stbds_header(a)); +} + +// +// stbds_hm hash table implementation +// + +#ifdef STBDS_INTERNAL_SMALL_BUCKET +#define STBDS_BUCKET_LENGTH 4 +#else +#define STBDS_BUCKET_LENGTH 8 +#endif + +#define STBDS_BUCKET_SHIFT (STBDS_BUCKET_LENGTH == 8 ? 3 : 2) +#define STBDS_BUCKET_MASK (STBDS_BUCKET_LENGTH-1) +#define STBDS_CACHE_LINE_SIZE 64 + +#define STBDS_ALIGN_FWD(n,a) (((n) + (a) - 1) & ~((a)-1)) + +typedef struct +{ + size_t hash [STBDS_BUCKET_LENGTH]; + ptrdiff_t index[STBDS_BUCKET_LENGTH]; +} stbds_hash_bucket; // in 32-bit, this is one 64-byte cache line; in 64-bit, each array is one 64-byte cache line + +typedef struct +{ + char * temp_key; // this MUST be the first field of the hash table + size_t slot_count; + size_t used_count; + size_t used_count_threshold; + size_t used_count_shrink_threshold; + size_t tombstone_count; + size_t tombstone_count_threshold; + size_t seed; + size_t slot_count_log2; + stbds_string_arena string; + stbds_hash_bucket *storage; // not a separate allocation, just 64-byte aligned storage after this struct +} stbds_hash_index; + +#define STBDS_INDEX_EMPTY -1 +#define STBDS_INDEX_DELETED -2 +#define STBDS_INDEX_IN_USE(x) ((x) >= 0) + +#define STBDS_HASH_EMPTY 0 +#define STBDS_HASH_DELETED 1 + +static size_t stbds_hash_seed=0x31415926; + +void stbds_rand_seed(size_t seed) +{ + stbds_hash_seed = seed; +} + +#define stbds_load_32_or_64(var, temp, v32, v64_hi, v64_lo) \ + temp = v64_lo ^ v32, temp <<= 16, temp <<= 16, temp >>= 16, temp >>= 16, /* discard if 32-bit */ \ + var = v64_hi, var <<= 16, var <<= 16, /* discard if 32-bit */ \ + var ^= temp ^ v32 + +#define STBDS_SIZE_T_BITS ((sizeof (size_t)) * 8) + +static size_t stbds_probe_position(size_t hash, size_t slot_count, size_t slot_log2) +{ + size_t pos; + STBDS_NOTUSED(slot_log2); + pos = hash & (slot_count-1); + #ifdef STBDS_INTERNAL_BUCKET_START + pos &= ~STBDS_BUCKET_MASK; + #endif + return pos; +} + +static size_t stbds_log2(size_t slot_count) +{ + size_t n=0; + while (slot_count > 1) { + slot_count >>= 1; + ++n; + } + return n; +} + +static stbds_hash_index *stbds_make_hash_index(size_t slot_count, stbds_hash_index *ot) +{ + stbds_hash_index *t; + t = (stbds_hash_index *) STBDS_REALLOC(NULL,0,(slot_count >> STBDS_BUCKET_SHIFT) * sizeof(stbds_hash_bucket) + sizeof(stbds_hash_index) + STBDS_CACHE_LINE_SIZE-1); + t->storage = (stbds_hash_bucket *) STBDS_ALIGN_FWD((size_t) (t+1), STBDS_CACHE_LINE_SIZE); + t->slot_count = slot_count; + t->slot_count_log2 = stbds_log2(slot_count); + t->tombstone_count = 0; + t->used_count = 0; + + #if 0 // A1 + t->used_count_threshold = slot_count*12/16; // if 12/16th of table is occupied, grow + t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild + t->used_count_shrink_threshold = slot_count* 4/16; // if table is only 4/16th full, shrink + #elif 1 // A2 + //t->used_count_threshold = slot_count*12/16; // if 12/16th of table is occupied, grow + //t->tombstone_count_threshold = slot_count* 3/16; // if tombstones are 3/16th of table, rebuild + //t->used_count_shrink_threshold = slot_count* 4/16; // if table is only 4/16th full, shrink + + // compute without overflowing + t->used_count_threshold = slot_count - (slot_count>>2); + t->tombstone_count_threshold = (slot_count>>3) + (slot_count>>4); + t->used_count_shrink_threshold = slot_count >> 2; + + #elif 0 // B1 + t->used_count_threshold = slot_count*13/16; // if 13/16th of table is occupied, grow + t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild + t->used_count_shrink_threshold = slot_count* 5/16; // if table is only 5/16th full, shrink + #else // C1 + t->used_count_threshold = slot_count*14/16; // if 14/16th of table is occupied, grow + t->tombstone_count_threshold = slot_count* 2/16; // if tombstones are 2/16th of table, rebuild + t->used_count_shrink_threshold = slot_count* 6/16; // if table is only 6/16th full, shrink + #endif + // Following statistics were measured on a Core i7-6700 @ 4.00Ghz, compiled with clang 7.0.1 -O2 + // Note that the larger tables have high variance as they were run fewer times + // A1 A2 B1 C1 + // 0.10ms : 0.10ms : 0.10ms : 0.11ms : 2,000 inserts creating 2K table + // 0.96ms : 0.95ms : 0.97ms : 1.04ms : 20,000 inserts creating 20K table + // 14.48ms : 14.46ms : 10.63ms : 11.00ms : 200,000 inserts creating 200K table + // 195.74ms : 196.35ms : 203.69ms : 214.92ms : 2,000,000 inserts creating 2M table + // 2193.88ms : 2209.22ms : 2285.54ms : 2437.17ms : 20,000,000 inserts creating 20M table + // 65.27ms : 53.77ms : 65.33ms : 65.47ms : 500,000 inserts & deletes in 2K table + // 72.78ms : 62.45ms : 71.95ms : 72.85ms : 500,000 inserts & deletes in 20K table + // 89.47ms : 77.72ms : 96.49ms : 96.75ms : 500,000 inserts & deletes in 200K table + // 97.58ms : 98.14ms : 97.18ms : 97.53ms : 500,000 inserts & deletes in 2M table + // 118.61ms : 119.62ms : 120.16ms : 118.86ms : 500,000 inserts & deletes in 20M table + // 192.11ms : 194.39ms : 196.38ms : 195.73ms : 500,000 inserts & deletes in 200M table + + if (slot_count <= STBDS_BUCKET_LENGTH) + t->used_count_shrink_threshold = 0; + // to avoid infinite loop, we need to guarantee that at least one slot is empty and will terminate probes + STBDS_ASSERT(t->used_count_threshold + t->tombstone_count_threshold < t->slot_count); + STBDS_STATS(++stbds_hash_alloc); + if (ot) { + t->string = ot->string; + // reuse old seed so we can reuse old hashes so below "copy out old data" doesn't do any hashing + t->seed = ot->seed; + } else { + size_t a,b,temp; + memset(&t->string, 0, sizeof(t->string)); + t->seed = stbds_hash_seed; + // LCG + // in 32-bit, a = 2147001325 b = 715136305 + // in 64-bit, a = 2862933555777941757 b = 3037000493 + stbds_load_32_or_64(a,temp, 2147001325, 0x27bb2ee6, 0x87b0b0fd); + stbds_load_32_or_64(b,temp, 715136305, 0, 0xb504f32d); + stbds_hash_seed = stbds_hash_seed * a + b; + } + + { + size_t i,j; + for (i=0; i < slot_count >> STBDS_BUCKET_SHIFT; ++i) { + stbds_hash_bucket *b = &t->storage[i]; + for (j=0; j < STBDS_BUCKET_LENGTH; ++j) + b->hash[j] = STBDS_HASH_EMPTY; + for (j=0; j < STBDS_BUCKET_LENGTH; ++j) + b->index[j] = STBDS_INDEX_EMPTY; + } + } + + // copy out the old data, if any + if (ot) { + size_t i,j; + t->used_count = ot->used_count; + for (i=0; i < ot->slot_count >> STBDS_BUCKET_SHIFT; ++i) { + stbds_hash_bucket *ob = &ot->storage[i]; + for (j=0; j < STBDS_BUCKET_LENGTH; ++j) { + if (STBDS_INDEX_IN_USE(ob->index[j])) { + size_t hash = ob->hash[j]; + size_t pos = stbds_probe_position(hash, t->slot_count, t->slot_count_log2); + size_t step = STBDS_BUCKET_LENGTH; + STBDS_STATS(++stbds_rehash_items); + for (;;) { + size_t limit,z; + stbds_hash_bucket *bucket; + bucket = &t->storage[pos >> STBDS_BUCKET_SHIFT]; + STBDS_STATS(++stbds_rehash_probes); + + for (z=pos & STBDS_BUCKET_MASK; z < STBDS_BUCKET_LENGTH; ++z) { + if (bucket->hash[z] == 0) { + bucket->hash[z] = hash; + bucket->index[z] = ob->index[j]; + goto done; + } + } + + limit = pos & STBDS_BUCKET_MASK; + for (z = 0; z < limit; ++z) { + if (bucket->hash[z] == 0) { + bucket->hash[z] = hash; + bucket->index[z] = ob->index[j]; + goto done; + } + } + + pos += step; // quadratic probing + step += STBDS_BUCKET_LENGTH; + pos &= (t->slot_count-1); + } + } + done: + ; + } + } + } + + return t; +} + +#define STBDS_ROTATE_LEFT(val, n) (((val) << (n)) | ((val) >> (STBDS_SIZE_T_BITS - (n)))) +#define STBDS_ROTATE_RIGHT(val, n) (((val) >> (n)) | ((val) << (STBDS_SIZE_T_BITS - (n)))) + +size_t stbds_hash_string(char *str, size_t seed) +{ + size_t hash = seed; + while (*str) + hash = STBDS_ROTATE_LEFT(hash, 9) + (unsigned char) *str++; + + // Thomas Wang 64-to-32 bit mix function, hopefully also works in 32 bits + hash ^= seed; + hash = (~hash) + (hash << 18); + hash ^= hash ^ STBDS_ROTATE_RIGHT(hash,31); + hash = hash * 21; + hash ^= hash ^ STBDS_ROTATE_RIGHT(hash,11); + hash += (hash << 6); + hash ^= STBDS_ROTATE_RIGHT(hash,22); + return hash+seed; +} + +#ifdef STBDS_SIPHASH_2_4 +#define STBDS_SIPHASH_C_ROUNDS 2 +#define STBDS_SIPHASH_D_ROUNDS 4 +typedef int STBDS_SIPHASH_2_4_can_only_be_used_in_64_bit_builds[sizeof(size_t) == 8 ? 1 : -1]; +#endif + +#ifndef STBDS_SIPHASH_C_ROUNDS +#define STBDS_SIPHASH_C_ROUNDS 1 +#endif +#ifndef STBDS_SIPHASH_D_ROUNDS +#define STBDS_SIPHASH_D_ROUNDS 1 +#endif + +#ifdef _MSC_VER +#pragma warning(push) +#pragma warning(disable:4127) // conditional expression is constant, for do..while(0) and sizeof()== +#endif + +static size_t stbds_siphash_bytes(void *p, size_t len, size_t seed) +{ + unsigned char *d = (unsigned char *) p; + size_t i,j; + size_t v0,v1,v2,v3, data; + + // hash that works on 32- or 64-bit registers without knowing which we have + // (computes different results on 32-bit and 64-bit platform) + // derived from siphash, but on 32-bit platforms very different as it uses 4 32-bit state not 4 64-bit + v0 = ((((size_t) 0x736f6d65 << 16) << 16) + 0x70736575) ^ seed; + v1 = ((((size_t) 0x646f7261 << 16) << 16) + 0x6e646f6d) ^ ~seed; + v2 = ((((size_t) 0x6c796765 << 16) << 16) + 0x6e657261) ^ seed; + v3 = ((((size_t) 0x74656462 << 16) << 16) + 0x79746573) ^ ~seed; + + #ifdef STBDS_TEST_SIPHASH_2_4 + // hardcoded with key material in the siphash test vectors + v0 ^= 0x0706050403020100ull ^ seed; + v1 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed; + v2 ^= 0x0706050403020100ull ^ seed; + v3 ^= 0x0f0e0d0c0b0a0908ull ^ ~seed; + #endif + + #define STBDS_SIPROUND() \ + do { \ + v0 += v1; v1 = STBDS_ROTATE_LEFT(v1, 13); v1 ^= v0; v0 = STBDS_ROTATE_LEFT(v0,STBDS_SIZE_T_BITS/2); \ + v2 += v3; v3 = STBDS_ROTATE_LEFT(v3, 16); v3 ^= v2; \ + v2 += v1; v1 = STBDS_ROTATE_LEFT(v1, 17); v1 ^= v2; v2 = STBDS_ROTATE_LEFT(v2,STBDS_SIZE_T_BITS/2); \ + v0 += v3; v3 = STBDS_ROTATE_LEFT(v3, 21); v3 ^= v0; \ + } while (0) + + for (i=0; i+sizeof(size_t) <= len; i += sizeof(size_t), d += sizeof(size_t)) { + data = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24); + data |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // discarded if size_t == 4 + + v3 ^= data; + for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j) + STBDS_SIPROUND(); + v0 ^= data; + } + data = len << (STBDS_SIZE_T_BITS-8); + switch (len - i) { + case 7: data |= ((size_t) d[6] << 24) << 24; // fall through + case 6: data |= ((size_t) d[5] << 20) << 20; // fall through + case 5: data |= ((size_t) d[4] << 16) << 16; // fall through + case 4: data |= (d[3] << 24); // fall through + case 3: data |= (d[2] << 16); // fall through + case 2: data |= (d[1] << 8); // fall through + case 1: data |= d[0]; // fall through + case 0: break; + } + v3 ^= data; + for (j=0; j < STBDS_SIPHASH_C_ROUNDS; ++j) + STBDS_SIPROUND(); + v0 ^= data; + v2 ^= 0xff; + for (j=0; j < STBDS_SIPHASH_D_ROUNDS; ++j) + STBDS_SIPROUND(); + +#ifdef STBDS_SIPHASH_2_4 + return v0^v1^v2^v3; +#else + return v1^v2^v3; // slightly stronger since v0^v3 in above cancels out final round operation? I tweeted at the authors of SipHash about this but they didn't reply +#endif +} + +size_t stbds_hash_bytes(void *p, size_t len, size_t seed) +{ +#ifdef STBDS_SIPHASH_2_4 + return stbds_siphash_bytes(p,len,seed); +#else + unsigned char *d = (unsigned char *) p; + + if (len == 4) { + unsigned int hash = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24); + #if 0 + // HASH32-A Bob Jenkin's hash function w/o large constants + hash ^= seed; + hash -= (hash<<6); + hash ^= (hash>>17); + hash -= (hash<<9); + hash ^= seed; + hash ^= (hash<<4); + hash -= (hash<<3); + hash ^= (hash<<10); + hash ^= (hash>>15); + #elif 1 + // HASH32-BB Bob Jenkin's presumably-accidental version of Thomas Wang hash with rotates turned into shifts. + // Note that converting these back to rotates makes it run a lot slower, presumably due to collisions, so I'm + // not really sure what's going on. + hash ^= seed; + hash = (hash ^ 61) ^ (hash >> 16); + hash = hash + (hash << 3); + hash = hash ^ (hash >> 4); + hash = hash * 0x27d4eb2d; + hash ^= seed; + hash = hash ^ (hash >> 15); + #else // HASH32-C - Murmur3 + hash ^= seed; + hash *= 0xcc9e2d51; + hash = (hash << 17) | (hash >> 15); + hash *= 0x1b873593; + hash ^= seed; + hash = (hash << 19) | (hash >> 13); + hash = hash*5 + 0xe6546b64; + hash ^= hash >> 16; + hash *= 0x85ebca6b; + hash ^= seed; + hash ^= hash >> 13; + hash *= 0xc2b2ae35; + hash ^= hash >> 16; + #endif + // Following statistics were measured on a Core i7-6700 @ 4.00Ghz, compiled with clang 7.0.1 -O2 + // Note that the larger tables have high variance as they were run fewer times + // HASH32-A // HASH32-BB // HASH32-C + // 0.10ms // 0.10ms // 0.10ms : 2,000 inserts creating 2K table + // 0.96ms // 0.95ms // 0.99ms : 20,000 inserts creating 20K table + // 14.69ms // 14.43ms // 14.97ms : 200,000 inserts creating 200K table + // 199.99ms // 195.36ms // 202.05ms : 2,000,000 inserts creating 2M table + // 2234.84ms // 2187.74ms // 2240.38ms : 20,000,000 inserts creating 20M table + // 55.68ms // 53.72ms // 57.31ms : 500,000 inserts & deletes in 2K table + // 63.43ms // 61.99ms // 65.73ms : 500,000 inserts & deletes in 20K table + // 80.04ms // 77.96ms // 81.83ms : 500,000 inserts & deletes in 200K table + // 100.42ms // 97.40ms // 102.39ms : 500,000 inserts & deletes in 2M table + // 119.71ms // 120.59ms // 121.63ms : 500,000 inserts & deletes in 20M table + // 185.28ms // 195.15ms // 187.74ms : 500,000 inserts & deletes in 200M table + // 15.58ms // 14.79ms // 15.52ms : 200,000 inserts creating 200K table with varying key spacing + + return (((size_t) hash << 16 << 16) | hash) ^ seed; + } else if (len == 8 && sizeof(size_t) == 8) { + size_t hash = d[0] | (d[1] << 8) | (d[2] << 16) | (d[3] << 24); + hash |= (size_t) (d[4] | (d[5] << 8) | (d[6] << 16) | (d[7] << 24)) << 16 << 16; // avoid warning if size_t == 4 + hash ^= seed; + hash = (~hash) + (hash << 21); + hash ^= STBDS_ROTATE_RIGHT(hash,24); + hash *= 265; + hash ^= STBDS_ROTATE_RIGHT(hash,14); + hash ^= seed; + hash *= 21; + hash ^= STBDS_ROTATE_RIGHT(hash,28); + hash += (hash << 31); + hash = (~hash) + (hash << 18); + return hash; + } else { + return stbds_siphash_bytes(p,len,seed); + } +#endif +} +#ifdef _MSC_VER +#pragma warning(pop) +#endif + + +static int stbds_is_key_equal(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode, size_t i) +{ + if (mode >= STBDS_HM_STRING) + return 0==strcmp((char *) key, * (char **) ((char *) a + elemsize*i + keyoffset)); + else + return 0==memcmp(key, (char *) a + elemsize*i + keyoffset, keysize); +} + +#define STBDS_HASH_TO_ARR(x,elemsize) ((char*) (x) - (elemsize)) +#define STBDS_ARR_TO_HASH(x,elemsize) ((char*) (x) + (elemsize)) + +#define stbds_hash_table(a) ((stbds_hash_index *) stbds_header(a)->hash_table) + +void stbds_hmfree_func(void *a, size_t elemsize) +{ + if (a == NULL) return; + if (stbds_hash_table(a) != NULL) { + if (stbds_hash_table(a)->string.mode == STBDS_SH_STRDUP) { + size_t i; + // skip 0th element, which is default + for (i=1; i < stbds_header(a)->length; ++i) + STBDS_FREE(NULL, *(char**) ((char *) a + elemsize*i)); + } + stbds_strreset(&stbds_hash_table(a)->string); + } + STBDS_FREE(NULL, stbds_header(a)->hash_table); + STBDS_FREE(NULL, stbds_header(a)); +} + +static ptrdiff_t stbds_hm_find_slot(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode) +{ + void *raw_a = STBDS_HASH_TO_ARR(a,elemsize); + stbds_hash_index *table = stbds_hash_table(raw_a); + size_t hash = mode >= STBDS_HM_STRING ? stbds_hash_string((char*)key,table->seed) : stbds_hash_bytes(key, keysize,table->seed); + size_t step = STBDS_BUCKET_LENGTH; + size_t limit,i; + size_t pos; + stbds_hash_bucket *bucket; + + if (hash < 2) hash += 2; // stored hash values are forbidden from being 0, so we can detect empty slots + + pos = stbds_probe_position(hash, table->slot_count, table->slot_count_log2); + + for (;;) { + STBDS_STATS(++stbds_hash_probes); + bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT]; + + // start searching from pos to end of bucket, this should help performance on small hash tables that fit in cache + for (i=pos & STBDS_BUCKET_MASK; i < STBDS_BUCKET_LENGTH; ++i) { + if (bucket->hash[i] == hash) { + if (stbds_is_key_equal(a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { + return (pos & ~STBDS_BUCKET_MASK)+i; + } + } else if (bucket->hash[i] == STBDS_HASH_EMPTY) { + return -1; + } + } + + // search from beginning of bucket to pos + limit = pos & STBDS_BUCKET_MASK; + for (i = 0; i < limit; ++i) { + if (bucket->hash[i] == hash) { + if (stbds_is_key_equal(a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { + return (pos & ~STBDS_BUCKET_MASK)+i; + } + } else if (bucket->hash[i] == STBDS_HASH_EMPTY) { + return -1; + } + } + + // quadratic probing + pos += step; + step += STBDS_BUCKET_LENGTH; + pos &= (table->slot_count-1); + } + /* NOTREACHED */ +} + +void * stbds_hmget_key_ts(void *a, size_t elemsize, void *key, size_t keysize, ptrdiff_t *temp, int mode) +{ + size_t keyoffset = 0; + if (a == NULL) { + // make it non-empty so we can return a temp + a = stbds_arrgrowf(0, elemsize, 0, 1); + stbds_header(a)->length += 1; + memset(a, 0, elemsize); + *temp = STBDS_INDEX_EMPTY; + // adjust a to point after the default element + return STBDS_ARR_TO_HASH(a,elemsize); + } else { + stbds_hash_index *table; + void *raw_a = STBDS_HASH_TO_ARR(a,elemsize); + // adjust a to point to the default element + table = (stbds_hash_index *) stbds_header(raw_a)->hash_table; + if (table == 0) { + *temp = -1; + } else { + ptrdiff_t slot = stbds_hm_find_slot(a, elemsize, key, keysize, keyoffset, mode); + if (slot < 0) { + *temp = STBDS_INDEX_EMPTY; + } else { + stbds_hash_bucket *b = &table->storage[slot >> STBDS_BUCKET_SHIFT]; + *temp = b->index[slot & STBDS_BUCKET_MASK]; + } + } + return a; + } +} + +void * stbds_hmget_key(void *a, size_t elemsize, void *key, size_t keysize, int mode) +{ + ptrdiff_t temp; + void *p = stbds_hmget_key_ts(a, elemsize, key, keysize, &temp, mode); + stbds_temp(STBDS_HASH_TO_ARR(p,elemsize)) = temp; + return p; +} + +void * stbds_hmput_default(void *a, size_t elemsize) +{ + // three cases: + // a is NULL <- allocate + // a has a hash table but no entries, because of shmode <- grow + // a has entries <- do nothing + if (a == NULL || stbds_header(STBDS_HASH_TO_ARR(a,elemsize))->length == 0) { + a = stbds_arrgrowf(a ? STBDS_HASH_TO_ARR(a,elemsize) : NULL, elemsize, 0, 1); + stbds_header(a)->length += 1; + memset(a, 0, elemsize); + a=STBDS_ARR_TO_HASH(a,elemsize); + } + return a; +} + +static char *stbds_strdup(char *str); + +void *stbds_hmput_key(void *a, size_t elemsize, void *key, size_t keysize, int mode) +{ + size_t keyoffset=0; + void *raw_a; + stbds_hash_index *table; + + if (a == NULL) { + a = stbds_arrgrowf(0, elemsize, 0, 1); + memset(a, 0, elemsize); + stbds_header(a)->length += 1; + // adjust a to point AFTER the default element + a = STBDS_ARR_TO_HASH(a,elemsize); + } + + // adjust a to point to the default element + raw_a = a; + a = STBDS_HASH_TO_ARR(a,elemsize); + + table = (stbds_hash_index *) stbds_header(a)->hash_table; + + if (table == NULL || table->used_count >= table->used_count_threshold) { + stbds_hash_index *nt; + size_t slot_count; + + slot_count = (table == NULL) ? STBDS_BUCKET_LENGTH : table->slot_count*2; + nt = stbds_make_hash_index(slot_count, table); + if (table) + STBDS_FREE(NULL, table); + else + nt->string.mode = mode >= STBDS_HM_STRING ? STBDS_SH_DEFAULT : 0; + stbds_header(a)->hash_table = table = nt; + STBDS_STATS(++stbds_hash_grow); + } + + // we iterate hash table explicitly because we want to track if we saw a tombstone + { + size_t hash = mode >= STBDS_HM_STRING ? stbds_hash_string((char*)key,table->seed) : stbds_hash_bytes(key, keysize,table->seed); + size_t step = STBDS_BUCKET_LENGTH; + size_t pos; + ptrdiff_t tombstone = -1; + stbds_hash_bucket *bucket; + + // stored hash values are forbidden from being 0, so we can detect empty slots to early out quickly + if (hash < 2) hash += 2; + + pos = stbds_probe_position(hash, table->slot_count, table->slot_count_log2); + + for (;;) { + size_t limit, i; + STBDS_STATS(++stbds_hash_probes); + bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT]; + + // start searching from pos to end of bucket + for (i=pos & STBDS_BUCKET_MASK; i < STBDS_BUCKET_LENGTH; ++i) { + if (bucket->hash[i] == hash) { + if (stbds_is_key_equal(raw_a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { + stbds_temp(a) = bucket->index[i]; + if (mode >= STBDS_HM_STRING) + stbds_temp_key(a) = * (char **) ((char *) raw_a + elemsize*bucket->index[i] + keyoffset); + return STBDS_ARR_TO_HASH(a,elemsize); + } + } else if (bucket->hash[i] == 0) { + pos = (pos & ~STBDS_BUCKET_MASK) + i; + goto found_empty_slot; + } else if (tombstone < 0) { + if (bucket->index[i] == STBDS_INDEX_DELETED) + tombstone = (ptrdiff_t) ((pos & ~STBDS_BUCKET_MASK) + i); + } + } + + // search from beginning of bucket to pos + limit = pos & STBDS_BUCKET_MASK; + for (i = 0; i < limit; ++i) { + if (bucket->hash[i] == hash) { + if (stbds_is_key_equal(raw_a, elemsize, key, keysize, keyoffset, mode, bucket->index[i])) { + stbds_temp(a) = bucket->index[i]; + return STBDS_ARR_TO_HASH(a,elemsize); + } + } else if (bucket->hash[i] == 0) { + pos = (pos & ~STBDS_BUCKET_MASK) + i; + goto found_empty_slot; + } else if (tombstone < 0) { + if (bucket->index[i] == STBDS_INDEX_DELETED) + tombstone = (ptrdiff_t) ((pos & ~STBDS_BUCKET_MASK) + i); + } + } + + // quadratic probing + pos += step; + step += STBDS_BUCKET_LENGTH; + pos &= (table->slot_count-1); + } + found_empty_slot: + if (tombstone >= 0) { + pos = tombstone; + --table->tombstone_count; + } + ++table->used_count; + + { + ptrdiff_t i = (ptrdiff_t) stbds_arrlen(a); + // we want to do stbds_arraddn(1), but we can't use the macros since we don't have something of the right type + if ((size_t) i+1 > stbds_arrcap(a)) + *(void **) &a = stbds_arrgrowf(a, elemsize, 1, 0); + raw_a = STBDS_ARR_TO_HASH(a,elemsize); + + STBDS_ASSERT((size_t) i+1 <= stbds_arrcap(a)); + stbds_header(a)->length = i+1; + bucket = &table->storage[pos >> STBDS_BUCKET_SHIFT]; + bucket->hash[pos & STBDS_BUCKET_MASK] = hash; + bucket->index[pos & STBDS_BUCKET_MASK] = i-1; + stbds_temp(a) = i-1; + + switch (table->string.mode) { + case STBDS_SH_STRDUP: stbds_temp_key(a) = *(char **) ((char *) a + elemsize*i) = stbds_strdup((char*) key); break; + case STBDS_SH_ARENA: stbds_temp_key(a) = *(char **) ((char *) a + elemsize*i) = stbds_stralloc(&table->string, (char*)key); break; + case STBDS_SH_DEFAULT: stbds_temp_key(a) = *(char **) ((char *) a + elemsize*i) = (char *) key; break; + default: memcpy((char *) a + elemsize*i, key, keysize); break; + } + } + return STBDS_ARR_TO_HASH(a,elemsize); + } +} + +void * stbds_shmode_func(size_t elemsize, int mode) +{ + void *a = stbds_arrgrowf(0, elemsize, 0, 1); + stbds_hash_index *h; + memset(a, 0, elemsize); + stbds_header(a)->length = 1; + stbds_header(a)->hash_table = h = (stbds_hash_index *) stbds_make_hash_index(STBDS_BUCKET_LENGTH, NULL); + h->string.mode = (unsigned char) mode; + return STBDS_ARR_TO_HASH(a,elemsize); +} + +void * stbds_hmdel_key(void *a, size_t elemsize, void *key, size_t keysize, size_t keyoffset, int mode) +{ + if (a == NULL) { + return 0; + } else { + stbds_hash_index *table; + void *raw_a = STBDS_HASH_TO_ARR(a,elemsize); + table = (stbds_hash_index *) stbds_header(raw_a)->hash_table; + stbds_temp(raw_a) = 0; + if (table == 0) { + return a; + } else { + ptrdiff_t slot; + slot = stbds_hm_find_slot(a, elemsize, key, keysize, keyoffset, mode); + if (slot < 0) + return a; + else { + stbds_hash_bucket *b = &table->storage[slot >> STBDS_BUCKET_SHIFT]; + int i = slot & STBDS_BUCKET_MASK; + ptrdiff_t old_index = b->index[i]; + ptrdiff_t final_index = (ptrdiff_t) stbds_arrlen(raw_a)-1-1; // minus one for the raw_a vs a, and minus one for 'last' + STBDS_ASSERT(slot < (ptrdiff_t) table->slot_count); + --table->used_count; + ++table->tombstone_count; + stbds_temp(raw_a) = 1; + STBDS_ASSERT(table->used_count >= 0); + //STBDS_ASSERT(table->tombstone_count < table->slot_count/4); + b->hash[i] = STBDS_HASH_DELETED; + b->index[i] = STBDS_INDEX_DELETED; + + if (mode == STBDS_HM_STRING && table->string.mode == STBDS_SH_STRDUP) + STBDS_FREE(NULL, *(char**) ((char *) a+elemsize*old_index)); + + // if indices are the same, memcpy is a no-op, but back-pointer-fixup will fail, so skip + if (old_index != final_index) { + // swap delete + memmove((char*) a + elemsize*old_index, (char*) a + elemsize*final_index, elemsize); + + // now find the slot for the last element + if (mode == STBDS_HM_STRING) + slot = stbds_hm_find_slot(a, elemsize, *(char**) ((char *) a+elemsize*old_index + keyoffset), keysize, keyoffset, mode); + else + slot = stbds_hm_find_slot(a, elemsize, (char* ) a+elemsize*old_index + keyoffset, keysize, keyoffset, mode); + STBDS_ASSERT(slot >= 0); + b = &table->storage[slot >> STBDS_BUCKET_SHIFT]; + i = slot & STBDS_BUCKET_MASK; + STBDS_ASSERT(b->index[i] == final_index); + b->index[i] = old_index; + } + stbds_header(raw_a)->length -= 1; + + if (table->used_count < table->used_count_shrink_threshold && table->slot_count > STBDS_BUCKET_LENGTH) { + stbds_header(raw_a)->hash_table = stbds_make_hash_index(table->slot_count>>1, table); + STBDS_FREE(NULL, table); + STBDS_STATS(++stbds_hash_shrink); + } else if (table->tombstone_count > table->tombstone_count_threshold) { + stbds_header(raw_a)->hash_table = stbds_make_hash_index(table->slot_count , table); + STBDS_FREE(NULL, table); + STBDS_STATS(++stbds_hash_rebuild); + } + + return a; + } + } + } + /* NOTREACHED */ +} + +static char *stbds_strdup(char *str) +{ + // to keep replaceable allocator simple, we don't want to use strdup. + // rolling our own also avoids problem of strdup vs _strdup + size_t len = strlen(str)+1; + char *p = (char*) STBDS_REALLOC(NULL, 0, len); + memmove(p, str, len); + return p; +} + +#ifndef STBDS_STRING_ARENA_BLOCKSIZE_MIN +#define STBDS_STRING_ARENA_BLOCKSIZE_MIN 512u +#endif +#ifndef STBDS_STRING_ARENA_BLOCKSIZE_MAX +#define STBDS_STRING_ARENA_BLOCKSIZE_MAX (1u<<20) +#endif + +char *stbds_stralloc(stbds_string_arena *a, char *str) +{ + char *p; + size_t len = strlen(str)+1; + if (len > a->remaining) { + // compute the next blocksize + size_t blocksize = a->block; + + // size is 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, etc., so that + // there are log(SIZE) allocations to free when we destroy the table + blocksize = (size_t) (STBDS_STRING_ARENA_BLOCKSIZE_MIN) << (blocksize>>1); + + // if size is under 1M, advance to next blocktype + if (blocksize < (size_t)(STBDS_STRING_ARENA_BLOCKSIZE_MAX)) + ++a->block; + + if (len > blocksize) { + // if string is larger than blocksize, then just allocate the full size. + // note that we still advance string_block so block size will continue + // increasing, so e.g. if somebody only calls this with 1000-long strings, + // eventually the arena will start doubling and handling those as well + stbds_string_block *sb = (stbds_string_block *) STBDS_REALLOC(NULL, 0, sizeof(*sb)-8 + len); + memmove(sb->storage, str, len); + if (a->storage) { + // insert it after the first element, so that we don't waste the space there + sb->next = a->storage->next; + a->storage->next = sb; + } else { + sb->next = 0; + a->storage = sb; + a->remaining = 0; // this is redundant, but good for clarity + } + return sb->storage; + } else { + stbds_string_block *sb = (stbds_string_block *) STBDS_REALLOC(NULL, 0, sizeof(*sb)-8 + blocksize); + sb->next = a->storage; + a->storage = sb; + a->remaining = blocksize; + } + } + + STBDS_ASSERT(len <= a->remaining); + p = a->storage->storage + a->remaining - len; + a->remaining -= len; + memmove(p, str, len); + return p; +} + +void stbds_strreset(stbds_string_arena *a) +{ + stbds_string_block *x,*y; + x = a->storage; + while (x) { + y = x->next; + STBDS_FREE(NULL, x); + x = y; + } + memset(a, 0, sizeof(*a)); +} + +#endif + +////////////////////////////////////////////////////////////////////////////// +// +// UNIT TESTS +// + +#ifdef STBDS_UNIT_TESTS +#include +#ifdef STBDS_ASSERT_WAS_UNDEFINED +#undef STBDS_ASSERT +#endif +#ifndef STBDS_ASSERT +#define STBDS_ASSERT assert +#include +#endif + +typedef struct { int key,b,c,d; } stbds_struct; +typedef struct { int key[2],b,c,d; } stbds_struct2; + +static char buffer[256]; +char *strkey(int n) +{ +#if defined(_WIN32) && defined(__STDC_WANT_SECURE_LIB__) + sprintf_s(buffer, sizeof(buffer), "test_%d", n); +#else + sprintf(buffer, "test_%d", n); +#endif + return buffer; +} + +void stbds_unit_tests(void) +{ +#if defined(_MSC_VER) && _MSC_VER <= 1200 && defined(__cplusplus) + // VC6 C++ doesn't like the template<> trick on unnamed structures, so do nothing! + STBDS_ASSERT(0); +#else + const int testsize = 100000; + const int testsize2 = testsize/20; + int *arr=NULL; + struct { int key; int value; } *intmap = NULL; + struct { char *key; int value; } *strmap = NULL, s; + struct { stbds_struct key; int value; } *map = NULL; + stbds_struct *map2 = NULL; + stbds_struct2 *map3 = NULL; + stbds_string_arena sa = { 0 }; + int key3[2] = { 1,2 }; + ptrdiff_t temp; + + int i,j; + + STBDS_ASSERT(arrlen(arr)==0); + for (i=0; i < 20000; i += 50) { + for (j=0; j < i; ++j) + arrpush(arr,j); + arrfree(arr); + } + + for (i=0; i < 4; ++i) { + arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4); + arrdel(arr,i); + arrfree(arr); + arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4); + arrdelswap(arr,i); + arrfree(arr); + } + + for (i=0; i < 5; ++i) { + arrpush(arr,1); arrpush(arr,2); arrpush(arr,3); arrpush(arr,4); + stbds_arrins(arr,i,5); + STBDS_ASSERT(arr[i] == 5); + if (i < 4) + STBDS_ASSERT(arr[4] == 4); + arrfree(arr); + } + + i = 1; + STBDS_ASSERT(hmgeti(intmap,i) == -1); + hmdefault(intmap, -2); + STBDS_ASSERT(hmgeti(intmap, i) == -1); + STBDS_ASSERT(hmget (intmap, i) == -2); + for (i=0; i < testsize; i+=2) + hmput(intmap, i, i*5); + for (i=0; i < testsize; i+=1) { + if (i & 1) STBDS_ASSERT(hmget(intmap, i) == -2 ); + else STBDS_ASSERT(hmget(intmap, i) == i*5); + if (i & 1) STBDS_ASSERT(hmget_ts(intmap, i, temp) == -2 ); + else STBDS_ASSERT(hmget_ts(intmap, i, temp) == i*5); + } + for (i=0; i < testsize; i+=2) + hmput(intmap, i, i*3); + for (i=0; i < testsize; i+=1) + if (i & 1) STBDS_ASSERT(hmget(intmap, i) == -2 ); + else STBDS_ASSERT(hmget(intmap, i) == i*3); + for (i=2; i < testsize; i+=4) + hmdel(intmap, i); // delete half the entries + for (i=0; i < testsize; i+=1) + if (i & 3) STBDS_ASSERT(hmget(intmap, i) == -2 ); + else STBDS_ASSERT(hmget(intmap, i) == i*3); + for (i=0; i < testsize; i+=1) + hmdel(intmap, i); // delete the rest of the entries + for (i=0; i < testsize; i+=1) + STBDS_ASSERT(hmget(intmap, i) == -2 ); + hmfree(intmap); + for (i=0; i < testsize; i+=2) + hmput(intmap, i, i*3); + hmfree(intmap); + + #if defined(__clang__) || defined(__GNUC__) + #ifndef __cplusplus + intmap = NULL; + hmput(intmap, 15, 7); + hmput(intmap, 11, 3); + hmput(intmap, 9, 5); + STBDS_ASSERT(hmget(intmap, 9) == 5); + STBDS_ASSERT(hmget(intmap, 11) == 3); + STBDS_ASSERT(hmget(intmap, 15) == 7); + #endif + #endif + + for (i=0; i < testsize; ++i) + stralloc(&sa, strkey(i)); + strreset(&sa); + + { + s.key = "a", s.value = 1; + shputs(strmap, s); + STBDS_ASSERT(*strmap[0].key == 'a'); + STBDS_ASSERT(strmap[0].key == s.key); + STBDS_ASSERT(strmap[0].value == s.value); + shfree(strmap); + } + + { + s.key = "a", s.value = 1; + sh_new_strdup(strmap); + shputs(strmap, s); + STBDS_ASSERT(*strmap[0].key == 'a'); + STBDS_ASSERT(strmap[0].key != s.key); + STBDS_ASSERT(strmap[0].value == s.value); + shfree(strmap); + } + + { + s.key = "a", s.value = 1; + sh_new_arena(strmap); + shputs(strmap, s); + STBDS_ASSERT(*strmap[0].key == 'a'); + STBDS_ASSERT(strmap[0].key != s.key); + STBDS_ASSERT(strmap[0].value == s.value); + shfree(strmap); + } + + for (j=0; j < 2; ++j) { + STBDS_ASSERT(shgeti(strmap,"foo") == -1); + if (j == 0) + sh_new_strdup(strmap); + else + sh_new_arena(strmap); + STBDS_ASSERT(shgeti(strmap,"foo") == -1); + shdefault(strmap, -2); + STBDS_ASSERT(shgeti(strmap,"foo") == -1); + for (i=0; i < testsize; i+=2) + shput(strmap, strkey(i), i*3); + for (i=0; i < testsize; i+=1) + if (i & 1) STBDS_ASSERT(shget(strmap, strkey(i)) == -2 ); + else STBDS_ASSERT(shget(strmap, strkey(i)) == i*3); + for (i=2; i < testsize; i+=4) + shdel(strmap, strkey(i)); // delete half the entries + for (i=0; i < testsize; i+=1) + if (i & 3) STBDS_ASSERT(shget(strmap, strkey(i)) == -2 ); + else STBDS_ASSERT(shget(strmap, strkey(i)) == i*3); + for (i=0; i < testsize; i+=1) + shdel(strmap, strkey(i)); // delete the rest of the entries + for (i=0; i < testsize; i+=1) + STBDS_ASSERT(shget(strmap, strkey(i)) == -2 ); + shfree(strmap); + } + + { + struct { char *key; char value; } *hash = NULL; + char name[4] = "jen"; + shput(hash, "bob" , 'h'); + shput(hash, "sally" , 'e'); + shput(hash, "fred" , 'l'); + shput(hash, "jen" , 'x'); + shput(hash, "doug" , 'o'); + + shput(hash, name , 'l'); + shfree(hash); + } + + for (i=0; i < testsize; i += 2) { + stbds_struct s = { i,i*2,i*3,i*4 }; + hmput(map, s, i*5); + } + + for (i=0; i < testsize; i += 1) { + stbds_struct s = { i,i*2,i*3 ,i*4 }; + stbds_struct t = { i,i*2,i*3+1,i*4 }; + if (i & 1) STBDS_ASSERT(hmget(map, s) == 0); + else STBDS_ASSERT(hmget(map, s) == i*5); + if (i & 1) STBDS_ASSERT(hmget_ts(map, s, temp) == 0); + else STBDS_ASSERT(hmget_ts(map, s, temp) == i*5); + //STBDS_ASSERT(hmget(map, t.key) == 0); + } + + for (i=0; i < testsize; i += 2) { + stbds_struct s = { i,i*2,i*3,i*4 }; + hmputs(map2, s); + } + hmfree(map); + + for (i=0; i < testsize; i += 1) { + stbds_struct s = { i,i*2,i*3,i*4 }; + stbds_struct t = { i,i*2,i*3+1,i*4 }; + if (i & 1) STBDS_ASSERT(hmgets(map2, s.key).d == 0); + else STBDS_ASSERT(hmgets(map2, s.key).d == i*4); + //STBDS_ASSERT(hmgetp(map2, t.key) == 0); + } + hmfree(map2); + + for (i=0; i < testsize; i += 2) { + stbds_struct2 s = { { i,i*2 }, i*3,i*4, i*5 }; + hmputs(map3, s); + } + for (i=0; i < testsize; i += 1) { + stbds_struct2 s = { { i,i*2}, i*3, i*4, i*5 }; + stbds_struct2 t = { { i,i*2}, i*3+1, i*4, i*5 }; + if (i & 1) STBDS_ASSERT(hmgets(map3, s.key).d == 0); + else STBDS_ASSERT(hmgets(map3, s.key).d == i*5); + //STBDS_ASSERT(hmgetp(map3, t.key) == 0); + } +#endif +} +#endif + + +/* +------------------------------------------------------------------------------ +This software is available under 2 licenses -- choose whichever you prefer. +------------------------------------------------------------------------------ +ALTERNATIVE A - MIT License +Copyright (c) 2019 Sean Barrett +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. +------------------------------------------------------------------------------ +ALTERNATIVE B - Public Domain (www.unlicense.org) +This is free and unencumbered software released into the public domain. +Anyone is free to copy, modify, publish, use, compile, sell, or distribute this +software, either in source code form or as a compiled binary, for any purpose, +commercial or non-commercial, and by any means. +In jurisdictions that recognize copyright laws, the author or authors of this +software dedicate any and all copyright interest in the software to the public +domain. We make this dedication for the benefit of the public at large and to +the detriment of our heirs and successors. We intend this dedication to be an +overt act of relinquishment in perpetuity of all present and future rights to +this software under copyright law. +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 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. +------------------------------------------------------------------------------ +*/ diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/.bazelrc --- a/gara/android/firebase-cloud-messaging/.bazelrc Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ -common --enable_workspace -common --experimental_google_legacy_api -common --experimental_enable_android_migration_apis -# Necesary until bazel 7.2.0rc2 or later is released (https://github.com/bazelbuild/bazel/issues/22415) -common --nocheck_visibility diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/.bazelversion --- a/gara/android/firebase-cloud-messaging/.bazelversion Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1 +0,0 @@ -7.2.0rc1 diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/BUILD --- a/gara/android/firebase-cloud-messaging/BUILD Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ -platform( - name = "arm64-v8a", - constraint_values = [ - "@platforms//cpu:arm64", - "@platforms//os:android", - ], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/README.md --- a/gara/android/firebase-cloud-messaging/README.md Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,96 +0,0 @@ - -# Bazel Firebase Cloud Messaging (FCM) example - -FCM requires certain information about your app (API key, app ID, project id, -etc) to be present in the `res/values/values.xml` resource file. This example -shows how to use the tools provided in the -[bazelbuild/tools_android](https://github.com/bazelbuild/tools_android) repo to -generate the `values.xml` file from the `google-services.json` file from your -Firebase console. - -## Building the Example - -To build the example: - -1. Make sure the `ANDROID_HOME` environment variable is set to the absolute path - of your Android SDK. - -2. Go to the Firebase console for your project, and in Settings, download - `google-service.json`, and replace the sample file in the `app` directory. - -3. Run `bazel build //app` in the project. - -## Applying the Example to Your Code - -To apply this example to your code: - -1. Add the following to your `WORKSPACE` file: -```python -TOOLS_ANDROID_VERSION = "0.1" -http_archive( - name = "tools_android", - strip_prefix = "tools_android-" + TOOLS_ANDROID_VERSION, - url = "https://github.com/bazelbuild/tools_android/archive/%s.tar.gz" % TOOLS_ANDROID_VERSION, -) -load("@tools_android//tools/googleservices:defs.bzl", "google_services_workspace_dependencies") -google_services_workspace_dependencies() -``` - -2. Add the following to your `BUILD` file: -```python -load("@tools_android//tools/googleservices:defs.bzl", "google_services_xml") - -GOOGLE_SERVICES_XML = google_services_xml( - package_name = "com.example.myapplication", - google_services_json = "google-services.json" -) -``` - -3. Add `GOOGLE_SERVICES_XML` to the `resource_files` attribute of your - `android_binary` rule. For example: -```python -android_binary( - ... - resource_files = glob(["src/main/res/**"]) + GOOGLE_SERVICES_XML, - ... -) -``` - -4. Bazel's `AndroidManifest.xml` merging logic does not merge permissions from - dependent libraries (see issue [#5411](https://github.com/bazelbuild/bazel/issues/5411)). - You may need to add the following permissions to the `AndroidManifest.xml` of - your top-level `android_binary` rule: -```xml - - - - -``` - -## Manual Integration - -It's also possible to run the Google Services values.xml generator manually and -add the results to your project: - -1. Go to the Firebase console for your project, and in Settings, download - `google-service.json`. - -2. From the workspace root of the `tools_android` project, run the Google - Services XML generator: -``` - bazel run //third_party/googleservices:GenerateGoogleServicesXml -- \ - com.example.myapplication \ - /absolute/path/to/google-services.json \ - /tmp/values.xml -``` - The arguments are the package name for your app, the absolute file path to - the `google-services.json` file, and finally the file path for `values.xml`. - -3. Merge the resulting `values.xml` file into your `values.xml` file (or put the - file into your `res/values` directory if you don't already have a - `values.xml` file). Alternatively, the `values.xml` file can be put into a - separate `res/values` directory and added to the `resource_files`. For the - example here, if `values.xml` is in - `app/src/main/google_services_xml/res/values/values.xml`, the `BUILD` file - would have - `resource_files = glob(["src/main/res/**"]) + ["src/main/google_services_xml/res/values/values.xml"],`. diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/WORKSPACE --- a/gara/android/firebase-cloud-messaging/WORKSPACE Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,81 +0,0 @@ -# FIXME(alexeagle): move to bzlmod -load("@bazel_tools//tools/build_defs/repo:http.bzl", "http_archive") - -RULES_JVM_EXTERNAL_TAG = "5.3" - -RULES_JVM_EXTERNAL_SHA = "d31e369b854322ca5098ea12c69d7175ded971435e55c18dd9dd5f29cc5249ac" - -http_archive( - name = "rules_jvm_external", - sha256 = RULES_JVM_EXTERNAL_SHA, - strip_prefix = "rules_jvm_external-%s" % RULES_JVM_EXTERNAL_TAG, - url = - "https://github.com/bazelbuild/rules_jvm_external/releases/download/%s/rules_jvm_external-%s.tar.gz" % (RULES_JVM_EXTERNAL_TAG, RULES_JVM_EXTERNAL_TAG), -) - -load("@rules_jvm_external//:defs.bzl", "maven_install") - -maven_install( - aar_import_bzl_label = "@rules_android//rules:rules.bzl", - artifacts = [ - "com.google.firebase:firebase-messaging:17.0.0", - "com.android.support:appcompat-v7:26.1.0", - "com.android.support.constraint:constraint-layout:1.0.2", - "com.google.code.gson:gson:2.8.2", - ], - # See https://github.com/bazelbuild/rules_jvm_external/#repository-aliases - # This can be removed if none of your external dependencies uses `maven_jar`. - generate_compat_repositories = True, - repositories = [ - "https://jcenter.bintray.com", - "https://maven.google.com", - "https://repo1.maven.org/maven2", - ], - use_starlark_android_rules = True, - version_conflict_policy = "pinned", -) - -load("@maven//:compat.bzl", "compat_repositories") - -compat_repositories() - -TOOLS_ANDROID_COMMIT = "0e864ba5a86958513658250de587416d8e17c481" - -http_archive( - name = "tools_android", - repo_mapping = { - "@com_google_code_gson_2_8_2": "@com_google_code_gson_gson", - }, - sha256 = "57c50d6331ba578fc8adfcede20ef12b437cb4cc2edf60c852e4b834eefee5fc", - strip_prefix = "tools_android-" + TOOLS_ANDROID_COMMIT, - url = "https://github.com/bazelbuild/tools_android/archive/%s.tar.gz" % TOOLS_ANDROID_COMMIT, -) - -RULES_ANDROID_COMMIT = "93e27030d3f0defa39cbbc35195638cb772b0c27" - -http_archive( - name = "rules_android", - sha256 = "71cae2413868a24f17d43fd595af6f3905d2e5b3235f76514f54800bfd90c903", - strip_prefix = "rules_android-" + RULES_ANDROID_COMMIT, - urls = ["https://github.com/bazelbuild/rules_android/archive/%s.zip" % RULES_ANDROID_COMMIT], -) - -load("@rules_android//:prereqs.bzl", "rules_android_prereqs") - -rules_android_prereqs() - -load("@rules_android//:defs.bzl", "rules_android_workspace") - -rules_android_workspace() - -load("@rules_android//rules:rules.bzl", "android_sdk_repository") - -# Requires that the ANDROID_HOME environment variable is set to the Android SDK path. -android_sdk_repository( - name = "androidsdk", -) - -register_toolchains( - "@rules_android//toolchains/android:android_default_toolchain", - "@rules_android//toolchains/android_sdk:android_sdk_tools", -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/BUILD --- a/gara/android/firebase-cloud-messaging/app/BUILD Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,29 +0,0 @@ -load("@rules_android//android:rules.bzl", "android_binary") -load("@tools_android//tools/googleservices:defs.bzl", "google_services_xml") - -GOOGLE_SERVICES_XML = google_services_xml( - package_name = "com.example.myapplication", - google_services_json = "google-services.json", -) - -android_binary( - name = "app", - srcs = glob(["src/main/java/**/*.java"]), - # this sets the java package for the R class, since this android_binary - # rule isn't under a java root (i.e., some directory named "java" for the - # root of the java code for the app). - custom_package = "com.example.myapplication", - manifest = "src/main/AndroidManifest.xml", - manifest_values = { - "minSdkVersion": "15", - "applicationId": "com.example.myapplication", - }, - resource_files = glob(["src/main/res/**"]) + GOOGLE_SERVICES_XML, - deps = [ - "@maven//:com_google_firebase_firebase_messaging", - "@maven//:com_google_firebase_firebase_iid", - "@maven//:com_android_support_appcompat_v7", - # activity_main layout uses contraints - "@maven//:com_android_support_constraint_constraint_layout", - ], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/google-services.json --- a/gara/android/firebase-cloud-messaging/app/google-services.json Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,42 +0,0 @@ -{ - "project_info": { - "project_number": "12345678901", - "firebase_url": "https://replace.with.your.project.example.com", - "project_id": "example-123", - "storage_bucket": "replace.with.your.project.example.org" - }, - "client": [ - { - "client_info": { - "mobilesdk_app_id": "1:12345678901:android:abcdef1111111111", - "android_client_info": { - "package_name": "com.example.myapplication" - } - }, - "oauth_client": [ - { - "client_id": "12345678901-abcdabcdabcdabcdabcdabcdabcdabcd.apps.googleusercontent.com", - "client_type": 1 - } - ], - "api_key": [ - { - "current_key": "abcdef12345678901_abcdef123456_abcdef12" - } - ], - "services": { - "analytics_service": { - "status": 1 - }, - "appinvite_service": { - "status": 1, - "other_platform_oauth_client": [] - }, - "ads_service": { - "status": 2 - } - } - } - ], - "configuration_version": "1" -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/AndroidManifest.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/AndroidManifest.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,44 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/java/com/example/myapplication/MainActivity.java --- a/gara/android/firebase-cloud-messaging/app/src/main/java/com/example/myapplication/MainActivity.java Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,18 +0,0 @@ -package com.example.myapplication; - -import android.support.v7.app.AppCompatActivity; -import android.os.Bundle; -import android.util.Log; - -import com.google.firebase.iid.FirebaseInstanceId; - -public class MainActivity extends AppCompatActivity { - - @Override - protected void onCreate(Bundle savedInstanceState) { - super.onCreate(savedInstanceState); - setContentView(R.layout.activity_main); - - Log.i("myapp", "token: " + FirebaseInstanceId.getInstance().getToken()); - } -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/java/com/example/myapplication/MyFirebaseInstanceIdService.java --- a/gara/android/firebase-cloud-messaging/app/src/main/java/com/example/myapplication/MyFirebaseInstanceIdService.java Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,21 +0,0 @@ -package com.example.myapplication; - -import android.util.Log; - -import com.google.firebase.iid.FirebaseInstanceId; -import com.google.firebase.iid.FirebaseInstanceIdService; - -public class MyFirebaseInstanceIdService extends FirebaseInstanceIdService { - @Override - public void onTokenRefresh() { - // Get updated InstanceID token. - String refreshedToken = FirebaseInstanceId.getInstance().getToken(); - Log.d("myapp", "Refreshed token: " + refreshedToken); - - // If you want to send messages to this application instance or - // manage this apps subscriptions on the server side, send the - // Instance ID token to your app server. - } - -} - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/java/com/example/myapplication/MyFirebaseMessagingService.java --- a/gara/android/firebase-cloud-messaging/app/src/main/java/com/example/myapplication/MyFirebaseMessagingService.java Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,39 +0,0 @@ -package com.example.myapplication; - -import android.util.Log; - -import com.google.firebase.messaging.FirebaseMessagingService; -import com.google.firebase.messaging.RemoteMessage; - -public class MyFirebaseMessagingService extends FirebaseMessagingService { - @Override - public void onMessageReceived(RemoteMessage remoteMessage) { - - // TODO(developer): Handle FCM messages here. - // Not getting messages here? See why this may be: https://goo.gl/39bRNJ - Log.d("myapp", "From: " + remoteMessage.getFrom()); - - // Check if message contains a data payload. - if (remoteMessage.getData().size() > 0) { - Log.d("myapp", "Message data payload: " + remoteMessage.getData()); - - if (/* Check if data needs to be processed by long running job */ true) { - // For long-running tasks (10 seconds or more) use Firebase Job Dispatcher. - //scheduleJob(); - } else { - // Handle message within 10 seconds - //handleNow(); - } - - } - - // Check if message contains a notification payload. - if (remoteMessage.getNotification() != null) { - Log.d("myapp", "Message Notification Body: " + remoteMessage.getNotification().getBody()); - } - - // Also if you intend on generating your own notifications as a result of a received FCM - // message, here is where that should be initiated. See sendNotification method below. - } - -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/drawable-v24/ic_launcher_foreground.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/drawable-v24/ic_launcher_foreground.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/drawable/ic_launcher_background.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/drawable/ic_launcher_background.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,170 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/layout/activity_main.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/layout/activity_main.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,18 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-anydpi-v26/ic_launcher.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-anydpi-v26/ic_launcher.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ - - - - - \ No newline at end of file diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-anydpi-v26/ic_launcher_round.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-anydpi-v26/ic_launcher_round.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ - - - - - \ No newline at end of file diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-mdpi/ic_launcher.png Binary file gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-mdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-mdpi/ic_launcher_round.png Binary file gara/android/firebase-cloud-messaging/app/src/main/res/mipmap-mdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/values/colors.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/values/colors.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ - - - #3F51B5 - #303F9F - #FF4081 - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/values/strings.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/values/strings.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,3 +0,0 @@ - - My Application - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/firebase-cloud-messaging/app/src/main/res/values/styles.xml --- a/gara/android/firebase-cloud-messaging/app/src/main/res/values/styles.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/.bazelversion --- a/gara/android/jetpack-compose/.bazelversion Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1 +0,0 @@ -6.5.0 diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/BUILD.bazel --- a/gara/android/jetpack-compose/BUILD.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,17 +0,0 @@ -load("@io_bazel_rules_kotlin//kotlin:core.bzl", "kt_compiler_plugin") - -kt_compiler_plugin( - name = "jetpack_compose_compiler_plugin", - id = "androidx.compose.compiler", - target_embedded_compiler = True, - visibility = ["//visibility:public"], - deps = ["@maven//:androidx_compose_compiler_compiler"], -) - -platform( - name = "arm64-v8a", - constraint_values = [ - "@platforms//cpu:arm64", - "@platforms//os:android", - ], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/MODULE.bazel --- a/gara/android/jetpack-compose/MODULE.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,38 +0,0 @@ -"Bazel dependencies" - -bazel_dep(name = "platforms", version = "0.0.11") -bazel_dep(name = "rules_jvm_external", version = "5.3") - -maven = use_extension("@rules_jvm_external//:extensions.bzl", "maven") -maven.install( - artifacts = [ - "androidx.appcompat:appcompat:1.5.1", - # Jetpack Compose Dependencies - "androidx.activity:activity-compose:1.6.0", - "androidx.compose.material:material:1.2.1", - "androidx.compose.ui:ui:1.2.1", - "androidx.compose.ui:ui-tooling:1.2.1", - "androidx.compose.compiler:compiler:1.3.2", - "androidx.compose.runtime:runtime:1.2.1", - # Dependencies needed to manage version conflicts - "androidx.core:core:1.6.0", - "androidx.core:core-ktx:1.6.0", - "androidx.savedstate:savedstate-ktx:1.2.0", - "androidx.savedstate:savedstate:1.2.0", - "androidx.lifecycle:lifecycle-livedata-core-ktx:2.5.1", - "androidx.lifecycle:lifecycle-livedata-core:2.5.1", - "androidx.lifecycle:lifecycle-livedata:2.5.1", - "androidx.lifecycle:lifecycle-process:2.5.1", - "androidx.lifecycle:lifecycle-runtime-ktx:2.5.1", - "androidx.lifecycle:lifecycle-runtime:2.5.1", - "androidx.lifecycle:lifecycle-service:2.5.1", - "androidx.lifecycle:lifecycle-viewmodel-ktx:2.5.1", - "androidx.lifecycle:lifecycle-viewmodel-savedstate:2.5.1", - "androidx.lifecycle:lifecycle-viewmodel:2.5.1", - ], - repositories = [ - "https://maven.google.com", - "https://repo1.maven.org/maven2", - ], -) -use_repo(maven, "maven") diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/README.md --- a/gara/android/jetpack-compose/README.md Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ -# Android Jetpack Compose with Bazel example - -## Documentation - -For the full documentation, please visit -the [rules_kotlin documentation page](https://github.com/bazelbuild/rules_kotlin/blob/master/docs/kotlin.md). - -## Instructions - -1) Launch emulator -2) Run `bazel mobile-install //app/src/main:app --start_app` diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/WORKSPACE --- a/gara/android/jetpack-compose/WORKSPACE Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,42 +0,0 @@ -# FIXME(alexeagle): move to bzlmod -workspace(name = "bazel_android_sample_project") - -load("@bazel_tools//tools/build_defs/repo:http.bzl", "http_archive") - -_KOTLIN_COMPILER_VERSION = "1.7.20" - -_KOTLIN_COMPILER_SHA = "5e3c8d0f965410ff12e90d6f8dc5df2fc09fd595a684d514616851ce7e94ae7d" - -## Android - -http_archive( - name = "build_bazel_rules_android", - sha256 = "cd06d15dd8bb59926e4d65f9003bfc20f9da4b2519985c27e190cddc8b7a7806", - strip_prefix = "rules_android-0.1.1", - urls = ["https://github.com/bazelbuild/rules_android/archive/v0.1.1.zip"], -) - -load("@build_bazel_rules_android//android:rules.bzl", "android_sdk_repository") - -android_sdk_repository(name = "androidsdk") - -## Kotlin - -http_archive( - name = "io_bazel_rules_kotlin", - sha256 = "f033fa36f51073eae224f18428d9493966e67c27387728b6be2ebbdae43f140e", - url = "https://github.com/bazelbuild/rules_kotlin/releases/download/v1.7.0-RC-3/rules_kotlin_release.tgz", -) - -load("@io_bazel_rules_kotlin//kotlin:repositories.bzl", "kotlin_repositories", "kotlinc_version") - -kotlin_repositories( - compiler_release = kotlinc_version( - release = _KOTLIN_COMPILER_VERSION, - sha256 = _KOTLIN_COMPILER_SHA, - ), -) - -load("@io_bazel_rules_kotlin//kotlin:core.bzl", "kt_register_toolchains") - -kt_register_toolchains() diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/AndroidManifest.xml --- a/gara/android/jetpack-compose/app/src/main/AndroidManifest.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/BUILD.bazel --- a/gara/android/jetpack-compose/app/src/main/BUILD.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,27 +0,0 @@ -load("@build_bazel_rules_android//android:rules.bzl", "android_binary") -load("@io_bazel_rules_kotlin//kotlin:android.bzl", "kt_android_library") - -kt_android_library( - name = "lib", - srcs = ["java/com/example/android/bazel/MainActivity.kt"], - custom_package = "com.example.android.bazel", - manifest = "LibraryManifest.xml", - plugins = ["//:jetpack_compose_compiler_plugin"], - resource_files = glob(["res/**/*"]), - deps = [ - "@maven//:androidx_activity_activity_compose", - "@maven//:androidx_appcompat_appcompat", - "@maven//:androidx_compose_foundation_foundation", - "@maven//:androidx_compose_foundation_foundation_layout", - "@maven//:androidx_compose_runtime_runtime", - "@maven//:androidx_compose_ui_ui", - "@maven//:androidx_compose_ui_ui_tooling", - ], -) - -android_binary( - name = "app", - manifest = "AndroidManifest.xml", - manifest_values = {"applicationId": "com.example.android.bazel"}, - deps = [":lib"], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/LibraryManifest.xml --- a/gara/android/jetpack-compose/app/src/main/LibraryManifest.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,23 +0,0 @@ - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/java/com/example/android/bazel/MainActivity.kt --- a/gara/android/jetpack-compose/app/src/main/java/com/example/android/bazel/MainActivity.kt Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,38 +0,0 @@ -package com.example.android.bazel - -import android.os.Bundle -import androidx.activity.compose.setContent -import androidx.appcompat.app.AppCompatActivity -import androidx.compose.foundation.layout.Arrangement -import androidx.compose.foundation.layout.Column -import androidx.compose.foundation.layout.fillMaxSize -import androidx.compose.foundation.layout.padding -import androidx.compose.material.Text -import androidx.compose.runtime.Composable -import androidx.compose.ui.Alignment -import androidx.compose.ui.Modifier -import androidx.compose.ui.text.style.TextAlign -import androidx.compose.ui.tooling.preview.Preview -import androidx.compose.ui.unit.dp - -class MainActivity : AppCompatActivity() { - - override fun onCreate(savedInstanceState: Bundle?) { - super.onCreate(savedInstanceState) - setContent { HelloWorld("Jetpack Compose") } - } - - @Preview - @Composable - fun HelloWorld(name: String) = Column( - verticalArrangement = Arrangement.Center, - horizontalAlignment = Alignment.CenterHorizontally, - modifier = Modifier - .fillMaxSize() - .padding(20.dp)) { - Text( - text = "Hello $name", - textAlign = TextAlign.Center - ) - } -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/drawable-v24/ic_launcher_foreground.xml --- a/gara/android/jetpack-compose/app/src/main/res/drawable-v24/ic_launcher_foreground.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/drawable/ic_launcher_background.xml --- a/gara/android/jetpack-compose/app/src/main/res/drawable/ic_launcher_background.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,170 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-anydpi-v26/ic_launcher.xml --- a/gara/android/jetpack-compose/app/src/main/res/mipmap-anydpi-v26/ic_launcher.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ - - - - - \ No newline at end of file diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-anydpi-v26/ic_launcher_round.xml --- a/gara/android/jetpack-compose/app/src/main/res/mipmap-anydpi-v26/ic_launcher_round.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ - - - - - \ No newline at end of file diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-hdpi/ic_launcher.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-hdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-hdpi/ic_launcher_round.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-hdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-mdpi/ic_launcher.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-mdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-mdpi/ic_launcher_round.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-mdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-xhdpi/ic_launcher.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-xhdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-xhdpi/ic_launcher_round.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-xhdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-xxhdpi/ic_launcher.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-xxhdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-xxhdpi/ic_launcher_round.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-xxhdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-xxxhdpi/ic_launcher.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-xxxhdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/mipmap-xxxhdpi/ic_launcher_round.png Binary file gara/android/jetpack-compose/app/src/main/res/mipmap-xxxhdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/values/colors.xml --- a/gara/android/jetpack-compose/app/src/main/res/values/colors.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ - - - #3F51B5 - #303F9F - #FF4081 - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/values/strings.xml --- a/gara/android/jetpack-compose/app/src/main/res/values/strings.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,3 +0,0 @@ - - Built By Bazel - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/jetpack-compose/app/src/main/res/values/styles.xml --- a/gara/android/jetpack-compose/app/src/main/res/values/styles.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/.bazelrc --- a/gara/android/ndk/.bazelrc Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ -common --enable_workspace -common --experimental_google_legacy_api -common --experimental_enable_android_migration_apis -# Necesary until bazel 7.2.0rc2 or later is released (https://github.com/bazelbuild/bazel/issues/22415) -common --nocheck_visibility diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/.bazelversion --- a/gara/android/ndk/.bazelversion Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,2 +0,0 @@ -7.3.1 - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/BUILD.bazel --- a/gara/android/ndk/BUILD.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,15 +0,0 @@ -platform( - name = "arm64-v8a", - constraint_values = [ - "@platforms//cpu:arm64", - "@platforms//os:android", - ], -) - -platform( - name = "x86", - constraint_values = [ - "@platforms//cpu:x86_32", - "@platforms//os:android", - ], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/MODULE.bazel --- a/gara/android/ndk/MODULE.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,30 +0,0 @@ -"Bazel dependencies" - -bazel_dep(name = "platforms", version = "0.0.11") -bazel_dep(name = "rules_jvm_external", version = "5.3") -bazel_dep(name = "rules_cc", version = "0.0.9") -bazel_dep(name = "rules_android", version = "0.5.1") - -maven = use_extension("@rules_jvm_external//:extensions.bzl", "maven") -maven.install( - aar_import_bzl_label = "@rules_android//rules:rules.bzl", - artifacts = [ - "androidx.appcompat:appcompat:1.5.1", - "androidx.constraintlayout:constraintlayout:2.2.1", - # Needed to enforce version conflict resolution - "androidx.savedstate:savedstate:1.2.0", - "androidx.lifecycle:lifecycle-livedata-core:2.5.1", - "androidx.lifecycle:lifecycle-livedata:2.5.1", - "androidx.lifecycle:lifecycle-process:2.5.1", - "androidx.lifecycle:lifecycle-runtime:2.5.1", - "androidx.lifecycle:lifecycle-service:2.5.1", - "androidx.lifecycle:lifecycle-viewmodel-savedstate:2.5.1", - "androidx.lifecycle:lifecycle-viewmodel:2.5.1", - ], - repositories = [ - "https://maven.google.com", - "https://repo1.maven.org/maven2", - ], - use_starlark_android_rules = True, -) -use_repo(maven, "maven") diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/README.md --- a/gara/android/ndk/README.md Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,24 +0,0 @@ -# Android NDK with Bazel example - -## Documentation - -For the full documentation, please visit the [Bazel documentation page](https://bazel.build/docs/android-ndk). - -## Instructions - -1) Launch emulator -2) Run `bazel mobile-install //app/src/main:app --android_platforms=//:x86 --start_app` - - - -## Build graph - -![](/images/graph.png) - -- JNI/C++ sources goes into the `cc_library` target, `//app/src/main:jni_lib`. -- Java sources, resource files, and assets go into the `android_library` - target, `//app/src/main:lib`. This target depends on the `cc_library` target. -- The APK is built from the `android_binary` target, `//app/src/main:app`. This - target depends on the `android_library` target. - -NOTE: This graph omits the Google Maven AAR dependencies. diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/WORKSPACE --- a/gara/android/ndk/WORKSPACE Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,43 +0,0 @@ -load("@bazel_tools//tools/build_defs/repo:http.bzl", "http_archive") - -RULES_ANDROID_COMMIT = "93e27030d3f0defa39cbbc35195638cb772b0c27" - -http_archive( - name = "rules_android", - sha256 = "71cae2413868a24f17d43fd595af6f3905d2e5b3235f76514f54800bfd90c903", - strip_prefix = "rules_android-" + RULES_ANDROID_COMMIT, - urls = ["https://github.com/bazelbuild/rules_android/archive/%s.zip" % RULES_ANDROID_COMMIT], -) - -load("@rules_android//:prereqs.bzl", "rules_android_prereqs") - -rules_android_prereqs() - -load("@rules_android//:defs.bzl", "rules_android_workspace") - -rules_android_workspace() - -load("@rules_android//rules:rules.bzl", "android_sdk_repository") - -# Requires that the ANDROID_HOME environment variable is set to the Android SDK path. -android_sdk_repository( - name = "androidsdk", -) - -register_toolchains( - "@rules_android//toolchains/android:android_default_toolchain", - "@rules_android//toolchains/android_sdk:android_sdk_tools", -) - -http_archive( - name = "rules_android_ndk", - sha256 = "b1a5ddd784e6ed915c2035c0db536a278b5f50c64412128c06877115991391ef", - strip_prefix = "rules_android_ndk-877c68ef34c9f3353028bf490d269230c1990483", - url = "https://github.com/bazelbuild/rules_android_ndk/archive/877c68ef34c9f3353028bf490d269230c1990483.zip", -) - -load("@rules_android_ndk//:rules.bzl", "android_ndk_repository") - -android_ndk_repository(name = "androidndk") - -register_toolchains("@androidndk//:all") diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/AndroidManifest.xml --- a/gara/android/ndk/app/src/main/AndroidManifest.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,8 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/BUILD.bazel --- a/gara/android/ndk/app/src/main/BUILD.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,27 +0,0 @@ -load("@rules_android//android:rules.bzl", "android_binary", "android_library") -load("@rules_cc//cc:defs.bzl", "cc_library") - -android_library( - name = "lib", - srcs = ["java/com/example/android/bazel/MainActivity.java"], - custom_package = "com.example.android.bazel", - manifest = "LibraryManifest.xml", - resource_files = glob(["res/**/*"]), - deps = [ - ":jni_lib", - "@maven//:androidx_appcompat_appcompat", - "@maven//:androidx_constraintlayout_constraintlayout", - ], -) - -cc_library( - name = "jni_lib", - srcs = ["cpp/native-lib.cpp"], -) - -android_binary( - name = "app", - manifest = "AndroidManifest.xml", - manifest_values = {"applicationId": "com.example.android.bazel"}, - deps = [":lib"], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/LibraryManifest.xml --- a/gara/android/ndk/app/src/main/LibraryManifest.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,28 +0,0 @@ - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/cpp/native-lib.cpp --- a/gara/android/ndk/app/src/main/cpp/native-lib.cpp Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,13 +0,0 @@ -#include -#include - -extern "C" -JNIEXPORT jstring - -JNICALL -Java_com_example_android_bazel_MainActivity_stringFromJNI( - JNIEnv *env, - jobject /* this */) { - std::string hello = "Hello from C++"; - return env->NewStringUTF(hello.c_str()); -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/java/com/example/android/bazel/MainActivity.java --- a/gara/android/ndk/app/src/main/java/com/example/android/bazel/MainActivity.java Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,28 +0,0 @@ -package com.example.android.bazel; - -import android.os.Bundle; -import android.widget.TextView; -import androidx.appcompat.app.AppCompatActivity; - -public class MainActivity extends AppCompatActivity { - - static { - System.loadLibrary("app"); - } - - @Override - protected void onCreate(Bundle savedInstanceState) { - super.onCreate(savedInstanceState); - setContentView(R.layout.activity_main); - - // Example of a call to a native method - TextView tv = (TextView) findViewById(R.id.sample_text); - tv.setText(stringFromJNI()); - } - - /** - * A native method that is implemented by the 'native-lib' native library, - * which is packaged with this application. - */ - public native String stringFromJNI(); -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/drawable-v24/ic_launcher_foreground.xml --- a/gara/android/ndk/app/src/main/res/drawable-v24/ic_launcher_foreground.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/drawable/ic_launcher_background.xml --- a/gara/android/ndk/app/src/main/res/drawable/ic_launcher_background.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,170 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/layout/activity_main.xml --- a/gara/android/ndk/app/src/main/res/layout/activity_main.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,21 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-anydpi-v26/ic_launcher.xml --- a/gara/android/ndk/app/src/main/res/mipmap-anydpi-v26/ic_launcher.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ - - - - - \ No newline at end of file diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-anydpi-v26/ic_launcher_round.xml --- a/gara/android/ndk/app/src/main/res/mipmap-anydpi-v26/ic_launcher_round.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,5 +0,0 @@ - - - - - \ No newline at end of file diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-hdpi/ic_launcher.png Binary file gara/android/ndk/app/src/main/res/mipmap-hdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-hdpi/ic_launcher_round.png Binary file gara/android/ndk/app/src/main/res/mipmap-hdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-mdpi/ic_launcher.png Binary file gara/android/ndk/app/src/main/res/mipmap-mdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-mdpi/ic_launcher_round.png Binary file gara/android/ndk/app/src/main/res/mipmap-mdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-xhdpi/ic_launcher.png Binary file gara/android/ndk/app/src/main/res/mipmap-xhdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-xhdpi/ic_launcher_round.png Binary file gara/android/ndk/app/src/main/res/mipmap-xhdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-xxhdpi/ic_launcher.png Binary file gara/android/ndk/app/src/main/res/mipmap-xxhdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-xxhdpi/ic_launcher_round.png Binary file gara/android/ndk/app/src/main/res/mipmap-xxhdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-xxxhdpi/ic_launcher.png Binary file gara/android/ndk/app/src/main/res/mipmap-xxxhdpi/ic_launcher.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/mipmap-xxxhdpi/ic_launcher_round.png Binary file gara/android/ndk/app/src/main/res/mipmap-xxxhdpi/ic_launcher_round.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/values/colors.xml --- a/gara/android/ndk/app/src/main/res/values/colors.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ - - - #3F51B5 - #303F9F - #FF4081 - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/values/strings.xml --- a/gara/android/ndk/app/src/main/res/values/strings.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,3 +0,0 @@ - - Built By Bazel - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/app/src/main/res/values/styles.xml --- a/gara/android/ndk/app/src/main/res/values/styles.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/images/graph.png Binary file gara/android/ndk/images/graph.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/ndk/images/result.png Binary file gara/android/ndk/images/result.png has changed diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/BUILD.bazel --- a/gara/android/robolectric-testing/BUILD.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,7 +0,0 @@ -platform( - name = "arm64-v8a", - constraint_values = [ - "@platforms//cpu:arm64", - "@platforms//os:android", - ], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/MODULE.bazel --- a/gara/android/robolectric-testing/MODULE.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,22 +0,0 @@ -"Bazel dependencies" - -bazel_dep(name = "platforms", version = "0.0.11") -bazel_dep(name = "rules_jvm_external", version = "5.3") - -maven = use_extension("@rules_jvm_external//:extensions.bzl", "maven") -maven.install( - artifacts = [ - "org.robolectric:robolectric:4.9", - "junit:junit:4.13.2", - "com.google.truth:truth:1.1.3", - "org.jetbrains.kotlin:kotlin-stdlib-common:1.7.10", - "org.jetbrains.kotlin:kotlin-stdlib-jdk7:1.7.10", - "org.jetbrains.kotlin:kotlin-stdlib-jdk8:1.7.10", - "org.jetbrains.kotlin:kotlin-stdlib:1.7.10", - ], - repositories = [ - "https://maven.google.com", - "https://repo1.maven.org/maven2", - ], -) -use_repo(maven, "maven") diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/README.md --- a/gara/android/robolectric-testing/README.md Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ -# Android Jetpack Compose with Bazel example - -## Documentation - -For the full documentation, please visit -the [robolectric-bazel documentation page](https://github.com/robolectric/robolectric-bazel#usage). - -## Instructions - -1) Launch emulator -2) Run `bazel test //app:test` diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/WORKSPACE --- a/gara/android/robolectric-testing/WORKSPACE Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -# FIXME(alexeagle): move to bzlmod -workspace(name = "bazel_android_sample_project") - -load("@bazel_tools//tools/build_defs/repo:http.bzl", "http_archive") - -## Android - -http_archive( - name = "build_bazel_rules_android", - sha256 = "cd06d15dd8bb59926e4d65f9003bfc20f9da4b2519985c27e190cddc8b7a7806", - strip_prefix = "rules_android-0.1.1", - urls = ["https://github.com/bazelbuild/rules_android/archive/v0.1.1.zip"], -) - -load("@build_bazel_rules_android//android:rules.bzl", "android_sdk_repository") - -android_sdk_repository(name = "androidsdk") - -## Kotlin - -http_archive( - name = "io_bazel_rules_kotlin", - sha256 = "f033fa36f51073eae224f18428d9493966e67c27387728b6be2ebbdae43f140e", - url = "https://github.com/bazelbuild/rules_kotlin/releases/download/v1.7.0-RC-3/rules_kotlin_release.tgz", -) - -load("@io_bazel_rules_kotlin//kotlin:repositories.bzl", "kotlin_repositories") - -kotlin_repositories() - -load("@io_bazel_rules_kotlin//kotlin:core.bzl", "kt_register_toolchains") - -kt_register_toolchains() - -# Android Testing - -http_archive( - name = "robolectric", - sha256 = "7655c49633ec85a18b5a94b1ec36e250671808e45494194959b1d1d7f3e73a23", - strip_prefix = "robolectric-bazel-4.9", - urls = ["https://github.com/robolectric/robolectric-bazel/archive/4.9.tar.gz"], -) - -load("@robolectric//bazel:robolectric.bzl", "robolectric_repositories") - -robolectric_repositories() diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/BUILD.bazel --- a/gara/android/robolectric-testing/app/BUILD.bazel Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,29 +0,0 @@ -load("@io_bazel_rules_kotlin//kotlin:android.bzl", "kt_android_library", "kt_android_local_test") - -kt_android_library( - name = "lib", - srcs = glob(["src/main/java/**/*.kt"]), - custom_package = "com.example.android.bazel", - manifest = "src/main/AndroidManifest.xml", - resource_files = glob(["src/main/res/**"]), - deps = [ - "@maven//:org_jetbrains_kotlin_kotlin_stdlib", - "@maven//:org_jetbrains_kotlin_kotlin_stdlib_common", - "@maven//:org_jetbrains_kotlin_kotlin_stdlib_jdk7", - "@maven//:org_jetbrains_kotlin_kotlin_stdlib_jdk8", - ], -) - -kt_android_local_test( - name = "test", - srcs = ["src/test/java/com/example/android/bazel/WelcomeActivityTest.kt"], - custom_package = "com.example.android.bazel.test", - test_class = "com.example.android.bazel.WelcomeActivityTest", - deps = [ - ":lib", - "@maven//:com_google_truth_truth", - "@maven//:junit_junit", - "@maven//:org_robolectric_robolectric", - "@robolectric//bazel:android-all", - ], -) diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/src/main/AndroidManifest.xml --- a/gara/android/robolectric-testing/app/src/main/AndroidManifest.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,25 +0,0 @@ - - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/src/main/java/com/example/android/bazel/LoginActivity.kt --- a/gara/android/robolectric-testing/app/src/main/java/com/example/android/bazel/LoginActivity.kt Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ -package com.example.android.bazel - -import android.app.Activity -import android.os.Bundle - -class LoginActivity : Activity() { - - override fun onCreate(savedInstanceState: Bundle?) { - super.onCreate(savedInstanceState) - } -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/src/main/java/com/example/android/bazel/WelcomeActivity.kt --- a/gara/android/robolectric-testing/app/src/main/java/com/example/android/bazel/WelcomeActivity.kt Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,20 +0,0 @@ -package com.example.android.bazel - -import android.app.Activity -import android.os.Bundle -import android.view.View -import android.content.Intent - -class WelcomeActivity : Activity() { - - override fun onCreate(savedInstanceState: Bundle?) { - super.onCreate(savedInstanceState) - - setContentView(R.layout.welcome_activity) - - val button: View = findViewById(R.id.login) - button.setOnClickListener({ v -> - startActivity(Intent(this@WelcomeActivity, LoginActivity::class.java)) - }) - } -} diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/src/main/res/drawable-v24/ic_launcher_foreground.xml --- a/gara/android/robolectric-testing/app/src/main/res/drawable-v24/ic_launcher_foreground.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/src/main/res/drawable/ic_launcher_background.xml --- a/gara/android/robolectric-testing/app/src/main/res/drawable/ic_launcher_background.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,170 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff -r 4bc56e88e1f3 -r 75de5903355c gara/android/robolectric-testing/app/src/main/res/layout/welcome_activity.xml --- a/gara/android/robolectric-testing/app/src/main/res/layout/welcome_activity.xml Thu Dec 25 20:10:46 2025 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,13 +0,0 @@ - - - -