Fixing 65868 REGRESSION(r92610) caused by 65668 - Optimize floating elements lookup
[WebKit-https.git] / Source / WebCore / platform / PODRedBlackTree.h
1 /*
2  * Copyright (C) 2010 Google Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 // A red-black tree, which is a form of a balanced binary tree. It
27 // supports efficient insertion, deletion and queries of comparable
28 // elements. The same element may be inserted multiple times. The
29 // algorithmic complexity of common operations is:
30 //
31 //   Insertion: O(lg(n))
32 //   Deletion:  O(lg(n))
33 //   Querying:  O(lg(n))
34 //
35 // The data type T that is stored in this red-black tree must be only
36 // Plain Old Data (POD), or bottom out into POD. It must _not_ rely on
37 // having its destructor called. This implementation internally
38 // allocates storage in large chunks and does not call the destructor
39 // on each object.
40 //
41 // Type T must supply a default constructor, a copy constructor, and
42 // the "<" and "==" operators.
43 //
44 // In debug mode, printing of the data contained in the tree is
45 // enabled. This requires the template specialization to be available:
46 //
47 //   template<> struct WebCore::ValueToString<T> {
48 //       static String string(const T& t);
49 //   };
50 //
51 // Note that when complex types are stored in this red/black tree, it
52 // is possible that single invocations of the "<" and "==" operators
53 // will be insufficient to describe the ordering of elements in the
54 // tree during queries. As a concrete example, consider the case where
55 // intervals are stored in the tree sorted by low endpoint. The "<"
56 // operator on the Interval class only compares the low endpoint, but
57 // the "==" operator takes into account the high endpoint as well.
58 // This makes the necessary logic for querying and deletion somewhat
59 // more complex. In order to properly handle such situations, the
60 // property "needsFullOrderingComparisons" must be set to true on
61 // the tree.
62 //
63 // This red-black tree is designed to be _augmented_; subclasses can
64 // add additional and summary information to each node to efficiently
65 // store and index more complex data structures. A concrete example is
66 // the IntervalTree, which extends each node with a summary statistic
67 // to efficiently store one-dimensional intervals.
68 //
69 // The design of this red-black tree comes from Cormen, Leiserson,
70 // and Rivest, _Introduction to Algorithms_, MIT Press, 1990.
71
72 #ifndef PODRedBlackTree_h
73 #define PODRedBlackTree_h
74
75 #include "PODArena.h"
76 #include <wtf/Assertions.h>
77 #include <wtf/Noncopyable.h>
78 #include <wtf/RefPtr.h>
79 #ifndef NDEBUG
80 #include "Logging.h"
81 #include <wtf/text/CString.h>
82 #include <wtf/text/StringBuilder.h>
83 #include <wtf/text/WTFString.h>
84 #endif
85
86 namespace WebCore {
87
88 #ifndef NDEBUG
89 template<class T>
90 struct ValueToString;
91 #endif
92
93 enum UninitializedTreeEnum {
94     UninitializedTree
95 };
96
97 template<class T>
98 class PODRedBlackTree {
99 public:
100     // Visitor interface for walking all of the tree's elements.
101     class Visitor {
102     public:
103         virtual void visit(const T& data) = 0;
104     protected:
105         virtual ~Visitor() { }
106     };
107
108     // Constructs a new red-black tree without allocating an arena.
109     // isInitialized will return false in this case. initIfNeeded can be used
110     // to init the structure. This constructor is usefull for creating
111     // lazy initialized tree.
112     PODRedBlackTree(UninitializedTreeEnum)
113         : m_root(0)
114         , m_needsFullOrderingComparisons(false)
115 #ifndef NDEBUG
116         , m_verboseDebugging(false)
117 #endif
118     {
119     }
120
121     // Constructs a new red-black tree, allocating temporary objects
122     // from a newly constructed PODArena.
123     PODRedBlackTree()
124         : m_arena(PODArena::create())
125         , m_root(0)
126         , m_needsFullOrderingComparisons(false)
127 #ifndef NDEBUG
128         , m_verboseDebugging(false)
129 #endif
130     {
131     }
132
133     // Constructs a new red-black tree, allocating temporary objects
134     // from the given PODArena.
135     explicit PODRedBlackTree(PassRefPtr<PODArena> arena)
136         : m_arena(arena)
137         , m_root(0)
138         , m_needsFullOrderingComparisons(false)
139 #ifndef NDEBUG
140         , m_verboseDebugging(false)
141 #endif
142     {
143     }
144
145     virtual ~PODRedBlackTree() { }
146
147     // Clearing will delete the contents of the tree. After this call
148     // isInitialized will return false.
149     void clear()
150     {
151         m_arena = 0;
152         m_root = 0;
153     }
154     
155     bool isInitialized() const
156     {
157         return m_arena;
158     }
159     
160     void initIfNeeded()
161     {
162         if (!m_arena)
163             m_arena = PODArena::create();
164     }
165
166     void add(const T& data)
167     {
168         ASSERT(isInitialized());
169         Node* node = m_arena->allocateObject<Node, T>(data);
170         insertNode(node);
171     }
172
173     // Returns true if the datum was found in the tree.
174     bool remove(const T& data)
175     {
176         ASSERT(isInitialized());
177         Node* node = treeSearch(data);
178         if (node) {
179             deleteNode(node);
180             return true;
181         }
182         return false;
183     }
184
185     bool contains(const T& data) const
186     {
187         ASSERT(isInitialized());
188         return treeSearch(data);
189     }
190
191     void visitInorder(Visitor* visitor) const
192     {
193         ASSERT(isInitialized());
194         if (!m_root)
195             return;
196         visitInorderImpl(m_root, visitor);
197     }
198
199     int size() const
200     {
201         ASSERT(isInitialized());
202         Counter counter;
203         visitInorder(&counter);
204         return counter.count();
205     }
206
207     // See the class documentation for an explanation of this property.
208     void setNeedsFullOrderingComparisons(bool needsFullOrderingComparisons)
209     {
210         m_needsFullOrderingComparisons = needsFullOrderingComparisons;
211     }
212
213     virtual bool checkInvariants() const
214     {
215         ASSERT(isInitialized());
216         int blackCount;
217         return checkInvariantsFromNode(m_root, &blackCount);
218     }
219
220 #ifndef NDEBUG
221     // Dumps the tree's contents to the logging info stream for
222     // debugging purposes.
223     void dump() const
224     {
225         if (m_arena)
226             dumpFromNode(m_root, 0);
227     }
228
229     // Turns on or off verbose debugging of the tree, causing many
230     // messages to be logged during insertion and other operations in
231     // debug mode.
232     void setVerboseDebugging(bool verboseDebugging)
233     {
234         m_verboseDebugging = verboseDebugging;
235     }
236 #endif
237
238 protected:
239     enum Color {
240         Red = 1,
241         Black
242     };
243
244     // The base Node class which is stored in the tree. Nodes are only
245     // an internal concept; users of the tree deal only with the data
246     // they store in it.
247     class Node {
248         WTF_MAKE_NONCOPYABLE(Node);
249     public:
250         // Constructor. Newly-created nodes are colored red.
251         explicit Node(const T& data)
252             : m_left(0)
253             , m_right(0)
254             , m_parent(0)
255             , m_color(Red)
256             , m_data(data)
257         {
258         }
259
260         virtual ~Node() { }
261
262         Color color() const { return m_color; }
263         void setColor(Color color) { m_color = color; }
264
265         // Fetches the user data.
266         T& data() { return m_data; }
267
268         // Copies all user-level fields from the source node, but not
269         // internal fields. For example, the base implementation of this
270         // method copies the "m_data" field, but not the child or parent
271         // fields. Any augmentation information also does not need to be
272         // copied, as it will be recomputed. Subclasses must call the
273         // superclass implementation.
274         virtual void copyFrom(Node* src) { m_data = src->data(); }
275
276         Node* left() const { return m_left; }
277         void setLeft(Node* node) { m_left = node; }
278
279         Node* right() const { return m_right; }
280         void setRight(Node* node) { m_right = node; }
281
282         Node* parent() const { return m_parent; }
283         void setParent(Node* node) { m_parent = node; }
284
285     private:
286         Node* m_left;
287         Node* m_right;
288         Node* m_parent;
289         Color m_color;
290         T m_data;
291     };
292
293     // Returns the root of the tree, which is needed by some subclasses.
294     Node* root() const { return m_root; }
295
296 private:
297     // This virtual method is the hook that subclasses should use when
298     // augmenting the red-black tree with additional per-node summary
299     // information. For example, in the case of an interval tree, this
300     // is used to compute the maximum endpoint of the subtree below the
301     // given node based on the values in the left and right children. It
302     // is guaranteed that this will be called in the correct order to
303     // properly update such summary information based only on the values
304     // in the left and right children. This method should return true if
305     // the node's summary information changed.
306     virtual bool updateNode(Node*) { return false; }
307
308     //----------------------------------------------------------------------
309     // Generic binary search tree operations
310     //
311
312     // Searches the tree for the given datum.
313     Node* treeSearch(const T& data) const
314     {
315         if (m_needsFullOrderingComparisons)
316             return treeSearchFullComparisons(m_root, data);
317
318         return treeSearchNormal(m_root, data);
319     }
320
321     // Searches the tree using the normal comparison operations,
322     // suitable for simple data types such as numbers.
323     Node* treeSearchNormal(Node* current, const T& data) const
324     {
325         while (current) {
326             if (current->data() == data)
327                 return current;
328             if (data < current->data())
329                 current = current->left();
330             else
331                 current = current->right();
332         }
333         return 0;
334     }
335
336     // Searches the tree using multiple comparison operations, required
337     // for data types with more complex behavior such as intervals.
338     Node* treeSearchFullComparisons(Node* current, const T& data) const
339     {
340         if (!current)
341             return 0;
342         if (data < current->data())
343             return treeSearchFullComparisons(current->left(), data);
344         if (current->data() < data)
345             return treeSearchFullComparisons(current->right(), data);
346         if (data == current->data())
347             return current;
348
349         // We may need to traverse both the left and right subtrees.
350         Node* result = treeSearchFullComparisons(current->left(), data);
351         if (!result)
352             result = treeSearchFullComparisons(current->right(), data);
353         return result;
354     }
355
356     void treeInsert(Node* z)
357     {
358         Node* y = 0;
359         Node* x = m_root;
360         while (x) {
361             y = x;
362             if (z->data() < x->data())
363                 x = x->left();
364             else
365                 x = x->right();
366         }
367         z->setParent(y);
368         if (!y)
369             m_root = z;
370         else {
371             if (z->data() < y->data())
372                 y->setLeft(z);
373             else
374                 y->setRight(z);
375         }
376     }
377
378     // Finds the node following the given one in sequential ordering of
379     // their data, or null if none exists.
380     Node* treeSuccessor(Node* x)
381     {
382         if (x->right())
383             return treeMinimum(x->right());
384         Node* y = x->parent();
385         while (y && x == y->right()) {
386             x = y;
387             y = y->parent();
388         }
389         return y;
390     }
391
392     // Finds the minimum element in the sub-tree rooted at the given
393     // node.
394     Node* treeMinimum(Node* x)
395     {
396         while (x->left())
397             x = x->left();
398         return x;
399     }
400
401     // Helper for maintaining the augmented red-black tree.
402     void propagateUpdates(Node* start)
403     {
404         bool shouldContinue = true;
405         while (start && shouldContinue) {
406             shouldContinue = updateNode(start);
407             start = start->parent();
408         }
409     }
410
411     //----------------------------------------------------------------------
412     // Red-Black tree operations
413     //
414
415     // Left-rotates the subtree rooted at x.
416     // Returns the new root of the subtree (x's right child).
417     Node* leftRotate(Node* x)
418     {
419         // Set y.
420         Node* y = x->right();
421
422         // Turn y's left subtree into x's right subtree.
423         x->setRight(y->left());
424         if (y->left())
425             y->left()->setParent(x);
426
427         // Link x's parent to y.
428         y->setParent(x->parent());
429         if (!x->parent())
430             m_root = y;
431         else {
432             if (x == x->parent()->left())
433                 x->parent()->setLeft(y);
434             else
435                 x->parent()->setRight(y);
436         }
437
438         // Put x on y's left.
439         y->setLeft(x);
440         x->setParent(y);
441
442         // Update nodes lowest to highest.
443         updateNode(x);
444         updateNode(y);
445         return y;
446     }
447
448     // Right-rotates the subtree rooted at y.
449     // Returns the new root of the subtree (y's left child).
450     Node* rightRotate(Node* y)
451     {
452         // Set x.
453         Node* x = y->left();
454
455         // Turn x's right subtree into y's left subtree.
456         y->setLeft(x->right());
457         if (x->right())
458             x->right()->setParent(y);
459
460         // Link y's parent to x.
461         x->setParent(y->parent());
462         if (!y->parent())
463             m_root = x;
464         else {
465             if (y == y->parent()->left())
466                 y->parent()->setLeft(x);
467             else
468                 y->parent()->setRight(x);
469         }
470
471         // Put y on x's right.
472         x->setRight(y);
473         y->setParent(x);
474
475         // Update nodes lowest to highest.
476         updateNode(y);
477         updateNode(x);
478         return x;
479     }
480
481     // Inserts the given node into the tree.
482     void insertNode(Node* x)
483     {
484         treeInsert(x);
485         x->setColor(Red);
486         updateNode(x);
487
488         logIfVerbose("  PODRedBlackTree::InsertNode");
489
490         // The node from which to start propagating updates upwards.
491         Node* updateStart = x->parent();
492
493         while (x != m_root && x->parent()->color() == Red) {
494             if (x->parent() == x->parent()->parent()->left()) {
495                 Node* y = x->parent()->parent()->right();
496                 if (y && y->color() == Red) {
497                     // Case 1
498                     logIfVerbose("  Case 1/1");
499                     x->parent()->setColor(Black);
500                     y->setColor(Black);
501                     x->parent()->parent()->setColor(Red);
502                     updateNode(x->parent());
503                     x = x->parent()->parent();
504                     updateNode(x);
505                     updateStart = x->parent();
506                 } else {
507                     if (x == x->parent()->right()) {
508                         logIfVerbose("  Case 1/2");
509                         // Case 2
510                         x = x->parent();
511                         leftRotate(x);
512                     }
513                     // Case 3
514                     logIfVerbose("  Case 1/3");
515                     x->parent()->setColor(Black);
516                     x->parent()->parent()->setColor(Red);
517                     Node* newSubTreeRoot = rightRotate(x->parent()->parent());
518                     updateStart = newSubTreeRoot->parent();
519                 }
520             } else {
521                 // Same as "then" clause with "right" and "left" exchanged.
522                 Node* y = x->parent()->parent()->left();
523                 if (y && y->color() == Red) {
524                     // Case 1
525                     logIfVerbose("  Case 2/1");
526                     x->parent()->setColor(Black);
527                     y->setColor(Black);
528                     x->parent()->parent()->setColor(Red);
529                     updateNode(x->parent());
530                     x = x->parent()->parent();
531                     updateNode(x);
532                     updateStart = x->parent();
533                 } else {
534                     if (x == x->parent()->left()) {
535                         // Case 2
536                         logIfVerbose("  Case 2/2");
537                         x = x->parent();
538                         rightRotate(x);
539                     }
540                     // Case 3
541                     logIfVerbose("  Case 2/3");
542                     x->parent()->setColor(Black);
543                     x->parent()->parent()->setColor(Red);
544                     Node* newSubTreeRoot = leftRotate(x->parent()->parent());
545                     updateStart = newSubTreeRoot->parent();
546                 }
547             }
548         }
549
550         propagateUpdates(updateStart);
551
552         m_root->setColor(Black);
553     }
554
555     // Restores the red-black property to the tree after splicing out
556     // a node. Note that x may be null, which is why xParent must be
557     // supplied.
558     void deleteFixup(Node* x, Node* xParent)
559     {
560         while (x != m_root && (!x || x->color() == Black)) {
561             if (x == xParent->left()) {
562                 // Note: the text points out that w can not be null.
563                 // The reason is not obvious from simply looking at
564                 // the code; it comes about from the properties of the
565                 // red-black tree.
566                 Node* w = xParent->right();
567                 ASSERT(w); // x's sibling should not be null.
568                 if (w->color() == Red) {
569                     // Case 1
570                     w->setColor(Black);
571                     xParent->setColor(Red);
572                     leftRotate(xParent);
573                     w = xParent->right();
574                 }
575                 if ((!w->left() || w->left()->color() == Black)
576                     && (!w->right() || w->right()->color() == Black)) {
577                     // Case 2
578                     w->setColor(Red);
579                     x = xParent;
580                     xParent = x->parent();
581                 } else {
582                     if (!w->right() || w->right()->color() == Black) {
583                         // Case 3
584                         w->left()->setColor(Black);
585                         w->setColor(Red);
586                         rightRotate(w);
587                         w = xParent->right();
588                     }
589                     // Case 4
590                     w->setColor(xParent->color());
591                     xParent->setColor(Black);
592                     if (w->right())
593                         w->right()->setColor(Black);
594                     leftRotate(xParent);
595                     x = m_root;
596                     xParent = x->parent();
597                 }
598             } else {
599                 // Same as "then" clause with "right" and "left"
600                 // exchanged.
601
602                 // Note: the text points out that w can not be null.
603                 // The reason is not obvious from simply looking at
604                 // the code; it comes about from the properties of the
605                 // red-black tree.
606                 Node* w = xParent->left();
607                 ASSERT(w); // x's sibling should not be null.
608                 if (w->color() == Red) {
609                     // Case 1
610                     w->setColor(Black);
611                     xParent->setColor(Red);
612                     rightRotate(xParent);
613                     w = xParent->left();
614                 }
615                 if ((!w->right() || w->right()->color() == Black)
616                     && (!w->left() || w->left()->color() == Black)) {
617                     // Case 2
618                     w->setColor(Red);
619                     x = xParent;
620                     xParent = x->parent();
621                 } else {
622                     if (!w->left() || w->left()->color() == Black) {
623                         // Case 3
624                         w->right()->setColor(Black);
625                         w->setColor(Red);
626                         leftRotate(w);
627                         w = xParent->left();
628                     }
629                     // Case 4
630                     w->setColor(xParent->color());
631                     xParent->setColor(Black);
632                     if (w->left())
633                         w->left()->setColor(Black);
634                     rightRotate(xParent);
635                     x = m_root;
636                     xParent = x->parent();
637                 }
638             }
639         }
640         if (x)
641             x->setColor(Black);
642     }
643
644     // Deletes the given node from the tree. Note that this
645     // particular node may not actually be removed from the tree;
646     // instead, another node might be removed and its contents
647     // copied into z.
648     void deleteNode(Node* z)
649     {
650         // Y is the node to be unlinked from the tree.
651         Node* y;
652         if (!z->left() || !z->right())
653             y = z;
654         else
655             y = treeSuccessor(z);
656
657         // Y is guaranteed to be non-null at this point.
658         Node* x;
659         if (y->left())
660             x = y->left();
661         else
662             x = y->right();
663
664         // X is the child of y which might potentially replace y in
665         // the tree. X might be null at this point.
666         Node* xParent;
667         if (x) {
668             x->setParent(y->parent());
669             xParent = x->parent();
670         } else
671             xParent = y->parent();
672         if (!y->parent())
673             m_root = x;
674         else {
675             if (y == y->parent()->left())
676                 y->parent()->setLeft(x);
677             else
678                 y->parent()->setRight(x);
679         }
680         if (y != z) {
681             z->copyFrom(y);
682             // This node has changed location in the tree and must be updated.
683             updateNode(z);
684             // The parent and its parents may now be out of date.
685             propagateUpdates(z->parent());
686         }
687
688         // If we haven't already updated starting from xParent, do so now.
689         if (xParent && xParent != y && xParent != z)
690             propagateUpdates(xParent);
691         if (y->color() == Black)
692             deleteFixup(x, xParent);
693     }
694
695     // Visits the subtree rooted at the given node in order.
696     void visitInorderImpl(Node* node, Visitor* visitor) const
697     {
698         if (node->left())
699             visitInorderImpl(node->left(), visitor);
700         visitor->visit(node->data());
701         if (node->right())
702             visitInorderImpl(node->right(), visitor);
703     }
704
705     //----------------------------------------------------------------------
706     // Helper class for size()
707
708     // A Visitor which simply counts the number of visited elements.
709     class Counter : public Visitor {
710         WTF_MAKE_NONCOPYABLE(Counter);
711     public:
712         Counter()
713             : m_count(0) { }
714
715         virtual void visit(const T&) { ++m_count; }
716         int count() const { return m_count; }
717
718     private:
719         int m_count;
720     };
721
722     //----------------------------------------------------------------------
723     // Verification and debugging routines
724     //
725
726     // Returns in the "blackCount" parameter the number of black
727     // children along all paths to all leaves of the given node.
728     bool checkInvariantsFromNode(Node* node, int* blackCount) const
729     {
730         // Base case is a leaf node.
731         if (!node) {
732             *blackCount = 1;
733             return true;
734         }
735
736         // Each node is either red or black.
737         if (!(node->color() == Red || node->color() == Black))
738             return false;
739
740         // Every leaf (or null) is black.
741
742         if (node->color() == Red) {
743             // Both of its children are black.
744             if (!((!node->left() || node->left()->color() == Black)))
745                 return false;
746             if (!((!node->right() || node->right()->color() == Black)))
747                 return false;
748         }
749
750         // Every simple path to a leaf node contains the same number of
751         // black nodes.
752         int leftCount = 0, rightCount = 0;
753         bool leftValid = checkInvariantsFromNode(node->left(), &leftCount);
754         bool rightValid = checkInvariantsFromNode(node->right(), &rightCount);
755         if (!leftValid || !rightValid)
756             return false;
757         *blackCount = leftCount + (node->color() == Black ? 1 : 0);
758         return leftCount == rightCount;
759     }
760
761 #ifdef NDEBUG
762     void logIfVerbose(const char*) const { }
763 #else
764     void logIfVerbose(const char* output) const
765     {
766         if (m_verboseDebugging)
767             LOG_ERROR("%s", output);
768     }
769 #endif
770
771 #ifndef NDEBUG
772     // Dumps the subtree rooted at the given node.
773     void dumpFromNode(Node* node, int indentation) const
774     {
775         StringBuilder builder;
776         for (int i = 0; i < indentation; i++)
777             builder.append(" ");
778         builder.append("-");
779         if (node) {
780             builder.append(" ");
781             builder.append(ValueToString<T>::string(node->data()));
782             builder.append((node->color() == Black) ? " (black)" : " (red)");
783         }
784         LOG_ERROR("%s", builder.toString().ascii().data());
785         if (node) {
786             dumpFromNode(node->left(), indentation + 2);
787             dumpFromNode(node->right(), indentation + 2);
788         }
789     }
790 #endif
791
792     //----------------------------------------------------------------------
793     // Data members
794
795     RefPtr<PODArena> m_arena;
796     Node* m_root;
797     bool m_needsFullOrderingComparisons;
798 #ifndef NDEBUG
799     bool m_verboseDebugging;
800 #endif
801 };
802
803 } // namespace WebCore
804
805 #endif // PODRedBlackTree_h