src/compiler/glsl/list.h

   1 /*
   2  * Copyright © 2008, 2010 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 /**
  25  * \file list.h
  26  * \brief Doubly-linked list abstract container type.
  27  *
  28  * Each doubly-linked list has a sentinel head and tail node.  These nodes
  29  * contain no data.  The head sentinel can be identified by its \c prev
  30  * pointer being \c NULL.  The tail sentinel can be identified by its
  31  * \c next pointer being \c NULL.
  32  *
  33  * A list is empty if either the head sentinel's \c next pointer points to the
  34  * tail sentinel or the tail sentinel's \c prev poiner points to the head
  35  * sentinel. The head sentinel and tail sentinel nodes are allocated within the
  36  * list structure.
  37  *
  38  * Do note that this means that the list nodes will contain pointers into the
  39  * list structure itself and as a result you may not \c realloc() an  \c
  40  * exec_list or any structure in which an \c exec_list is embedded.
  41  */
  42
  43 #ifndef LIST_CONTAINER_H
  44 #define LIST_CONTAINER_H
  45
  46 #ifndef __cplusplus
  47 #include <stddef.h>
  48 #endif
  49 #include <assert.h>
  50
  51 #include "util/ralloc.h"
  52
  53 struct exec_node {
  54    struct exec_node *next;
  55    struct exec_node *prev;
  56
  57 #ifdef __cplusplus
  58    DECLARE_RZALLOC_CXX_OPERATORS(exec_node)
  59
  60    exec_node() : next(NULL), prev(NULL)
  61    {
  62       /* empty */
  63    }
  64
  65    const exec_node *get_next() const;
  66    exec_node *get_next();
  67
  68    const exec_node *get_prev() const;
  69    exec_node *get_prev();
  70
  71    void remove();
  72
  73    /**
  74     * Link a node with itself
  75     *
  76     * This creates a sort of degenerate list that is occasionally useful.
  77     */
  78    void self_link();
  79
  80    /**
  81     * Insert a node in the list after the current node
  82     */
  83    void insert_after(exec_node *after);
  84
  85    /**
  86     * Insert another list in the list after the current node
  87     */
  88    void insert_after(struct exec_list *after);
  89
  90    /**
  91     * Insert a node in the list before the current node
  92     */
  93    void insert_before(exec_node *before);
  94
  95    /**
  96     * Insert another list in the list before the current node
  97     */
  98    void insert_before(struct exec_list *before);
  99
 100    /**
 101     * Replace the current node with the given node.
 102     */
 103    void replace_with(exec_node *replacement);
 104
 105    /**
 106     * Is this the sentinel at the tail of the list?
 107     */
 108    bool is_tail_sentinel() const;
 109
 110    /**
 111     * Is this the sentinel at the head of the list?
 112     */
 113    bool is_head_sentinel() const;
 114 #endif
 115 };
 116
 117 static inline void
 118 exec_node_init(struct exec_node *n)
 119 {
 120    n->next = NULL;
 121    n->prev = NULL;
 122 }
 123
 124 static inline const struct exec_node *
 125 exec_node_get_next_const(const struct exec_node *n)
 126 {
 127    return n->next;
 128 }
 129
 130 static inline struct exec_node *
 131 exec_node_get_next(struct exec_node *n)
 132 {
 133    return n->next;
 134 }
 135
 136 static inline const struct exec_node *
 137 exec_node_get_prev_const(const struct exec_node *n)
 138 {
 139    return n->prev;
 140 }
 141
 142 static inline struct exec_node *
 143 exec_node_get_prev(struct exec_node *n)
 144 {
 145    return n->prev;
 146 }
 147
 148 static inline void
 149 exec_node_remove(struct exec_node *n)
 150 {
 151    n->next->prev = n->prev;
 152    n->prev->next = n->next;
 153    n->next = NULL;
 154    n->prev = NULL;
 155 }
 156
 157 static inline void
 158 exec_node_self_link(struct exec_node *n)
 159 {
 160    n->next = n;
 161    n->prev = n;
 162 }
 163
 164 static inline void
 165 exec_node_insert_after(struct exec_node *n, struct exec_node *after)
 166 {
 167    after->next = n->next;
 168    after->prev = n;
 169
 170    n->next->prev = after;
 171    n->next = after;
 172 }
 173
 174 static inline void
 175 exec_node_insert_node_before(struct exec_node *n, struct exec_node *before)
 176 {
 177    before->next = n;
 178    before->prev = n->prev;
 179
 180    n->prev->next = before;
 181    n->prev = before;
 182 }
 183
 184 static inline void
 185 exec_node_replace_with(struct exec_node *n, struct exec_node *replacement)
 186 {
 187    replacement->prev = n->prev;
 188    replacement->next = n->next;
 189
 190    n->prev->next = replacement;
 191    n->next->prev = replacement;
 192 }
 193
 194 static inline bool
 195 exec_node_is_tail_sentinel(const struct exec_node *n)
 196 {
 197    return n->next == NULL;
 198 }
 199
 200 static inline bool
 201 exec_node_is_head_sentinel(const struct exec_node *n)
 202 {
 203    return n->prev == NULL;
 204 }
 205
 206 #ifdef __cplusplus
 207 inline const exec_node *exec_node::get_next() const
 208 {
 209    return exec_node_get_next_const(this);
 210 }
 211
 212 inline exec_node *exec_node::get_next()
 213 {
 214    return exec_node_get_next(this);
 215 }
 216
 217 inline const exec_node *exec_node::get_prev() const
 218 {
 219    return exec_node_get_prev_const(this);
 220 }
 221
 222 inline exec_node *exec_node::get_prev()
 223 {
 224    return exec_node_get_prev(this);
 225 }
 226
 227 inline void exec_node::remove()
 228 {
 229    exec_node_remove(this);
 230 }
 231
 232 inline void exec_node::self_link()
 233 {
 234    exec_node_self_link(this);
 235 }
 236
 237 inline void exec_node::insert_after(exec_node *after)
 238 {
 239    exec_node_insert_after(this, after);
 240 }
 241
 242 inline void exec_node::insert_before(exec_node *before)
 243 {
 244    exec_node_insert_node_before(this, before);
 245 }
 246
 247 inline void exec_node::replace_with(exec_node *replacement)
 248 {
 249    exec_node_replace_with(this, replacement);
 250 }
 251
 252 inline bool exec_node::is_tail_sentinel() const
 253 {
 254    return exec_node_is_tail_sentinel(this);
 255 }
 256
 257 inline bool exec_node::is_head_sentinel() const
 258 {
 259    return exec_node_is_head_sentinel(this);
 260 }
 261 #endif
 262
 263 #ifdef __cplusplus
 264 /* This macro will not work correctly if `t' uses virtual inheritance.  If you
 265  * are using virtual inheritance, you deserve a slow and painful death.  Enjoy!
 266  */
 267 #define exec_list_offsetof(t, f, p) \
 268    (((char *) &((t *) p)->f) - ((char *) p))
 269 #else
 270 #define exec_list_offsetof(t, f, p) offsetof(t, f)
 271 #endif
 272
 273 /**
 274  * Get a pointer to the structure containing an exec_node
 275  *
 276  * Given a pointer to an \c exec_node embedded in a structure, get a pointer to
 277  * the containing structure.
 278  *
 279  * \param type  Base type of the structure containing the node
 280  * \param node  Pointer to the \c exec_node
 281  * \param field Name of the field in \c type that is the embedded \c exec_node
 282  */
 283 #define exec_node_data(type, node, field) \
 284    ((type *) (((char *) node) - exec_list_offsetof(type, field, node)))
 285
 286 #ifdef __cplusplus
 287 struct exec_node;
 288 #endif
 289
 290 struct exec_list {
 291    struct exec_node head_sentinel;
 292    struct exec_node tail_sentinel;
 293
 294 #ifdef __cplusplus
 295    DECLARE_RALLOC_CXX_OPERATORS(exec_list)
 296
 297    exec_list()
 298    {
 299       make_empty();
 300    }
 301
 302    void make_empty();
 303
 304    bool is_empty() const;
 305
 306    const exec_node *get_head() const;
 307    exec_node *get_head();
 308    const exec_node *get_head_raw() const;
 309    exec_node *get_head_raw();
 310
 311    const exec_node *get_tail() const;
 312    exec_node *get_tail();
 313    const exec_node *get_tail_raw() const;
 314    exec_node *get_tail_raw();
 315
 316    unsigned length() const;
 317
 318    void push_head(exec_node *n);
 319    void push_tail(exec_node *n);
 320    void push_degenerate_list_at_head(exec_node *n);
 321
 322    /**
 323     * Remove the first node from a list and return it
 324     *
 325     * \return
 326     * The first node in the list or \c NULL if the list is empty.
 327     *
 328     * \sa exec_list::get_head
 329     */
 330    exec_node *pop_head();
 331
 332    /**
 333     * Move all of the nodes from this list to the target list
 334     */
 335    void move_nodes_to(exec_list *target);
 336
 337    /**
 338     * Append all nodes from the source list to the end of the target list
 339     */
 340    void append_list(exec_list *source);
 341
 342    /**
 343     * Prepend all nodes from the source list to the beginning of the target
 344     * list
 345     */
 346    void prepend_list(exec_list *source);
 347 #endif
 348 };
 349
 350 static inline void
 351 exec_list_make_empty(struct exec_list *list)
 352 {
 353    list->head_sentinel.next = &list->tail_sentinel;
 354    list->head_sentinel.prev = NULL;
 355    list->tail_sentinel.next = NULL;
 356    list->tail_sentinel.prev = &list->head_sentinel;
 357 }
 358
 359 static inline bool
 360 exec_list_is_empty(const struct exec_list *list)
 361 {
 362    /* There are three ways to test whether a list is empty or not.
 363     *
 364     * - Check to see if the head sentinel's \c next is the tail sentinel.
 365     * - Check to see if the tail sentinel's \c prev is the head sentinel.
 366     * - Check to see if the head is the sentinel node by test whether its
 367     *   \c next pointer is \c NULL.
 368     *
 369     * The first two methods tend to generate better code on modern systems
 370     * because they save a pointer dereference.
 371     */
 372    return list->head_sentinel.next == &list->tail_sentinel;
 373 }
 374
 375 static inline const struct exec_node *
 376 exec_list_get_head_const(const struct exec_list *list)
 377 {
 378    return !exec_list_is_empty(list) ? list->head_sentinel.next : NULL;
 379 }
 380
 381 static inline struct exec_node *
 382 exec_list_get_head(struct exec_list *list)
 383 {
 384    return !exec_list_is_empty(list) ? list->head_sentinel.next : NULL;
 385 }
 386
 387 static inline const struct exec_node *
 388 exec_list_get_head_raw_const(const struct exec_list *list)
 389 {
 390    return list->head_sentinel.next;
 391 }
 392
 393 static inline struct exec_node *
 394 exec_list_get_head_raw(struct exec_list *list)
 395 {
 396    return list->head_sentinel.next;
 397 }
 398
 399 static inline const struct exec_node *
 400 exec_list_get_tail_const(const struct exec_list *list)
 401 {
 402    return !exec_list_is_empty(list) ? list->tail_sentinel.prev : NULL;
 403 }
 404
 405 static inline struct exec_node *
 406 exec_list_get_tail(struct exec_list *list)
 407 {
 408    return !exec_list_is_empty(list) ? list->tail_sentinel.prev : NULL;
 409 }
 410
 411 static inline const struct exec_node *
 412 exec_list_get_tail_raw_const(const struct exec_list *list)
 413 {
 414    return list->tail_sentinel.prev;
 415 }
 416
 417 static inline struct exec_node *
 418 exec_list_get_tail_raw(struct exec_list *list)
 419 {
 420    return list->tail_sentinel.prev;
 421 }
 422
 423 static inline unsigned
 424 exec_list_length(const struct exec_list *list)
 425 {
 426    unsigned size = 0;
 427    struct exec_node *node;
 428
 429    for (node = list->head_sentinel.next; node->next != NULL; node = node->next) {
 430       size++;
 431    }
 432
 433    return size;
 434 }
 435
 436 static inline void
 437 exec_list_push_head(struct exec_list *list, struct exec_node *n)
 438 {
 439    n->next = list->head_sentinel.next;
 440    n->prev = &list->head_sentinel;
 441
 442    n->next->prev = n;
 443    list->head_sentinel.next = n;
 444 }
 445
 446 static inline void
 447 exec_list_push_tail(struct exec_list *list, struct exec_node *n)
 448 {
 449    n->next = &list->tail_sentinel;
 450    n->prev = list->tail_sentinel.prev;
 451
 452    n->prev->next = n;
 453    list->tail_sentinel.prev = n;
 454 }
 455
 456 static inline void
 457 exec_list_push_degenerate_list_at_head(struct exec_list *list, struct exec_node *n)
 458 {
 459    assert(n->prev->next == n);
 460
 461    n->prev->next = list->head_sentinel.next;
 462    list->head_sentinel.next->prev = n->prev;
 463    n->prev = &list->head_sentinel;
 464    list->head_sentinel.next = n;
 465 }
 466
 467 static inline struct exec_node *
 468 exec_list_pop_head(struct exec_list *list)
 469 {
 470    struct exec_node *const n = exec_list_get_head(list);
 471    if (n != NULL)
 472       exec_node_remove(n);
 473
 474    return n;
 475 }
 476
 477 static inline void
 478 exec_list_move_nodes_to(struct exec_list *list, struct exec_list *target)
 479 {
 480    if (exec_list_is_empty(list)) {
 481       exec_list_make_empty(target);
 482    } else {
 483       target->head_sentinel.next = list->head_sentinel.next;
 484       target->head_sentinel.prev = NULL;
 485       target->tail_sentinel.next = NULL;
 486       target->tail_sentinel.prev = list->tail_sentinel.prev;
 487
 488       target->head_sentinel.next->prev = &target->head_sentinel;
 489       target->tail_sentinel.prev->next = &target->tail_sentinel;
 490
 491       exec_list_make_empty(list);
 492    }
 493 }
 494
 495 static inline void
 496 exec_list_append(struct exec_list *list, struct exec_list *source)
 497 {
 498    if (exec_list_is_empty(source))
 499       return;
 500
 501    /* Link the first node of the source with the last node of the target list.
 502     */
 503    list->tail_sentinel.prev->next = source->head_sentinel.next;
 504    source->head_sentinel.next->prev = list->tail_sentinel.prev;
 505
 506    /* Make the tail of the source list be the tail of the target list.
 507     */
 508    list->tail_sentinel.prev = source->tail_sentinel.prev;
 509    list->tail_sentinel.prev->next = &list->tail_sentinel;
 510
 511    /* Make the source list empty for good measure.
 512     */
 513    exec_list_make_empty(source);
 514 }
 515
 516 static inline void
 517 exec_node_insert_list_after(struct exec_node *n, struct exec_list *after)
 518 {
 519    if (exec_list_is_empty(after))
 520       return;
 521
 522    after->tail_sentinel.prev->next = n->next;
 523    after->head_sentinel.next->prev = n;
 524
 525    n->next->prev = after->tail_sentinel.prev;
 526    n->next = after->head_sentinel.next;
 527
 528    exec_list_make_empty(after);
 529 }
 530
 531 static inline void
 532 exec_list_prepend(struct exec_list *list, struct exec_list *source)
 533 {
 534    exec_list_append(source, list);
 535    exec_list_move_nodes_to(source, list);
 536 }
 537
 538 static inline void
 539 exec_node_insert_list_before(struct exec_node *n, struct exec_list *before)
 540 {
 541    if (exec_list_is_empty(before))
 542       return;
 543
 544    before->tail_sentinel.prev->next = n;
 545    before->head_sentinel.next->prev = n->prev;
 546
 547    n->prev->next = before->head_sentinel.next;
 548    n->prev = before->tail_sentinel.prev;
 549
 550    exec_list_make_empty(before);
 551 }
 552
 553 static inline void
 554 exec_list_validate(const struct exec_list *list)
 555 {
 556    const struct exec_node *node;
 557
 558    assert(list->head_sentinel.next->prev == &list->head_sentinel);
 559    assert(list->head_sentinel.prev == NULL);
 560    assert(list->tail_sentinel.next == NULL);
 561    assert(list->tail_sentinel.prev->next == &list->tail_sentinel);
 562
 563    /* We could try to use one of the interators below for this but they all
 564     * either require C++ or assume the exec_node is embedded in a structure
 565     * which is not the case for this function.
 566     */
 567    for (node = list->head_sentinel.next; node->next != NULL; node = node->next) {
 568       assert(node->next->prev == node);
 569       assert(node->prev->next == node);
 570    }
 571 }
 572
 573 #ifdef __cplusplus
 574 inline void exec_list::make_empty()
 575 {
 576    exec_list_make_empty(this);
 577 }
 578
 579 inline bool exec_list::is_empty() const
 580 {
 581    return exec_list_is_empty(this);
 582 }
 583
 584 inline const exec_node *exec_list::get_head() const
 585 {
 586    return exec_list_get_head_const(this);
 587 }
 588
 589 inline exec_node *exec_list::get_head()
 590 {
 591    return exec_list_get_head(this);
 592 }
 593
 594 inline const exec_node *exec_list::get_head_raw() const
 595 {
 596    return exec_list_get_head_raw_const(this);
 597 }
 598
 599 inline exec_node *exec_list::get_head_raw()
 600 {
 601    return exec_list_get_head_raw(this);
 602 }
 603
 604 inline const exec_node *exec_list::get_tail() const
 605 {
 606    return exec_list_get_tail_const(this);
 607 }
 608
 609 inline exec_node *exec_list::get_tail()
 610 {
 611    return exec_list_get_tail(this);
 612 }
 613
 614 inline const exec_node *exec_list::get_tail_raw() const
 615 {
 616    return exec_list_get_tail_raw_const(this);
 617 }
 618
 619 inline exec_node *exec_list::get_tail_raw()
 620 {
 621    return exec_list_get_tail_raw(this);
 622 }
 623
 624 inline unsigned exec_list::length() const
 625 {
 626    return exec_list_length(this);
 627 }
 628
 629 inline void exec_list::push_head(exec_node *n)
 630 {
 631    exec_list_push_head(this, n);
 632 }
 633
 634 inline void exec_list::push_tail(exec_node *n)
 635 {
 636    exec_list_push_tail(this, n);
 637 }
 638
 639 inline void exec_list::push_degenerate_list_at_head(exec_node *n)
 640 {
 641    exec_list_push_degenerate_list_at_head(this, n);
 642 }
 643
 644 inline exec_node *exec_list::pop_head()
 645 {
 646    return exec_list_pop_head(this);
 647 }
 648
 649 inline void exec_list::move_nodes_to(exec_list *target)
 650 {
 651    exec_list_move_nodes_to(this, target);
 652 }
 653
 654 inline void exec_list::append_list(exec_list *source)
 655 {
 656    exec_list_append(this, source);
 657 }
 658
 659 inline void exec_node::insert_after(exec_list *after)
 660 {
 661    exec_node_insert_list_after(this, after);
 662 }
 663
 664 inline void exec_list::prepend_list(exec_list *source)
 665 {
 666    exec_list_prepend(this, source);
 667 }
 668
 669 inline void exec_node::insert_before(exec_list *before)
 670 {
 671    exec_node_insert_list_before(this, before);
 672 }
 673 #endif
 674
 675 #define foreach_in_list(__type, __inst, __list)      \
 676    for (__type *__inst = (__type *)(__list)->head_sentinel.next; \
 677         !(__inst)->is_tail_sentinel();               \
 678         (__inst) = (__type *)(__inst)->next)
 679
 680 #define foreach_in_list_reverse(__type, __inst, __list)   \
 681    for (__type *__inst = (__type *)(__list)->tail_sentinel.prev; \
 682         !(__inst)->is_head_sentinel();                    \
 683         (__inst) = (__type *)(__inst)->prev)
 684
 685 /**
 686  * This version is safe even if the current node is removed.
 687  */
 688 #define foreach_in_list_safe(__type, __node, __list) \
 689    for (__type *__node = (__type *)(__list)->head_sentinel.next,   \
 690                *__next = (__type *)__node->next;     \
 691         __next != NULL;                              \
 692         __node = __next, __next = (__type *)__next->next)
 693
 694 #define foreach_in_list_reverse_safe(__type, __node, __list) \
 695    for (__type *__node = (__type *)(__list)->tail_sentinel.prev,      \
 696                *__prev = (__type *)__node->prev;             \
 697         __prev != NULL;                                      \
 698         __node = __prev, __prev = (__type *)__prev->prev)
 699
 700 #define foreach_in_list_use_after(__type, __inst, __list) \
 701    __type *__inst;                                        \
 702    for ((__inst) = (__type *)(__list)->head_sentinel.next; \
 703         !(__inst)->is_tail_sentinel();                    \
 704         (__inst) = (__type *)(__inst)->next)
 705 /**
 706  * Iterate through two lists at once.  Stops at the end of the shorter list.
 707  *
 708  * This is safe against either current node being removed or replaced.
 709  */
 710 #define foreach_two_lists(__node1, __list1, __node2, __list2) \
 711    for (struct exec_node * __node1 = (__list1)->head_sentinel.next, \
 712                          * __node2 = (__list2)->head_sentinel.next, \
 713                          * __next1 = __node1->next,           \
 714                          * __next2 = __node2->next            \
 715         ; __next1 != NULL && __next2 != NULL                  \
 716         ; __node1 = __next1,                                  \
 717           __node2 = __next2,                                  \
 718           __next1 = __next1->next,                            \
 719           __next2 = __next2->next)
 720
 721 #define foreach_list_typed(__type, __node, __field, __list)             \
 722    for (__type * __node =                                               \
 723          exec_node_data(__type, (__list)->head_sentinel.next, __field); \
 724         (__node)->__field.next != NULL;                                 \
 725         (__node) = exec_node_data(__type, (__node)->__field.next, __field))
 726
 727 #define foreach_list_typed_from(__type, __node, __field, __list, __start)  \
 728    for (__type * __node = exec_node_data(__type, (__start), __field);      \
 729         (__node)->__field.next != NULL;                                    \
 730         (__node) = exec_node_data(__type, (__node)->__field.next, __field))
 731
 732 #define foreach_list_typed_reverse(__type, __node, __field, __list)        \
 733    for (__type * __node =                                                \
 734            exec_node_data(__type, (__list)->tail_sentinel.prev, __field);  \
 735         (__node)->__field.prev != NULL;                                 \
 736         (__node) = exec_node_data(__type, (__node)->__field.prev, __field))
 737
 738 #define foreach_list_typed_safe(__type, __node, __field, __list)           \
 739    for (__type * __node =                                                  \
 740            exec_node_data(__type, (__list)->head_sentinel.next, __field),  \
 741                * __next =                                                  \
 742            exec_node_data(__type, (__node)->__field.next, __field);        \
 743         (__node)->__field.next != NULL;                                    \
 744         __node = __next, __next =                                          \
 745            exec_node_data(__type, (__next)->__field.next, __field))
 746
 747 #define foreach_list_typed_reverse_safe(__type, __node, __field, __list)   \
 748    for (__type * __node =                                                  \
 749            exec_node_data(__type, (__list)->tail_sentinel.prev, __field),  \
 750                * __prev =                                                  \
 751            exec_node_data(__type, (__node)->__field.prev, __field);        \
 752         (__node)->__field.prev != NULL;                                    \
 753         __node = __prev, __prev =                                          \
 754            exec_node_data(__type, (__prev)->__field.prev, __field))
 755
 756 #endif /* LIST_CONTAINER_H */