LCOV - code coverage report
Current view: top level - src/libavutil/tests - tree.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 34 52 65.4 %
Date: 2017-01-22 02:20:28 Functions: 3 4 75.0 %

          Line data    Source code
       1             : /*
       2             :  * This file is part of FFmpeg.
       3             :  *
       4             :  * FFmpeg is free software; you can redistribute it and/or
       5             :  * modify it under the terms of the GNU Lesser General Public
       6             :  * License as published by the Free Software Foundation; either
       7             :  * version 2.1 of the License, or (at your option) any later version.
       8             :  *
       9             :  * FFmpeg is distributed in the hope that it will be useful,
      10             :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      11             :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      12             :  * Lesser General Public License for more details.
      13             :  *
      14             :  * You should have received a copy of the GNU Lesser General Public
      15             :  * License along with FFmpeg; if not, write to the Free Software
      16             :  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
      17             :  */
      18             : 
      19             : #include "libavutil/tree.c"
      20             : 
      21             : #include <stdint.h>
      22             : 
      23             : #include "libavutil/common.h"
      24             : #include "libavutil/lfg.h"
      25             : #include "libavutil/log.h"
      26             : 
      27    92932756 : static int check(AVTreeNode *t)
      28             : {
      29    92932756 :     if (t) {
      30    46461378 :         int left  = check(t->child[0]);
      31    46461378 :         int right = check(t->child[1]);
      32             : 
      33    46461378 :         if (left > 999 || right > 999)
      34           0 :             return 1000;
      35    46461378 :         if (right - left != t->state)
      36           0 :             return 1000;
      37    46461378 :         if (t->state > 1 || t->state < -1)
      38           0 :             return 1000;
      39    46461378 :         return FFMAX(left, right) + 1;
      40             :     }
      41    46471378 :     return 0;
      42             : }
      43             : 
      44           0 : static void print(AVTreeNode *t, int depth)
      45             : {
      46             :     int i;
      47           0 :     for (i = 0; i < depth * 4; i++)
      48           0 :         av_log(NULL, AV_LOG_ERROR, " ");
      49           0 :     if (t) {
      50           0 :         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
      51           0 :         print(t->child[0], depth + 1);
      52           0 :         print(t->child[1], depth + 1);
      53             :     } else
      54           0 :         av_log(NULL, AV_LOG_ERROR, "NULL\n");
      55           0 : }
      56             : 
      57      360426 : static int cmp(const void *a, const void *b)
      58             : {
      59      360426 :     return (const uint8_t *) a - (const uint8_t *) b;
      60             : }
      61             : 
      62           1 : int main(int argc, char **argv)
      63             : {
      64             :     int i;
      65             :     void *k;
      66           1 :     AVTreeNode *root = NULL, *node = NULL;
      67             :     AVLFG prng;
      68           1 :     int log_level = argc <= 1 ? AV_LOG_INFO : atoi(argv[1]);
      69             : 
      70           1 :     av_log_set_level(log_level);
      71             : 
      72           1 :     av_lfg_init(&prng, 1);
      73             : 
      74       10001 :     for (i = 0; i < 10000; i++) {
      75       10000 :         intptr_t j = av_lfg_get(&prng) % 86294;
      76             : 
      77       10000 :         if (check(root) > 999) {
      78           0 :             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
      79           0 :             print(root, 0);
      80           0 :             return 1;
      81             :         }
      82       10000 :         av_log(NULL, AV_LOG_DEBUG, "inserting %4d\n", (int)j);
      83             : 
      84       10000 :         if (!node)
      85        9513 :             node = av_tree_node_alloc();
      86       10000 :         if (!node) {
      87           0 :             av_log(NULL, AV_LOG_ERROR, "Memory allocation failure.\n");
      88           0 :             return 1;
      89             :         }
      90       10000 :         av_tree_insert(&root, (void *)(j + 1), cmp, &node);
      91             : 
      92       10000 :         j = av_lfg_get(&prng) % 86294;
      93             :         {
      94       10000 :             AVTreeNode *node2 = NULL;
      95       10000 :             av_log(NULL, AV_LOG_DEBUG, "removing %4d\n", (int)j);
      96       10000 :             av_tree_insert(&root, (void *)(j + 1), cmp, &node2);
      97       10000 :             k = av_tree_find(root, (void *)(j + 1), cmp, NULL);
      98       10000 :             if (k)
      99           0 :                 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
     100       10000 :             av_free(node2);
     101             :         }
     102             :     }
     103           1 :     av_free(node);
     104             : 
     105           1 :     av_tree_destroy(root);
     106             : 
     107           1 :     return 0;
     108             : }

Generated by: LCOV version 1.12