/src/igraph/src/graph/caching.c

Source
/*
   igraph library.
   Copyright (C) 2022  The igraph development team <igraph@igraph.org>

   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, see <https://www.gnu.org/licenses/>.
*/

#include "igraph_interface.h"

#include "graph/caching.h"
#include "internal/hacks.h" /* IGRAPH_STATIC_ASSERT */

#include <assert.h>
#include <string.h> /* memset */

/****** Strictly internal functions ******/

/**
 * \brief Initializes a property cache, ensuring that all values are unknown.
 */
igraph_error_t igraph_i_property_cache_init(igraph_i_property_cache_t *cache) {
    IGRAPH_STATIC_ASSERT(IGRAPH_PROP_I_SIZE <= 32);

    memset(cache->value, 0, sizeof(cache->value));
    cache->known = 0;
    return IGRAPH_SUCCESS;
}

/**
 * \brief Copies a property cache.
 */
igraph_error_t igraph_i_property_cache_copy(
        igraph_i_property_cache_t *cache,
        const igraph_i_property_cache_t *other_cache) {
    *cache = *other_cache;
    return IGRAPH_SUCCESS;
}

/**
 * \brief Destroys a property cache.
 */
void igraph_i_property_cache_destroy(igraph_i_property_cache_t *cache) {
    IGRAPH_UNUSED(cache);
    /* Nothing to do */
}

/***** Developer functions, exposed *****/

/**
 * \brief Returns the value of a cached boolean property.
 *
 * This function provides valid results only when the property is already
 * cached. Use \ref igraph_i_property_cache_has() to retrieve whether the
 * property is cached.
 *
 * \param graph  the graph whose cache is to be checked
 * \param prop   the property to retrieve from the cache
 * \return the cached value of the property if the value is in the cache, or
 *         an undefined value otherwise
 */
igraph_bool_t igraph_i_property_cache_get_bool(const igraph_t *graph, igraph_cached_property_t prop) {
    IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
    assert(graph->cache != NULL);
    return graph->cache->value[prop];
}

/**
 * \brief Returns whether the cache contains a value for the given cached property.
 *
 * \param graph  the graph whose cache is to be checked
 * \param prop   the property to check in the cache
 */
igraph_bool_t igraph_i_property_cache_has(const igraph_t *graph, igraph_cached_property_t prop) {
    IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
    assert(graph->cache != NULL);
    return graph->cache->known & (1 << prop);
}

/**
 * \brief Stores a property value in the cache.
 *
 * \param graph  the graph whose cache is to be modified
 * \param prop   the property to update in the cache
 * \param value  the value of the property to add to the cache
 */
void igraph_i_property_cache_set_bool(const igraph_t *graph, igraph_cached_property_t prop, igraph_bool_t value) {
    IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
    assert(graph->cache != NULL);
    /* Even though graph is const, updating the cache is not considered modification.
     * Functions that merely compute graph properties, and thus leave the graph structure
     * intact, will often update the cache. */
    graph->cache->value[prop] = value;
    graph->cache->known |= (1 << prop);
}

/**
 * \brief Stores a property value in the cache.
 *
 * This function asserts that if the value of \p prop was already known,
 * then \p value is consistent with the previously stored value.
 * If this is not the case, a fatal error is triggered, with the reasoning
 * that the cache must have become invalid/inconsistent due to a bug.
 *
 * Therefore, this function cannot be used to change an already stored
 * property to a different value. If this is your intention, invalidate
 * the cache explicitly first.
 *
 * \param graph  the graph whose cache is to be modified
 * \param prop   the property to update in the cache
 * \param value  the value of the property to add to the cache
 */
void igraph_i_property_cache_set_bool_checked(const igraph_t *graph, igraph_cached_property_t prop, igraph_bool_t value) {
    IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
    assert(graph->cache != NULL);
    /* Even though graph is const, updating the cache is not considered modification.
     * Functions that merely compute graph properties, and thus leave the graph structure
     * intact, will often update the cache. */
    if (graph->cache->known & (1 << prop)) {
        IGRAPH_ASSERT(graph->cache->value[prop] == value);
    } else {
        igraph_i_property_cache_set_bool(graph, prop, value);
    }
}

