LCOV - code coverage report
Current view: top level - src/libavutil - tree.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 77 77 100.0 %
Date: 2017-01-24 04:42:20 Functions: 5 5 100.0 %

          Line data    Source code
       1             : /*
       2             :  * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
       3             :  *
       4             :  * This file is part of FFmpeg.
       5             :  *
       6             :  * FFmpeg is free software; you can redistribute it and/or
       7             :  * modify it under the terms of the GNU Lesser General Public
       8             :  * License as published by the Free Software Foundation; either
       9             :  * version 2.1 of the License, or (at your option) any later version.
      10             :  *
      11             :  * FFmpeg is distributed in the hope that it will be useful,
      12             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      14             :  * Lesser General Public License for more details.
      15             :  *
      16             :  * You should have received a copy of the GNU Lesser General Public
      17             :  * License along with FFmpeg; if not, write to the Free Software
      18             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      19             :  */
      20             : 
      21             : #include "error.h"
      22             : #include "log.h"
      23             : #include "mem.h"
      24             : #include "tree.h"
      25             : 
      26             : typedef struct AVTreeNode {
      27             :     struct AVTreeNode *child[2];
      28             :     void *elem;
      29             :     int state;
      30             : } AVTreeNode;
      31             : 
      32             : const int av_tree_node_size = sizeof(AVTreeNode);
      33             : 
      34       13588 : struct AVTreeNode *av_tree_node_alloc(void)
      35             : {
      36       13588 :     return av_mallocz(sizeof(struct AVTreeNode));
      37             : }
      38             : 
      39      146667 : void *av_tree_find(const AVTreeNode *t, void *key,
      40             :                    int (*cmp)(const void *key, const void *b), void *next[2])
      41             : {
      42      146667 :     if (t) {
      43      131201 :         unsigned int v = cmp(key, t->elem);
      44      131201 :         if (v) {
      45      129498 :             if (next)
      46        9572 :                 next[v >> 31] = t->elem;
      47      129498 :             return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next);
      48             :         } else {
      49        1703 :             if (next) {
      50        1703 :                 av_tree_find(t->child[0], key, cmp, next);
      51        1703 :                 av_tree_find(t->child[1], key, cmp, next);
      52             :             }
      53        1703 :             return t->elem;
      54             :         }
      55             :     }
      56       15466 :     return NULL;
      57             : }
      58             : 
      59      272067 : void *av_tree_insert(AVTreeNode **tp, void *key,
      60             :                      int (*cmp)(const void *key, const void *b), AVTreeNode **next)
      61             : {
      62      272067 :     AVTreeNode *t = *tp;
      63      272067 :     if (t) {
      64      249051 :         unsigned int v = cmp(t->elem, key);
      65             :         void *ret;
      66      249051 :         if (!v) {
      67        1412 :             if (*next)
      68         510 :                 return t->elem;
      69        1255 :             else if (t->child[0] || t->child[1]) {
      70         353 :                 int i = !t->child[0];
      71             :                 void *next_elem[2];
      72         353 :                 av_tree_find(t->child[i], key, cmp, next_elem);
      73         353 :                 key = t->elem = next_elem[i];
      74         353 :                 v   = -i;
      75             :             } else {
      76         549 :                 *next = t;
      77         549 :                 *tp   = NULL;
      78         549 :                 return NULL;
      79             :             }
      80             :         }
      81      247992 :         ret = av_tree_insert(&t->child[v >> 31], key, cmp, next);
      82      247992 :         if (!ret) {
      83       33168 :             int i              = (v >> 31) ^ !!*next;
      84       33168 :             AVTreeNode **child = &t->child[i];
      85       33168 :             t->state += 2 * i - 1;
      86             : 
      87       33168 :             if (!(t->state & 1)) {
      88       11872 :                 if (t->state) {
      89             :                     /* The following code is equivalent to
      90             :                      * if ((*child)->state * 2 == -t->state)
      91             :                      *     rotate(child, i ^ 1);
      92             :                      * rotate(tp, i);
      93             :                      *
      94             :                      * with rotate():
      95             :                      * static void rotate(AVTreeNode **tp, int i)
      96             :                      * {
      97             :                      *     AVTreeNode *t= *tp;
      98             :                      *
      99             :                      *     *tp = t->child[i];
     100             :                      *     t->child[i] = t->child[i]->child[i ^ 1];
     101             :                      *     (*tp)->child[i ^ 1] = t;
     102             :                      *     i = 4 * t->state + 2 * (*tp)->state + 12;
     103             :                      *     t->state     = ((0x614586 >> i) & 3) - 1;
     104             :                      *     (*tp)->state = ((0x400EEA >> i) & 3) - 1 +
     105             :                      *                    ((*tp)->state >> 1);
     106             :                      * }
     107             :                      * but such a rotate function is both bigger and slower
     108             :                      */
     109        6392 :                     if ((*child)->state * 2 == -t->state) {
     110        2289 :                         *tp                    = (*child)->child[i ^ 1];
     111        2289 :                         (*child)->child[i ^ 1] = (*tp)->child[i];
     112        2289 :                         (*tp)->child[i]        = *child;
     113        2289 :                         *child                 = (*tp)->child[i ^ 1];
     114        2289 :                         (*tp)->child[i ^ 1]    = t;
     115             : 
     116        2289 :                         (*tp)->child[0]->state = -((*tp)->state > 0);
     117        2289 :                         (*tp)->child[1]->state = (*tp)->state < 0;
     118        2289 :                         (*tp)->state           = 0;
     119             :                     } else {
     120        4103 :                         *tp                 = *child;
     121        4103 :                         *child              = (*child)->child[i ^ 1];
     122        4103 :                         (*tp)->child[i ^ 1] = t;
     123        4103 :                         if ((*tp)->state)
     124        4059 :                             t->state = 0;
     125             :                         else
     126          44 :                             t->state >>= 1;
     127        4103 :                         (*tp)->state = -t->state;
     128             :                     }
     129             :                 }
     130             :             }
     131       33168 :             if (!(*tp)->state ^ !!*next)
     132       11850 :                 return key;
     133             :         }
     134      236142 :         return ret;
     135             :     } else {
     136       23016 :         *tp   = *next;
     137       23016 :         *next = NULL;
     138       23016 :         if (*tp) {
     139       13565 :             (*tp)->elem = key;
     140       13565 :             return NULL;
     141             :         } else
     142        9451 :             return key;
     143             :     }
     144             : }
     145             : 
     146       27734 : void av_tree_destroy(AVTreeNode *t)
     147             : {
     148       27734 :     if (t) {
     149       13016 :         av_tree_destroy(t->child[0]);
     150       13016 :         av_tree_destroy(t->child[1]);
     151       13016 :         av_free(t);
     152             :     }
     153       27734 : }
     154             : 
     155        9805 : void av_tree_enumerate(AVTreeNode *t, void *opaque,
     156             :                        int (*cmp)(void *opaque, void *elem),
     157             :                        int (*enu)(void *opaque, void *elem))
     158             : {
     159        9805 :     if (t) {
     160        4052 :         int v = cmp ? cmp(opaque, t->elem) : 0;
     161        4052 :         if (v >= 0)
     162        4052 :             av_tree_enumerate(t->child[0], opaque, cmp, enu);
     163        4052 :         if (v == 0)
     164        4052 :             enu(opaque, t->elem);
     165        4052 :         if (v <= 0)
     166        4052 :             av_tree_enumerate(t->child[1], opaque, cmp, enu);
     167             :     }
     168        9805 : }

Generated by: LCOV version 1.12