/src/hdf5/src/H5HFdtable.c

Source
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
 * Copyright by The HDF Group.                                               *
 * All rights reserved.                                                      *
 *                                                                           *
 * This file is part of HDF5.  The full HDF5 copyright notice, including     *
 * terms governing use, modification, and redistribution, is contained in    *
 * the LICENSE file, which can be found at the root of the source code       *
 * distribution tree, or in https://www.hdfgroup.org/licenses.               *
 * If you do not have access to either file, you may request a copy from     *
 * help@hdfgroup.org.                                                        *
 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

/*-------------------------------------------------------------------------
 *
 * Created:   H5HFdtable.c
 *
 * Purpose:   "Doubling table" routines for fractal heaps.
 *
 *-------------------------------------------------------------------------
 */

/****************/
/* Module Setup */
/****************/

#include "H5HFmodule.h" /* This source code file is part of the H5HF module */

/***********/
/* Headers */
/***********/
#include "H5private.h"   /* Generic Functions     */
#include "H5Eprivate.h"  /* Error handling        */
#include "H5HFpkg.h"     /* Fractal heaps     */
#include "H5MMprivate.h" /* Memory management     */
#include "H5VMprivate.h" /* Vectors and arrays      */

/****************/
/* Local Macros */
/****************/

/******************/
/* Local Typedefs */
/******************/

/********************/
/* Package Typedefs */
/********************/

/********************/
/* Local Prototypes */
/********************/

/*********************/
/* Package Variables */
/*********************/

/*****************************/
/* Library Private Variables */
/*****************************/

/*******************/
/* Local Variables */
/*******************/

/*-------------------------------------------------------------------------
 * Function:  H5HF__dtable_init
 *
 * Purpose: Initialize values for doubling table
 *
 * Return:  Non-negative on success/Negative on failure
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5HF__dtable_init(H5HF_dtable_t *dtable)
{
    hsize_t tmp_block_size;      /* Temporary block size */
    hsize_t acc_block_off;       /* Accumulated block offset */
    size_t  u;                   /* Local index variable */
    herr_t  ret_value = SUCCEED; /* Return value */

    FUNC_ENTER_PACKAGE

    /*
     * Check arguments.
     */
    assert(dtable);

    /* Compute/cache some values */
    dtable->start_bits           = H5VM_log2_of2((uint32_t)dtable->cparam.start_block_size);
    dtable->first_row_bits       = dtable->start_bits + H5VM_log2_of2(dtable->cparam.width);
    dtable->max_root_rows        = (dtable->cparam.max_index - dtable->first_row_bits) + 1;
    dtable->max_direct_bits      = H5VM_log2_of2((uint32_t)dtable->cparam.max_direct_size);
    dtable->max_direct_rows      = (dtable->max_direct_bits - dtable->start_bits) + 2;
    dtable->num_id_first_row     = dtable->cparam.start_block_size * dtable->cparam.width;
    dtable->max_dir_blk_off_size = H5HF_SIZEOF_OFFSET_LEN(dtable->cparam.max_direct_size);

    /* Build table of block sizes for each row */
    if (NULL == (dtable->row_block_size = (hsize_t *)H5MM_malloc(dtable->max_root_rows * sizeof(hsize_t))))
        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create doubling table block size table");
    if (NULL == (dtable->row_block_off = (hsize_t *)H5MM_malloc(dtable->max_root_rows * sizeof(hsize_t))))
        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create doubling table block offset table");
    if (NULL ==
        (dtable->row_tot_dblock_free = (hsize_t *)H5MM_malloc(dtable->max_root_rows * sizeof(hsize_t))))
        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL,
                    "can't create doubling table total direct block free space table");
    if (NULL == (dtable->row_max_dblock_free = (size_t *)H5MM_malloc(dtable->max_root_rows * sizeof(size_t))))
        HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL,
                    "can't create doubling table max. direct block free space table");
    tmp_block_size            = dtable->cparam.start_block_size;
    acc_block_off             = dtable->cparam.start_block_size * dtable->cparam.width;
    dtable->row_block_size[0] = dtable->cparam.start_block_size;
    dtable->row_block_off[0]  = 0;
    for (u = 1; u < dtable->max_root_rows; u++) {
        dtable->row_block_size[u] = tmp_block_size;
        dtable->row_block_off[u]  = acc_block_off;
        tmp_block_size *= 2;
        acc_block_off *= 2;
    } /* end for */

done:
    FUNC_LEAVE_NOAPI(ret_value)
} /* end H5HF__dtable_init() */