/**
 * \brief Invalidates the cached value of a property in a graph.
 *
 * \param graph  the graph whose cache is to be modified
 * \param prop   the property to invalidate in the cache
 */
void igraph_i_property_cache_invalidate(const igraph_t *graph, igraph_cached_property_t prop) {
    IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
    assert(graph->cache != NULL);
    graph->cache->known &= ~(1 << prop);
}

/**
 * \brief Invalidates all cached properties of the graph.
 *
 * This function is typically called after the graph is modified.
 *
 * \param graph  the graph whose cache is to be invalidated
 */
void igraph_i_property_cache_invalidate_all(const igraph_t *graph) {
    assert(graph->cache != NULL);
    graph->cache->known = 0;
}

/**
 * \brief Invalidates all but a few cached properties of the graph, subject to specific conditions.
 *
 * This function is typically called after the graph is modified if we know that
 * the modification does not affect certain cached properties in certain cases.
 * For instance, adding more vertices does not make a connected graph disconnected,
 * so we can keep the cached properties related to graph connectivity if they
 * were already cached as true, but we need to invalidate them if they were
 * cached as false.
 *
 * </para><para>
 * Use <code>1 << IGRAPH_PROP_SOMETHING</code> to encode an individual property
 * in the bits of the bitmask used in the arguments of this function.
 *
 * \param graph       the graph whose cache is to be invalidated
 * \param keep_always bitmask where the i-th bit corresponds to cached property \em i
 *        and it should be set to 1 if the property should be \em kept ,
 *        irrespectively of its current cached value.
 */
void igraph_i_property_cache_invalidate_conditionally(
    const igraph_t *graph, uint32_t keep_always, uint32_t keep_when_false,
    uint32_t keep_when_true
) {
    uint32_t invalidate = ~keep_always;
    uint32_t mask;
    uint32_t maybe_keep;
    igraph_bool_t cached_value;

    assert(graph->cache != NULL);

    /* The bits of maybe_keep are set to 1 for those properties that are:
     *
     * - currently cached
     * - should _probably_ be invalidated
     * - _but_ the current cached value of the property may change the decision
     */
    maybe_keep = graph->cache->known & invalidate & (keep_when_false | keep_when_true);

    if (maybe_keep) {
        for (igraph_cached_property_t prop = (igraph_cached_property_t ) 0; prop < IGRAPH_PROP_I_SIZE; ++prop) {
            mask = 1 << prop;
            if (maybe_keep & mask) {
                /* if we get here, we know that the property is cached; we have
                 * masked maybe_keep with graph->cache->known */
                cached_value = igraph_i_property_cache_get_bool(graph, prop);
                if (
                    ((keep_when_false & mask) && !cached_value) ||
                    ((keep_when_true & mask) && cached_value)
                ) {
                    invalidate &= ~mask;
                }
            }
        }
    }

    graph->cache->known &= ~invalidate;
}

Coverage Report

Created: 2026-04-12 06:25

