Zabbix

/*

** Zabbix

** Copyright (C) 2001-2023 Zabbix SIA

**

** This program is free software; you can redistribute it and/or modify

** it under the terms of the GNU General Public License as published by

** the Free Software Foundation; either version 2 of the License, or

** (at your option) any later version.

**

** This program is distributed in the hope that it will be useful,

** but WITHOUT ANY WARRANTY; without even the implied warranty of

** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

** GNU General Public License for more details.

**

** You should have received a copy of the GNU General Public License

** along with this program; if not, write to the Free Software

** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

**/

​

#include "zbxalgo.h"

​

#include "zbxcommon.h"

#include "log.h"

​

static void swap(zbx_binary_heap_t *heap, int index_1, int index_2);

​

static void __binary_heap_ensure_free_space(zbx_binary_heap_t *heap);

​

static int  __binary_heap_bubble_up(zbx_binary_heap_t *heap, int index);

static int  __binary_heap_bubble_down(zbx_binary_heap_t *heap, int index);

​

#define ARRAY_GROWTH_FACTOR 3/2

​

#define HAS_DIRECT_OPTION(heap) (0 != (heap->options & ZBX_BINARY_HEAP_OPTION_DIRECT))

​

/* helper functions */

​

static void swap(zbx_binary_heap_t *heap, int index_1, int index_2)

{

    zbx_binary_heap_elem_t  tmp;

​

    tmp = heap->elems[index_1];

    heap->elems[index_1] = heap->elems[index_2];

    heap->elems[index_2] = tmp;

​

    if (HAS_DIRECT_OPTION(heap))

    {

        zbx_hashmap_set(heap->key_index, heap->elems[index_1].key, index_1);

        zbx_hashmap_set(heap->key_index, heap->elems[index_2].key, index_2);

    }

}

​

/* private binary heap functions */

​

static void __binary_heap_ensure_free_space(zbx_binary_heap_t *heap)

{

    int tmp_elems_alloc = heap->elems_alloc;

​

    /* In order to prevent memory corruption heap->elems_alloc is set only after successful allocation. */

    /* Otherwise, in case of shared memory, other processes might read or write past the actually       */

    /* allocated memory.                                                                                */

​

    if (NULL == heap->elems)

    {

        heap->elems_num = 0;

        tmp_elems_alloc = 32;

    }

    else if (heap->elems_num == heap->elems_alloc)

        tmp_elems_alloc = MAX(heap->elems_alloc + 1, heap->elems_alloc * ARRAY_GROWTH_FACTOR);

​

    if (heap->elems_alloc != tmp_elems_alloc)

    {

        heap->elems = (zbx_binary_heap_elem_t *)heap->mem_realloc_func(heap->elems, tmp_elems_alloc * sizeof(zbx_binary_heap_elem_t));

​

        if (NULL == heap->elems)

        {

            THIS_SHOULD_NEVER_HAPPEN;

            exit(EXIT_FAILURE);

        }

​

        heap->elems_alloc = tmp_elems_alloc;

    }

}

​

static int  __binary_heap_bubble_up(zbx_binary_heap_t *heap, int index)

{

    while (0 != index)

    {

        if (heap->compare_func(&heap->elems[(index - 1) / 2], &heap->elems[index]) <= 0)

            break;

​