/*-------------------------------------------------------------------------
 * Function:  H5HF__dtable_lookup
 *
 * Purpose: Compute the row & col of an offset in a doubling-table
 *
 * Return:  Non-negative on success/Negative on failure
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5HF__dtable_lookup(const H5HF_dtable_t *dtable, hsize_t off, unsigned *row, unsigned *col)
{
    FUNC_ENTER_PACKAGE_NOERR

    /*
     * Check arguments.
     */
    assert(dtable);
    assert(row);
    assert(col);

    /* Check for offset in first row */
    if (off < dtable->num_id_first_row) {
        *row = 0;
        H5_CHECKED_ASSIGN(*col, unsigned, (off / dtable->cparam.start_block_size), hsize_t);
    } /* end if */
    else {
        unsigned high_bit = H5VM_log2_gen(off);       /* Determine the high bit in the offset */
        hsize_t  off_mask = ((hsize_t)1) << high_bit; /* Compute mask for determining column */

        *row = (high_bit - dtable->first_row_bits) + 1;
        H5_CHECKED_ASSIGN(*col, unsigned, ((off - off_mask) / dtable->row_block_size[*row]), hsize_t);
    } /* end else */

    FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5HF__dtable_lookup() */

/*-------------------------------------------------------------------------
 * Function:  H5HF__dtable_dest
 *
 * Purpose: Release information for doubling table
 *
 * Return:  Non-negative on success/Negative on failure
 *
 *-------------------------------------------------------------------------
 */
herr_t
H5HF__dtable_dest(H5HF_dtable_t *dtable)
{
    FUNC_ENTER_PACKAGE_NOERR

    /*
     * Check arguments.
     */
    assert(dtable);

    /* Free the block size lookup table for the doubling table */
    H5MM_xfree(dtable->row_block_size);

    /* Free the block offset lookup table for the doubling table */
    H5MM_xfree(dtable->row_block_off);

    /* Free the total direct block free space lookup table for the doubling table */
    H5MM_xfree(dtable->row_tot_dblock_free);

    /* Free the max. direct block free space lookup table for the doubling table */
    H5MM_xfree(dtable->row_max_dblock_free);

    FUNC_LEAVE_NOAPI(SUCCEED)
} /* end H5HF__dtable_dest() */

/*-------------------------------------------------------------------------
 * Function:  H5HF__dtable_size_to_row
 *
 * Purpose: Compute row that can hold block of a certain size
 *
 * Return:  Non-negative on success (can't fail)
 *
 *-------------------------------------------------------------------------
 */
unsigned
H5HF__dtable_size_to_row(const H5HF_dtable_t *dtable, size_t block_size)
{
    unsigned row = 0; /* Row where block will fit */

    FUNC_ENTER_PACKAGE_NOERR

    /*
     * Check arguments.
     */
    assert(dtable);

    if (block_size == dtable->cparam.start_block_size)
        row = 0;
    else
        row =
            (H5VM_log2_of2((uint32_t)block_size) - H5VM_log2_of2((uint32_t)dtable->cparam.start_block_size)) +
            1;

    FUNC_LEAVE_NOAPI(row)
} /* end H5HF__dtable_size_to_row() */

/*-------------------------------------------------------------------------
 * Function:  H5HF__dtable_size_to_rows
 *
 * Purpose: Compute # of rows of indirect block of a given size
 *
 * Return:  Non-negative on success (can't fail)
 *
 *-------------------------------------------------------------------------
 */
unsigned
H5HF__dtable_size_to_rows(const H5HF_dtable_t *dtable, hsize_t size)
{
    unsigned rows = 0; /* # of rows required for indirect block */

    FUNC_ENTER_PACKAGE_NOERR

    /*
     * Check arguments.
     */
    assert(dtable);

    rows = (H5VM_log2_gen(size) - dtable->first_row_bits) + 1;

    FUNC_LEAVE_NOAPI(rows)
} /* end H5HF__dtable_size_to_rows() */

/*-------------------------------------------------------------------------
 * Function:  H5HF__dtable_span_size
 *
 * Purpose: Compute the size covered by a span of entries
 *
 * Return:  Non-zero span size on success/zero on failure
 *
 *-------------------------------------------------------------------------
 */
