[HarfBuzz] harfbuzz: Branch 'master' - 2 commits
Behdad Esfahbod
behdad at kemper.freedesktop.org
Tue May 29 23:29:18 UTC 2018
src/Makefile.sources | 3
src/hb-blob.cc | 6 -
src/hb-map-private.hh | 180 ++++++++++++++++++++++++++++++++
src/hb-map.cc | 279 ++++++++++++++++++++++++++++++++++++++++++++++++++
src/hb-map.h | 110 +++++++++++++++++++
src/hb.h | 1
6 files changed, 578 insertions(+), 1 deletion(-)
New commits:
commit 743fdd9c618c949d7f45324386bd0bb37435db46
Author: Behdad Esfahbod <behdad at behdad.org>
Date: Tue May 29 16:28:48 2018 -0700
[map] First try at implementing an integer-to-integer hashmap
Fully untested.
diff --git a/src/Makefile.sources b/src/Makefile.sources
index 2304f308..299af983 100644
--- a/src/Makefile.sources
+++ b/src/Makefile.sources
@@ -14,6 +14,8 @@ HB_BASE_sources = \
hb-face.cc \
hb-font-private.hh \
hb-font.cc \
+ hb-map-private.hh \
+ hb-map.cc \
hb-mutex-private.hh \
hb-object-private.hh \
hb-open-file-private.hh \
@@ -69,6 +71,7 @@ HB_BASE_headers = \
hb-deprecated.h \
hb-face.h \
hb-font.h \
+ hb-map.h \
hb-set.h \
hb-shape.h \
hb-shape-plan.h \
diff --git a/src/hb-map-private.hh b/src/hb-map-private.hh
new file mode 100644
index 00000000..723dde4f
--- /dev/null
+++ b/src/hb-map-private.hh
@@ -0,0 +1,180 @@
+/*
+ * Copyright © 2012,2017 Google, Inc.
+ *
+ * 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.
+ *
+ * Google Author(s): Behdad Esfahbod
+ */
+
+#ifndef HB_MAP_PRIVATE_HH
+#define HB_MAP_PRIVATE_HH
+
+#include "hb-private.hh"
+#include "hb-object-private.hh"
+
+
+template <typename T>
+inline uint32_t Hash (const T &v)
+{
+ /* Knuth's multiplicative method: */
+ return (uint32_t) v * 2654435761u;
+}
+
+
+/*
+ * hb_map_t
+ */
+
+struct hb_map_t
+{
+ struct item_t
+ {
+ hb_codepoint_t key;
+ hb_codepoint_t value;
+
+ inline bool is_unused (void) const { return key == INVALID; }
+ inline bool is_tombstone (void) const { return key != INVALID && value == INVALID; }
+ };
+
+ hb_object_header_t header;
+ ASSERT_POD ();
+ bool in_error;
+ unsigned int occupancy; /* Including tombstones. */
+ unsigned int mask;
+ unsigned int prime;
+ item_t *items;
+
+ inline void init_shallow (void)
+ {
+ in_error = false;
+ occupancy = 0;
+ mask = 0;
+ prime = 0;
+ items = nullptr;
+ }
+ inline void init (void)
+ {
+ hb_object_init (this);
+ init_shallow ();
+ }
+ inline void fini_shallow (void)
+ {
+ free (items);
+ }
+ inline void fini (void)
+ {
+ hb_object_fini (this);
+ fini_shallow ();
+ }
+
+ inline bool resize (void)
+ {
+ if (unlikely (in_error)) return false;
+
+ unsigned int power = _hb_bit_storage (occupancy * 2 + 8) - 1;
+ unsigned int new_size = 1u << power;
+ item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t));
+ if (unlikely (!new_items))
+ {
+ in_error = true;
+ return false;
+ }
+ memset (new_items, 0xFF, (size_t) new_size * sizeof (item_t));
+
+ unsigned int old_size = mask + 1;
+ item_t *old_items = items;
+
+ /* Switch to new, empty, array. */
+ occupancy = 0;
+ mask = new_size - 1;
+ prime = prime_for (power);
+ items = new_items;
+
+ /* Insert back old items. */
+ for (unsigned int i = 0; i < old_size; i++)
+ if (old_items[i].key != INVALID && old_items[i].value != INVALID)
+ set (old_items[i].key, old_items[i].value);
+
+ free (old_items);
+
+ return true;
+ }
+
+ inline void set (hb_codepoint_t key, hb_codepoint_t value)
+ {
+ if (unlikely (in_error)) return;
+ if ((occupancy + occupancy / 2) > mask && !resize ()) return;
+ unsigned int i = bucket_for (key);
+ if (items[i].key != key)
+ {
+ if (items[i].key == INVALID && key != INVALID)
+ occupancy++;
+ items[i].key = key;
+ }
+ items[i].value = value;
+ }
+ inline hb_codepoint_t get (hb_codepoint_t key) const
+ {
+ if (unlikely (in_error)) return INVALID;
+ if (unlikely (!items)) return INVALID;
+ unsigned int i = bucket_for (key);
+ return items[i].key == key ? items[i].value : INVALID;
+ }
+
+ inline void del (hb_codepoint_t key)
+ {
+ if (unlikely (in_error)) return;
+ if (unlikely (!items)) return;
+ unsigned int i = bucket_for (key);
+ items[i].value = INVALID;
+ }
+ inline bool has (hb_codepoint_t key) const
+ {
+ return get (key) != INVALID;
+ }
+
+ static const hb_codepoint_t INVALID = HB_MAP_VALUE_INVALID;
+
+ protected:
+ static HB_INTERNAL unsigned int prime_for (unsigned int shift);
+
+ unsigned int bucket_for (hb_codepoint_t key) const
+ {
+ unsigned int i = Hash (key) % prime;
+ unsigned int step = 0;
+ unsigned int tombstone = INVALID;
+ while (!items[i].is_unused ())
+ {
+ if (items[i].key == key)
+ return i;
+ if (tombstone == INVALID && items[i].is_tombstone ())
+ tombstone = i;
+ i = (i + ++step) & mask;
+ }
+ return tombstone == INVALID ? i : tombstone;
+ }
+
+ private:
+ HB_DISALLOW_COPY_AND_ASSIGN (hb_map_t);
+};
+
+
+#endif /* HB_MAP_PRIVATE_HH */
diff --git a/src/hb-map.cc b/src/hb-map.cc
new file mode 100644
index 00000000..4f50828f
--- /dev/null
+++ b/src/hb-map.cc
@@ -0,0 +1,279 @@
+/*
+ * Copyright © 2018 Google, Inc.
+ *
+ * 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.
+ *
+ * Google Author(s): Behdad Esfahbod
+ */
+
+#include "hb-map-private.hh"
+
+
+/* Public API */
+
+
+/**
+ * hb_map_create: (Xconstructor)
+ *
+ * Return value: (transfer full):
+ *
+ * Since: REPLACEME
+ **/
+hb_map_t *
+hb_map_create (void)
+{
+ hb_map_t *map;
+
+ if (!(map = hb_object_create<hb_map_t> ()))
+ return hb_map_get_empty ();
+
+ map->init_shallow ();
+
+ return map;
+}
+
+static const hb_map_t _hb_map_nil = {
+ HB_OBJECT_HEADER_STATIC,
+ true, /* in_error */
+ 0, /* occupancy */
+ 0, /* mask */
+ 0, /* prime */
+ nullptr /* items */
+};
+
+/**
+ * hb_map_get_empty:
+ *
+ * Return value: (transfer full):
+ *
+ * Since: REPLACEME
+ **/
+hb_map_t *
+hb_map_get_empty (void)
+{
+ return const_cast<hb_map_t *> (&_hb_map_nil);
+}
+
+/**
+ * hb_map_reference: (skip)
+ * @map: a map.
+ *
+ * Return value: (transfer full):
+ *
+ * Since: REPLACEME
+ **/
+hb_map_t *
+hb_map_reference (hb_map_t *map)
+{
+ return hb_object_reference (map);
+}
+
+/**
+ * hb_map_destroy: (skip)
+ * @map: a map.
+ *
+ * Since: REPLACEME
+ **/
+void
+hb_map_destroy (hb_map_t *map)
+{
+ if (!hb_object_destroy (map)) return;
+
+ map->fini_shallow ();
+
+ free (map);
+}
+
+/**
+ * hb_map_set_user_data: (skip)
+ * @map: a map.
+ * @key:
+ * @data:
+ * @destroy:
+ * @replace:
+ *
+ * Return value:
+ *
+ * Since: REPLACEME
+ **/
+hb_bool_t
+hb_map_set_user_data (hb_map_t *map,
+ hb_user_data_key_t *key,
+ void * data,
+ hb_destroy_func_t destroy,
+ hb_bool_t replace)
+{
+ return hb_object_set_user_data (map, key, data, destroy, replace);
+}
+
+/**
+ * hb_map_get_user_data: (skip)
+ * @map: a map.
+ * @key:
+ *
+ * Return value: (transfer none):
+ *
+ * Since: REPLACEME
+ **/
+void *
+hb_map_get_user_data (hb_map_t *map,
+ hb_user_data_key_t *key)
+{
+ return hb_object_get_user_data (map, key);
+}
+
+
+/**
+ * hb_map_allocation_successful:
+ * @map: a map.
+ *
+ *
+ *
+ * Return value:
+ *
+ * Since: REPLACEME
+ **/
+hb_bool_t
+hb_map_allocation_successful (const hb_map_t *map)
+{
+ return !map->in_error;
+}
+
+
+/**
+ * hb_map_set:
+ * @map: a map.
+ * @key:
+ * @value:
+ *
+ *
+ *
+ * Return value:
+ *
+ * Since: REPLACEME
+ **/
+void
+hb_map_set (hb_map_t *map,
+ hb_codepoint_t key,
+ hb_codepoint_t value)
+{
+ map->set (key, value);
+}
+
+/**
+ * hb_map_get:
+ * @map: a map.
+ * @key:
+ *
+ *
+ *
+ * Since: REPLACEME
+ **/
+hb_codepoint_t
+hb_map_get (const hb_map_t *map,
+ hb_codepoint_t key)
+{
+ return map->get (key);
+}
+
+/**
+ * hb_map_del:
+ * @map: a map.
+ * @codepoint:
+ *
+ *
+ *
+ * Since: REPLACEME
+ **/
+void
+hb_map_del (hb_map_t *map,
+ hb_codepoint_t key)
+{
+ map->del (key);
+}
+
+/**
+ * hb_map_has:
+ * @map: a map.
+ * @codepoint:
+ *
+ *
+ *
+ * Since: REPLACEME
+ **/
+bool
+hb_map_has (const hb_map_t *map,
+ hb_codepoint_t key)
+{
+ return map->has (key);
+}
+
+
+/* Following comment and table copied from glib. */
+/* Each table size has an associated prime modulo (the first prime
+ * lower than the table size) used to find the initial bucket. Probing
+ * then works modulo 2^n. The prime modulo is necessary to get a
+ * good distribution with poor hash functions.
+ */
+static const unsigned int prime_mod [] =
+{
+ 1, /* For 1 << 0 */
+ 2,
+ 3,
+ 7,
+ 13,
+ 31,
+ 61,
+ 127,
+ 251,
+ 509,
+ 1021,
+ 2039,
+ 4093,
+ 8191,
+ 16381,
+ 32749,
+ 65521, /* For 1 << 16 */
+ 131071,
+ 262139,
+ 524287,
+ 1048573,
+ 2097143,
+ 4194301,
+ 8388593,
+ 16777213,
+ 33554393,
+ 67108859,
+ 134217689,
+ 268435399,
+ 536870909,
+ 1073741789,
+ 2147483647 /* For 1 << 31 */
+};
+
+unsigned int
+hb_map_t::prime_for (unsigned int shift)
+{
+ if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))
+ return prime_mod[ARRAY_LENGTH (prime_mod) -1];
+
+ return prime_mod[shift];
+}
diff --git a/src/hb-map.h b/src/hb-map.h
new file mode 100644
index 00000000..0901e3bd
--- /dev/null
+++ b/src/hb-map.h
@@ -0,0 +1,110 @@
+/*
+ * Copyright © 2018 Google, Inc.
+ *
+ * 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.
+ *
+ * Google Author(s): Behdad Esfahbod
+ */
+
+#ifndef HB_H_IN
+#error "Include <hb.h> instead."
+#endif
+
+#ifndef HB_MAP_H
+#define HB_MAP_H
+
+#include "hb-common.h"
+
+HB_BEGIN_DECLS
+
+
+/*
+ * Since: REPLACEME
+ */
+#define HB_MAP_VALUE_INVALID ((hb_codepoint_t) -1)
+
+typedef struct hb_map_t hb_map_t;
+
+
+HB_EXTERN hb_map_t *
+hb_map_create (void);
+
+HB_EXTERN hb_map_t *
+hb_map_get_empty (void);
+
+HB_EXTERN hb_map_t *
+hb_map_reference (hb_map_t *map);
+
+HB_EXTERN void
+hb_map_destroy (hb_map_t *map);
+
+HB_EXTERN hb_bool_t
+hb_map_set_user_data (hb_map_t *map,
+ hb_user_data_key_t *key,
+ void * data,
+ hb_destroy_func_t destroy,
+ hb_bool_t replace);
+
+HB_EXTERN void *
+hb_map_get_user_data (hb_map_t *map,
+ hb_user_data_key_t *key);
+
+
+/* Returns false if allocation has failed before */
+HB_EXTERN hb_bool_t
+hb_map_allocation_successful (const hb_map_t *map);
+
+/*
+ HB_EXTERN void
+ hb_map_clear (hb_map_t *map);
+
+ HB_EXTERN hb_bool_t
+ hb_map_is_empty (const hb_map_t *map);
+
+ HB_EXTERN unsigned int
+ hb_set_get_population (const hb_set_t *set);
+
+ HB_EXTERN hb_bool_t
+ hb_map_is_equal (const hb_map_t *map,
+ const hb_map_t *other);
+*/
+
+HB_EXTERN void
+hb_map_set (hb_map_t *map,
+ hb_codepoint_t key,
+ hb_codepoint_t value);
+
+HB_EXTERN hb_codepoint_t
+hb_map_get (const hb_map_t *map,
+ hb_codepoint_t key);
+
+HB_EXTERN void
+hb_map_del (hb_map_t *map,
+ hb_codepoint_t key);
+
+HB_EXTERN bool
+hb_map_has (const hb_map_t *map,
+ hb_codepoint_t key);
+
+
+HB_END_DECLS
+
+#endif /* HB_MAP_H */
diff --git a/src/hb.h b/src/hb.h
index 7402034f..fc75a691 100644
--- a/src/hb.h
+++ b/src/hb.h
@@ -38,6 +38,7 @@
#include "hb-deprecated.h"
#include "hb-face.h"
#include "hb-font.h"
+#include "hb-map.h"
#include "hb-set.h"
#include "hb-shape.h"
#include "hb-shape-plan.h"
commit 65c82179c9b3aafd90987485a49c09dbbb473c90
Author: Ebrahim Byagowi <ebrahim at gnu.org>
Date: Sat May 26 23:50:10 2018 +0430
[blob] Use MAP_NORESERVE if available (#1039)
MAP_NORESERVE is not available on macOS for example so set the flag
to zero if not defined on the headers.
diff --git a/src/hb-blob.cc b/src/hb-blob.cc
index 0beb024e..7c51090b 100644
--- a/src/hb-blob.cc
+++ b/src/hb-blob.cc
@@ -495,6 +495,10 @@ hb_blob_t::try_make_writable (void)
# define _O_BINARY 0
#endif
+#ifndef MAP_NORESERVE
+# define MAP_NORESERVE 0
+#endif
+
struct hb_mapped_file_t
{
char *contents;
@@ -551,7 +555,7 @@ hb_blob_create_from_file (const char *file_name)
file->length = (unsigned long) st.st_size;
file->contents = (char *) mmap (nullptr, file->length,
writable ? PROT_READ|PROT_WRITE : PROT_READ,
- MAP_PRIVATE, fd, 0);
+ MAP_PRIVATE | MAP_NORESERVE, fd, 0);
if (unlikely (file->contents == MAP_FAILED)) goto fail;
More information about the HarfBuzz
mailing list