mirror of
https://github.com/storytold/harfbuzz.git
synced 2026-11-19 05:51:05 +01:00
hb_hashmap_t::update() iterates other's items array while inserting each pair into *this with set(). When other is *this and occupancy sits on a growth threshold (5 of 8, 10 of 16, ...), the first set() calls alloc(), which frees the items array the iterator is still walking, so the rest of the loop reads freed memory. The existing in_storage() guard only protects set()'s own key/value references, not this iterator. Merging a map into itself cannot change it, so make update() a no-op in that case with an early &other == this return, mirroring the self-check in hb_vector_t. hb_map_update() is the only caller. Regression tests are added in src/test-map.cc (including the tombstone case at 42 used / 10 live slots) and test/api/test-map.c; both fail under ASan without the fix. Reported by Anthropic's OSS Scanner as ordinary bug ANT-2026-7TMM2Z2T. Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>
421 lines
11 KiB
C++
421 lines
11 KiB
C++
/*
|
|
* Copyright © 2021 Behdad Esfahbod
|
|
*
|
|
* This is part of HarfBuzz, a text shaping library.
|
|
*
|
|
* Permission is hereby granted, without written agreement and without
|
|
* license or royalty fees, to use, copy, modify, and distribute this
|
|
* software and its documentation for any purpose, provided that the
|
|
* above copyright notice and the following two paragraphs appear in
|
|
* all copies of this software.
|
|
*
|
|
* IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
|
|
* DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
|
|
* ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
|
|
* IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
|
|
* DAMAGE.
|
|
*
|
|
* THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
|
|
* BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
|
|
* FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
|
|
* ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
|
|
* PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
|
|
*/
|
|
|
|
#include "hb.hh"
|
|
#include "hb-map.hh"
|
|
#include "hb-set.hh"
|
|
#include <string>
|
|
|
|
int
|
|
main (int argc, char **argv)
|
|
{
|
|
|
|
/* Test copy constructor. */
|
|
{
|
|
hb_map_t v1;
|
|
v1.set (1, 2);
|
|
hb_map_t v2 {v1};
|
|
hb_always_assert (v1.get_population () == 1);
|
|
hb_always_assert (v2.get_population () == 1);
|
|
hb_always_assert (v1[1] == 2);
|
|
hb_always_assert (v2[1] == 2);
|
|
}
|
|
|
|
/* Test copy assignment. */
|
|
{
|
|
hb_map_t v1;
|
|
v1.set (1, 2);
|
|
hb_map_t v2 = v1;
|
|
hb_always_assert (v1.get_population () == 1);
|
|
hb_always_assert (v2.get_population () == 1);
|
|
hb_always_assert (v1[1] == 2);
|
|
hb_always_assert (v2[1] == 2);
|
|
}
|
|
|
|
/* Test move constructor. */
|
|
{
|
|
hb_map_t s {};
|
|
s.set (1, 2);
|
|
hb_map_t v (std::move (s));
|
|
hb_always_assert (s.get_population () == 0);
|
|
hb_always_assert (v.get_population () == 1);
|
|
}
|
|
|
|
/* Test move assignment. */
|
|
{
|
|
hb_map_t s {};
|
|
s.set (1, 2);
|
|
hb_map_t v;
|
|
v = std::move (s);
|
|
hb_always_assert (s.get_population () == 0);
|
|
hb_always_assert (v.get_population () == 1);
|
|
}
|
|
|
|
/* Test initializing from iterable. */
|
|
{
|
|
hb_map_t s;
|
|
|
|
s.set (1, 2);
|
|
s.set (3, 4);
|
|
|
|
hb_vector_t<hb_codepoint_pair_t> v (s);
|
|
hb_map_t v0 (v);
|
|
hb_map_t v1 (s);
|
|
hb_map_t v2 (std::move (s));
|
|
|
|
hb_always_assert (s.get_population () == 0);
|
|
hb_always_assert (v0.get_population () == 2);
|
|
hb_always_assert (v1.get_population () == 2);
|
|
hb_always_assert (v2.get_population () == 2);
|
|
}
|
|
|
|
/* Test call fini() twice. */
|
|
{
|
|
hb_map_t s;
|
|
for (int i = 0; i < 16; i++)
|
|
s.set(i, i+1);
|
|
s.fini();
|
|
}
|
|
|
|
/* Test initializing from iterator. */
|
|
{
|
|
hb_map_t s;
|
|
|
|
s.set (1, 2);
|
|
s.set (3, 4);
|
|
|
|
hb_map_t v (hb_iter (s));
|
|
|
|
hb_always_assert (v.get_population () == 2);
|
|
}
|
|
|
|
/* Test initializing from initializer list and swapping. */
|
|
{
|
|
using pair_t = hb_codepoint_pair_t;
|
|
hb_map_t v1 {pair_t{1,2}, pair_t{4,5}};
|
|
hb_map_t v2 {pair_t{3,4}};
|
|
hb_swap (v1, v2);
|
|
hb_always_assert (v1.get_population () == 1);
|
|
hb_always_assert (v2.get_population () == 2);
|
|
}
|
|
|
|
/* Test class key / value types. */
|
|
{
|
|
hb_hashmap_t<hb_bytes_t, int> m1;
|
|
hb_hashmap_t<int, hb_bytes_t> m2;
|
|
hb_hashmap_t<hb_bytes_t, hb_bytes_t> m3;
|
|
hb_always_assert (m1.get_population () == 0);
|
|
hb_always_assert (m2.get_population () == 0);
|
|
hb_always_assert (m3.get_population () == 0);
|
|
}
|
|
|
|
{
|
|
hb_hashmap_t<int, int> m0;
|
|
hb_hashmap_t<std::string, int> m1;
|
|
hb_hashmap_t<int, std::string> m2;
|
|
hb_hashmap_t<std::string, std::string> m3;
|
|
|
|
std::string s;
|
|
for (unsigned i = 1; i < 1000; i++)
|
|
{
|
|
s += "x";
|
|
m0.set (i, i);
|
|
m1.set (s, i);
|
|
m2.set (i, s);
|
|
m3.set (s, s);
|
|
}
|
|
}
|
|
|
|
/* Test hashing maps. */
|
|
{
|
|
using pair = hb_codepoint_pair_t;
|
|
|
|
hb_hashmap_t<hb_map_t, hb_map_t> m1;
|
|
|
|
m1.set (hb_map_t (), hb_map_t {});
|
|
m1.set (hb_map_t (), hb_map_t {pair (1u, 2u)});
|
|
m1.set (hb_map_t {pair (1u, 2u)}, hb_map_t {pair (2u, 3u)});
|
|
|
|
hb_always_assert (m1.get (hb_map_t ()) == hb_map_t {pair (1u, 2u)});
|
|
hb_always_assert (m1.get (hb_map_t {pair (1u, 2u)}) == hb_map_t {pair (2u, 3u)});
|
|
}
|
|
|
|
/* Test hashing sets. */
|
|
{
|
|
hb_hashmap_t<hb_set_t, hb_set_t> m1;
|
|
|
|
m1.set (hb_set_t (), hb_set_t ());
|
|
m1.set (hb_set_t (), hb_set_t {1});
|
|
m1.set (hb_set_t {1, 1000}, hb_set_t {2});
|
|
|
|
hb_always_assert (m1.get (hb_set_t ()) == hb_set_t {1});
|
|
hb_always_assert (m1.get (hb_set_t {1000, 1}) == hb_set_t {2});
|
|
}
|
|
|
|
/* Test hashing vectors. */
|
|
{
|
|
using vector_t = hb_vector_t<unsigned>;
|
|
|
|
hb_hashmap_t<vector_t, vector_t> m1;
|
|
|
|
m1.set (vector_t (), vector_t {1});
|
|
m1.set (vector_t {1}, vector_t {2});
|
|
|
|
m1 << hb_pair_t<vector_t, vector_t> {vector_t {2}, vector_t ()};
|
|
|
|
hb_always_assert (m1.get (vector_t ()) == vector_t {1});
|
|
hb_always_assert (m1.get (vector_t {1}) == vector_t {2});
|
|
}
|
|
|
|
/* Test moving values */
|
|
{
|
|
using vector_t = hb_vector_t<unsigned>;
|
|
|
|
hb_hashmap_t<vector_t, vector_t> m1;
|
|
vector_t v {3};
|
|
hb_always_assert (v.length == 1);
|
|
m1 << hb_pair_t<vector_t, vector_t> {vector_t {3}, v};
|
|
hb_always_assert (v.length == 1);
|
|
m1 << hb_pair_t<vector_t, vector_t&&> {vector_t {4}, std::move (v)};
|
|
hb_always_assert (v.length == 0);
|
|
m1 << hb_pair_t<vector_t&&, vector_t> {vector_t {4}, vector_t {5}};
|
|
m1 << hb_pair_t<vector_t&&, vector_t&&> {vector_t {4}, vector_t {5}};
|
|
|
|
hb_hashmap_t<vector_t, vector_t> m2;
|
|
vector_t v2 {3};
|
|
m2.set (vector_t {4}, v2);
|
|
hb_always_assert (v2.length == 1);
|
|
m2.set (vector_t {5}, std::move (v2));
|
|
hb_always_assert (v2.length == 0);
|
|
}
|
|
|
|
/* Test hb::shared_ptr. */
|
|
{
|
|
hb_hashmap_t<hb::shared_ptr<hb_set_t>, hb::shared_ptr<hb_set_t>> m;
|
|
|
|
m.set (hb::shared_ptr<hb_set_t> (hb_set_get_empty ()),
|
|
hb::shared_ptr<hb_set_t> (hb_set_get_empty ()));
|
|
m.get (hb::shared_ptr<hb_set_t> (hb_set_get_empty ()));
|
|
m.iter ();
|
|
m.keys ();
|
|
m.values ();
|
|
m.iter_ref ();
|
|
m.keys_ref ();
|
|
m.values_ref ();
|
|
}
|
|
/* Test hb::unique_ptr. */
|
|
{
|
|
hb_hashmap_t<hb::unique_ptr<hb_set_t>, hb::unique_ptr<hb_set_t>> m;
|
|
|
|
m.set (hb::unique_ptr<hb_set_t> (hb_set_get_empty ()),
|
|
hb::unique_ptr<hb_set_t> (hb_set_get_empty ()));
|
|
m.get (hb::unique_ptr<hb_set_t> (hb_set_get_empty ()));
|
|
hb::unique_ptr<hb_set_t> *v;
|
|
m.has (hb::unique_ptr<hb_set_t> (hb_set_get_empty ()), &v);
|
|
m.iter_ref ();
|
|
m.keys_ref ();
|
|
m.values_ref ();
|
|
}
|
|
/* Test hashmap with complex shared_ptrs as keys. */
|
|
{
|
|
hb_hashmap_t<hb::shared_ptr<hb_map_t>, unsigned> m;
|
|
|
|
hb_map_t *m1 = hb_map_create ();
|
|
hb_map_t *m2 = hb_map_create ();
|
|
m1->set (1,3);
|
|
m2->set (1,3);
|
|
|
|
hb::shared_ptr<hb_map_t> p1 {m1};
|
|
hb::shared_ptr<hb_map_t> p2 {m2};
|
|
m.set (p1,1);
|
|
|
|
hb_always_assert (m.has (p2));
|
|
|
|
m1->set (2,4);
|
|
hb_always_assert (!m.has (p2));
|
|
}
|
|
/* Test value type with hb_bytes_t. */
|
|
{
|
|
hb_hashmap_t<int, hb_bytes_t> m;
|
|
char c_str[] = "Test";
|
|
hb_bytes_t bytes (c_str);
|
|
|
|
m.set (1, bytes);
|
|
hb_always_assert (m.has (1));
|
|
hb_always_assert (m.get (1) == hb_bytes_t {"Test"});
|
|
}
|
|
/* Test operators. */
|
|
{
|
|
hb_map_t m1, m2, m3;
|
|
m1.set (1, 2);
|
|
m1.set (2, 4);
|
|
m2.set (1, 2);
|
|
m2.set (2, 4);
|
|
m3.set (1, 3);
|
|
m3.set (3, 5);
|
|
|
|
hb_always_assert (m1 == m2);
|
|
hb_always_assert (m1 != m3);
|
|
hb_always_assert (!(m2 == m3));
|
|
|
|
m2 = m3;
|
|
hb_always_assert (m2.has (1));
|
|
hb_always_assert (!m2.has (2));
|
|
hb_always_assert (m2.has (3));
|
|
|
|
hb_always_assert (m3.has (3));
|
|
}
|
|
/* Test reset. */
|
|
{
|
|
hb_hashmap_t<int, hb_set_t> m;
|
|
m.set (1, hb_set_t {1, 2, 3});
|
|
m.reset ();
|
|
}
|
|
/* Test iteration. */
|
|
{
|
|
hb_map_t m;
|
|
m.set (1, 1);
|
|
m.set (4, 3);
|
|
m.set (5, 5);
|
|
m.set (2, 1);
|
|
m.set (3, 2);
|
|
m.set (6, 8);
|
|
|
|
hb_codepoint_t k;
|
|
hb_codepoint_t v;
|
|
unsigned pop = 0;
|
|
for (signed i = -1;
|
|
m.next (&i, &k, &v);)
|
|
{
|
|
pop++;
|
|
if (k == 1) hb_always_assert (v == 1);
|
|
else if (k == 2) hb_always_assert (v == 1);
|
|
else if (k == 3) hb_always_assert (v == 2);
|
|
else if (k == 4) hb_always_assert (v == 3);
|
|
else if (k == 5) hb_always_assert (v == 5);
|
|
else if (k == 6) hb_always_assert (v == 8);
|
|
else hb_always_assert (false);
|
|
}
|
|
hb_always_assert (pop == m.get_population ());
|
|
}
|
|
/* Test update */
|
|
{
|
|
hb_map_t m1, m2;
|
|
m1.set (1, 2);
|
|
m1.set (2, 4);
|
|
m2.set (1, 3);
|
|
|
|
m1.update (m2);
|
|
hb_always_assert (m1.get_population () == 2);
|
|
hb_always_assert (m1[1] == 3);
|
|
hb_always_assert (m1[2] == 4);
|
|
}
|
|
/* Test update with self, with the table at its growth threshold so
|
|
* that set () would reallocate the items being iterated. */
|
|
{
|
|
hb_map_t m;
|
|
for (unsigned i = 0; i < 5; i++)
|
|
m.set (i, i * 2);
|
|
|
|
m.update (m);
|
|
hb_always_assert (m.get_population () == 5);
|
|
for (unsigned i = 0; i < 5; i++)
|
|
hb_always_assert (m[i] == i * 2);
|
|
|
|
for (unsigned i = 5; i < 42; i++)
|
|
m.set (i, i * 2);
|
|
for (unsigned i = 0; i < 32; i++)
|
|
m.del (i);
|
|
|
|
m.update (m);
|
|
hb_always_assert (m.get_population () == 10);
|
|
for (unsigned i = 32; i < 42; i++)
|
|
hb_always_assert (m[i] == i * 2);
|
|
}
|
|
/* Test keys / values */
|
|
{
|
|
hb_map_t m;
|
|
m.set (1, 1);
|
|
m.set (4, 3);
|
|
m.set (5, 5);
|
|
m.set (2, 1);
|
|
m.set (3, 2);
|
|
m.set (6, 8);
|
|
|
|
hb_set_t keys;
|
|
hb_set_t values;
|
|
|
|
hb_copy (m.keys (), keys);
|
|
hb_copy (m.values (), values);
|
|
|
|
hb_always_assert (keys.is_equal (hb_set_t ({1, 2, 3, 4, 5, 6})));
|
|
hb_always_assert (values.is_equal (hb_set_t ({1, 1, 2, 3, 5, 8})));
|
|
|
|
hb_always_assert (keys.is_equal (hb_set_t (m.keys ())));
|
|
hb_always_assert (values.is_equal (hb_set_t (m.values ())));
|
|
}
|
|
/* Test setting a key or value that lives in the map's own storage
|
|
* while the map grows. */
|
|
{
|
|
hb_map_t m;
|
|
m.set (1, 2);
|
|
for (unsigned i = 0; i < 1000; i++)
|
|
{
|
|
m.set (1000 + i, m.get (1));
|
|
hb_always_assert (m.get (1000 + i) == 2);
|
|
}
|
|
hb_map_t m2;
|
|
m2.set (1, 5000);
|
|
for (unsigned i = 0; i < 1000; i++)
|
|
{
|
|
m2.set (m2.get (1), i);
|
|
m2.set (1, 5001 + i);
|
|
hb_always_assert (m2.get (5000 + i) == i);
|
|
}
|
|
hb_hashmap_t<unsigned, hb_vector_t<unsigned>> v;
|
|
v.set (1, hb_vector_t<unsigned> {1, 2, 3});
|
|
for (unsigned i = 0; i < 1000; i++)
|
|
{
|
|
v.set (1000 + i, v.get (1));
|
|
hb_always_assert (v.get (1000 + i).length == 3);
|
|
}
|
|
}
|
|
/* Test allocation bounds and overflow protection. */
|
|
{
|
|
hb_map_t m1;
|
|
hb_always_assert (!m1.alloc ((unsigned) -1));
|
|
hb_always_assert (m1.in_error ());
|
|
|
|
hb_map_t m2;
|
|
hb_always_assert (!m2.alloc (0x40000000u));
|
|
hb_always_assert (m2.in_error ());
|
|
|
|
/* Test copy of map in error state. */
|
|
hb_map_t m3 (m1);
|
|
hb_always_assert (m3.in_error ());
|
|
}
|
|
|
|
return 0;
|
|
}
|