hsize_t
H5HF__dtable_span_size(const H5HF_dtable_t *dtable, unsigned start_row, unsigned start_col,
                       unsigned num_entries)
{
    unsigned start_entry;       /* Entry for first block covered */
    unsigned end_row;           /* Row for last block covered */
    unsigned end_col;           /* Column for last block covered */
    unsigned end_entry;         /* Entry for last block covered */
    hsize_t  acc_span_size = 0; /* Accumulated span size */

    FUNC_ENTER_PACKAGE_NOERR

    /*
     * Check arguments.
     */
    assert(dtable);
    assert(num_entries > 0);

    /* Compute starting entry */
    start_entry = (start_row * dtable->cparam.width) + start_col;

    /* Compute ending entry, column & row */
    end_entry = (start_entry + num_entries) - 1;
    end_row   = end_entry / dtable->cparam.width;
    end_col   = end_entry % dtable->cparam.width;

    /* Initialize accumulated span size */
    acc_span_size = 0;

    /* Compute span size covered */

    /* Check for multi-row span */
    if (start_row != end_row) {
        /* Accommodate partial starting row */
        if (start_col > 0) {
            acc_span_size = dtable->row_block_size[start_row] * (dtable->cparam.width - start_col);
            start_row++;
        } /* end if */

        /* Accumulate full rows */
        while (start_row < end_row) {
            acc_span_size += dtable->row_block_size[start_row] * dtable->cparam.width;
            start_row++;
        } /* end while */

        /* Accommodate partial ending row */
        acc_span_size += dtable->row_block_size[start_row] * (end_col + 1);
    } /* end if */
    else {
        /* Span is in same row */
        acc_span_size = dtable->row_block_size[start_row] * ((end_col - start_col) + 1);
    } /* end else */

    FUNC_LEAVE_NOAPI(acc_span_size)
} /* end H5HF__dtable_span_size() */

Coverage Report

Created: 2026-09-14 06:17