Line	Count	Source
1		/*
2		igraph library.
3		Copyright (C) 2022 The igraph development team <igraph@igraph.org>
4
5		This program is free software; you can redistribute it and/or modify
6		it under the terms of the GNU General Public License as published by
7		the Free Software Foundation; either version 2 of the License, or
8		(at your option) any later version.
9
10		This program is distributed in the hope that it will be useful,
11		but WITHOUT ANY WARRANTY; without even the implied warranty of
12		MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13		GNU General Public License for more details.
14
15		You should have received a copy of the GNU General Public License
16		along with this program. If not, see <https://www.gnu.org/licenses/>.
17		*/
18
19		#include "igraph_interface.h"
20
21		#include "graph/caching.h"
22		#include "internal/hacks.h" /* IGRAPH_STATIC_ASSERT */
23
24		#include <assert.h>
25		#include <string.h> /* memset */
26
27		/**** Strictly internal functions ****/
28
29		/**
30		* \brief Initializes a property cache, ensuring that all values are unknown.
31		*/
32	2.52k	igraph_error_t igraph_i_property_cache_init(igraph_i_property_cache_t *cache) {
33	2.52k	IGRAPH_STATIC_ASSERT(IGRAPH_PROP_I_SIZE <= 32);
34
35	2.52k	memset(cache->value, 0, sizeof(cache->value));
36	2.52k	cache->known = 0;
37	2.52k	return IGRAPH_SUCCESS;
38	2.52k	}
39
40		/**
41		* \brief Copies a property cache.
42		*/
43		igraph_error_t igraph_i_property_cache_copy(
44		igraph_i_property_cache_t *cache,
45	0	const igraph_i_property_cache_t *other_cache) {
46	0	cache = other_cache;
47	0	return IGRAPH_SUCCESS;
48	0	}
49
50		/**
51		* \brief Destroys a property cache.
52		*/
53	2.52k	void igraph_i_property_cache_destroy(igraph_i_property_cache_t *cache) {
54	2.52k	IGRAPH_UNUSED(cache);
55		/* Nothing to do */
56	2.52k	}
57
58		/*** Developer functions, exposed ***/
59
60		/**
61		* \brief Returns the value of a cached boolean property.
62		*
63		* This function provides valid results only when the property is already
64		* cached. Use \ref igraph_i_property_cache_has() to retrieve whether the
65		* property is cached.
66		*
67		* \param graph the graph whose cache is to be checked
68		* \param prop the property to retrieve from the cache
69		* \return the cached value of the property if the value is in the cache, or
70		* an undefined value otherwise
71		*/
72	1.65k	igraph_bool_t igraph_i_property_cache_get_bool(const igraph_t *graph, igraph_cached_property_t prop) {
73	1.65k	IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
74	1.65k	assert(graph->cache != NULL);
75	1.65k	return graph->cache->value[prop];
76	1.65k	}
77
78		/**
79		* \brief Returns whether the cache contains a value for the given cached property.
80		*
81		* \param graph the graph whose cache is to be checked
82		* \param prop the property to check in the cache
83		*/
84	3.30k	igraph_bool_t igraph_i_property_cache_has(const igraph_t *graph, igraph_cached_property_t prop) {
85	3.30k	IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
86	3.30k	assert(graph->cache != NULL);
87	3.30k	return graph->cache->known & (1 << prop);
88	3.30k	}
89
90		/**
91		* \brief Stores a property value in the cache.
92		*
93		* \param graph the graph whose cache is to be modified
94		* \param prop the property to update in the cache
95		* \param value the value of the property to add to the cache
96		*/
97	1.65k	void igraph_i_property_cache_set_bool(const igraph_t *graph, igraph_cached_property_t prop, igraph_bool_t value) {
98	1.65k	IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
99	1.65k	assert(graph->cache != NULL);
100		/* Even though graph is const, updating the cache is not considered modification.
101		* Functions that merely compute graph properties, and thus leave the graph structure
102		* intact, will often update the cache. */
103	1.65k	graph->cache->value[prop] = value;
104	1.65k	graph->cache->known \|= (1 << prop);
105	1.65k	}
106
107		/**
108		* \brief Stores a property value in the cache.
109		*
110		* This function asserts that if the value of \p prop was already known,
111		* then \p value is consistent with the previously stored value.
112		* If this is not the case, a fatal error is triggered, with the reasoning
113		* that the cache must have become invalid/inconsistent due to a bug.
114		*
115		* Therefore, this function cannot be used to change an already stored
116		* property to a different value. If this is your intention, invalidate
117		* the cache explicitly first.
118		*
119		* \param graph the graph whose cache is to be modified
120		* \param prop the property to update in the cache
121		* \param value the value of the property to add to the cache
122		*/
123	1.65k	void igraph_i_property_cache_set_bool_checked(const igraph_t *graph, igraph_cached_property_t prop, igraph_bool_t value) {
124	1.65k	IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
125	1.65k	assert(graph->cache != NULL);
126		/* Even though graph is const, updating the cache is not considered modification.
127		* Functions that merely compute graph properties, and thus leave the graph structure
128		* intact, will often update the cache. */
129	1.65k	if (graph->cache->known & (1 << prop)) {
130	0	IGRAPH_ASSERT(graph->cache->value[prop] == value);
131	1.65k	} else {
132	1.65k	igraph_i_property_cache_set_bool(graph, prop, value);
133	1.65k	}
134	1.65k	}
135
136		/**
137		* \brief Invalidates the cached value of a property in a graph.
138		*
139		* \param graph the graph whose cache is to be modified
140		* \param prop the property to invalidate in the cache
141		*/
142	0	void igraph_i_property_cache_invalidate(const igraph_t *graph, igraph_cached_property_t prop) {
143	0	IGRAPH_ASSERT(prop >= 0 && prop < IGRAPH_PROP_I_SIZE);
144	0	assert(graph->cache != NULL);
145	0	graph->cache->known &= ~(1 << prop);
146	0	}
147
148		/**
149		* \brief Invalidates all cached properties of the graph.
150		*
151		* This function is typically called after the graph is modified.
152		*
153		* \param graph the graph whose cache is to be invalidated
154		*/
155	0	void igraph_i_property_cache_invalidate_all(const igraph_t *graph) {
156	0	assert(graph->cache != NULL);
157	0	graph->cache->known = 0;
158	0	}
159
160		/**
161		* \brief Invalidates all but a few cached properties of the graph, subject to specific conditions.
162		*
163		* This function is typically called after the graph is modified if we know that
164		* the modification does not affect certain cached properties in certain cases.
165		* For instance, adding more vertices does not make a connected graph disconnected,
166		* so we can keep the cached properties related to graph connectivity if they
167		* were already cached as true, but we need to invalidate them if they were
168		* cached as false.
169		*
170		* </para><para>
171		* Use <code>1 << IGRAPH_PROP_SOMETHING</code> to encode an individual property
172		* in the bits of the bitmask used in the arguments of this function.
173		*
174		* \param graph the graph whose cache is to be invalidated
175		* \param keep_always bitmask where the i-th bit corresponds to cached property \em i
176		* and it should be set to 1 if the property should be \em kept ,
177		* irrespectively of its current cached value.
178		*/
179		void igraph_i_property_cache_invalidate_conditionally(
180		const igraph_t *graph, uint32_t keep_always, uint32_t keep_when_false,
181		uint32_t keep_when_true
182	5.50k	) {
183	5.50k	uint32_t invalidate = ~keep_always;
184	5.50k	uint32_t mask;
185	5.50k	uint32_t maybe_keep;
186	5.50k	igraph_bool_t cached_value;
187
188	5.50k	assert(graph->cache != NULL);
189
190		/* The bits of maybe_keep are set to 1 for those properties that are:
191		*
192		* - currently cached
193		* - should _probably_ be invalidated
194		* - _but_ the current cached value of the property may change the decision
195		*/
196	5.50k	maybe_keep = graph->cache->known & invalidate & (keep_when_false \| keep_when_true);
197
198	5.50k	if (maybe_keep) {
199	0	for (igraph_cached_property_t prop = (igraph_cached_property_t ) 0; prop < IGRAPH_PROP_I_SIZE; ++prop) {
200	0	mask = 1 << prop;
201	0	if (maybe_keep & mask) {
202		/* if we get here, we know that the property is cached; we have
203		* masked maybe_keep with graph->cache->known */
204	0	cached_value = igraph_i_property_cache_get_bool(graph, prop);
205	0	if (
206	0	((keep_when_false & mask) && !cached_value) \|\|
207	0	((keep_when_true & mask) && cached_value)
208	0	) {
209	0	invalidate &= ~mask;
210	0	}
211	0	}
212	0	}
213	0	}
214
215	5.50k	graph->cache->known &= ~invalidate;
216	5.50k	}