1 /* 2 * Copyright © 2019 Adobe Inc. 3 * 4 * This is part of HarfBuzz, a text shaping library. 5 * 6 * Permission is hereby granted, without written agreement and without 7 * license or royalty fees, to use, copy, modify, and distribute this 8 * software and its documentation for any purpose, provided that the 9 * above copyright notice and the following two paragraphs appear in 10 * all copies of this software. 11 * 12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 16 * DAMAGE. 17 * 18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 23 * 24 * Adobe Author(s): Michiharu Ariza 25 */ 26 27 #ifndef HB_BIMAP_HH 28 #define HB_BIMAP_HH 29 30 #include "hb.hh" 31 #include "hb-map.hh" 32 33 /* Bi-directional map */ 34 struct hb_bimap_t 35 { resethb_bimap_t36 void reset () 37 { 38 forw_map.reset (); 39 back_map.reset (); 40 } 41 allochb_bimap_t42 void alloc (unsigned pop) 43 { 44 forw_map.alloc (pop); 45 back_map.alloc (pop); 46 } 47 in_errorhb_bimap_t48 bool in_error () const { return forw_map.in_error () || back_map.in_error (); } 49 sethb_bimap_t50 void set (hb_codepoint_t lhs, hb_codepoint_t rhs) 51 { 52 if (in_error ()) return; 53 if (unlikely (lhs == HB_MAP_VALUE_INVALID)) return; 54 if (unlikely (rhs == HB_MAP_VALUE_INVALID)) { del (lhs); return; } 55 56 forw_map.set (lhs, rhs); 57 if (unlikely (in_error ())) return; 58 59 back_map.set (rhs, lhs); 60 if (unlikely (in_error ())) forw_map.del (lhs); 61 } 62 gethb_bimap_t63 hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); } backwardhb_bimap_t64 hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map.get (rhs); } 65 operator []hb_bimap_t66 hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); } hashb_bimap_t67 bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); } 68 69 delhb_bimap_t70 void del (hb_codepoint_t lhs) 71 { 72 back_map.del (get (lhs)); 73 forw_map.del (lhs); 74 } 75 clearhb_bimap_t76 void clear () 77 { 78 forw_map.clear (); 79 back_map.clear (); 80 } 81 is_emptyhb_bimap_t82 bool is_empty () const { return forw_map.is_empty (); } 83 get_populationhb_bimap_t84 unsigned int get_population () const { return forw_map.get_population (); } 85 86 protected: 87 hb_map_t forw_map; 88 hb_map_t back_map; 89 90 public: 91 auto keys () const HB_AUTO_RETURN (+ forw_map.keys()) 92 auto values () const HB_AUTO_RETURN (+ forw_map.values()) 93 auto iter () const HB_AUTO_RETURN (+ forw_map.iter()) 94 }; 95 96 /* Incremental bimap: only lhs is given, rhs is incrementally assigned */ 97 struct hb_inc_bimap_t 98 { in_errorhb_inc_bimap_t99 bool in_error () const { return forw_map.in_error () || back_map.in_error (); } 100 get_populationhb_inc_bimap_t101 unsigned int get_population () const { return forw_map.get_population (); } 102 resethb_inc_bimap_t103 void reset () 104 { 105 forw_map.reset (); 106 back_map.reset (); 107 } 108 allochb_inc_bimap_t109 void alloc (unsigned pop) 110 { 111 forw_map.alloc (pop); 112 back_map.alloc (pop); 113 } 114 clearhb_inc_bimap_t115 void clear () 116 { 117 forw_map.clear (); 118 back_map.resize (0); 119 } 120 121 /* Add a mapping from lhs to rhs with a unique value if lhs is unknown. 122 * Return the rhs value as the result. 123 */ addhb_inc_bimap_t124 hb_codepoint_t add (hb_codepoint_t lhs) 125 { 126 hb_codepoint_t rhs = forw_map[lhs]; 127 if (rhs == HB_MAP_VALUE_INVALID) 128 { 129 rhs = back_map.length; 130 forw_map.set (lhs, rhs); 131 back_map.push (lhs); 132 } 133 return rhs; 134 } 135 skiphb_inc_bimap_t136 hb_codepoint_t skip () 137 { 138 hb_codepoint_t start = back_map.length; 139 back_map.push (HB_MAP_VALUE_INVALID); 140 return start; 141 } 142 skiphb_inc_bimap_t143 hb_codepoint_t skip (unsigned count) 144 { 145 hb_codepoint_t start = back_map.length; 146 back_map.alloc (back_map.length + count); 147 for (unsigned i = 0; i < count; i++) 148 back_map.push (HB_MAP_VALUE_INVALID); 149 return start; 150 } 151 get_next_valuehb_inc_bimap_t152 hb_codepoint_t get_next_value () const 153 { return back_map.length; } 154 add_sethb_inc_bimap_t155 void add_set (const hb_set_t *set) 156 { 157 for (auto i : *set) add (i); 158 } 159 160 /* Create an identity map. */ identityhb_inc_bimap_t161 bool identity (unsigned int size) 162 { 163 clear (); 164 for (hb_codepoint_t i = 0; i < size; i++) add (i); 165 return !in_error (); 166 } 167 168 protected: cmp_idhb_inc_bimap_t169 static int cmp_id (const void* a, const void* b) 170 { return (int)*(const hb_codepoint_t *)a - (int)*(const hb_codepoint_t *)b; } 171 172 public: 173 /* Optional: after finished adding all mappings in a random order, 174 * reassign rhs to lhs so that they are in the same order. */ sorthb_inc_bimap_t175 void sort () 176 { 177 hb_codepoint_t count = get_population (); 178 hb_vector_t <hb_codepoint_t> work; 179 if (unlikely (!work.resize (count, false))) return; 180 181 for (hb_codepoint_t rhs = 0; rhs < count; rhs++) 182 work.arrayZ[rhs] = back_map[rhs]; 183 184 work.qsort (cmp_id); 185 186 clear (); 187 for (hb_codepoint_t rhs = 0; rhs < count; rhs++) 188 add (work.arrayZ[rhs]); 189 } 190 gethb_inc_bimap_t191 hb_codepoint_t get (hb_codepoint_t lhs) const { return forw_map.get (lhs); } backwardhb_inc_bimap_t192 hb_codepoint_t backward (hb_codepoint_t rhs) const { return back_map[rhs]; } 193 operator []hb_inc_bimap_t194 hb_codepoint_t operator [] (hb_codepoint_t lhs) const { return get (lhs); } hashb_inc_bimap_t195 bool has (hb_codepoint_t lhs) const { return forw_map.has (lhs); } 196 197 protected: 198 hb_map_t forw_map; 199 hb_vector_t<hb_codepoint_t> back_map; 200 201 public: 202 auto keys () const HB_AUTO_RETURN (+ back_map.iter()) 203 }; 204 205 #endif /* HB_BIMAP_HH */ 206