Line	Count	Source
1		/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2		* Copyright by The HDF Group. *
3		* All rights reserved. *
4		* *
5		* This file is part of HDF5. The full HDF5 copyright notice, including *
6		* terms governing use, modification, and redistribution, is contained in *
7		* the LICENSE file, which can be found at the root of the source code *
8		* distribution tree, or in https://www.hdfgroup.org/licenses. *
9		* If you do not have access to either file, you may request a copy from *
10		* help@hdfgroup.org. *
11		* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
12
13		/*-------------------------------------------------------------------------
14		*
15		* Created: H5HFdtable.c
16		*
17		* Purpose: "Doubling table" routines for fractal heaps.
18		*
19		*-------------------------------------------------------------------------
20		*/
21
22		/****************/
23		/* Module Setup */
24		/****************/
25
26		#include "H5HFmodule.h" /* This source code file is part of the H5HF module */
27
28		/***********/
29		/* Headers */
30		/***********/
31		#include "H5private.h" /* Generic Functions */
32		#include "H5Eprivate.h" /* Error handling */
33		#include "H5HFpkg.h" /* Fractal heaps */
34		#include "H5MMprivate.h" /* Memory management */
35		#include "H5VMprivate.h" /* Vectors and arrays */
36
37		/****************/
38		/* Local Macros */
39		/****************/
40
41		/******************/
42		/* Local Typedefs */
43		/******************/
44
45		/********************/
46		/* Package Typedefs */
47		/********************/
48
49		/********************/
50		/* Local Prototypes */
51		/********************/
52
53		/*********************/
54		/* Package Variables */
55		/*********************/
56
57		/*****************************/
58		/* Library Private Variables */
59		/*****************************/
60
61		/*******************/
62		/* Local Variables */
63		/*******************/
64
65		/*-------------------------------------------------------------------------
66		* Function: H5HF__dtable_init
67		*
68		* Purpose: Initialize values for doubling table
69		*
70		* Return: Non-negative on success/Negative on failure
71		*
72		*-------------------------------------------------------------------------
73		*/
74		herr_t
75		H5HF__dtable_init(H5HF_dtable_t *dtable)
76	0	{
77	0	hsize_t tmp_block_size; /* Temporary block size */
78	0	hsize_t acc_block_off; /* Accumulated block offset */
79	0	size_t u; /* Local index variable */
80	0	herr_t ret_value = SUCCEED; /* Return value */
81
82	0	FUNC_ENTER_PACKAGE
83
84		/*
85		* Check arguments.
86		*/
87	0	assert(dtable);
88
89		/* Compute/cache some values */
90	0	dtable->start_bits = H5VM_log2_of2((uint32_t)dtable->cparam.start_block_size);
91	0	dtable->first_row_bits = dtable->start_bits + H5VM_log2_of2(dtable->cparam.width);
92	0	dtable->max_root_rows = (dtable->cparam.max_index - dtable->first_row_bits) + 1;
93	0	dtable->max_direct_bits = H5VM_log2_of2((uint32_t)dtable->cparam.max_direct_size);
94	0	dtable->max_direct_rows = (dtable->max_direct_bits - dtable->start_bits) + 2;
95	0	dtable->num_id_first_row = dtable->cparam.start_block_size * dtable->cparam.width;
96	0	dtable->max_dir_blk_off_size = H5HF_SIZEOF_OFFSET_LEN(dtable->cparam.max_direct_size);
97
98		/* Build table of block sizes for each row */
99	0	if (NULL == (dtable->row_block_size = (hsize_t )H5MM_malloc(dtable->max_root_rows sizeof(hsize_t))))
100	0	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create doubling table block size table");
101	0	if (NULL == (dtable->row_block_off = (hsize_t )H5MM_malloc(dtable->max_root_rows sizeof(hsize_t))))
102	0	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL, "can't create doubling table block offset table");
103	0	if (NULL ==
104	0	(dtable->row_tot_dblock_free = (hsize_t )H5MM_malloc(dtable->max_root_rows sizeof(hsize_t))))
105	0	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL,
106	0	"can't create doubling table total direct block free space table");
107	0	if (NULL == (dtable->row_max_dblock_free = (size_t )H5MM_malloc(dtable->max_root_rows sizeof(size_t))))
108	0	HGOTO_ERROR(H5E_RESOURCE, H5E_NOSPACE, FAIL,
109	0	"can't create doubling table max. direct block free space table");
110	0	tmp_block_size = dtable->cparam.start_block_size;
111	0	acc_block_off = dtable->cparam.start_block_size * dtable->cparam.width;
112	0	dtable->row_block_size[0] = dtable->cparam.start_block_size;
113	0	dtable->row_block_off[0] = 0;
114	0	for (u = 1; u < dtable->max_root_rows; u++) {
115	0	dtable->row_block_size[u] = tmp_block_size;
116	0	dtable->row_block_off[u] = acc_block_off;
117	0	tmp_block_size *= 2;
118	0	acc_block_off *= 2;
119	0	} /* end for */
120
121	0	done:
122	0	FUNC_LEAVE_NOAPI(ret_value)
123	0	} /* end H5HF__dtable_init() */
124
125		/*-------------------------------------------------------------------------
126		* Function: H5HF__dtable_lookup
127		*
128		* Purpose: Compute the row & col of an offset in a doubling-table
129		*
130		* Return: Non-negative on success/Negative on failure
131		*
132		*-------------------------------------------------------------------------
133		*/
134		herr_t
135		H5HF__dtable_lookup(const H5HF_dtable_t dtable, hsize_t off, unsigned row, unsigned *col)
136	0	{
137	0	FUNC_ENTER_PACKAGE_NOERR
138
139		/*
140		* Check arguments.
141		*/
142	0	assert(dtable);
143	0	assert(row);
144	0	assert(col);
145
146		/* Check for offset in first row */
147	0	if (off < dtable->num_id_first_row) {
148	0	*row = 0;
149	0	H5_CHECKED_ASSIGN(*col, unsigned, (off / dtable->cparam.start_block_size), hsize_t);
150	0	} /* end if */
151	0	else {
152	0	unsigned high_bit = H5VM_log2_gen(off); /* Determine the high bit in the offset */
153	0	hsize_t off_mask = ((hsize_t)1) << high_bit; /* Compute mask for determining column */
154
155	0	*row = (high_bit - dtable->first_row_bits) + 1;
156	0	H5_CHECKED_ASSIGN(col, unsigned, ((off - off_mask) / dtable->row_block_size[row]), hsize_t);
157	0	} /* end else */
158
159	0	FUNC_LEAVE_NOAPI(SUCCEED)
160	0	} /* end H5HF__dtable_lookup() */
161
162		/*-------------------------------------------------------------------------
163		* Function: H5HF__dtable_dest
164		*
165		* Purpose: Release information for doubling table
166		*
167		* Return: Non-negative on success/Negative on failure
168		*
169		*-------------------------------------------------------------------------
170		*/
171		herr_t
172		H5HF__dtable_dest(H5HF_dtable_t *dtable)
173	0	{
174	0	FUNC_ENTER_PACKAGE_NOERR
175
176		/*
177		* Check arguments.
178		*/
179	0	assert(dtable);
180
181		/* Free the block size lookup table for the doubling table */
182	0	H5MM_xfree(dtable->row_block_size);
183
184		/* Free the block offset lookup table for the doubling table */
185	0	H5MM_xfree(dtable->row_block_off);
186
187		/* Free the total direct block free space lookup table for the doubling table */
188	0	H5MM_xfree(dtable->row_tot_dblock_free);
189
190		/* Free the max. direct block free space lookup table for the doubling table */
191	0	H5MM_xfree(dtable->row_max_dblock_free);
192
193	0	FUNC_LEAVE_NOAPI(SUCCEED)
194	0	} /* end H5HF__dtable_dest() */
195
196		/*-------------------------------------------------------------------------
197		* Function: H5HF__dtable_size_to_row
198		*
199		* Purpose: Compute row that can hold block of a certain size
200		*
201		* Return: Non-negative on success (can't fail)
202		*
203		*-------------------------------------------------------------------------
204		*/
205		unsigned
206		H5HF__dtable_size_to_row(const H5HF_dtable_t *dtable, size_t block_size)
207	0	{
208	0	unsigned row = 0; /* Row where block will fit */
209
210	0	FUNC_ENTER_PACKAGE_NOERR
211
212		/*
213		* Check arguments.
214		*/
215	0	assert(dtable);
216
217	0	if (block_size == dtable->cparam.start_block_size)
218	0	row = 0;
219	0	else
220	0	row =
221	0	(H5VM_log2_of2((uint32_t)block_size) - H5VM_log2_of2((uint32_t)dtable->cparam.start_block_size)) +
222	0	1;
223
224	0	FUNC_LEAVE_NOAPI(row)
225	0	} /* end H5HF__dtable_size_to_row() */
226
227		/*-------------------------------------------------------------------------
228		* Function: H5HF__dtable_size_to_rows
229		*
230		* Purpose: Compute # of rows of indirect block of a given size
231		*
232		* Return: Non-negative on success (can't fail)
233		*
234		*-------------------------------------------------------------------------
235		*/
236		unsigned
237		H5HF__dtable_size_to_rows(const H5HF_dtable_t *dtable, hsize_t size)
238	0	{
239	0	unsigned rows = 0; /* # of rows required for indirect block */
240
241	0	FUNC_ENTER_PACKAGE_NOERR
242
243		/*
244		* Check arguments.
245		*/
246	0	assert(dtable);
247
248	0	rows = (H5VM_log2_gen(size) - dtable->first_row_bits) + 1;
249
250	0	FUNC_LEAVE_NOAPI(rows)
251	0	} /* end H5HF__dtable_size_to_rows() */
252
253		/*-------------------------------------------------------------------------
254		* Function: H5HF__dtable_span_size
255		*
256		* Purpose: Compute the size covered by a span of entries
257		*
258		* Return: Non-zero span size on success/zero on failure
259		*
260		*-------------------------------------------------------------------------
261		*/
262		hsize_t
263		H5HF__dtable_span_size(const H5HF_dtable_t *dtable, unsigned start_row, unsigned start_col,
264		unsigned num_entries)
265	0	{
266	0	unsigned start_entry; /* Entry for first block covered */
267	0	unsigned end_row; /* Row for last block covered */
268	0	unsigned end_col; /* Column for last block covered */
269	0	unsigned end_entry; /* Entry for last block covered */
270	0	hsize_t acc_span_size = 0; /* Accumulated span size */
271
272	0	FUNC_ENTER_PACKAGE_NOERR
273
274		/*
275		* Check arguments.
276		*/
277	0	assert(dtable);
278	0	assert(num_entries > 0);
279
280		/* Compute starting entry */
281	0	start_entry = (start_row * dtable->cparam.width) + start_col;
282
283		/* Compute ending entry, column & row */
284	0	end_entry = (start_entry + num_entries) - 1;
285	0	end_row = end_entry / dtable->cparam.width;
286	0	end_col = end_entry % dtable->cparam.width;
287
288		/* Initialize accumulated span size */
289	0	acc_span_size = 0;
290
291		/* Compute span size covered */
292
293		/* Check for multi-row span */
294	0	if (start_row != end_row) {
295		/* Accommodate partial starting row */
296	0	if (start_col > 0) {
297	0	acc_span_size = dtable->row_block_size[start_row] * (dtable->cparam.width - start_col);
298	0	start_row++;
299	0	} /* end if */
300
301		/* Accumulate full rows */
302	0	while (start_row < end_row) {
303	0	acc_span_size += dtable->row_block_size[start_row] * dtable->cparam.width;
304	0	start_row++;
305	0	} /* end while */
306
307		/* Accommodate partial ending row */
308	0	acc_span_size += dtable->row_block_size[start_row] * (end_col + 1);
309	0	} /* end if */
310	0	else {
311		/* Span is in same row */
312	0	acc_span_size = dtable->row_block_size[start_row] * ((end_col - start_col) + 1);
313	0	} /* end else */
314
315	0	FUNC_LEAVE_NOAPI(acc_span_size)
316	0	} /* end H5HF__dtable_span_size() */