diff options
Diffstat (limited to 'third_party/rust/litemap')
22 files changed, 4125 insertions, 0 deletions
diff --git a/third_party/rust/litemap/.cargo-checksum.json b/third_party/rust/litemap/.cargo-checksum.json new file mode 100644 index 0000000000..b999bc2dad --- /dev/null +++ b/third_party/rust/litemap/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.lock":"42f9ffcf78063754cab6c45e22c35b90ccb6c9b2471c85bf9970c5cf60cba4ef","Cargo.toml":"5d721a7b3498c739fe8d755b292a2301d604ae1ab25f7530cbb3f20bd82149f2","LICENSE":"853f87c96f3d249f200fec6db1114427bc8bdf4afddc93c576956d78152ce978","README.md":"8d48b860b4895a3757ded795f1e0a125515ced1e883d754684c64e3191f5ebeb","benches/litemap.rs":"e7ed317126a7251b62f0ef5c2a0897ff119a401db5c464f8068d590158aac350","examples/language_names_hash_map.rs":"d8ee06487584caf18d0950ed8eeef4b25d26260b644c43ed0d8101beeb32f7e4","examples/language_names_lite_map.rs":"9f510009856e4edbdd9d3edb130e06a1e6dab691a639899e235e6d4b2aed6287","examples/litemap_bincode.rs":"76df7e65788467329089488f82bf01bffdc19f18778d42157f17beb1b4fe139c","examples/litemap_postcard.rs":"3c63447b5d3c10109970508189793351753f8fc12887775a1a00817b9f0320ef","src/databake.rs":"28049dc8426a2b53047918920d486ac3c635592a87c73ab297bb7daa8e633892","src/lib.rs":"7ce0d0d792c64152e8c2b49c36210ebe4cef017668ee6faf703ad974d70ac2b4","src/map.rs":"591706fa52b8588a3109ae94a12243e9ce4d06b05d1aa28c0858a1899da24a50","src/serde.rs":"56cda02d9da4f555fe103a9aa2d015cf90468a98482dad3d3ba284bb10241231","src/serde_helpers.rs":"72787005972b93e49b9dc17aa47d30699364e6da9dc95aadb820ce58e4bf5c54","src/store/mod.rs":"ddfbf20008b3b925dbfb4bcabee28ca123a0bb4d33dc7512f3f5552a3d5eebcc","src/store/slice_impl.rs":"1807eb84cf263357ed356bc55f8ab7a2bc8b0ef56923155c659f2b5ee1f89180","src/store/vec_impl.rs":"60962147ced42c7442ff66616c615680e461f8e1eded52cde2599ad5c3c4bb34","src/testing.rs":"6e6dcb65920f9d10719b843409e8287f579ec864f9d69a9b33b80578a9fc9e4f","tests/rkyv.rs":"b19d91eda9105699a4340340f0a8961de5f02673599dd8eddb43269634777cc4","tests/serde.rs":"0051274f8490c5837d88447bf72fc7266e970fa95c6e4ca540eeba45b7947ce6","tests/store.rs":"c8b1d7899b68187aa31735f3703b056cab549310fecc3631d8fd3adc17ae714d"},"package":"f9d642685b028806386b2b6e75685faadd3eb65a85fff7df711ce18446a422da"}
\ No newline at end of file diff --git a/third_party/rust/litemap/Cargo.lock b/third_party/rust/litemap/Cargo.lock new file mode 100644 index 0000000000..92dbc7aced --- /dev/null +++ b/third_party/rust/litemap/Cargo.lock @@ -0,0 +1,899 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "ahash" +version = "0.7.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fcb51a0695d8f838b1ee009b3fbf66bda078cd64590202a864a8f3e8c4315c47" +dependencies = [ + "getrandom", + "once_cell", + "version_check", +] + +[[package]] +name = "aho-corasick" +version = "1.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ea5d730647d4fadd988536d06fecce94b7b4f2a7efdae548f1cf4b63205518ab" +dependencies = [ + "memchr", +] + +[[package]] +name = "anes" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4b46cbb362ab8752921c97e041f5e366ee6297bd428a31275b9fcf1e380f7299" + +[[package]] +name = "atty" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8" +dependencies = [ + "hermit-abi", + "libc", + "winapi", +] + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "bincode" +version = "1.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b1f45e9417d87227c7a56d22e471c6206462cba514c7590c09aff4cf6d1ddcad" +dependencies = [ + "serde", +] + +[[package]] +name = "bitflags" +version = "1.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" + +[[package]] +name = "bitvec" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1bc2832c24239b0141d5674bb9174f9d68a8b5b3f2753311927c172ca46f7e9c" +dependencies = [ + "funty", + "radium", + "tap", + "wyz", +] + +[[package]] +name = "bumpalo" +version = "3.14.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7f30e7476521f6f8af1a1c4c0b8cc94f0bee37d91763d0ca2665f299b6cd8aec" + +[[package]] +name = "bytecheck" +version = "0.6.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8b6372023ac861f6e6dc89c8344a8f398fb42aaba2b5dbc649ca0c0e9dbcb627" +dependencies = [ + "bytecheck_derive", + "ptr_meta", + "simdutf8", +] + +[[package]] +name = "bytecheck_derive" +version = "0.6.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a7ec4c6f261935ad534c0c22dbef2201b45918860eb1c574b972bd213a76af61" +dependencies = [ + "proc-macro2", + "quote", + "syn 1.0.109", +] + +[[package]] +name = "cast" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "37b2a672a2cb129a2e41c10b1224bb368f9f37a2b16b612598138befd7b37eb5" + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "ciborium" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "effd91f6c78e5a4ace8a5d3c0b6bfaec9e2baaef55f3efc00e45fb2e477ee926" +dependencies = [ + "ciborium-io", + "ciborium-ll", + "serde", +] + +[[package]] +name = "ciborium-io" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cdf919175532b369853f5d5e20b26b43112613fd6fe7aee757e35f7a44642656" + +[[package]] +name = "ciborium-ll" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "defaa24ecc093c77630e6c15e17c51f5e187bf35ee514f4e2d67baaa96dae22b" +dependencies = [ + "ciborium-io", + "half", +] + +[[package]] +name = "clap" +version = "3.2.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ea181bf566f71cb9a5d17a59e1871af638180a18fb0035c92ae62b705207123" +dependencies = [ + "bitflags", + "clap_lex", + "indexmap", + "textwrap", +] + +[[package]] +name = "clap_lex" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2850f2f5a82cbf437dd5af4d49848fbdfc27c157c3d010345776f952765261c5" +dependencies = [ + "os_str_bytes", +] + +[[package]] +name = "cobs" +version = "0.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "67ba02a97a2bd10f4b59b25c7973101c79642302776489e030cd13cdab09ed15" + +[[package]] +name = "criterion" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e7c76e09c1aae2bc52b3d2f29e13c6572553b30c4aa1b8a49fd70de6412654cb" +dependencies = [ + "anes", + "atty", + "cast", + "ciborium", + "clap", + "criterion-plot", + "itertools", + "lazy_static", + "num-traits", + "oorandom", + "plotters", + "rayon", + "regex", + "serde", + "serde_derive", + "serde_json", + "tinytemplate", + "walkdir", +] + +[[package]] +name = "criterion-plot" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6b50826342786a51a89e2da3a28f1c32b06e387201bc2d19791f622c673706b1" +dependencies = [ + "cast", + "itertools", +] + +[[package]] +name = "crossbeam-deque" +version = "0.8.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ce6fd6f855243022dcecf8702fef0c297d4338e226845fe067f6341ad9fa0cef" +dependencies = [ + "cfg-if", + "crossbeam-epoch", + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-epoch" +version = "0.9.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ae211234986c545741a7dc064309f67ee1e5ad243d0e48335adc0484d960bcc7" +dependencies = [ + "autocfg", + "cfg-if", + "crossbeam-utils", + "memoffset", + "scopeguard", +] + +[[package]] +name = "crossbeam-utils" +version = "0.8.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5a22b2d63d4d1dc0b7f1b6b2747dd0088008a9be28b6ddf0b1e7d335e3037294" +dependencies = [ + "cfg-if", +] + +[[package]] +name = "databake" +version = "0.1.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "82175d72e69414ceafbe2b49686794d3a8bed846e0d50267355f83ea8fdd953a" +dependencies = [ + "proc-macro2", + "quote", +] + +[[package]] +name = "either" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07" + +[[package]] +name = "funty" +version = "2.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6d5a32815ae3f33302d95fdcb2ce17862f8c65363dcfd29360480ba1001fc9c" + +[[package]] +name = "getrandom" +version = "0.2.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "be4136b2a15dd319360be1c07d9933517ccf0be8f16bf62a3bee4f0d618df427" +dependencies = [ + "cfg-if", + "libc", + "wasi", +] + +[[package]] +name = "half" +version = "1.8.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eabb4a44450da02c90444cf74558da904edde8fb4e9035a9a6a4e15445af0bd7" + +[[package]] +name = "hashbrown" +version = "0.12.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888" +dependencies = [ + "ahash", +] + +[[package]] +name = "hermit-abi" +version = "0.1.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "62b467343b94ba476dcb2500d242dadbb39557df889310ac77c5d99100aaac33" +dependencies = [ + "libc", +] + +[[package]] +name = "indexmap" +version = "1.9.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bd070e393353796e801d209ad339e89596eb4c8d430d18ede6a1cced8fafbd99" +dependencies = [ + "autocfg", + "hashbrown", +] + +[[package]] +name = "itertools" +version = "0.10.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0fd2260e829bddf4cb6ea802289de2f86d6a7a690192fbe91b3f46e0f2c8473" +dependencies = [ + "either", +] + +[[package]] +name = "itoa" +version = "1.0.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "af150ab688ff2122fcef229be89cb50dd66af9e01a4ff320cc137eecc9bacc38" + +[[package]] +name = "js-sys" +version = "0.3.64" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c5f195fe497f702db0f318b07fdd68edb16955aed830df8363d837542f8f935a" +dependencies = [ + "wasm-bindgen", +] + +[[package]] +name = "lazy_static" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" + +[[package]] +name = "libc" +version = "0.2.148" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9cdc71e17332e86d2e1d38c1f99edcb6288ee11b815fb1a4b049eaa2114d369b" + +[[package]] +name = "litemap" +version = "0.7.2" +dependencies = [ + "bincode", + "bytecheck", + "criterion", + "databake", + "postcard", + "rkyv", + "serde", + "serde_json", + "yoke", +] + +[[package]] +name = "log" +version = "0.4.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5e6163cb8c49088c2c36f57875e58ccd8c87c7427f7fbd50ea6710b2f3f2e8f" + +[[package]] +name = "memchr" +version = "2.6.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8f232d6ef707e1956a43342693d2a31e72989554d58299d7a88738cc95b0d35c" + +[[package]] +name = "memoffset" +version = "0.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5a634b1c61a95585bd15607c6ab0c4e5b226e695ff2800ba0cdccddf208c406c" +dependencies = [ + "autocfg", +] + +[[package]] +name = "num-traits" +version = "0.2.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f30b0abd723be7e2ffca1272140fac1a2f084c77ec3e123c192b66af1ee9e6c2" +dependencies = [ + "autocfg", +] + +[[package]] +name = "once_cell" +version = "1.18.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dd8b5dd2ae5ed71462c540258bedcb51965123ad7e7ccf4b9a8cafaa4a63576d" + +[[package]] +name = "oorandom" +version = "11.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0ab1bc2a289d34bd04a330323ac98a1b4bc82c9d9fcb1e66b63caa84da26b575" + +[[package]] +name = "os_str_bytes" +version = "6.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4d5d9eb14b174ee9aa2ef96dc2b94637a2d4b6e7cb873c7e171f0c20c6cf3eac" + +[[package]] +name = "plotters" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d2c224ba00d7cadd4d5c660deaf2098e5e80e07846537c51f9cfa4be50c1fd45" +dependencies = [ + "num-traits", + "plotters-backend", + "plotters-svg", + "wasm-bindgen", + "web-sys", +] + +[[package]] +name = "plotters-backend" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9e76628b4d3a7581389a35d5b6e2139607ad7c75b17aed325f210aa91f4a9609" + +[[package]] +name = "plotters-svg" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38f6d39893cca0701371e3c27294f09797214b86f1fb951b89ade8ec04e2abab" +dependencies = [ + "plotters-backend", +] + +[[package]] +name = "postcard" +version = "1.0.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d534c6e61df1c7166e636ca612d9820d486fe96ddad37f7abc671517b297488e" +dependencies = [ + "cobs", + "serde", +] + +[[package]] +name = "proc-macro2" +version = "1.0.67" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3d433d9f1a3e8c1263d9456598b16fec66f4acc9a74dacffd35c7bb09b3a1328" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "ptr_meta" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0738ccf7ea06b608c10564b31debd4f5bc5e197fc8bfe088f68ae5ce81e7a4f1" +dependencies = [ + "ptr_meta_derive", +] + +[[package]] +name = "ptr_meta_derive" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "16b845dbfca988fa33db069c0e230574d15a3088f147a87b64c7589eb662c9ac" +dependencies = [ + "proc-macro2", + "quote", + "syn 1.0.109", +] + +[[package]] +name = "quote" +version = "1.0.33" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5267fca4496028628a95160fc423a33e8b2e6af8a5302579e322e4b520293cae" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "radium" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dc33ff2d4973d518d823d61aa239014831e521c75da58e3df4840d3f47749d09" + +[[package]] +name = "rayon" +version = "1.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c27db03db7734835b3f53954b534c91069375ce6ccaa2e065441e07d9b6cdb1" +dependencies = [ + "either", + "rayon-core", +] + +[[package]] +name = "rayon-core" +version = "1.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5ce3fb6ad83f861aac485e76e1985cd109d9a3713802152be56c3b1f0e0658ed" +dependencies = [ + "crossbeam-deque", + "crossbeam-utils", +] + +[[package]] +name = "regex" +version = "1.9.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "697061221ea1b4a94a624f67d0ae2bfe4e22b8a17b6a192afb11046542cc8c47" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata", + "regex-syntax", +] + +[[package]] +name = "regex-automata" +version = "0.3.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c2f401f4955220693b56f8ec66ee9c78abffd8d1c4f23dc41a23839eb88f0795" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-syntax" +version = "0.7.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dbb5fb1acd8a1a18b3dd5be62d25485eb770e05afb408a9627d14d451bae12da" + +[[package]] +name = "rend" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "581008d2099240d37fb08d77ad713bcaec2c4d89d50b5b21a8bb1996bbab68ab" +dependencies = [ + "bytecheck", +] + +[[package]] +name = "rkyv" +version = "0.7.42" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0200c8230b013893c0b2d6213d6ec64ed2b9be2e0e016682b7224ff82cff5c58" +dependencies = [ + "bitvec", + "bytecheck", + "hashbrown", + "ptr_meta", + "rend", + "rkyv_derive", + "seahash", + "tinyvec", + "uuid", +] + +[[package]] +name = "rkyv_derive" +version = "0.7.42" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b2e06b915b5c230a17d7a736d1e2e63ee753c256a8614ef3f5147b13a4f5541d" +dependencies = [ + "proc-macro2", + "quote", + "syn 1.0.109", +] + +[[package]] +name = "ryu" +version = "1.0.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1ad4cc8da4ef723ed60bced201181d83791ad433213d8c24efffda1eec85d741" + +[[package]] +name = "same-file" +version = "1.0.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502" +dependencies = [ + "winapi-util", +] + +[[package]] +name = "scopeguard" +version = "1.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "94143f37725109f92c262ed2cf5e59bce7498c01bcc1502d7b9afe439a4e9f49" + +[[package]] +name = "seahash" +version = "4.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1c107b6f4780854c8b126e228ea8869f4d7b71260f962fefb57b996b8959ba6b" + +[[package]] +name = "serde" +version = "1.0.188" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf9e0fcba69a370eed61bcf2b728575f726b50b55cba78064753d708ddc7549e" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.188" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4eca7ac642d82aa35b60049a6eccb4be6be75e599bd2e9adb5f875a737654af2" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.37", +] + +[[package]] +name = "serde_json" +version = "1.0.107" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6b420ce6e3d8bd882e9b243c6eed35dbc9a6110c9769e74b584e0d68d1f20c65" +dependencies = [ + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "simdutf8" +version = "0.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f27f6278552951f1f2b8cf9da965d10969b2efdea95a6ec47987ab46edfe263a" + +[[package]] +name = "stable_deref_trait" +version = "1.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a8f112729512f8e442d81f95a8a7ddf2b7c6b8a1a6f509a95864142b30cab2d3" + +[[package]] +name = "syn" +version = "1.0.109" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "72b64191b275b66ffe2469e8af2c1cfe3bafa67b529ead792a6d0160888b4237" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "syn" +version = "2.0.37" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7303ef2c05cd654186cb250d29049a24840ca25d2747c25c0381c8d9e2f582e8" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "synstructure" +version = "0.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "285ba80e733fac80aa4270fbcdf83772a79b80aa35c97075320abfee4a915b06" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.37", + "unicode-xid", +] + +[[package]] +name = "tap" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "55937e1799185b12863d447f42597ed69d9928686b8d88a1df17376a097d8369" + +[[package]] +name = "textwrap" +version = "0.16.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "222a222a5bfe1bba4a77b45ec488a741b3cb8872e5e499451fd7d0129c9c7c3d" + +[[package]] +name = "tinytemplate" +version = "1.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "be4d6b5f19ff7664e8c98d03e2139cb510db9b0a60b55f8e8709b689d939b6bc" +dependencies = [ + "serde", + "serde_json", +] + +[[package]] +name = "tinyvec" +version = "1.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "87cc5ceb3875bb20c2890005a4e226a4651264a5c75edb2421b52861a0a0cb50" +dependencies = [ + "tinyvec_macros", +] + +[[package]] +name = "tinyvec_macros" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1f3ccbac311fea05f86f61904b462b55fb3df8837a366dfc601a0161d0532f20" + +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" + +[[package]] +name = "unicode-xid" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f962df74c8c05a667b5ee8bcf162993134c104e96440b663c8daa176dc772d8c" + +[[package]] +name = "uuid" +version = "1.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "79daa5ed5740825c40b389c5e50312b9c86df53fccd33f281df655642b43869d" + +[[package]] +name = "version_check" +version = "0.9.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f" + +[[package]] +name = "walkdir" +version = "2.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d71d857dc86794ca4c280d616f7da00d2dbfd8cd788846559a6813e6aa4b54ee" +dependencies = [ + "same-file", + "winapi-util", +] + +[[package]] +name = "wasi" +version = "0.11.0+wasi-snapshot-preview1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c8d87e72b64a3b4db28d11ce29237c246188f4f51057d65a7eab63b7987e423" + +[[package]] +name = "wasm-bindgen" +version = "0.2.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7706a72ab36d8cb1f80ffbf0e071533974a60d0a308d01a5d0375bf60499a342" +dependencies = [ + "cfg-if", + "wasm-bindgen-macro", +] + +[[package]] +name = "wasm-bindgen-backend" +version = "0.2.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5ef2b6d3c510e9625e5fe6f509ab07d66a760f0885d858736483c32ed7809abd" +dependencies = [ + "bumpalo", + "log", + "once_cell", + "proc-macro2", + "quote", + "syn 2.0.37", + "wasm-bindgen-shared", +] + +[[package]] +name = "wasm-bindgen-macro" +version = "0.2.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "dee495e55982a3bd48105a7b947fd2a9b4a8ae3010041b9e0faab3f9cd028f1d" +dependencies = [ + "quote", + "wasm-bindgen-macro-support", +] + +[[package]] +name = "wasm-bindgen-macro-support" +version = "0.2.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "54681b18a46765f095758388f2d0cf16eb8d4169b639ab575a8f5693af210c7b" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.37", + "wasm-bindgen-backend", + "wasm-bindgen-shared", +] + +[[package]] +name = "wasm-bindgen-shared" +version = "0.2.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ca6ad05a4870b2bf5fe995117d3728437bd27d7cd5f06f13c17443ef369775a1" + +[[package]] +name = "web-sys" +version = "0.3.64" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9b85cbef8c220a6abc02aefd892dfc0fc23afb1c6a426316ec33253a3877249b" +dependencies = [ + "js-sys", + "wasm-bindgen", +] + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-util" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f29e6f9198ba0d26b4c9f07dbe6f9ed633e1f3d5b8b414090084349e46a52596" +dependencies = [ + "winapi", +] + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" + +[[package]] +name = "wyz" +version = "0.5.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "05f360fc0b24296329c78fda852a1e9ae82de9cf7b27dae4b7f62f118f77b9ed" +dependencies = [ + "tap", +] + +[[package]] +name = "yoke" +version = "0.7.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "65e71b2e4f287f467794c671e2b8f8a5f3716b3c829079a1c44740148eff07e4" +dependencies = [ + "stable_deref_trait", + "yoke-derive", + "zerofrom", +] + +[[package]] +name = "yoke-derive" +version = "0.7.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9e6936f0cce458098a201c245a11bef556c6a0181129c7034d10d76d1ec3a2b8" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.37", + "synstructure", +] + +[[package]] +name = "zerofrom" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "655b0814c5c0b19ade497851070c640773304939a6c0fd5f5fb43da0696d05b7" +dependencies = [ + "zerofrom-derive", +] + +[[package]] +name = "zerofrom-derive" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6a647510471d372f2e6c2e6b7219e44d8c574d24fdc11c610a61455782f18c3" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.37", + "synstructure", +] diff --git a/third_party/rust/litemap/Cargo.toml b/third_party/rust/litemap/Cargo.toml new file mode 100644 index 0000000000..dc8b38e665 --- /dev/null +++ b/third_party/rust/litemap/Cargo.toml @@ -0,0 +1,124 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2021" +rust-version = "1.67" +name = "litemap" +version = "0.7.2" +authors = ["The ICU4X Project Developers"] +include = [ + "data/**/*", + "src/**/*", + "examples/**/*", + "benches/**/*", + "tests/**/*", + "Cargo.toml", + "LICENSE", + "README.md", +] +description = "A key-value Map implementation based on a flat, sorted Vec." +documentation = "https://docs.rs/litemap" +readme = "README.md" +keywords = [ + "sorted", + "vec", + "map", + "hashmap", + "btreemap", +] +license-file = "LICENSE" +repository = "https://github.com/unicode-org/icu4x" + +[package.metadata.cargo-all-features] +denylist = ["bench"] + +[package.metadata.docs.rs] +all-features = true + +[package.metadata.workspaces] +independent = true + +[lib] +bench = false + +[[example]] +name = "litemap_bincode" +path = "examples/litemap_bincode.rs" +required-features = ["serde"] + +[[example]] +name = "litemap_postcard" +path = "examples/litemap_postcard.rs" +required-features = ["serde"] + +[[test]] +name = "serde" +required-features = ["serde"] + +[[test]] +name = "store" +required-features = ["testing"] + +[[bench]] +name = "litemap" +harness = false +required-features = ["serde"] + +[dependencies.databake] +version = "0.1.7" +optional = true +default-features = false + +[dependencies.serde] +version = "1" +features = ["alloc"] +optional = true +default-features = false + +[dependencies.yoke] +version = "0.7.3" +features = ["derive"] +optional = true +default-features = false + +[dev-dependencies.bincode] +version = "1" + +[dev-dependencies.bytecheck] +version = "0.6" + +[dev-dependencies.postcard] +version = "1.0.0" +features = ["use-std"] +default-features = false + +[dev-dependencies.rkyv] +version = "0.7" +features = ["validation"] + +[dev-dependencies.serde] +version = "1" + +[dev-dependencies.serde_json] +version = "1" + +[features] +alloc = [] +bench = ["serde"] +databake = ["dep:databake"] +default = ["alloc"] +serde = ["dep:serde"] +testing = ["alloc"] +yoke = ["dep:yoke"] + +[target."cfg(not(target_arch = \"wasm32\"))".dev-dependencies.criterion] +version = "0.4" diff --git a/third_party/rust/litemap/LICENSE b/third_party/rust/litemap/LICENSE new file mode 100644 index 0000000000..9845aa5f48 --- /dev/null +++ b/third_party/rust/litemap/LICENSE @@ -0,0 +1,44 @@ +UNICODE LICENSE V3 + +COPYRIGHT AND PERMISSION NOTICE + +Copyright © 2020-2023 Unicode, Inc. + +NOTICE TO USER: Carefully read the following legal agreement. BY +DOWNLOADING, INSTALLING, COPYING OR OTHERWISE USING DATA FILES, AND/OR +SOFTWARE, YOU UNEQUIVOCALLY ACCEPT, AND AGREE TO BE BOUND BY, ALL OF THE +TERMS AND CONDITIONS OF THIS AGREEMENT. IF YOU DO NOT AGREE, DO NOT +DOWNLOAD, INSTALL, COPY, DISTRIBUTE OR USE THE DATA FILES OR SOFTWARE. + +Permission is hereby granted, free of charge, to any person obtaining a +copy of data files and any associated documentation (the "Data Files") or +software and any associated documentation (the "Software") to deal in the +Data Files or Software without restriction, including without limitation +the rights to use, copy, modify, merge, publish, distribute, and/or sell +copies of the Data Files or Software, and to permit persons to whom the +Data Files or Software are furnished to do so, provided that either (a) +this copyright and permission notice appear with all copies of the Data +Files or Software, or (b) this copyright and permission notice appear in +associated Documentation. + +THE DATA FILES AND SOFTWARE ARE 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 OF +THIRD PARTY RIGHTS. + +IN NO EVENT SHALL THE COPYRIGHT HOLDER OR HOLDERS INCLUDED IN THIS NOTICE +BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL INDIRECT OR CONSEQUENTIAL DAMAGES, +OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, +WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, +ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THE DATA +FILES OR SOFTWARE. + +Except as contained in this notice, the name of a copyright holder shall +not be used in advertising or otherwise to promote the sale, use or other +dealings in these Data Files or Software without prior written +authorization of the copyright holder. + +— + +Portions of ICU4X may have been adapted from ICU4C and/or ICU4J. +ICU 1.8.1 to ICU 57.1 © 1995-2016 International Business Machines Corporation and others. diff --git a/third_party/rust/litemap/README.md b/third_party/rust/litemap/README.md new file mode 100644 index 0000000000..9aa80172b4 --- /dev/null +++ b/third_party/rust/litemap/README.md @@ -0,0 +1,37 @@ +# litemap [](https://crates.io/crates/litemap) + +<!-- cargo-rdme start --> + +## `litemap` + +`litemap` is a crate providing [`LiteMap`], a highly simplistic "flat" key-value map +based off of a single sorted vector. + +The goal of this crate is to provide a map that is good enough for small +sizes, and does not carry the binary size impact of [`HashMap`](std::collections::HashMap) +or [`BTreeMap`](alloc::collections::BTreeMap). + +If binary size is not a concern, [`std::collections::BTreeMap`] may be a better choice +for your use case. It behaves very similarly to [`LiteMap`] for less than 12 elements, +and upgrades itself gracefully for larger inputs. + +### Pluggable Backends + +By default, [`LiteMap`] is backed by a [`Vec`]; however, it can be backed by any appropriate +random-access data store, giving that data store a map-like interface. See the [`store`] +module for more details. + +### Const construction + +[`LiteMap`] supports const construction from any store that is const-constructible, such as a +static slice, via [`LiteMap::from_sorted_store_unchecked()`]. This also makes [`LiteMap`] +suitable for use with [`databake`]. See [`impl Bake for LiteMap`] for more details. + +[`impl Bake for LiteMap`]: ./struct.LiteMap.html#impl-Bake-for-LiteMap<K,+V,+S> +[`Vec`]: alloc::vec::Vec + +<!-- cargo-rdme end --> + +## More Information + +For more information on development, authorship, contributing etc. please visit [`ICU4X home page`](https://github.com/unicode-org/icu4x). diff --git a/third_party/rust/litemap/benches/litemap.rs b/third_party/rust/litemap/benches/litemap.rs new file mode 100644 index 0000000000..b32b8ba878 --- /dev/null +++ b/third_party/rust/litemap/benches/litemap.rs @@ -0,0 +1,120 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use criterion::{black_box, criterion_group, criterion_main, Criterion}; + +use litemap::LiteMap; + +const DATA: [(&str, &str); 16] = [ + ("ar", "Arabic"), + ("bn", "Bangla"), + ("ccp", "Chakma"), + ("chr", "Cherokee"), + ("el", "Greek"), + ("en", "English"), + ("eo", "Esperanto"), + ("es", "Spanish"), + ("fr", "French"), + ("iu", "Inuktitut"), + ("ja", "Japanese"), + ("ru", "Russian"), + ("sr", "Serbian"), + ("th", "Thai"), + ("tr", "Turkish"), + ("zh", "Chinese"), +]; + +const POSTCARD: [u8; 176] = [ + 16, 2, 97, 114, 6, 65, 114, 97, 98, 105, 99, 2, 98, 110, 6, 66, 97, 110, 103, 108, 97, 3, 99, + 99, 112, 6, 67, 104, 97, 107, 109, 97, 3, 99, 104, 114, 8, 67, 104, 101, 114, 111, 107, 101, + 101, 2, 101, 108, 5, 71, 114, 101, 101, 107, 2, 101, 110, 7, 69, 110, 103, 108, 105, 115, 104, + 2, 101, 111, 9, 69, 115, 112, 101, 114, 97, 110, 116, 111, 2, 101, 115, 7, 83, 112, 97, 110, + 105, 115, 104, 2, 102, 114, 6, 70, 114, 101, 110, 99, 104, 2, 105, 117, 9, 73, 110, 117, 107, + 116, 105, 116, 117, 116, 2, 106, 97, 8, 74, 97, 112, 97, 110, 101, 115, 101, 2, 114, 117, 7, + 82, 117, 115, 115, 105, 97, 110, 2, 115, 114, 7, 83, 101, 114, 98, 105, 97, 110, 2, 116, 104, + 4, 84, 104, 97, 105, 2, 116, 114, 7, 84, 117, 114, 107, 105, 115, 104, 2, 122, 104, 7, 67, 104, + 105, 110, 101, 115, 101, +]; + +/// Run this function to print new data to the console. +#[allow(dead_code)] +fn generate() { + let map = build_litemap(false); + let buf = postcard::to_stdvec(&map).unwrap(); + println!("{buf:?}"); +} + +fn large_litemap_postcard_bytes() -> Vec<u8> { + postcard::to_stdvec(&build_litemap(true)).unwrap() +} + +fn overview_bench(c: &mut Criterion) { + // Uncomment the following line to re-generate the binary data. + // generate(); + + bench_deserialize(c); + bench_deserialize_large(c); + bench_lookup(c); + bench_lookup_large(c); + + #[cfg(feature = "generate")] + generate_test_data(); +} + +fn build_litemap(large: bool) -> LiteMap<String, String> { + let mut map: LiteMap<String, String> = LiteMap::new(); + for (key, value) in DATA.into_iter() { + if large { + for n in 0..8192 { + map.insert(format!("{key}{n}"), value.to_owned()); + } + } else { + map.insert(key.to_owned(), value.to_owned()); + } + } + map +} + +fn bench_deserialize(c: &mut Criterion) { + c.bench_function("litemap/deserialize/small", |b| { + b.iter(|| { + let map: LiteMap<String, String> = postcard::from_bytes(black_box(&POSTCARD)).unwrap(); + assert_eq!(map.get("iu"), Some(&"Inuktitut".to_owned())); + }) + }); +} + +fn bench_deserialize_large(c: &mut Criterion) { + let buf = large_litemap_postcard_bytes(); + c.bench_function("litemap/deseralize/large", |b| { + b.iter(|| { + let map: LiteMap<String, String> = postcard::from_bytes(black_box(&buf)).unwrap(); + assert_eq!(map.get("iu3333"), Some(&"Inuktitut".to_owned())); + }); + }); +} + +fn bench_lookup(c: &mut Criterion) { + let map: LiteMap<String, String> = postcard::from_bytes(&POSTCARD).unwrap(); + c.bench_function("litemap/lookup/small", |b| { + b.iter(|| { + assert_eq!(map.get(black_box("iu")), Some(&"Inuktitut".to_owned())); + assert_eq!(map.get(black_box("zz")), None); + }); + }); +} + +fn bench_lookup_large(c: &mut Criterion) { + let buf = large_litemap_postcard_bytes(); + let map: LiteMap<String, String> = postcard::from_bytes(&buf).unwrap(); + c.bench_function("litemap/lookup/large", |b| { + b.iter(|| { + assert_eq!(map.get(black_box("iu3333")), Some(&"Inuktitut".to_owned())); + assert_eq!(map.get(black_box("zz")), None); + }); + }); +} + +criterion_group!(benches, overview_bench); +criterion_main!(benches); diff --git a/third_party/rust/litemap/examples/language_names_hash_map.rs b/third_party/rust/litemap/examples/language_names_hash_map.rs new file mode 100644 index 0000000000..cb0f750b81 --- /dev/null +++ b/third_party/rust/litemap/examples/language_names_hash_map.rs @@ -0,0 +1,46 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +// LiteMap is intended as a small and low-memory drop-in replacement for HashMap. +// +// This example does not use LiteMap. The reader may compare this HashMap example to the +// LiteMap example to showcase analogous operations between HashMap and LiteMap. + +#![no_main] // https://github.com/unicode-org/icu4x/issues/395 + +icu_benchmark_macros::static_setup!(); + +use icu_locid::subtags::{language, Language}; +use std::collections::HashMap; + +const DATA: [(Language, &str); 11] = [ + (language!("ar"), "Arabic"), + (language!("bn"), "Bangla"), + (language!("ccp"), "Chakma"), + (language!("en"), "English"), + (language!("es"), "Spanish"), + (language!("fr"), "French"), + (language!("ja"), "Japanese"), + (language!("ru"), "Russian"), + (language!("sr"), "Serbian"), + (language!("th"), "Thai"), + (language!("tr"), "Turkish"), +]; + +#[no_mangle] +fn main(_argc: isize, _argv: *const *const u8) -> isize { + icu_benchmark_macros::main_setup!(); + + let mut map = HashMap::new(); + // https://github.com/rust-lang/rust/issues/62633 was declined :( + for (lang, name) in DATA.iter() { + map.insert(lang, name).ok_or(()).unwrap_err(); + } + + assert_eq!(11, map.len()); + assert_eq!(Some(&&"Thai"), map.get(&language!("th"))); + assert_eq!(None, map.get(&language!("de"))); + + 0 +} diff --git a/third_party/rust/litemap/examples/language_names_lite_map.rs b/third_party/rust/litemap/examples/language_names_lite_map.rs new file mode 100644 index 0000000000..a8641bf82d --- /dev/null +++ b/third_party/rust/litemap/examples/language_names_lite_map.rs @@ -0,0 +1,46 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +// LiteMap is intended as a small and low-memory drop-in replacement for HashMap. +// +// The reader may compare this LiteMap example with the HashMap example to see analogous +// operations between LiteMap and HashMap. + +#![no_main] // https://github.com/unicode-org/icu4x/issues/395 + +icu_benchmark_macros::static_setup!(); + +use icu_locid::subtags::{language, Language}; +use litemap::LiteMap; + +const DATA: [(Language, &str); 11] = [ + (language!("ar"), "Arabic"), + (language!("bn"), "Bangla"), + (language!("ccp"), "Chakma"), + (language!("en"), "English"), + (language!("es"), "Spanish"), + (language!("fr"), "French"), + (language!("ja"), "Japanese"), + (language!("ru"), "Russian"), + (language!("sr"), "Serbian"), + (language!("th"), "Thai"), + (language!("tr"), "Turkish"), +]; + +#[no_mangle] +fn main(_argc: isize, _argv: *const *const u8) -> isize { + icu_benchmark_macros::main_setup!(); + + let mut map = LiteMap::new_vec(); + // https://github.com/rust-lang/rust/issues/62633 was declined :( + for (lang, name) in DATA.iter() { + map.try_append(lang, name).ok_or(()).unwrap_err(); + } + + assert_eq!(11, map.len()); + assert_eq!(Some(&&"Thai"), map.get(&language!("th"))); + assert_eq!(None, map.get(&language!("de"))); + + 0 +} diff --git a/third_party/rust/litemap/examples/litemap_bincode.rs b/third_party/rust/litemap/examples/litemap_bincode.rs new file mode 100644 index 0000000000..bb17aaba01 --- /dev/null +++ b/third_party/rust/litemap/examples/litemap_bincode.rs @@ -0,0 +1,66 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +// LiteMap is intended as a small and low-memory drop-in replacement for +// HashMap. This example demonstrates how it works with Serde. + +#![no_main] // https://github.com/unicode-org/icu4x/issues/395 + +icu_benchmark_macros::static_setup!(); + +use litemap::LiteMap; + +const DATA: [(&str, &str); 11] = [ + ("ar", "Arabic"), + ("bn", "Bangla"), + ("ccp", "Chakma"), + ("en", "English"), + ("es", "Spanish"), + ("fr", "French"), + ("ja", "Japanese"), + ("ru", "Russian"), + ("sr", "Serbian"), + ("th", "Thai"), + ("tr", "Turkish"), +]; + +#[allow(dead_code)] +const BINCODE: [u8; 278] = [ + 11, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 97, 114, 6, 0, 0, 0, 0, 0, 0, 0, 65, 114, 97, + 98, 105, 99, 2, 0, 0, 0, 0, 0, 0, 0, 98, 110, 6, 0, 0, 0, 0, 0, 0, 0, 66, 97, 110, 103, 108, + 97, 3, 0, 0, 0, 0, 0, 0, 0, 99, 99, 112, 6, 0, 0, 0, 0, 0, 0, 0, 67, 104, 97, 107, 109, 97, 2, + 0, 0, 0, 0, 0, 0, 0, 101, 110, 7, 0, 0, 0, 0, 0, 0, 0, 69, 110, 103, 108, 105, 115, 104, 2, 0, + 0, 0, 0, 0, 0, 0, 101, 115, 7, 0, 0, 0, 0, 0, 0, 0, 83, 112, 97, 110, 105, 115, 104, 2, 0, 0, + 0, 0, 0, 0, 0, 102, 114, 6, 0, 0, 0, 0, 0, 0, 0, 70, 114, 101, 110, 99, 104, 2, 0, 0, 0, 0, 0, + 0, 0, 106, 97, 8, 0, 0, 0, 0, 0, 0, 0, 74, 97, 112, 97, 110, 101, 115, 101, 2, 0, 0, 0, 0, 0, + 0, 0, 114, 117, 7, 0, 0, 0, 0, 0, 0, 0, 82, 117, 115, 115, 105, 97, 110, 2, 0, 0, 0, 0, 0, 0, + 0, 115, 114, 7, 0, 0, 0, 0, 0, 0, 0, 83, 101, 114, 98, 105, 97, 110, 2, 0, 0, 0, 0, 0, 0, 0, + 116, 104, 4, 0, 0, 0, 0, 0, 0, 0, 84, 104, 97, 105, 2, 0, 0, 0, 0, 0, 0, 0, 116, 114, 7, 0, 0, + 0, 0, 0, 0, 0, 84, 117, 114, 107, 105, 115, 104, +]; + +/// Run this function to print new data to the console. +#[allow(dead_code)] +fn generate() { + let mut map = LiteMap::new_vec(); + for (lang, name) in DATA.iter() { + map.try_append(lang, name).ok_or(()).unwrap_err(); + } + + let buf = bincode::serialize(&map).unwrap(); + println!("{buf:?}"); +} + +#[no_mangle] +fn main(_argc: isize, _argv: *const *const u8) -> isize { + icu_benchmark_macros::main_setup!(); + + // Uncomment the following line to re-generate the binary data. + // generate(); + + let map: LiteMap<&str, &str> = bincode::deserialize(&BINCODE).unwrap(); + assert_eq!(map.get("tr"), Some(&"Turkish")); + + 0 +} diff --git a/third_party/rust/litemap/examples/litemap_postcard.rs b/third_party/rust/litemap/examples/litemap_postcard.rs new file mode 100644 index 0000000000..d7033c21c5 --- /dev/null +++ b/third_party/rust/litemap/examples/litemap_postcard.rs @@ -0,0 +1,60 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +// LiteMap is intended as a small and low-memory drop-in replacement for +// HashMap. This example demonstrates how it works with Serde. + +#![no_main] // https://github.com/unicode-org/icu4x/issues/395 + +icu_benchmark_macros::static_setup!(); + +use litemap::LiteMap; + +const DATA: [(&str, &str); 11] = [ + ("ar", "Arabic"), + ("bn", "Bangla"), + ("ccp", "Chakma"), + ("en", "English"), + ("es", "Spanish"), + ("fr", "French"), + ("ja", "Japanese"), + ("ru", "Russian"), + ("sr", "Serbian"), + ("th", "Thai"), + ("tr", "Turkish"), +]; + +const POSTCARD: [u8; 117] = [ + 11, 2, 97, 114, 6, 65, 114, 97, 98, 105, 99, 2, 98, 110, 6, 66, 97, 110, 103, 108, 97, 3, 99, + 99, 112, 6, 67, 104, 97, 107, 109, 97, 2, 101, 110, 7, 69, 110, 103, 108, 105, 115, 104, 2, + 101, 115, 7, 83, 112, 97, 110, 105, 115, 104, 2, 102, 114, 6, 70, 114, 101, 110, 99, 104, 2, + 106, 97, 8, 74, 97, 112, 97, 110, 101, 115, 101, 2, 114, 117, 7, 82, 117, 115, 115, 105, 97, + 110, 2, 115, 114, 7, 83, 101, 114, 98, 105, 97, 110, 2, 116, 104, 4, 84, 104, 97, 105, 2, 116, + 114, 7, 84, 117, 114, 107, 105, 115, 104, +]; + +/// Run this function to print new data to the console. +#[allow(dead_code)] +fn generate() { + let mut map = LiteMap::new_vec(); + for (lang, name) in DATA.iter() { + map.try_append(lang, name).ok_or(()).unwrap_err(); + } + + let buf = postcard::to_stdvec(&map).unwrap(); + println!("{buf:?}"); +} + +#[no_mangle] +fn main(_argc: isize, _argv: *const *const u8) -> isize { + icu_benchmark_macros::main_setup!(); + + // Uncomment the following line to re-generate the binary data. + // generate(); + + let map: LiteMap<&str, &str> = postcard::from_bytes(&POSTCARD).unwrap(); + assert_eq!(map.get("tr"), Some(&"Turkish")); + + 0 +} diff --git a/third_party/rust/litemap/src/databake.rs b/third_party/rust/litemap/src/databake.rs new file mode 100644 index 0000000000..d42085b9c6 --- /dev/null +++ b/third_party/rust/litemap/src/databake.rs @@ -0,0 +1,80 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use crate::LiteMap; +use databake::*; + +/// Bakes a LiteMap into Rust code for fast runtime construction from data. Use this impl during +/// code generation, such as in a `build.rs` script. +/// +/// For the most efficient bake, bake the [`LiteMap`] with a slice store. Use functions such as +/// the following for converting an allocated [`LiteMap`] to a borrowing [`LiteMap`]: +/// +/// - [`LiteMap::to_borrowed_keys()`] +/// - [`LiteMap::to_borrowed_values()`] +/// - [`LiteMap::to_borrowed_keys_values()`] +/// - [`LiteMap::as_sliced()`] +/// +/// # Examples +/// +/// ``` +/// use databake::*; +/// use litemap::LiteMap; +/// +/// // Construct the LiteMap fully owned and allocated: +/// let mut litemap_alloc: LiteMap<usize, String, Vec<_>> = LiteMap::new_vec(); +/// litemap_alloc.insert(1usize, "one".to_string()); +/// litemap_alloc.insert(2usize, "two".to_string()); +/// litemap_alloc.insert(10usize, "ten".to_string()); +/// +/// // Convert to a borrowed type for baking: +/// let litemap_str: LiteMap<usize, &str, Vec<_>> = +/// litemap_alloc.to_borrowed_values(); +/// let litemap_slice: LiteMap<usize, &str, &[_]> = litemap_str.as_sliced(); +/// +/// // The bake will now work for const construction: +/// let mut ctx = Default::default(); +/// println!( +/// "const FOO: LiteMap<usize, &str, &[(usize, &str)]> = {};", +/// litemap_slice.bake(&mut ctx) +/// ); +/// ``` +impl<K, V, S> Bake for LiteMap<K, V, S> +where + S: Bake, +{ + fn bake(&self, env: &CrateEnv) -> TokenStream { + env.insert("litemap"); + let store = self.values.bake(env); + quote! { litemap::LiteMap::from_sorted_store_unchecked(#store) } + } +} + +#[test] +fn test_baked_map() { + // Const construction: + test_bake!( + LiteMap<usize, &str, &[(usize, &str)]>, + const: crate::LiteMap::from_sorted_store_unchecked( + &[ + (1usize, "one"), + (2usize, "two"), + (10usize, "ten") + ] + ), + litemap + ); + // Non-const construction: + test_bake!( + LiteMap<usize, String, Vec<(usize, String)>>, + crate::LiteMap::from_sorted_store_unchecked( + alloc::vec![ + (1usize, "one".to_owned()), + (2usize, "two".to_owned()), + (10usize, "ten".to_owned()), + ] + ), + litemap + ); +} diff --git a/third_party/rust/litemap/src/lib.rs b/third_party/rust/litemap/src/lib.rs new file mode 100644 index 0000000000..b6f4019a70 --- /dev/null +++ b/third_party/rust/litemap/src/lib.rs @@ -0,0 +1,67 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +//! # `litemap` +//! +//! `litemap` is a crate providing [`LiteMap`], a highly simplistic "flat" key-value map +//! based off of a single sorted vector. +//! +//! The goal of this crate is to provide a map that is good enough for small +//! sizes, and does not carry the binary size impact of [`HashMap`](std::collections::HashMap) +//! or [`BTreeMap`](alloc::collections::BTreeMap). +//! +//! If binary size is not a concern, [`std::collections::BTreeMap`] may be a better choice +//! for your use case. It behaves very similarly to [`LiteMap`] for less than 12 elements, +//! and upgrades itself gracefully for larger inputs. +//! +//! ## Pluggable Backends +//! +//! By default, [`LiteMap`] is backed by a [`Vec`]; however, it can be backed by any appropriate +//! random-access data store, giving that data store a map-like interface. See the [`store`] +//! module for more details. +//! +//! ## Const construction +//! +//! [`LiteMap`] supports const construction from any store that is const-constructible, such as a +//! static slice, via [`LiteMap::from_sorted_store_unchecked()`]. This also makes [`LiteMap`] +//! suitable for use with [`databake`]. See [`impl Bake for LiteMap`] for more details. +//! +//! [`impl Bake for LiteMap`]: ./struct.LiteMap.html#impl-Bake-for-LiteMap<K,+V,+S> +//! [`Vec`]: alloc::vec::Vec + +// https://github.com/unicode-org/icu4x/blob/main/docs/process/boilerplate.md#library-annotations +#![cfg_attr(not(test), no_std)] +#![cfg_attr( + not(test), + deny( + clippy::indexing_slicing, + clippy::unwrap_used, + clippy::expect_used, + clippy::panic, + clippy::exhaustive_structs, + clippy::exhaustive_enums, + missing_debug_implementations, + ) +)] + +// for intra doc links +#[cfg(doc)] +extern crate std; + +extern crate alloc; + +#[cfg(feature = "databake")] +#[path = "databake.rs"] // to not conflict with `databake` as used in the docs +mod databake_impls; +mod map; +#[cfg(feature = "serde")] +mod serde; +#[cfg(feature = "serde")] +mod serde_helpers; +pub mod store; + +#[cfg(any(test, feature = "testing"))] +pub mod testing; + +pub use map::LiteMap; diff --git a/third_party/rust/litemap/src/map.rs b/third_party/rust/litemap/src/map.rs new file mode 100644 index 0000000000..195a46d723 --- /dev/null +++ b/third_party/rust/litemap/src/map.rs @@ -0,0 +1,1248 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use crate::store::*; +use alloc::borrow::Borrow; +use alloc::boxed::Box; +use alloc::vec::Vec; +use core::cmp::Ordering; +use core::iter::FromIterator; +use core::marker::PhantomData; +use core::mem; +use core::ops::{Index, IndexMut, Range}; + +/// A simple "flat" map based on a sorted vector +/// +/// See the [module level documentation][super] for why one should use this. +/// +/// The API is roughly similar to that of [`std::collections::BTreeMap`]. +#[derive(Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)] +#[cfg_attr(feature = "yoke", derive(yoke::Yokeable))] +pub struct LiteMap<K: ?Sized, V: ?Sized, S = alloc::vec::Vec<(K, V)>> { + pub(crate) values: S, + pub(crate) _key_type: PhantomData<K>, + pub(crate) _value_type: PhantomData<V>, +} + +impl<K, V> LiteMap<K, V> { + /// Construct a new [`LiteMap`] backed by Vec + pub const fn new_vec() -> Self { + Self { + values: alloc::vec::Vec::new(), + _key_type: PhantomData, + _value_type: PhantomData, + } + } +} + +impl<K, V, S> LiteMap<K, V, S> { + /// Construct a new [`LiteMap`] using the given values + /// + /// The store must be sorted and have no duplicate keys. + pub const fn from_sorted_store_unchecked(values: S) -> Self { + Self { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } +} + +impl<K, V> LiteMap<K, V, Vec<(K, V)>> { + /// Convert a [`LiteMap`] into a sorted `Vec<(K, V)>`. + #[inline] + pub fn into_tuple_vec(self) -> Vec<(K, V)> { + self.values + } +} + +impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> +where + S: StoreConstEmpty<K, V>, +{ + /// Create a new empty [`LiteMap`] + pub const fn new() -> Self { + Self { + values: S::EMPTY, + _key_type: PhantomData, + _value_type: PhantomData, + } + } +} + +impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> +where + S: Store<K, V>, +{ + /// The number of elements in the [`LiteMap`] + pub fn len(&self) -> usize { + self.values.lm_len() + } + + /// Whether the [`LiteMap`] is empty + pub fn is_empty(&self) -> bool { + self.values.lm_is_empty() + } + + /// Get the key-value pair residing at a particular index + /// + /// In most cases, prefer [`LiteMap::get()`] over this method. + #[inline] + pub fn get_indexed(&self, index: usize) -> Option<(&K, &V)> { + self.values.lm_get(index) + } + + /// Get the lowest-rank key/value pair from the `LiteMap`, if it exists. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = + /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]); + /// + /// assert_eq!(map.first(), Some((&1, &"uno"))); + /// ``` + #[inline] + pub fn first(&self) -> Option<(&K, &V)> { + self.values.lm_get(0) + } + + /// Get the highest-rank key/value pair from the `LiteMap`, if it exists. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = + /// LiteMap::<i32, &str, Vec<_>>::from_iter([(1, "uno"), (3, "tres")]); + /// + /// assert_eq!(map.last(), Some((&3, &"tres"))); + /// ``` + #[inline] + pub fn last(&self) -> Option<(&K, &V)> { + self.values.lm_get(self.len() - 1) + } + + /// Returns a new [`LiteMap`] with owned keys and values. + /// + /// The trait bounds allow transforming most slice and string types. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map: LiteMap<&str, &str> = LiteMap::new_vec(); + /// map.insert("one", "uno"); + /// map.insert("two", "dos"); + /// + /// let boxed_map: LiteMap<Box<str>, Box<str>> = map.to_boxed_keys_values(); + /// + /// assert_eq!(boxed_map.get("one"), Some(&Box::from("uno"))); + /// ``` + pub fn to_boxed_keys_values<KB: ?Sized, VB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, Box<VB>, SB> + where + SB: StoreMut<Box<KB>, Box<VB>>, + K: Borrow<KB>, + V: Borrow<VB>, + Box<KB>: for<'a> From<&'a KB>, + Box<VB>: for<'a> From<&'a VB>, + { + let mut values = SB::lm_with_capacity(self.len()); + for i in 0..self.len() { + #[allow(clippy::unwrap_used)] // iterating over our own length + let (k, v) = self.values.lm_get(i).unwrap(); + values.lm_push(Box::from(k.borrow()), Box::from(v.borrow())) + } + LiteMap { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } + + /// Returns a new [`LiteMap`] with owned keys and cloned values. + /// + /// The trait bounds allow transforming most slice and string types. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map: LiteMap<&str, usize> = LiteMap::new_vec(); + /// map.insert("one", 11); + /// map.insert("two", 22); + /// + /// let boxed_map: LiteMap<Box<str>, usize> = map.to_boxed_keys(); + /// + /// assert_eq!(boxed_map.get("one"), Some(&11)); + /// ``` + pub fn to_boxed_keys<KB: ?Sized, SB>(&self) -> LiteMap<Box<KB>, V, SB> + where + V: Clone, + SB: StoreMut<Box<KB>, V>, + K: Borrow<KB>, + Box<KB>: for<'a> From<&'a KB>, + { + let mut values = SB::lm_with_capacity(self.len()); + for i in 0..self.len() { + #[allow(clippy::unwrap_used)] // iterating over our own length + let (k, v) = self.values.lm_get(i).unwrap(); + values.lm_push(Box::from(k.borrow()), v.clone()) + } + LiteMap { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } + + /// Returns a new [`LiteMap`] with cloned keys and owned values. + /// + /// The trait bounds allow transforming most slice and string types. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map: LiteMap<usize, &str> = LiteMap::new_vec(); + /// map.insert(11, "uno"); + /// map.insert(22, "dos"); + /// + /// let boxed_map: LiteMap<usize, Box<str>> = map.to_boxed_values(); + /// + /// assert_eq!(boxed_map.get(&11), Some(&Box::from("uno"))); + /// ``` + pub fn to_boxed_values<VB: ?Sized, SB>(&self) -> LiteMap<K, Box<VB>, SB> + where + K: Clone, + SB: StoreMut<K, Box<VB>>, + V: Borrow<VB>, + Box<VB>: for<'a> From<&'a VB>, + { + let mut values = SB::lm_with_capacity(self.len()); + for i in 0..self.len() { + #[allow(clippy::unwrap_used)] // iterating over our own length + let (k, v) = self.values.lm_get(i).unwrap(); + values.lm_push(k.clone(), Box::from(v.borrow())) + } + LiteMap { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } +} + +impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> +where + K: Ord, + S: Store<K, V>, +{ + /// Get the value associated with `key`, if it exists. + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// assert_eq!(map.get(&1), Some(&"one")); + /// assert_eq!(map.get(&3), None); + /// ``` + pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> + where + K: Borrow<Q>, + Q: Ord, + { + match self.find_index(key) { + #[allow(clippy::unwrap_used)] // find_index returns a valid index + Ok(found) => Some(self.values.lm_get(found).unwrap().1), + Err(_) => None, + } + } + + /// Binary search the map with `predicate` to find a key, returning the value. + pub fn get_by(&self, predicate: impl FnMut(&K) -> Ordering) -> Option<&V> { + let index = self.values.lm_binary_search_by(predicate).ok()?; + self.values.lm_get(index).map(|(_, v)| v) + } + + /// Returns whether `key` is contained in this map + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// assert!(map.contains_key(&1)); + /// assert!(!map.contains_key(&3)); + /// ``` + pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool + where + K: Borrow<Q>, + Q: Ord, + { + self.find_index(key).is_ok() + } + + /// Obtain the index for a given key, or if the key is not found, the index + /// at which it would be inserted. + /// + /// (The return value works equivalently to [`slice::binary_search_by()`]) + /// + /// The indices returned can be used with [`Self::get_indexed()`]. Prefer using + /// [`Self::get()`] directly where possible. + #[inline] + pub fn find_index<Q: ?Sized>(&self, key: &Q) -> Result<usize, usize> + where + K: Borrow<Q>, + Q: Ord, + { + self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) + } +} + +impl<K: ?Sized, V: ?Sized, S> LiteMap<K, V, S> +where + S: StoreSlice<K, V>, +{ + /// Creates a new [`LiteMap`] from a range of the current [`LiteMap`]. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// map.insert(3, "three"); + /// + /// let mut sub_map = map.get_indexed_range(1..3).expect("valid range"); + /// assert_eq!(sub_map.get(&1), None); + /// assert_eq!(sub_map.get(&2), Some(&"two")); + /// assert_eq!(sub_map.get(&3), Some(&"three")); + /// ``` + pub fn get_indexed_range(&self, range: Range<usize>) -> Option<LiteMap<K, V, &S::Slice>> { + let subslice = self.values.lm_get_range(range)?; + Some(LiteMap { + values: subslice, + _key_type: PhantomData, + _value_type: PhantomData, + }) + } + + /// Borrows this [`LiteMap`] as one of its slice type. + /// + /// This can be useful in situations where you need a `LiteMap` by value but do not want + /// to clone the owned version. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// + /// let borrowed_map = map.as_sliced(); + /// assert_eq!(borrowed_map.get(&1), Some(&"one")); + /// assert_eq!(borrowed_map.get(&2), Some(&"two")); + /// ``` + pub fn as_sliced(&self) -> LiteMap<K, V, &S::Slice> { + // Won't panic: 0..self.len() is within range + #[allow(clippy::unwrap_used)] + let subslice = self.values.lm_get_range(0..self.len()).unwrap(); + LiteMap { + values: subslice, + _key_type: PhantomData, + _value_type: PhantomData, + } + } + + /// Borrows the backing buffer of this [`LiteMap`] as its slice type. + /// + /// The slice will be sorted. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// + /// let slice = map.as_slice(); + /// assert_eq!(slice, &[(1, "one"), (2, "two")]); + /// ``` + pub fn as_slice(&self) -> &S::Slice { + // Won't panic: 0..self.len() is within range + #[allow(clippy::unwrap_used)] + self.values.lm_get_range(0..self.len()).unwrap() + } +} + +impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> +where + S: Store<K, V>, +{ + /// Returns a new [`LiteMap`] with keys and values borrowed from this one. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); + /// map.insert(Box::new(1), "one".to_string()); + /// map.insert(Box::new(2), "two".to_string()); + /// + /// let borrowed_map: LiteMap<&usize, &str> = map.to_borrowed_keys_values(); + /// + /// assert_eq!(borrowed_map.get(&1), Some(&"one")); + /// ``` + pub fn to_borrowed_keys_values<KB: ?Sized, VB: ?Sized, SB>( + &'a self, + ) -> LiteMap<&'a KB, &'a VB, SB> + where + K: Borrow<KB>, + V: Borrow<VB>, + SB: StoreMut<&'a KB, &'a VB>, + { + let mut values = SB::lm_with_capacity(self.len()); + for i in 0..self.len() { + #[allow(clippy::unwrap_used)] // iterating over our own length + let (k, v) = self.values.lm_get(i).unwrap(); + values.lm_push(k.borrow(), v.borrow()) + } + LiteMap { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } + + /// Returns a new [`LiteMap`] with keys borrowed from this one and cloned values. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); + /// map.insert(Box::new(1), "one".to_string()); + /// map.insert(Box::new(2), "two".to_string()); + /// + /// let borrowed_map: LiteMap<&usize, String> = map.to_borrowed_keys(); + /// + /// assert_eq!(borrowed_map.get(&1), Some(&"one".to_string())); + /// ``` + pub fn to_borrowed_keys<KB: ?Sized, SB>(&'a self) -> LiteMap<&'a KB, V, SB> + where + K: Borrow<KB>, + V: Clone, + SB: StoreMut<&'a KB, V>, + { + let mut values = SB::lm_with_capacity(self.len()); + for i in 0..self.len() { + #[allow(clippy::unwrap_used)] // iterating over our own length + let (k, v) = self.values.lm_get(i).unwrap(); + values.lm_push(k.borrow(), v.clone()) + } + LiteMap { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } + + /// Returns a new [`LiteMap`] with values borrowed from this one and cloned keys. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map: LiteMap<Box<usize>, String> = LiteMap::new_vec(); + /// map.insert(Box::new(1), "one".to_string()); + /// map.insert(Box::new(2), "two".to_string()); + /// + /// let borrowed_map: LiteMap<Box<usize>, &str> = map.to_borrowed_values(); + /// + /// assert_eq!(borrowed_map.get(&1), Some(&"one")); + /// ``` + pub fn to_borrowed_values<VB: ?Sized, SB>(&'a self) -> LiteMap<K, &'a VB, SB> + where + K: Clone, + V: Borrow<VB>, + SB: StoreMut<K, &'a VB>, + { + let mut values = SB::lm_with_capacity(self.len()); + for i in 0..self.len() { + #[allow(clippy::unwrap_used)] // iterating over our own length + let (k, v) = self.values.lm_get(i).unwrap(); + values.lm_push(k.clone(), v.borrow()) + } + LiteMap { + values, + _key_type: PhantomData, + _value_type: PhantomData, + } + } +} + +impl<K, V, S> LiteMap<K, V, S> +where + S: StoreMut<K, V>, +{ + /// Construct a new [`LiteMap`] with a given capacity + pub fn with_capacity(capacity: usize) -> Self { + Self { + values: S::lm_with_capacity(capacity), + _key_type: PhantomData, + _value_type: PhantomData, + } + } + + /// Remove all elements from the [`LiteMap`] + pub fn clear(&mut self) { + self.values.lm_clear() + } + + /// Reserve capacity for `additional` more elements to be inserted into + /// the [`LiteMap`] to avoid frequent reallocations. + /// + /// See [`Vec::reserve()`] for more information. + /// + /// [`Vec::reserve()`]: alloc::vec::Vec::reserve + pub fn reserve(&mut self, additional: usize) { + self.values.lm_reserve(additional) + } +} + +impl<K, V, S> LiteMap<K, V, S> +where + K: Ord, + S: StoreMut<K, V>, +{ + /// Get the value associated with `key`, if it exists, as a mutable reference. + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// if let Some(mut v) = map.get_mut(&1) { + /// *v = "uno"; + /// } + /// assert_eq!(map.get(&1), Some(&"uno")); + /// ``` + pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> + where + K: Borrow<Q>, + Q: Ord, + { + match self.find_index(key) { + #[allow(clippy::unwrap_used)] // find_index returns a valid index + Ok(found) => Some(self.values.lm_get_mut(found).unwrap().1), + Err(_) => None, + } + } + + /// Appends `value` with `key` to the end of the underlying vector, returning + /// `key` and `value` _if it failed_. Useful for extending with an existing + /// sorted list. + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// assert!(map.try_append(1, "uno").is_none()); + /// assert!(map.try_append(3, "tres").is_none()); + /// + /// assert!( + /// matches!(map.try_append(3, "tres-updated"), Some((3, "tres-updated"))), + /// "append duplicate of last key", + /// ); + /// + /// assert!( + /// matches!(map.try_append(2, "dos"), Some((2, "dos"))), + /// "append out of order" + /// ); + /// + /// assert_eq!(map.get(&1), Some(&"uno")); + /// + /// // contains the original value for the key: 3 + /// assert_eq!(map.get(&3), Some(&"tres")); + /// + /// // not appended since it wasn't in order + /// assert_eq!(map.get(&2), None); + /// ``` + #[must_use] + pub fn try_append(&mut self, key: K, value: V) -> Option<(K, V)> { + if let Some(last) = self.values.lm_last() { + if last.0 >= &key { + return Some((key, value)); + } + } + + self.values.lm_push(key, value); + None + } + + /// Insert `value` with `key`, returning the existing value if it exists. + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// assert_eq!(map.get(&1), Some(&"one")); + /// assert_eq!(map.get(&3), None); + /// ``` + pub fn insert(&mut self, key: K, value: V) -> Option<V> { + self.insert_save_key(key, value).map(|(_, v)| v) + } + + /// Version of [`Self::insert()`] that returns both the key and the old value. + fn insert_save_key(&mut self, key: K, value: V) -> Option<(K, V)> { + match self.values.lm_binary_search_by(|k| k.cmp(&key)) { + #[allow(clippy::unwrap_used)] // Index came from binary_search + Ok(found) => Some(( + key, + mem::replace(self.values.lm_get_mut(found).unwrap().1, value), + )), + Err(ins) => { + self.values.lm_insert(ins, key, value); + None + } + } + } + + /// Attempts to insert a unique entry into the map. + /// + /// If `key` is not already in the map, inserts it with the corresponding `value` + /// and returns `None`. + /// + /// If `key` is already in the map, no change is made to the map, and the key and value + /// are returned back to the caller. + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(3, "three"); + /// + /// // 2 is not yet in the map... + /// assert_eq!(map.try_insert(2, "two"), None); + /// assert_eq!(map.len(), 3); + /// + /// // ...but now it is. + /// assert_eq!(map.try_insert(2, "TWO"), Some((2, "TWO"))); + /// assert_eq!(map.len(), 3); + /// ``` + pub fn try_insert(&mut self, key: K, value: V) -> Option<(K, V)> { + match self.values.lm_binary_search_by(|k| k.cmp(&key)) { + Ok(_) => Some((key, value)), + Err(ins) => { + self.values.lm_insert(ins, key, value); + None + } + } + } + + /// Attempts to insert a unique entry into the map. + /// + /// If `key` is not already in the map, invokes the closure to compute `value`, inserts + /// the pair into the map, and returns a reference to the value. The closure is passed + /// a reference to the `key` argument. + /// + /// If `key` is already in the map, a reference to the existing value is returned. + /// + /// Additionally, the index of the value in the map is returned. If it is not desirable + /// to hold on to the mutable reference's lifetime, the index can be used to access the + /// element via [`LiteMap::get_indexed()`]. + /// + /// The closure returns a `Result` to allow for a fallible insertion function. If the + /// creation of `value` is infallible, you can use [`core::convert::Infallible`]. + /// + /// ``` + /// use litemap::LiteMap; + /// + /// /// Helper function to unwrap an `Infallible` result from the insertion function + /// fn unwrap_infallible<T>(result: Result<T, core::convert::Infallible>) -> T { + /// result.unwrap_or_else(|never| match never {}) + /// } + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(3, "three"); + /// + /// // 2 is not yet in the map... + /// let result1 = unwrap_infallible( + /// map.try_get_or_insert(2, |_| Ok("two")) + /// ); + /// assert_eq!(result1.1, &"two"); + /// assert_eq!(map.len(), 3); + /// + /// // ...but now it is. + /// let result1 = unwrap_infallible( + /// map.try_get_or_insert(2, |_| Ok("TWO")) + /// ); + /// assert_eq!(result1.1, &"two"); + /// assert_eq!(map.len(), 3); + /// ``` + pub fn try_get_or_insert<E>( + &mut self, + key: K, + value: impl FnOnce(&K) -> Result<V, E>, + ) -> Result<(usize, &V), E> { + let idx = match self.values.lm_binary_search_by(|k| k.cmp(&key)) { + Ok(idx) => idx, + Err(idx) => { + let value = value(&key)?; + self.values.lm_insert(idx, key, value); + idx + } + }; + #[allow(clippy::unwrap_used)] // item at idx found or inserted above + Ok((idx, self.values.lm_get(idx).unwrap().1)) + } + + /// Remove the value at `key`, returning it if it exists. + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// assert_eq!(map.remove(&1), Some("one")); + /// assert_eq!(map.get(&1), None); + /// ``` + pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> + where + K: Borrow<Q>, + Q: Ord, + { + match self.values.lm_binary_search_by(|k| k.borrow().cmp(key)) { + Ok(found) => Some(self.values.lm_remove(found).1), + Err(_) => None, + } + } +} + +impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> +where + K: Ord, + S: StoreIterableMut<'a, K, V> + StoreFromIterator<K, V>, +{ + /// Insert all elements from `other` into this `LiteMap`. + /// + /// If `other` contains keys that already exist in `self`, the values in `other` replace the + /// corresponding ones in `self`, and the rejected items from `self` are returned as a new + /// `LiteMap`. Otherwise, `None` is returned. + /// + /// The implementation of this function is optimized if `self` and `other` have no overlap. + /// + /// # Examples + /// + /// ``` + /// use litemap::LiteMap; + /// + /// let mut map1 = LiteMap::new_vec(); + /// map1.insert(1, "one"); + /// map1.insert(2, "two"); + /// + /// let mut map2 = LiteMap::new_vec(); + /// map2.insert(2, "TWO"); + /// map2.insert(4, "FOUR"); + /// + /// let leftovers = map1.extend_from_litemap(map2); + /// + /// assert_eq!(map1.len(), 3); + /// assert_eq!(map1.get(&1), Some("one").as_ref()); + /// assert_eq!(map1.get(&2), Some("TWO").as_ref()); + /// assert_eq!(map1.get(&4), Some("FOUR").as_ref()); + /// + /// let map3 = leftovers.expect("Duplicate keys"); + /// assert_eq!(map3.len(), 1); + /// assert_eq!(map3.get(&2), Some("two").as_ref()); + /// ``` + pub fn extend_from_litemap(&mut self, other: Self) -> Option<Self> { + if self.is_empty() { + self.values = other.values; + return None; + } + if other.is_empty() { + return None; + } + if self.last().map(|(k, _)| k) < other.first().map(|(k, _)| k) { + // append other to self + self.values.lm_extend_end(other.values); + None + } else if self.first().map(|(k, _)| k) > other.last().map(|(k, _)| k) { + // prepend other to self + self.values.lm_extend_start(other.values); + None + } else { + // insert every element + let leftover_tuples = other + .values + .lm_into_iter() + .filter_map(|(k, v)| self.insert_save_key(k, v)) + .collect(); + let ret = LiteMap { + values: leftover_tuples, + _key_type: PhantomData, + _value_type: PhantomData, + }; + if ret.is_empty() { + None + } else { + Some(ret) + } + } + } +} + +impl<K, V, S> Default for LiteMap<K, V, S> +where + S: Store<K, V> + Default, +{ + fn default() -> Self { + Self { + values: S::default(), + _key_type: PhantomData, + _value_type: PhantomData, + } + } +} +impl<K, V, S> Index<&'_ K> for LiteMap<K, V, S> +where + K: Ord, + S: Store<K, V>, +{ + type Output = V; + fn index(&self, key: &K) -> &V { + #[allow(clippy::panic)] // documented + match self.get(key) { + Some(v) => v, + None => panic!("no entry found for key"), + } + } +} +impl<K, V, S> IndexMut<&'_ K> for LiteMap<K, V, S> +where + K: Ord, + S: StoreMut<K, V>, +{ + fn index_mut(&mut self, key: &K) -> &mut V { + #[allow(clippy::panic)] // documented + match self.get_mut(key) { + Some(v) => v, + None => panic!("no entry found for key"), + } + } +} +impl<K, V, S> FromIterator<(K, V)> for LiteMap<K, V, S> +where + K: Ord, + S: StoreFromIterable<K, V>, +{ + fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { + let values = S::lm_sort_from_iter(iter); + Self::from_sorted_store_unchecked(values) + } +} + +impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> +where + S: StoreIterable<'a, K, V>, +{ + /// Produce an ordered iterator over key-value pairs + pub fn iter(&'a self) -> impl DoubleEndedIterator<Item = (&'a K, &'a V)> { + self.values.lm_iter() + } + + /// Produce an ordered iterator over keys + pub fn iter_keys(&'a self) -> impl DoubleEndedIterator<Item = &'a K> { + self.values.lm_iter().map(|val| val.0) + } + + /// Produce an iterator over values, ordered by their keys + pub fn iter_values(&'a self) -> impl DoubleEndedIterator<Item = &'a V> { + self.values.lm_iter().map(|val| val.1) + } +} + +impl<'a, K: 'a, V: 'a, S> LiteMap<K, V, S> +where + S: StoreIterableMut<'a, K, V>, +{ + /// Produce an ordered mutable iterator over key-value pairs + pub fn iter_mut(&'a mut self) -> impl DoubleEndedIterator<Item = (&'a K, &'a mut V)> { + self.values.lm_iter_mut() + } +} + +impl<K, V, S> LiteMap<K, V, S> +where + S: StoreMut<K, V>, +{ + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all elements such that `f((&k, &v))` returns `false`. + /// + /// # Example + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// let mut map = LiteMap::new_vec(); + /// map.insert(1, "one"); + /// map.insert(2, "two"); + /// map.insert(3, "three"); + /// + /// // Retain elements with odd keys + /// map.retain(|k, _| k % 2 == 1); + /// + /// assert_eq!(map.get(&1), Some(&"one")); + /// assert_eq!(map.get(&2), None); + /// ``` + #[inline] + pub fn retain<F>(&mut self, predicate: F) + where + F: FnMut(&K, &V) -> bool, + { + self.values.lm_retain(predicate) + } +} + +impl<'a, K, V> LiteMap<K, V, &'a [(K, V)]> { + /// Const version of [`LiteMap::len()`] for a slice store. + /// + /// Note: This function will no longer be needed if const trait behavior is stabilized. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// static map: LiteMap<&str, usize, &[(&str, usize)]> = + /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]); + /// static len: usize = map.const_len(); + /// assert_eq!(len, 2); + /// ``` + #[inline] + pub const fn const_len(&self) -> usize { + self.values.len() + } + + /// Const version of [`LiteMap::is_empty()`] for a slice store. + /// + /// Note: This function will no longer be needed if const trait behavior is stabilized. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// static map: LiteMap<&str, usize, &[(&str, usize)]> = + /// LiteMap::from_sorted_store_unchecked(&[]); + /// static is_empty: bool = map.const_is_empty(); + /// assert!(is_empty); + /// ``` + #[inline] + pub const fn const_is_empty(&self) -> bool { + self.values.is_empty() + } + + /// Const version of [`LiteMap::get_indexed()`] for a slice store. + /// + /// Note: This function will no longer be needed if const trait behavior is stabilized. + /// + /// # Panics + /// + /// Panics if the index is out of bounds. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// static map: LiteMap<&str, usize, &[(&str, usize)]> = + /// LiteMap::from_sorted_store_unchecked(&[("a", 11), ("b", 22)]); + /// static t: &(&str, usize) = map.const_get_indexed_or_panic(0); + /// assert_eq!(t.0, "a"); + /// assert_eq!(t.1, 11); + /// ``` + #[inline] + #[allow(clippy::indexing_slicing)] // documented + pub const fn const_get_indexed_or_panic(&self, index: usize) -> &'a (K, V) { + &self.values[index] + } +} + +const fn const_cmp_bytes(a: &[u8], b: &[u8]) -> Ordering { + let (max, default) = if a.len() == b.len() { + (a.len(), Ordering::Equal) + } else if a.len() < b.len() { + (a.len(), Ordering::Less) + } else { + (b.len(), Ordering::Greater) + }; + let mut i = 0; + #[allow(clippy::indexing_slicing)] // indexes in range by above checks + while i < max { + if a[i] == b[i] { + i += 1; + continue; + } else if a[i] < b[i] { + return Ordering::Less; + } else { + return Ordering::Greater; + } + } + default +} + +impl<'a, V> LiteMap<&'a str, V, &'a [(&'a str, V)]> { + /// Const function to get the value associated with a `&str` key, if it exists. + /// + /// Also returns the index of the value. + /// + /// Note: This function will no longer be needed if const trait behavior is stabilized. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// static map: LiteMap<&str, usize, &[(&str, usize)]> = + /// LiteMap::from_sorted_store_unchecked(&[ + /// ("abc", 11), + /// ("bcd", 22), + /// ("cde", 33), + /// ("def", 44), + /// ("efg", 55), + /// ]); + /// + /// static d: Option<(usize, &usize)> = map.const_get_with_index("def"); + /// assert_eq!(d, Some((3, &44))); + /// + /// static n: Option<(usize, &usize)> = map.const_get_with_index("dng"); + /// assert_eq!(n, None); + /// ``` + pub const fn const_get_with_index(&self, key: &str) -> Option<(usize, &'a V)> { + let mut i = 0; + let mut j = self.const_len(); + while i < j { + let mid = (i + j) / 2; + #[allow(clippy::indexing_slicing)] // in range + let x = &self.values[mid]; + match const_cmp_bytes(key.as_bytes(), x.0.as_bytes()) { + Ordering::Equal => return Some((mid, &x.1)), + Ordering::Greater => i = mid + 1, + Ordering::Less => j = mid, + }; + } + None + } +} + +impl<'a, V> LiteMap<&'a [u8], V, &'a [(&'a [u8], V)]> { + /// Const function to get the value associated with a `&[u8]` key, if it exists. + /// + /// Also returns the index of the value. + /// + /// Note: This function will no longer be needed if const trait behavior is stabilized. + /// + /// # Examples + /// + /// ```rust + /// use litemap::LiteMap; + /// + /// static map: LiteMap<&[u8], usize, &[(&[u8], usize)]> = + /// LiteMap::from_sorted_store_unchecked(&[ + /// (b"abc", 11), + /// (b"bcd", 22), + /// (b"cde", 33), + /// (b"def", 44), + /// (b"efg", 55), + /// ]); + /// + /// static d: Option<(usize, &usize)> = map.const_get_with_index(b"def"); + /// assert_eq!(d, Some((3, &44))); + /// + /// static n: Option<(usize, &usize)> = map.const_get_with_index(b"dng"); + /// assert_eq!(n, None); + /// ``` + pub const fn const_get_with_index(&self, key: &[u8]) -> Option<(usize, &'a V)> { + let mut i = 0; + let mut j = self.const_len(); + while i < j { + let mid = (i + j) / 2; + #[allow(clippy::indexing_slicing)] // in range + let x = &self.values[mid]; + match const_cmp_bytes(key, x.0) { + Ordering::Equal => return Some((mid, &x.1)), + Ordering::Greater => i = mid + 1, + Ordering::Less => j = mid, + }; + } + None + } +} + +macro_rules! impl_const_get_with_index_for_integer { + ($integer:ty) => { + impl<'a, V> LiteMap<$integer, V, &'a [($integer, V)]> { + /// Const function to get the value associated with an integer key, if it exists. + /// + /// Note: This function will no longer be needed if const trait behavior is stabilized. + /// + /// Also returns the index of the value. + pub const fn const_get_with_index(&self, key: $integer) -> Option<(usize, &'a V)> { + let mut i = 0; + let mut j = self.const_len(); + while i < j { + let mid = (i + j) / 2; + #[allow(clippy::indexing_slicing)] // in range + let x = &self.values[mid]; + if key == x.0 { + return Some((mid, &x.1)); + } else if key > x.0 { + i = mid + 1; + } else { + j = mid; + } + } + return None; + } + } + }; +} + +impl_const_get_with_index_for_integer!(u8); +impl_const_get_with_index_for_integer!(u16); +impl_const_get_with_index_for_integer!(u32); +impl_const_get_with_index_for_integer!(u64); +impl_const_get_with_index_for_integer!(u128); +impl_const_get_with_index_for_integer!(usize); +impl_const_get_with_index_for_integer!(i8); +impl_const_get_with_index_for_integer!(i16); +impl_const_get_with_index_for_integer!(i32); +impl_const_get_with_index_for_integer!(i64); +impl_const_get_with_index_for_integer!(i128); +impl_const_get_with_index_for_integer!(isize); + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn from_iterator() { + let mut expected = LiteMap::with_capacity(4); + expected.insert(1, "updated-one"); + expected.insert(2, "original-two"); + expected.insert(3, "original-three"); + expected.insert(4, "updated-four"); + + let actual = [ + (1, "original-one"), + (2, "original-two"), + (4, "original-four"), + (4, "updated-four"), + (1, "updated-one"), + (3, "original-three"), + ] + .into_iter() + .collect::<LiteMap<_, _>>(); + + assert_eq!(expected, actual); + } + fn make_13() -> LiteMap<usize, &'static str> { + let mut result = LiteMap::new(); + result.insert(1, "one"); + result.insert(3, "three"); + result + } + + fn make_24() -> LiteMap<usize, &'static str> { + let mut result = LiteMap::new(); + result.insert(2, "TWO"); + result.insert(4, "FOUR"); + result + } + + fn make_46() -> LiteMap<usize, &'static str> { + let mut result = LiteMap::new(); + result.insert(4, "four"); + result.insert(6, "six"); + result + } + + #[test] + fn extend_from_litemap_append() { + let mut map = LiteMap::new(); + map.extend_from_litemap(make_13()) + .ok_or(()) + .expect_err("Append to empty map"); + map.extend_from_litemap(make_46()) + .ok_or(()) + .expect_err("Append to lesser map"); + assert_eq!(map.len(), 4); + } + + #[test] + fn extend_from_litemap_prepend() { + let mut map = LiteMap::new(); + map.extend_from_litemap(make_46()) + .ok_or(()) + .expect_err("Prepend to empty map"); + map.extend_from_litemap(make_13()) + .ok_or(()) + .expect_err("Prepend to lesser map"); + assert_eq!(map.len(), 4); + } + + #[test] + fn extend_from_litemap_insert() { + let mut map = LiteMap::new(); + map.extend_from_litemap(make_13()) + .ok_or(()) + .expect_err("Append to empty map"); + map.extend_from_litemap(make_24()) + .ok_or(()) + .expect_err("Insert with no conflict"); + map.extend_from_litemap(make_46()) + .ok_or(()) + .expect("Insert with conflict"); + assert_eq!(map.len(), 5); + } + + #[test] + fn test_const_cmp_bytes() { + let strs = &["a", "aa", "abc", "abde", "bcd", "bcde"]; + for i in 0..strs.len() { + for j in 0..strs.len() { + let a = strs[i].as_bytes(); + let b = strs[j].as_bytes(); + assert_eq!(a.cmp(b), const_cmp_bytes(a, b)); + } + } + } +} diff --git a/third_party/rust/litemap/src/serde.rs b/third_party/rust/litemap/src/serde.rs new file mode 100644 index 0000000000..45e249ea8d --- /dev/null +++ b/third_party/rust/litemap/src/serde.rs @@ -0,0 +1,213 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use super::LiteMap; +use crate::store::*; +use core::fmt; +use core::marker::PhantomData; +use serde::de::{MapAccess, SeqAccess, Visitor}; +use serde::{Deserialize, Deserializer}; + +#[cfg(feature = "serde")] +use serde::{ser::SerializeMap, Serialize, Serializer}; + +#[cfg(feature = "serde")] +impl<K, V, R> Serialize for LiteMap<K, V, R> +where + K: Serialize, + V: Serialize, + R: Store<K, V> + Serialize, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + // Many human-readable formats don't support values other + // than numbers and strings as map keys. For them, we can serialize + // as a vec of tuples instead + if serializer.is_human_readable() { + if let Some((ref k, _)) = self.values.lm_get(0) { + if !super::serde_helpers::is_num_or_string(k) { + return self.values.serialize(serializer); + } + // continue to regular serialization + } + } + let mut map = serializer.serialize_map(Some(self.len()))?; + let mut i = 0; + while i < self.values.lm_len() { + #[allow(clippy::unwrap_used)] // i is in range + let (k, v) = self.values.lm_get(i).unwrap(); + map.serialize_entry(k, v)?; + i += 1; + } + map.end() + } +} + +/// Modified example from https://serde.rs/deserialize-map.html +#[allow(clippy::type_complexity)] +struct LiteMapVisitor<K, V, R> { + marker: PhantomData<fn() -> LiteMap<K, V, R>>, +} + +impl<K, V, R> LiteMapVisitor<K, V, R> { + fn new() -> Self { + Self { + marker: PhantomData, + } + } +} + +impl<'de, K, V, R> Visitor<'de> for LiteMapVisitor<K, V, R> +where + K: Deserialize<'de> + Ord, + V: Deserialize<'de>, + R: StoreMut<K, V> + StoreFromIterable<K, V>, +{ + type Value = LiteMap<K, V, R>; + + fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result { + formatter.write_str("a map produced by LiteMap") + } + + fn visit_seq<S>(self, mut access: S) -> Result<Self::Value, S::Error> + where + S: SeqAccess<'de>, + { + let mut map = LiteMap::with_capacity(access.size_hint().unwrap_or(0)); + + // While there are entries remaining in the input, add them + // into our map. + while let Some((key, value)) = access.next_element()? { + // Try to append it at the end, hoping for a sorted map. + // If not sorted, insert as usual. + // This allows for arbitrary maps (e.g. from user JSON) + // to be deserialized into LiteMap + // without impacting performance in the case of deserializing + // a serialized map that came from another LiteMap + if let Some((key, value)) = map.try_append(key, value) { + // Note: this effectively selection sorts the map, + // which isn't efficient for large maps + map.insert(key, value); + } + } + + Ok(map) + } + + fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error> + where + M: MapAccess<'de>, + { + let mut map = LiteMap::with_capacity(access.size_hint().unwrap_or(0)); + + // While there are entries remaining in the input, add them + // into our map. + while let Some((key, value)) = access.next_entry()? { + // Try to append it at the end, hoping for a sorted map. + // If not sorted, insert as usual. + // This allows for arbitrary maps (e.g. from user JSON) + // to be deserialized into LiteMap + // without impacting performance in the case of deserializing + // a serialized map that came from another LiteMap + if let Some((key, value)) = map.try_append(key, value) { + // Note: this effectively selection sorts the map, + // which isn't efficient for large maps + map.insert(key, value); + } + } + + Ok(map) + } +} + +impl<'de, K, V, R> Deserialize<'de> for LiteMap<K, V, R> +where + K: Ord + Deserialize<'de>, + V: Deserialize<'de>, + R: StoreMut<K, V> + StoreFromIterable<K, V>, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + if deserializer.is_human_readable() { + // deserialize_any only works on self-describing (human-readable) + // formats + deserializer.deserialize_any(LiteMapVisitor::new()) + } else { + deserializer.deserialize_map(LiteMapVisitor::new()) + } + } +} + +#[cfg(test)] +mod test { + use crate::LiteMap; + use alloc::borrow::ToOwned; + use alloc::string::String; + + fn get_simple_map() -> LiteMap<u32, String> { + [ + (1, "one".to_owned()), + (2, "two".to_owned()), + (4, "four".to_owned()), + (5, "five".to_owned()), + ] + .into_iter() + .collect() + } + + fn get_tuple_map() -> LiteMap<(u32, String), String> { + [ + ((1, "en".to_owned()), "one".to_owned()), + ((1, "zh".to_owned()), "一".to_owned()), + ((2, "en".to_owned()), "two".to_owned()), + ((2, "zh".to_owned()), "二".to_owned()), + ((4, "en".to_owned()), "four".to_owned()), + ((5, "en".to_owned()), "five".to_owned()), + ((5, "zh".to_owned()), "五".to_owned()), + ((7, "zh".to_owned()), "七".to_owned()), + ] + .into_iter() + .collect() + } + + #[test] + fn test_roundtrip_json() { + let map = get_simple_map(); + let json = serde_json::to_string(&map).unwrap(); + assert_eq!( + json, + "{\"1\":\"one\",\"2\":\"two\",\"4\":\"four\",\"5\":\"five\"}" + ); + let deserialized: LiteMap<u32, String> = serde_json::from_str(&json).unwrap(); + assert_eq!(map, deserialized); + + let map = get_tuple_map(); + let json = serde_json::to_string(&map).unwrap(); + assert_eq!( + json, + "[[[1,\"en\"],\"one\"],[[1,\"zh\"],\"一\"],[[2,\"en\"],\"two\"],\ + [[2,\"zh\"],\"二\"],[[4,\"en\"],\"four\"],[[5,\"en\"],\"five\"],\ + [[5,\"zh\"],\"五\"],[[7,\"zh\"],\"七\"]]" + ); + let deserialized: LiteMap<(u32, String), String> = serde_json::from_str(&json).unwrap(); + assert_eq!(map, deserialized); + } + + #[test] + fn test_roundtrip_postcard() { + let map = get_simple_map(); + let postcard = postcard::to_stdvec(&map).unwrap(); + let deserialized: LiteMap<u32, String> = postcard::from_bytes(&postcard).unwrap(); + assert_eq!(map, deserialized); + + let map = get_tuple_map(); + let postcard = postcard::to_stdvec(&map).unwrap(); + let deserialized: LiteMap<(u32, String), String> = postcard::from_bytes(&postcard).unwrap(); + assert_eq!(map, deserialized); + } +} diff --git a/third_party/rust/litemap/src/serde_helpers.rs b/third_party/rust/litemap/src/serde_helpers.rs new file mode 100644 index 0000000000..b1ead938a0 --- /dev/null +++ b/third_party/rust/litemap/src/serde_helpers.rs @@ -0,0 +1,168 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +// @@@@@@@@@@@@@@@@ +// THIS FILE IS SHARED BETWEEN LITEMAP AND ZEROVEC. PLEASE KEEP IT IN SYNC FOR ALL EDITS +// @@@@@@@@@@@@@@@@ + +use serde::ser::{Impossible, Serialize, Serializer}; + +pub fn is_num_or_string<T: Serialize + ?Sized>(k: &T) -> bool { + // Serializer that errors in the same cases as serde_json::ser::MapKeySerializer + struct MapKeySerializerDryRun; + impl Serializer for MapKeySerializerDryRun { + type Ok = (); + // Singleton error type that implements serde::ser::Error + type Error = core::fmt::Error; + + type SerializeSeq = Impossible<(), Self::Error>; + type SerializeTuple = Impossible<(), Self::Error>; + type SerializeTupleStruct = Impossible<(), Self::Error>; + type SerializeTupleVariant = Impossible<(), Self::Error>; + type SerializeMap = Impossible<(), Self::Error>; + type SerializeStruct = Impossible<(), Self::Error>; + type SerializeStructVariant = Impossible<(), Self::Error>; + + fn serialize_str(self, _value: &str) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_unit_variant( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + ) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_newtype_struct<T: Serialize + ?Sized>( + self, + _name: &'static str, + value: &T, + ) -> Result<Self::Ok, Self::Error> { + // Recurse + value.serialize(self) + } + fn serialize_bool(self, _value: bool) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_i8(self, _value: i8) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_i16(self, _value: i16) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_i32(self, _value: i32) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_i64(self, _value: i64) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + serde::serde_if_integer128! { + fn serialize_i128(self, _value: i128) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + } + fn serialize_u8(self, _value: u8) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_u16(self, _value: u16) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_u32(self, _value: u32) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_u64(self, _value: u64) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + serde::serde_if_integer128! { + fn serialize_u128(self, _value: u128) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + } + fn serialize_f32(self, _value: f32) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_f64(self, _value: f64) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_char(self, _value: char) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + fn serialize_bytes(self, _value: &[u8]) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_unit(self) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_unit_struct(self, _name: &'static str) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_newtype_variant<T: Serialize + ?Sized>( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + _value: &T, + ) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_none(self) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_some<T: Serialize + ?Sized>( + self, + _value: &T, + ) -> Result<Self::Ok, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_seq(self, _len: Option<usize>) -> Result<Self::SerializeSeq, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_tuple(self, _len: usize) -> Result<Self::SerializeTuple, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_tuple_struct( + self, + _name: &'static str, + _len: usize, + ) -> Result<Self::SerializeTupleStruct, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_tuple_variant( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + _len: usize, + ) -> Result<Self::SerializeTupleVariant, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_map(self, _len: Option<usize>) -> Result<Self::SerializeMap, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_struct( + self, + _name: &'static str, + _len: usize, + ) -> Result<Self::SerializeStruct, Self::Error> { + Err(core::fmt::Error) + } + fn serialize_struct_variant( + self, + _name: &'static str, + _variant_index: u32, + _variant: &'static str, + _len: usize, + ) -> Result<Self::SerializeStructVariant, Self::Error> { + Err(core::fmt::Error) + } + fn collect_str<T: core::fmt::Display + ?Sized>( + self, + _value: &T, + ) -> Result<Self::Ok, Self::Error> { + Ok(()) + } + } + k.serialize(MapKeySerializerDryRun).is_ok() +} diff --git a/third_party/rust/litemap/src/store/mod.rs b/third_party/rust/litemap/src/store/mod.rs new file mode 100644 index 0000000000..ca696a1afa --- /dev/null +++ b/third_party/rust/litemap/src/store/mod.rs @@ -0,0 +1,178 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +//! Traits for pluggable LiteMap backends. +//! +//! By default, LiteMap is backed by a `Vec`. However, in some environments, it may be desirable +//! to use a different data store while still using LiteMap to manage proper ordering of items. +//! +//! The general guidelines for a performant data store are: +//! +//! 1. Must support efficient random access for binary search +//! 2. Should support efficient append operations for deserialization +//! +//! To plug a custom data store into LiteMap, implement: +//! +//! - [`Store`] for most of the methods +//! - [`StoreIterable`] for methods that return iterators +//! - [`StoreFromIterator`] to enable `FromIterator` for LiteMap +//! +//! To test your implementation, enable the `"testing"` Cargo feature and use [`check_store()`]. +//! +//! [`check_store()`]: crate::testing::check_store + +mod slice_impl; +#[cfg(feature = "alloc")] +mod vec_impl; + +use core::cmp::Ordering; +use core::iter::DoubleEndedIterator; +use core::iter::FromIterator; +use core::iter::Iterator; +use core::ops::Range; + +/// Trait to enable const construction of empty store. +pub trait StoreConstEmpty<K: ?Sized, V: ?Sized> { + /// An empty store + const EMPTY: Self; +} + +/// Trait to enable pluggable backends for LiteMap. +/// +/// Some methods have default implementations provided for convenience; however, it is generally +/// better to implement all methods that your data store supports. +pub trait Store<K: ?Sized, V: ?Sized>: Sized { + /// Returns the number of elements in the store. + fn lm_len(&self) -> usize; + + /// Returns whether the store is empty (contains 0 elements). + fn lm_is_empty(&self) -> bool { + self.lm_len() == 0 + } + + /// Gets a key/value pair at the specified index. + fn lm_get(&self, index: usize) -> Option<(&K, &V)>; + + /// Gets the last element in the store, or `None` if the store is empty. + fn lm_last(&self) -> Option<(&K, &V)> { + let len = self.lm_len(); + if len == 0 { + None + } else { + self.lm_get(len - 1) + } + } + + /// Searches the store for a particular element with a comparator function. + /// + /// See the binary search implementation on `slice` for more information. + fn lm_binary_search_by<F>(&self, cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering; +} + +pub trait StoreFromIterable<K, V>: Store<K, V> { + /// Create a sorted store from `iter`. + fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self; +} + +pub trait StoreSlice<K: ?Sized, V: ?Sized>: Store<K, V> { + type Slice: ?Sized; + + fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice>; +} + +pub trait StoreMut<K, V>: Store<K, V> { + /// Creates a new store with the specified capacity hint. + /// + /// Implementations may ignore the argument if they do not support pre-allocating capacity. + fn lm_with_capacity(capacity: usize) -> Self; + + /// Reserves additional capacity in the store. + /// + /// Implementations may ignore the argument if they do not support pre-allocating capacity. + fn lm_reserve(&mut self, additional: usize); + + /// Gets a key/value pair at the specified index, with a mutable value. + fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)>; + + /// Pushes one additional item onto the store. + fn lm_push(&mut self, key: K, value: V); + + /// Inserts an item at a specific index in the store. + /// + /// # Panics + /// + /// Panics if `index` is greater than the length. + fn lm_insert(&mut self, index: usize, key: K, value: V); + + /// Removes an item at a specific index in the store. + /// + /// # Panics + /// + /// Panics if `index` is greater than the length. + fn lm_remove(&mut self, index: usize) -> (K, V); + + /// Removes all items from the store. + fn lm_clear(&mut self); + + /// Retains items satisfying a predicate in this store. + fn lm_retain<F>(&mut self, mut predicate: F) + where + F: FnMut(&K, &V) -> bool, + { + let mut i = 0; + while i < self.lm_len() { + #[allow(clippy::unwrap_used)] // i is in range + let (k, v) = self.lm_get(i).unwrap(); + if predicate(k, v) { + i += 1; + } else { + self.lm_remove(i); + } + } + } +} + +/// Iterator methods for the LiteMap store. +pub trait StoreIterable<'a, K: 'a + ?Sized, V: 'a + ?Sized>: Store<K, V> { + type KeyValueIter: Iterator<Item = (&'a K, &'a V)> + DoubleEndedIterator + 'a; + + /// Returns an iterator over key/value pairs. + fn lm_iter(&'a self) -> Self::KeyValueIter; +} + +pub trait StoreIterableMut<'a, K: 'a, V: 'a>: StoreMut<K, V> + StoreIterable<'a, K, V> { + type KeyValueIterMut: Iterator<Item = (&'a K, &'a mut V)> + DoubleEndedIterator + 'a; + type KeyValueIntoIter: Iterator<Item = (K, V)>; + + /// Returns an iterator over key/value pairs, with a mutable value. + fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut; + + /// Returns an iterator that moves every item from this store. + fn lm_into_iter(self) -> Self::KeyValueIntoIter; + + /// Adds items from another store to the end of this store. + fn lm_extend_end(&mut self, other: Self) + where + Self: Sized, + { + for item in other.lm_into_iter() { + self.lm_push(item.0, item.1); + } + } + + /// Adds items from another store to the beginning of this store. + fn lm_extend_start(&mut self, other: Self) + where + Self: Sized, + { + for (i, item) in other.lm_into_iter().enumerate() { + self.lm_insert(i, item.0, item.1); + } + } +} + +/// A store that can be built from a tuple iterator. +pub trait StoreFromIterator<K, V>: FromIterator<(K, V)> {} diff --git a/third_party/rust/litemap/src/store/slice_impl.rs b/third_party/rust/litemap/src/store/slice_impl.rs new file mode 100644 index 0000000000..48f6ca40cf --- /dev/null +++ b/third_party/rust/litemap/src/store/slice_impl.rs @@ -0,0 +1,63 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use super::*; + +type MapF<K, V> = fn(&(K, V)) -> (&K, &V); + +#[inline] +fn map_f<K, V>(input: &(K, V)) -> (&K, &V) { + (&input.0, &input.1) +} + +impl<'a, K: 'a, V: 'a> StoreConstEmpty<K, V> for &'a [(K, V)] { + const EMPTY: &'a [(K, V)] = &[]; +} + +impl<'a, K: 'a, V: 'a> Store<K, V> for &'a [(K, V)] { + #[inline] + fn lm_len(&self) -> usize { + self.len() + } + + #[inline] + fn lm_is_empty(&self) -> bool { + self.is_empty() + } + + #[inline] + fn lm_get(&self, index: usize) -> Option<(&K, &V)> { + self.get(index).map(map_f) + } + + #[inline] + fn lm_last(&self) -> Option<(&K, &V)> { + self.last().map(map_f) + } + + #[inline] + fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering, + { + self.binary_search_by(|(k, _)| cmp(k)) + } +} + +impl<'a, K, V> StoreSlice<K, V> for &'a [(K, V)] { + type Slice = [(K, V)]; + + fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice> { + self.get(range) + } +} + +impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for &'a [(K, V)] { + type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>; + + #[inline] + fn lm_iter(&'a self) -> Self::KeyValueIter { + self.iter().map(map_f) + } +} diff --git a/third_party/rust/litemap/src/store/vec_impl.rs b/third_party/rust/litemap/src/store/vec_impl.rs new file mode 100644 index 0000000000..2205e8e8ff --- /dev/null +++ b/third_party/rust/litemap/src/store/vec_impl.rs @@ -0,0 +1,181 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use super::*; +use alloc::vec::Vec; + +type MapF<K, V> = fn(&(K, V)) -> (&K, &V); + +#[inline] +fn map_f<K, V>(input: &(K, V)) -> (&K, &V) { + (&input.0, &input.1) +} + +type MapFMut<K, V> = fn(&mut (K, V)) -> (&K, &mut V); + +#[inline] +fn map_f_mut<K, V>(input: &mut (K, V)) -> (&K, &mut V) { + (&input.0, &mut input.1) +} + +impl<K, V> StoreConstEmpty<K, V> for Vec<(K, V)> { + const EMPTY: Vec<(K, V)> = Vec::new(); +} + +impl<K, V> Store<K, V> for Vec<(K, V)> { + #[inline] + fn lm_len(&self) -> usize { + self.as_slice().len() + } + + #[inline] + fn lm_is_empty(&self) -> bool { + self.as_slice().is_empty() + } + + #[inline] + fn lm_get(&self, index: usize) -> Option<(&K, &V)> { + self.as_slice().get(index).map(map_f) + } + + #[inline] + fn lm_last(&self) -> Option<(&K, &V)> { + self.as_slice().last().map(map_f) + } + + #[inline] + fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering, + { + self.as_slice().binary_search_by(|(k, _)| cmp(k)) + } +} + +impl<K, V> StoreSlice<K, V> for Vec<(K, V)> { + type Slice = [(K, V)]; + + fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice> { + self.get(range) + } +} + +impl<K, V> StoreMut<K, V> for Vec<(K, V)> { + #[inline] + fn lm_with_capacity(capacity: usize) -> Self { + Self::with_capacity(capacity) + } + + #[inline] + fn lm_reserve(&mut self, additional: usize) { + self.reserve(additional) + } + + #[inline] + fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.as_mut_slice().get_mut(index).map(map_f_mut) + } + + #[inline] + fn lm_push(&mut self, key: K, value: V) { + self.push((key, value)) + } + + #[inline] + fn lm_insert(&mut self, index: usize, key: K, value: V) { + self.insert(index, (key, value)) + } + + #[inline] + fn lm_remove(&mut self, index: usize) -> (K, V) { + self.remove(index) + } + + #[inline] + fn lm_clear(&mut self) { + self.clear() + } + + #[inline] + fn lm_retain<F>(&mut self, mut predicate: F) + where + F: FnMut(&K, &V) -> bool, + { + self.retain(|(k, v)| predicate(k, v)) + } +} + +impl<K: Ord, V> StoreFromIterable<K, V> for Vec<(K, V)> { + fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { + let iter = iter.into_iter(); + let mut container = match iter.size_hint() { + (_, Some(upper)) => Self::with_capacity(upper), + (lower, None) => Self::with_capacity(lower), + }; + + for (key, value) in iter { + if let Some(last) = container.lm_last() { + if last.0 >= &key { + match container.lm_binary_search_by(|k| k.cmp(&key)) { + #[allow(clippy::unwrap_used)] // Index came from binary_search + Ok(found) => { + let _ = + core::mem::replace(container.lm_get_mut(found).unwrap().1, value); + } + Err(ins) => { + container.insert(ins, (key, value)); + } + } + } else { + container.push((key, value)) + } + } else { + container.push((key, value)) + } + } + + container + } +} + +impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for Vec<(K, V)> { + type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>; + + #[inline] + fn lm_iter(&'a self) -> Self::KeyValueIter { + self.as_slice().iter().map(map_f) + } +} + +impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for Vec<(K, V)> { + type KeyValueIterMut = core::iter::Map<core::slice::IterMut<'a, (K, V)>, MapFMut<K, V>>; + type KeyValueIntoIter = alloc::vec::IntoIter<(K, V)>; + + #[inline] + fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut { + self.as_mut_slice().iter_mut().map(map_f_mut) + } + + #[inline] + fn lm_into_iter(self) -> Self::KeyValueIntoIter { + IntoIterator::into_iter(self) + } + + #[inline] + fn lm_extend_end(&mut self, other: Self) { + self.extend(other) + } + + #[inline] + fn lm_extend_start(&mut self, other: Self) { + self.splice(0..0, other); + } +} + +impl<K, V> StoreFromIterator<K, V> for Vec<(K, V)> {} + +#[test] +fn test_vec_impl() { + crate::testing::check_store_full::<Vec<(u32, u64)>>(); +} diff --git a/third_party/rust/litemap/src/testing.rs b/third_party/rust/litemap/src/testing.rs new file mode 100644 index 0000000000..2fb8c522a4 --- /dev/null +++ b/third_party/rust/litemap/src/testing.rs @@ -0,0 +1,240 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +//! Test utilities, primarily targeted to custom LiteMap stores. + +use crate::store::*; +use crate::LiteMap; +use alloc::vec::Vec; +use core::fmt::Debug; + +// Test code +#[allow(clippy::expect_used)] +fn check_equivalence<'a, K, V, S0, S1>(mut a: S0, mut b: S1) +where + K: Ord + Debug + PartialEq + 'a, + V: Debug + PartialEq + 'a, + S0: StoreMut<K, V> + StoreIterable<'a, K, V>, + S1: StoreMut<K, V> + StoreIterable<'a, K, V>, +{ + let len = a.lm_len(); + assert_eq!(len, b.lm_len()); + if len == 0 { + assert!(a.lm_is_empty()); + assert!(b.lm_is_empty()); + } + for i in 0..len { + let a_kv = a.lm_get(i); + let b_kv = b.lm_get(i); + assert!(a_kv.is_some()); + assert_eq!(a_kv, b_kv); + let a_kv_mut = a.lm_get_mut(i); + let b_kv_mut = b.lm_get_mut(i); + assert!(a_kv_mut.is_some()); + assert_eq!(a_kv_mut, b_kv_mut); + } + for j in 0..len { + let needle = a.lm_get(j).expect("j is in range").0; + let a_binary = a.lm_binary_search_by(|k| k.cmp(needle)); + let b_binary = a.lm_binary_search_by(|k| k.cmp(needle)); + assert_eq!(Ok(j), a_binary); + assert_eq!(Ok(j), b_binary); + } + assert!(a.lm_get(len).is_none()); + assert!(b.lm_get(len).is_none()); + assert_eq!(a.lm_last(), b.lm_last()); +} + +// Test code +#[allow(clippy::expect_used)] +fn check_into_iter_equivalence<'a, K, V, S0, S1>(a: S0, b: S1) +where + K: Ord + Debug + PartialEq + 'a, + V: Debug + PartialEq + 'a, + S0: StoreIterableMut<'a, K, V>, + S1: StoreIterableMut<'a, K, V>, +{ + let a_vec = a.lm_into_iter().collect::<Vec<_>>(); + let b_vec = b.lm_into_iter().collect::<Vec<_>>(); + assert_eq!(a_vec, b_vec); +} + +const SORTED_DATA: &[(u32, u64)] = &[ + (106, 4816), + (147, 9864), + (188, 8588), + (252, 6031), + (434, 2518), + (574, 8500), + (607, 3756), + (619, 4965), + (663, 2669), + (724, 9211), +]; + +const RANDOM_DATA: &[(u32, u64)] = &[ + (546, 7490), + (273, 4999), + (167, 8078), + (176, 2101), + (373, 1304), + (339, 9613), + (561, 3620), + (301, 1214), + (483, 4453), + (704, 5359), +]; + +// Test code +#[allow(clippy::expect_used)] +#[allow(clippy::panic)] +fn populate_litemap<S>(map: &mut LiteMap<u32, u64, S>) +where + S: StoreMut<u32, u64> + Debug, +{ + assert_eq!(0, map.len()); + assert!(map.is_empty()); + for (k, v) in SORTED_DATA.iter() { + #[allow(clippy::single_match)] // for clarity + match map.try_append(*k, *v) { + Some(_) => panic!("appending sorted data: {k:?} to {map:?}"), + None => (), // OK + }; + } + assert_eq!(10, map.len()); + for (k, v) in RANDOM_DATA.iter() { + #[allow(clippy::single_match)] // for clarity + match map.try_append(*k, *v) { + Some(_) => (), // OK + None => panic!("cannot append random data: {k:?} to{map:?}"), + }; + } + assert_eq!(10, map.len()); + for (k, v) in RANDOM_DATA.iter() { + map.insert(*k, *v); + } + assert_eq!(20, map.len()); +} + +/// Tests that a litemap that uses the given store as backend has behavior consistent with the +/// reference impl. +/// +/// Call this function in a test with the store impl to test as a valid backend for LiteMap. +// Test code +#[allow(clippy::expect_used)] +pub fn check_store<'a, S>() +where + S: StoreConstEmpty<u32, u64> + + StoreMut<u32, u64> + + StoreIterable<'a, u32, u64> + + StoreFromIterator<u32, u64> + + Clone + + Debug + + PartialEq + + 'a, +{ + let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new(); + assert!(litemap_test.is_empty()); + let mut litemap_std = LiteMap::<u32, u64>::new(); + populate_litemap(&mut litemap_test); + populate_litemap(&mut litemap_std); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.retain(|_, v| v % 2 == 0); + litemap_std.retain(|_, v| v % 2 == 0); + assert_eq!(11, litemap_test.len()); + assert_eq!(11, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_test.remove(&147).ok_or(()).expect("exists"); + litemap_std + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_std.remove(&147).ok_or(()).expect("exists"); + + assert_eq!(10, litemap_test.len()); + assert_eq!(10, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.clear(); + litemap_std.clear(); + check_equivalence(litemap_test.values, litemap_std.values); +} + +/// Similar to [`check_store`] function, but also checks the validitiy of [`StoreIterableMut`] +/// trait. +// Test code +#[allow(clippy::expect_used)] +pub fn check_store_full<'a, S>() +where + S: StoreConstEmpty<u32, u64> + + StoreIterableMut<'a, u32, u64> + + StoreFromIterator<u32, u64> + + Clone + + Debug + + PartialEq + + 'a, +{ + let mut litemap_test: LiteMap<u32, u64, S> = LiteMap::new(); + assert!(litemap_test.is_empty()); + let mut litemap_std = LiteMap::<u32, u64>::new(); + populate_litemap(&mut litemap_test); + populate_litemap(&mut litemap_std); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + let extras_test = litemap_test.clone(); + let extras_test = litemap_test + .extend_from_litemap(extras_test) + .expect("duplicates"); + assert_eq!(extras_test, litemap_test); + let extras_std = litemap_std.clone(); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.retain(|_, v| v % 2 == 0); + litemap_std.retain(|_, v| v % 2 == 0); + assert_eq!(11, litemap_test.len()); + assert_eq!(11, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + let extras_test = litemap_test + .extend_from_litemap(extras_test) + .expect("duplicates"); + let extras_std = litemap_std + .extend_from_litemap(extras_std) + .expect("duplicates"); + assert_eq!(11, extras_test.len()); + assert_eq!(11, extras_std.len()); + assert_eq!(20, litemap_test.len()); + assert_eq!(20, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_test.remove(&176).ok_or(()).expect("exists"); + litemap_std + .remove(&175) + .ok_or(()) + .expect_err("does not exist"); + litemap_std.remove(&176).ok_or(()).expect("exists"); + assert_eq!(19, litemap_test.len()); + assert_eq!(19, litemap_std.len()); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.clone().values, litemap_std.clone().values); + + litemap_test.clear(); + litemap_std.clear(); + check_equivalence(litemap_test.clone().values, litemap_std.clone().values); + check_into_iter_equivalence(litemap_test.values, litemap_std.values); +} diff --git a/third_party/rust/litemap/tests/rkyv.rs b/third_party/rust/litemap/tests/rkyv.rs new file mode 100644 index 0000000000..7ab1eb3f5f --- /dev/null +++ b/third_party/rust/litemap/tests/rkyv.rs @@ -0,0 +1,83 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use litemap::LiteMap; +use rkyv::archived_root; +use rkyv::check_archived_root; +use rkyv::ser::serializers::AllocSerializer; +use rkyv::ser::Serializer; +use rkyv::util::AlignedBytes; +use rkyv::util::AlignedVec; +use rkyv::Deserialize; +use rkyv::Infallible; + +const DATA: [(&str, &str); 11] = [ + ("ar", "Arabic"), + ("bn", "Bangla"), + ("ccp", "Chakma"), + ("en", "English"), + ("es", "Spanish"), + ("fr", "French"), + ("ja", "Japanese"), + ("ru", "Russian"), + ("sr", "Serbian"), + ("th", "Thai"), + ("tr", "Turkish"), +]; + +const RKYV: AlignedBytes<192> = AlignedBytes([ + 74, 97, 112, 97, 110, 101, 115, 101, 97, 114, 0, 0, 0, 0, 0, 2, 65, 114, 97, 98, 105, 99, 0, 6, + 98, 110, 0, 0, 0, 0, 0, 2, 66, 97, 110, 103, 108, 97, 0, 6, 99, 99, 112, 0, 0, 0, 0, 3, 67, + 104, 97, 107, 109, 97, 0, 6, 101, 110, 0, 0, 0, 0, 0, 2, 69, 110, 103, 108, 105, 115, 104, 7, + 101, 115, 0, 0, 0, 0, 0, 2, 83, 112, 97, 110, 105, 115, 104, 7, 102, 114, 0, 0, 0, 0, 0, 2, 70, + 114, 101, 110, 99, 104, 0, 6, 106, 97, 0, 0, 0, 0, 0, 2, 8, 0, 0, 0, 144, 255, 255, 255, 114, + 117, 0, 0, 0, 0, 0, 2, 82, 117, 115, 115, 105, 97, 110, 7, 115, 114, 0, 0, 0, 0, 0, 2, 83, 101, + 114, 98, 105, 97, 110, 7, 116, 104, 0, 0, 0, 0, 0, 2, 84, 104, 97, 105, 0, 0, 0, 4, 116, 114, + 0, 0, 0, 0, 0, 2, 84, 117, 114, 107, 105, 115, 104, 7, 80, 255, 255, 255, 11, 0, 0, 0, +]); + +type LiteMapOfStrings = LiteMap<String, String>; +type TupleVecOfStrings = Vec<(String, String)>; + +fn generate() -> AlignedVec { + let map = DATA + .iter() + .map(|&(k, v)| (k.to_owned(), v.to_owned())) + .collect::<LiteMapOfStrings>(); + + let mut serializer = AllocSerializer::<4096>::default(); + serializer + .serialize_value(&map.into_tuple_vec()) + .expect("failed to archive test"); + serializer.into_serializer().into_inner() +} + +#[test] +fn rkyv_serialize() { + let serialized = generate(); + assert_eq!(RKYV.0, serialized.as_slice()); +} + +#[test] +fn rkyv_archive() { + let archived = unsafe { archived_root::<TupleVecOfStrings>(&RKYV.0) }; + let s = archived[0].1.as_str(); + assert_eq!(s, "Arabic"); +} + +#[test] +fn rkyv_checked_archive() { + let archived = check_archived_root::<TupleVecOfStrings>(&RKYV.0).unwrap(); + let s = archived[0].1.as_str(); + assert_eq!(s, "Arabic"); +} + +#[test] +fn rkyv_deserialize() { + let archived = unsafe { archived_root::<TupleVecOfStrings>(&RKYV.0) }; + let deserialized = archived.deserialize(&mut Infallible).unwrap(); + // Safe because we are deserializing a buffer from a trusted source + let deserialized: LiteMapOfStrings = LiteMap::from_sorted_store_unchecked(deserialized); + assert_eq!(deserialized.get("tr").map(String::as_str), Some("Turkish")); +} diff --git a/third_party/rust/litemap/tests/serde.rs b/third_party/rust/litemap/tests/serde.rs new file mode 100644 index 0000000000..72aa67ecaf --- /dev/null +++ b/third_party/rust/litemap/tests/serde.rs @@ -0,0 +1,22 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use litemap::LiteMap; + +#[test] +fn test_ser() { + let mut map = LiteMap::new_vec(); + map.insert(1, "jat"); + map.insert(4, "sei"); + map.insert(3, "saam"); + map.insert(2, "ji"); + + let json_string = serde_json::to_string(&map).unwrap(); + + assert_eq!(json_string, r#"{"1":"jat","2":"ji","3":"saam","4":"sei"}"#); + + let new_map = serde_json::from_str(&json_string).unwrap(); + + assert_eq!(map, new_map); +} diff --git a/third_party/rust/litemap/tests/store.rs b/third_party/rust/litemap/tests/store.rs new file mode 100644 index 0000000000..bd28bee96e --- /dev/null +++ b/third_party/rust/litemap/tests/store.rs @@ -0,0 +1,139 @@ +// This file is part of ICU4X. For terms of use, please see the file +// called LICENSE at the top level of the ICU4X source tree +// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). + +use litemap::store::*; +use litemap::testing::check_store_full; +use std::cmp::Ordering; + +/// A Vec wrapper that leverages the default function impls from `Store` +#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +struct VecWithDefaults<T>(Vec<T>); + +type MapF<K, V> = fn(&(K, V)) -> (&K, &V); + +#[inline] +fn map_f<K, V>(input: &(K, V)) -> (&K, &V) { + (&input.0, &input.1) +} + +type MapFMut<K, V> = fn(&mut (K, V)) -> (&K, &mut V); + +#[inline] +fn map_f_mut<K, V>(input: &mut (K, V)) -> (&K, &mut V) { + (&input.0, &mut input.1) +} + +impl<K, V> StoreConstEmpty<K, V> for VecWithDefaults<(K, V)> { + const EMPTY: VecWithDefaults<(K, V)> = VecWithDefaults(Vec::new()); +} + +impl<K, V> Store<K, V> for VecWithDefaults<(K, V)> { + #[inline] + fn lm_len(&self) -> usize { + self.0.as_slice().len() + } + + // leave lm_is_empty as default + + #[inline] + fn lm_get(&self, index: usize) -> Option<(&K, &V)> { + self.0.as_slice().get(index).map(map_f) + } + + // leave lm_last as default + + #[inline] + fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize> + where + F: FnMut(&K) -> Ordering, + { + self.0.as_slice().binary_search_by(|(k, _)| cmp(k)) + } +} + +impl<K: Ord, V> StoreFromIterable<K, V> for VecWithDefaults<(K, V)> { + fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { + let v: Vec<_> = Vec::lm_sort_from_iter(iter); + Self(v) + } +} + +impl<K, V> StoreMut<K, V> for VecWithDefaults<(K, V)> { + #[inline] + fn lm_with_capacity(capacity: usize) -> Self { + Self(Vec::with_capacity(capacity)) + } + + #[inline] + fn lm_reserve(&mut self, additional: usize) { + self.0.reserve(additional) + } + + #[inline] + fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> { + self.0.as_mut_slice().get_mut(index).map(map_f_mut) + } + + #[inline] + fn lm_push(&mut self, key: K, value: V) { + self.0.push((key, value)) + } + + #[inline] + fn lm_insert(&mut self, index: usize, key: K, value: V) { + self.0.insert(index, (key, value)) + } + + #[inline] + fn lm_remove(&mut self, index: usize) -> (K, V) { + self.0.remove(index) + } + #[inline] + fn lm_clear(&mut self) { + self.0.clear() + } + + // leave lm_retain as default +} + +impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for VecWithDefaults<(K, V)> { + type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>; + + #[inline] + fn lm_iter(&'a self) -> Self::KeyValueIter { + self.0.as_slice().iter().map(map_f) + } +} + +impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for VecWithDefaults<(K, V)> { + type KeyValueIterMut = core::iter::Map<core::slice::IterMut<'a, (K, V)>, MapFMut<K, V>>; + type KeyValueIntoIter = std::vec::IntoIter<(K, V)>; + + #[inline] + fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut { + self.0.as_mut_slice().iter_mut().map(map_f_mut) + } + + #[inline] + fn lm_into_iter(self) -> Self::KeyValueIntoIter { + IntoIterator::into_iter(self.0) + } + + // leave lm_extend_end as default + + // leave lm_extend_start as default +} + +impl<A> std::iter::FromIterator<A> for VecWithDefaults<A> { + fn from_iter<I: IntoIterator<Item = A>>(iter: I) -> Self { + Self(Vec::from_iter(iter)) + } +} + +impl<K, V> StoreFromIterator<K, V> for VecWithDefaults<(K, V)> {} + +#[test] +fn test_default_impl() { + check_store_full::<VecWithDefaults<(u32, u64)>>(); +} |