1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * @file map.h
30 * @brief Interface for map implementations.
31 * @author Mike Becker
32 * @author Olaf Wintermann
33 * @copyright 2-Clause BSD License
34 */
35
36 #ifndef UCX_MAP_H
37 #define UCX_MAP_H
38
39 #include "common.h"
40 #include "collection.h"
41 #include "string.h"
42 #include "hash_key.h"
43
44 #ifdef __cplusplus
45 extern "C" {
46 #endif
47
48 /** Type for the UCX map. */
49 typedef struct cx_map_s CxMap;
50
51 /** Type for a map entry. */
52 typedef struct cx_map_entry_s CxMapEntry;
53
54 /** Type for a map iterator. */
55 typedef struct cx_map_iterator_s CxMapIterator;
56
57 /** Type for map class definitions. */
58 typedef struct cx_map_class_s cx_map_class;
59
60 /** Structure for the UCX map. */
61 struct cx_map_s {
62 /**
63 * Base attributes.
64 */
65 CX_COLLECTION_BASE;
66 /** The map class definition. */
67 cx_map_class *cl;
68 };
69
70 /**
71 * A map entry.
72 */
73 struct cx_map_entry_s {
74 /**
75 * A pointer to the key.
76 */
77 const CxHashKey *key;
78 /**
79 * A pointer to the value.
80 */
81 void *value;
82 };
83
84 /**
85 * The type of iterator for a map.
86 */
87 enum cx_map_iterator_type {
88 /**
89 * Iterates over key/value pairs.
90 */
91 CX_MAP_ITERATOR_PAIRS,
92 /**
93 * Iterates over keys only.
94 */
95 CX_MAP_ITERATOR_KEYS,
96 /**
97 * Iterates over values only.
98 */
99 CX_MAP_ITERATOR_VALUES
100 };
101
102 /**
103 * Internal iterator struct - use CxMapIterator.
104 */
105 struct cx_map_iterator_s {
106 /**
107 * Inherited common data for all iterators.
108 */
109 CX_ITERATOR_BASE;
110
111 /**
112 * Handle for the source map.
113 */
114 union {
115 /**
116 * Access for mutating iterators.
117 */
118 CxMap *m;
119 /**
120 * Access for normal iterators.
121 */
122 const CxMap *c;
123 } map;
124
125 /**
126 * Handle for the current element.
127 *
128 * @attention Depends on the map implementation, do not assume a type (better: do not use!).
129 */
130 void *elem;
131
132 /**
133 * Reserved memory for a map entry.
134 *
135 * If a map implementation uses an incompatible layout, the iterator needs something
136 * to point to during iteration which @em is compatible.
137 */
138 CxMapEntry entry;
139
140 /**
141 * Field for storing the current slot number.
142 *
143 * (Used internally)
144 */
145 size_t slot;
146
147 /**
148 * Counts the elements successfully.
149 * It usually does not denote a stable index within the map as it would be for arrays.
150 */
151 size_t index;
152
153 /**
154 * The size of a value stored in this map.
155 */
156 size_t elem_size;
157
158 /**
159 * May contain the total number of elements, if known.
160 * Set to @c SIZE_MAX when the total number is unknown during iteration.
161 *
162 * @remark The UCX implementations of #CxMap always know the number of elements they store.
163 */
164 size_t elem_count;
165
166 /**
167 * The type of this iterator.
168 */
169 enum cx_map_iterator_type type;
170 };
171
172 /**
173 * The class definition for arbitrary maps.
174 */
175 struct cx_map_class_s {
176 /**
177 * Deallocates the entire memory.
178 */
179 void (*deallocate)(struct cx_map_s *map);
180
181 /**
182 * Removes all elements.
183 */
184 void (*clear)(struct cx_map_s *map);
185
186 /**
187 * Add or overwrite an element.
188 */
189 int (*put)(
190 CxMap *map,
191 CxHashKey key,
192 void *value
193 );
194
195 /**
196 * Returns an element.
197 */
198 void *(*get)(
199 const CxMap *map,
200 CxHashKey key
201 );
202
203 /**
204 * Removes an element.
205 *
206 * Implementations SHALL check if @p targetbuf is set and copy the elements
207 * to the buffer without invoking any destructor.
208 * When @p targetbuf is not set, the destructors SHALL be invoked.
209 *
210 * The function SHALL return zero when the @p key was found and
211 * non-zero, otherwise.
212 */
213 int (*remove)(
214 CxMap *map,
215 CxHashKey key,
216 void *targetbuf
217 );
218
219 /**
220 * Creates an iterator for this map.
221 */
222 CxMapIterator (*iterator)(const CxMap *map, enum cx_map_iterator_type type);
223 };
224
225 /**
226 * A shared instance of an empty map.
227 *
228 * Writing to that map is not allowed.
229 *
230 * You can use this is a placeholder for initializing CxMap pointers
231 * for which you do not want to reserve memory right from the beginning.
232 */
233 cx_attr_export
234 extern CxMap *const cxEmptyMap;
235
236 /**
237 * Deallocates the memory of the specified map.
238 *
239 * Also calls the content destructor functions for each element, if specified.
240 *
241 * @param map the map to be freed
242 */
243 cx_attr_export
244 void cxMapFree(CxMap *map);
245
246
247 /**
248 * Clears a map by removing all elements.
249 *
250 * Also calls the content destructor functions for each element, if specified.
251 *
252 * @param map the map to be cleared
253 */
254 cx_attr_nonnull
255 static inline void cxMapClear(CxMap *map) {
256 map->cl->clear(map);
257 }
258
259 /**
260 * Returns the number of elements in this map.
261 *
262 * @param map the map
263 * @return the number of stored elements
264 */
265 cx_attr_nonnull
266 static inline size_t cxMapSize(const CxMap *map) {
267 return map->collection.size;
268 }
269
270 /**
271 * Creates a value iterator for a map.
272 *
273 * When the map is storing pointers, those pointers are returned.
274 * Otherwise, the iterator iterates over pointers to the memory within the map where the
275 * respective elements are stored.
276 *
277 * @note An iterator iterates over all elements successively. Therefore, the order
278 * highly depends on the map implementation and may change arbitrarily when the contents change.
279 *
280 * @param map the map to create the iterator for
281 * @return an iterator for the currently stored values
282 */
283 cx_attr_nonnull
284 cx_attr_nodiscard
285 static inline CxMapIterator cxMapIteratorValues(const CxMap *map) {
286 return map->cl->iterator(map, CX_MAP_ITERATOR_VALUES);
287 }
288
289 /**
290 * Creates a key iterator for a map.
291 *
292 * The elements of the iterator are keys of type CxHashKey and the pointer returned
293 * during iterator shall be treated as @c const @c CxHashKey* .
294 *
295 * @note An iterator iterates over all elements successively. Therefore, the order
296 * highly depends on the map implementation and may change arbitrarily when the contents change.
297 *
298 * @param map the map to create the iterator for
299 * @return an iterator for the currently stored keys
300 */
301 cx_attr_nonnull
302 cx_attr_nodiscard
303 static inline CxMapIterator cxMapIteratorKeys(const CxMap *map) {
304 return map->cl->iterator(map, CX_MAP_ITERATOR_KEYS);
305 }
306
307 /**
308 * Creates an iterator for a map.
309 *
310 * The elements of the iterator are key/value pairs of type CxMapEntry and the pointer returned
311 * during iterator shall be treated as @c const @c CxMapEntry* .
312 *
313 * @note An iterator iterates over all elements successively. Therefore, the order
314 * highly depends on the map implementation and may change arbitrarily when the contents change.
315 *
316 * @param map the map to create the iterator for
317 * @return an iterator for the currently stored entries
318 * @see cxMapIteratorKeys()
319 * @see cxMapIteratorValues()
320 */
321 cx_attr_nonnull
322 cx_attr_nodiscard
323 static inline CxMapIterator cxMapIterator(const CxMap *map) {
324 return map->cl->iterator(map, CX_MAP_ITERATOR_PAIRS);
325 }
326
327
328 /**
329 * Creates a mutating iterator over the values of a map.
330 *
331 * When the map is storing pointers, those pointers are returned.
332 * Otherwise, the iterator iterates over pointers to the memory within the map where the
333 * respective elements are stored.
334 *
335 * @note An iterator iterates over all elements successively. Therefore, the order
336 * highly depends on the map implementation and may change arbitrarily when the contents change.
337 *
338 * @param map the map to create the iterator for
339 * @return an iterator for the currently stored values
340 */
341 cx_attr_nonnull
342 cx_attr_nodiscard
343 cx_attr_export
344 CxMapIterator cxMapMutIteratorValues(CxMap *map);
345
346 /**
347 * Creates a mutating iterator over the keys of a map.
348 *
349 * The elements of the iterator are keys of type CxHashKey and the pointer returned
350 * during iterator shall be treated as @c const @c CxHashKey* .
351 *
352 * @note An iterator iterates over all elements successively. Therefore, the order
353 * highly depends on the map implementation and may change arbitrarily when the contents change.
354 *
355 * @param map the map to create the iterator for
356 * @return an iterator for the currently stored keys
357 */
358 cx_attr_nonnull
359 cx_attr_nodiscard
360 cx_attr_export
361 CxMapIterator cxMapMutIteratorKeys(CxMap *map);
362
363 /**
364 * Creates a mutating iterator for a map.
365 *
366 * The elements of the iterator are key/value pairs of type CxMapEntry and the pointer returned
367 * during iterator shall be treated as @c const @c CxMapEntry* .
368 *
369 * @note An iterator iterates over all elements successively. Therefore, the order
370 * highly depends on the map implementation and may change arbitrarily when the contents change.
371 *
372 * @param map the map to create the iterator for
373 * @return an iterator for the currently stored entries
374 * @see cxMapMutIteratorKeys()
375 * @see cxMapMutIteratorValues()
376 */
377 cx_attr_nonnull
378 cx_attr_nodiscard
379 cx_attr_export
380 CxMapIterator cxMapMutIterator(CxMap *map);
381
382 #ifdef __cplusplus
383 } // end the extern "C" block here, because we want to start overloading
384 cx_attr_nonnull
385 static inline int cxMapPut(
386 CxMap *map,
387 CxHashKey const &key,
388 void *value
389 ) {
390 return map->cl->put(map, key, value);
391 }
392
393 cx_attr_nonnull
394 static inline int cxMapPut(
395 CxMap *map,
396 cxstring const &key,
397 void *value
398 ) {
399 return map->cl->put(map, cx_hash_key_cxstr(key), value);
400 }
401
402 cx_attr_nonnull
403 static inline int cxMapPut(
404 CxMap *map,
405 cxmutstr const &key,
406 void *value
407 ) {
408 return map->cl->put(map, cx_hash_key_cxstr(key), value);
409 }
410
411 cx_attr_nonnull
412 cx_attr_cstr_arg(2)
413 static inline int cxMapPut(
414 CxMap *map,
415 const char *key,
416 void *value
417 ) {
418 return map->cl->put(map, cx_hash_key_str(key), value);
419 }
420
421 cx_attr_nonnull
422 cx_attr_nodiscard
423 static inline void *cxMapGet(
424 const CxMap *map,
425 CxHashKey const &key
426 ) {
427 return map->cl->get(map, key);
428 }
429
430 cx_attr_nonnull
431 cx_attr_nodiscard
432 static inline void *cxMapGet(
433 const CxMap *map,
434 cxstring const &key
435 ) {
436 return map->cl->get(map, cx_hash_key_cxstr(key));
437 }
438
439 cx_attr_nonnull
440 cx_attr_nodiscard
441 static inline void *cxMapGet(
442 const CxMap *map,
443 cxmutstr const &key
444 ) {
445 return map->cl->get(map, cx_hash_key_cxstr(key));
446 }
447
448 cx_attr_nonnull
449 cx_attr_nodiscard
450 cx_attr_cstr_arg(2)
451 static inline void *cxMapGet(
452 const CxMap *map,
453 const char *key
454 ) {
455 return map->cl->get(map, cx_hash_key_str(key));
456 }
457
458 cx_attr_nonnull
459 static inline int cxMapRemove(
460 CxMap *map,
461 CxHashKey const &key
462 ) {
463 return map->cl->remove(map, key, nullptr);
464 }
465
466 cx_attr_nonnull
467 static inline int cxMapRemove(
468 CxMap *map,
469 cxstring const &key
470 ) {
471 return map->cl->remove(map, cx_hash_key_cxstr(key), nullptr);
472 }
473
474 cx_attr_nonnull
475 static inline int cxMapRemove(
476 CxMap *map,
477 cxmutstr const &key
478 ) {
479 return map->cl->remove(map, cx_hash_key_cxstr(key), nullptr);
480 }
481
482 cx_attr_nonnull
483 cx_attr_cstr_arg(2)
484 static inline int cxMapRemove(
485 CxMap *map,
486 const char *key
487 ) {
488 return map->cl->remove(map, cx_hash_key_str(key), nullptr);
489 }
490
491 cx_attr_nonnull
492 cx_attr_access_w(3)
493 static inline int cxMapRemoveAndGet(
494 CxMap *map,
495 CxHashKey key,
496 void *targetbuf
497 ) {
498 return map->cl->remove(map, key, targetbuf);
499 }
500
501 cx_attr_nonnull
502 cx_attr_access_w(3)
503 static inline int cxMapRemoveAndGet(
504 CxMap *map,
505 cxstring key,
506 void *targetbuf
507 ) {
508 return map->cl->remove(map, cx_hash_key_cxstr(key), targetbuf);
509 }
510
511 cx_attr_nonnull
512 cx_attr_access_w(3)
513 static inline int cxMapRemoveAndGet(
514 CxMap *map,
515 cxmutstr key,
516 void *targetbuf
517 ) {
518 return map->cl->remove(map, cx_hash_key_cxstr(key), targetbuf);
519 }
520
521 cx_attr_nonnull
522 cx_attr_access_w(3)
523 cx_attr_cstr_arg(2)
524 static inline int cxMapRemoveAndGet(
525 CxMap *map,
526 const char *key,
527 void *targetbuf
528 ) {
529 return map->cl->remove(map, cx_hash_key_str(key), targetbuf);
530 }
531
532 #else // __cplusplus
533
534 /**
535 * @copydoc cxMapPut()
536 */
537 cx_attr_nonnull
538 static inline int cx_map_put(
539 CxMap *map,
540 CxHashKey key,
541 void *value
542 ) {
543 return map->cl->put(map, key, value);
544 }
545
546 /**
547 * @copydoc cxMapPut()
548 */
549 cx_attr_nonnull
550 static inline int cx_map_put_cxstr(
551 CxMap *map,
552 cxstring key,
553 void *value
554 ) {
555 return map->cl->put(map, cx_hash_key_cxstr(key), value);
556 }
557
558 /**
559 * @copydoc cxMapPut()
560 */
561 cx_attr_nonnull
562 static inline int cx_map_put_mustr(
563 CxMap *map,
564 cxmutstr key,
565 void *value
566 ) {
567 return map->cl->put(map, cx_hash_key_cxstr(key), value);
568 }
569
570 /**
571 * @copydoc cxMapPut()
572 */
573 cx_attr_nonnull
574 cx_attr_cstr_arg(2)
575 static inline int cx_map_put_str(
576 CxMap *map,
577 const char *key,
578 void *value
579 ) {
580 return map->cl->put(map, cx_hash_key_str(key), value);
581 }
582
583 /**
584 * Puts a key/value-pair into the map.
585 *
586 * A possible existing value will be overwritten.
587 * If destructor functions are specified, they are called for
588 * the overwritten element.
589 *
590 * If this map is storing pointers, the @p value pointer is written
591 * to the map. Otherwise, the memory is copied from @p value with
592 * memcpy().
593 *
594 * The @p key is always copied.
595 *
596 * @param map (@c CxMap*) the map
597 * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
598 * @param value (@c void*) the value
599 * @retval zero success
600 * @retval non-zero value on memory allocation failure
601 */
602 #define cxMapPut(map, key, value) _Generic((key), \
603 CxHashKey: cx_map_put, \
604 cxstring: cx_map_put_cxstr, \
605 cxmutstr: cx_map_put_mustr, \
606 char*: cx_map_put_str, \
607 const char*: cx_map_put_str) \
608 (map, key, value)
609
610 /**
611 * @copydoc cxMapGet()
612 */
613 cx_attr_nonnull
614 cx_attr_nodiscard
615 static inline void *cx_map_get(
616 const CxMap *map,
617 CxHashKey key
618 ) {
619 return map->cl->get(map, key);
620 }
621
622 /**
623 * @copydoc cxMapGet()
624 */
625 cx_attr_nonnull
626 cx_attr_nodiscard
627 static inline void *cx_map_get_cxstr(
628 const CxMap *map,
629 cxstring key
630 ) {
631 return map->cl->get(map, cx_hash_key_cxstr(key));
632 }
633
634 /**
635 * @copydoc cxMapGet()
636 */
637 cx_attr_nonnull
638 cx_attr_nodiscard
639 static inline void *cx_map_get_mustr(
640 const CxMap *map,
641 cxmutstr key
642 ) {
643 return map->cl->get(map, cx_hash_key_cxstr(key));
644 }
645
646 /**
647 * @copydoc cxMapGet()
648 */
649 cx_attr_nonnull
650 cx_attr_nodiscard
651 cx_attr_cstr_arg(2)
652 static inline void *cx_map_get_str(
653 const CxMap *map,
654 const char *key
655 ) {
656 return map->cl->get(map, cx_hash_key_str(key));
657 }
658
659 /**
660 * Retrieves a value by using a key.
661 *
662 * If this map is storing pointers, the stored pointer is returned.
663 * Otherwise, a pointer to the element within the map's memory
664 * is returned (which is valid as long as the element stays in the map).
665 *
666 * @param map (@c CxMap*) the map
667 * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
668 * @return (@c void*) the value
669 */
670 #define cxMapGet(map, key) _Generic((key), \
671 CxHashKey: cx_map_get, \
672 cxstring: cx_map_get_cxstr, \
673 cxmutstr: cx_map_get_mustr, \
674 char*: cx_map_get_str, \
675 const char*: cx_map_get_str) \
676 (map, key)
677
678 /**
679 * @copydoc cxMapRemove()
680 */
681 cx_attr_nonnull
682 static inline int cx_map_remove(
683 CxMap *map,
684 CxHashKey key
685 ) {
686 return map->cl->remove(map, key, NULL);
687 }
688
689 /**
690 * @copydoc cxMapRemove()
691 */
692 cx_attr_nonnull
693 static inline int cx_map_remove_cxstr(
694 CxMap *map,
695 cxstring key
696 ) {
697 return map->cl->remove(map, cx_hash_key_cxstr(key), NULL);
698 }
699
700 /**
701 * @copydoc cxMapRemove()
702 */
703 cx_attr_nonnull
704 static inline int cx_map_remove_mustr(
705 CxMap *map,
706 cxmutstr key
707 ) {
708 return map->cl->remove(map, cx_hash_key_cxstr(key), NULL);
709 }
710
711 /**
712 * @copydoc cxMapRemove()
713 */
714 cx_attr_nonnull
715 cx_attr_cstr_arg(2)
716 static inline int cx_map_remove_str(
717 CxMap *map,
718 const char *key
719 ) {
720 return map->cl->remove(map, cx_hash_key_str(key), NULL);
721 }
722
723 /**
724 * Removes a key/value-pair from the map by using the key.
725 *
726 * Always invokes the destructors functions, if any, on the removed element.
727 *
728 * @param map (@c CxMap*) the map
729 * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
730 * @retval zero success
731 * @retval non-zero the key was not found
732 *
733 * @see cxMapRemoveAndGet()
734 */
735 #define cxMapRemove(map, key) _Generic((key), \
736 CxHashKey: cx_map_remove, \
737 cxstring: cx_map_remove_cxstr, \
738 cxmutstr: cx_map_remove_mustr, \
739 char*: cx_map_remove_str, \
740 const char*: cx_map_remove_str) \
741 (map, key)
742
743 /**
744 * @copydoc cxMapRemoveAndGet()
745 */
746 cx_attr_nonnull
747 cx_attr_access_w(3)
748 static inline int cx_map_remove_and_get(
749 CxMap *map,
750 CxHashKey key,
751 void *targetbuf
752 ) {
753 return map->cl->remove(map, key, targetbuf);
754 }
755
756 /**
757 * @copydoc cxMapRemoveAndGet()
758 */
759 cx_attr_nonnull
760 cx_attr_access_w(3)
761 static inline int cx_map_remove_and_get_cxstr(
762 CxMap *map,
763 cxstring key,
764 void *targetbuf
765 ) {
766 return map->cl->remove(map, cx_hash_key_cxstr(key), targetbuf);
767 }
768
769 /**
770 * @copydoc cxMapRemoveAndGet()
771 */
772 cx_attr_nonnull
773 cx_attr_access_w(3)
774 static inline int cx_map_remove_and_get_mustr(
775 CxMap *map,
776 cxmutstr key,
777 void *targetbuf
778 ) {
779 return map->cl->remove(map, cx_hash_key_cxstr(key), targetbuf);
780 }
781
782 /**
783 * @copydoc cxMapRemoveAndGet()
784 */
785 cx_attr_nonnull
786 cx_attr_access_w(3)
787 cx_attr_cstr_arg(2)
788 static inline int cx_map_remove_and_get_str(
789 CxMap *map,
790 const char *key,
791 void *targetbuf
792 ) {
793 return map->cl->remove(map, cx_hash_key_str(key), targetbuf);
794 }
795
796 /**
797 * Removes a key/value-pair from the map by using the key.
798 *
799 * This function will copy the contents of the removed element
800 * to the target buffer, which must be guaranteed to be large enough
801 * to hold the element (the map's element size).
802 * The destructor functions, if any, will @em not be called.
803 *
804 * If this map is storing pointers, the element is the pointer itself
805 * and not the object it points to.
806 *
807 * @param map (@c CxMap*) the map
808 * @param key (@c CxHashKey, @c char*, @c cxstring, or @c cxmutstr) the key
809 * @param targetbuf (@c void*) the buffer where the element shall be copied to
810 * @retval zero success
811 * @retval non-zero the key was not found
812 *
813 * @see cxMapRemove()
814 */
815 #define cxMapRemoveAndGet(map, key, targetbuf) _Generic((key), \
816 CxHashKey: cx_map_remove_and_get, \
817 cxstring: cx_map_remove_and_get_cxstr, \
818 cxmutstr: cx_map_remove_and_get_mustr, \
819 char*: cx_map_remove_and_get_str, \
820 const char*: cx_map_remove_and_get_str) \
821 (map, key, targetbuf)
822
823 #endif // __cplusplus
824
825 #endif // UCX_MAP_H
826