/src/leptonica/src/map.c

Source (jump to first uncovered line)
/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. Redistributions in binary form must reproduce the above
 -     copyright notice, this list of conditions and the following
 -     disclaimer in the documentation and/or other materials
 -     provided with the distribution.
 -
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *====================================================================*/

/*!
 * \file map.c
 * <pre>
 *
 *  This is an interface for map and set functions, based on using
 *  red-black binary search trees.  Because these trees are sorted,
 *  they are O(nlogn) to build.  They allow logn insertion, find
 *  and deletion of elements.
 *
 *  Both the map and set are ordered by key value, with unique keys.
 *  For the map, the elements are key/value pairs.
 *  For the set we only store unique, ordered keys, and the value
 *  (set to 0 in the implementation) is ignored.
 *
 *  The keys for the map and set can be any of the three types in the
 *  l_rbtree_keytype enum.  The values stored can be any of the four
 *  types in the rb_type union.
 *
 *  In-order forward and reverse iterators are provided for maps and sets.
 *  To forward iterate over the map for any type of key (in this example,
 *  uint32), extracting integer values:
 *
 *      L_AMAP  *m = l_amapCreate(L_UINT_TYPE);
 *      [add elements to the map ...]
 *      L_AMAP_NODE  *n = l_amapGetFirst(m);
 *      while (n) {
 *          l_int32 val = n->value.itype;
 *          // do something ...
 *          n = l_amapGetNext(n);
 *      }
 *
 *  If the nodes are deleted during the iteration:
 *
 *      L_AMAP  *m = l_amapCreate(L_UINT_TYPE);
 *      [add elements to the map ...]
 *      L_AMAP_NODE  *n = l_amapGetFirst(m);
 *      L_AMAP_NODE  *nn;
 *      while (n) {
 *          nn = l_amapGetNext(n);
 *          l_int32 val = n->value.itype;
 *          l_uint32 key = n->key.utype;
 *          // do something ...
 *          l_amapDelete(m, n->key);
 *          n = nn;
 *      }
 *
 *  See prog/maptest.c and prog/settest.c for more examples of usage.
 *
 *  Interface to (a) map using a general key and storing general values
 *           L_AMAP        *l_amapCreate()
 *           RB_TYPE       *l_amapFind()
 *           void           l_amapInsert()
 *           void           l_amapDelete()
 *           void           l_amapDestroy()
 *           L_AMAP_NODE   *l_amapGetFirst()
 *           L_AMAP_NODE   *l_amapGetNext()
 *           L_AMAP_NODE   *l_amapGetLast()
 *           L_AMAP_NODE   *l_amapGetPrev()
 *           l_int32        l_amapSize()
 *
 *  Interface to (a) set using a general key
 *           L_ASET        *l_asetCreate()
 *           RB_TYPE       *l_asetFind()
 *           void           l_asetInsert()
 *           void           l_asetDelete()
 *           void           l_asetDestroy()
 *           L_ASET_NODE   *l_asetGetFirst()
 *           L_ASET_NODE   *l_asetGetNext()
 *           L_ASET_NODE   *l_asetGetLast()
 *           L_ASET_NODE   *l_asetGetPrev()
 *           l_int32        l_asetSize()
 * </pre>
 */

#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */

#include "allheaders.h"

/* ------------------------------------------------------------- *
 *                         Interface to Map                      *
 * ------------------------------------------------------------- */
L_AMAP *
l_amapCreate(l_int32  keytype)
{
L_AMAP  *m;

    if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
        keytype != L_FLOAT_TYPE)
        return (L_AMAP *)ERROR_PTR("invalid keytype", __func__, NULL);

    m = (L_AMAP *)LEPT_CALLOC(1, sizeof(L_AMAP));
    m->keytype = keytype;
    return m;
}

RB_TYPE *
l_amapFind(L_AMAP  *m,
           RB_TYPE  key)
{
    return l_rbtreeLookup(m, key);
}

void
l_amapInsert(L_AMAP  *m,
             RB_TYPE  key,
             RB_TYPE  value)
{
    l_rbtreeInsert(m, key, value);
}

void
l_amapDelete(L_AMAP  *m,
             RB_TYPE  key)
{
    l_rbtreeDelete(m, key);
}

void
l_amapDestroy(L_AMAP  **pm)
{
    l_rbtreeDestroy(pm);
}

L_AMAP_NODE *
l_amapGetFirst(L_AMAP  *m)
{
    return l_rbtreeGetFirst(m);
}

L_AMAP_NODE *
l_amapGetNext(L_AMAP_NODE  *n)
{
    return l_rbtreeGetNext(n);
}

L_AMAP_NODE *
l_amapGetLast(L_AMAP  *m)
{
    return l_rbtreeGetLast(m);
}

L_AMAP_NODE *
l_amapGetPrev(L_AMAP_NODE  *n)
{
    return l_rbtreeGetPrev(n);
}

l_int32
l_amapSize(L_AMAP  *m)
{
    return l_rbtreeGetCount(m);
}


/* ------------------------------------------------------------- *
 *                         Interface to Set                      *
 * ------------------------------------------------------------- */
L_ASET *
l_asetCreate(l_int32  keytype)
{
L_ASET  *s;

    if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
        keytype != L_FLOAT_TYPE)
        return (L_ASET *)ERROR_PTR("invalid keytype", __func__, NULL);

    s = (L_ASET *)LEPT_CALLOC(1, sizeof(L_ASET));
    s->keytype = keytype;
    return s;
}

/*
 *  l_asetFind()
 *
 *  This returns NULL if not found, non-null if it is.  In the latter
 *  case, the value stored in the returned pointer has no significance.
 */
RB_TYPE *
l_asetFind(L_ASET  *s,
           RB_TYPE  key)
{
    return l_rbtreeLookup(s, key);
}

void
l_asetInsert(L_ASET  *s,
             RB_TYPE  key)
{
RB_TYPE  value;

    value.itype = 0;  /* meaningless */
    l_rbtreeInsert(s, key, value);
}

void
l_asetDelete(L_ASET  *s,
             RB_TYPE  key)
{
    l_rbtreeDelete(s, key);
}

void
l_asetDestroy(L_ASET  **ps)
{
    l_rbtreeDestroy(ps);
}

L_ASET_NODE *
l_asetGetFirst(L_ASET  *s)
{
    return l_rbtreeGetFirst(s);
}

L_ASET_NODE *
l_asetGetNext(L_ASET_NODE  *n)
{
    return l_rbtreeGetNext(n);
}

L_ASET_NODE *
l_asetGetLast(L_ASET  *s)
{
    return l_rbtreeGetLast(s);
}

L_ASET_NODE *
l_asetGetPrev(L_ASET_NODE  *n)
{
    return l_rbtreeGetPrev(n);
}

l_int32
l_asetSize(L_ASET  *s)
{
    return l_rbtreeGetCount(s);
}

Coverage Report

Created: 2025-06-13 07:02

Line	Count	Source (jump to first uncovered line)
1		/====================================================================
2		- Copyright (C) 2001 Leptonica. All rights reserved.
3		-
4		- Redistribution and use in source and binary forms, with or without
5		- modification, are permitted provided that the following conditions
6		- are met:
7		- 1. Redistributions of source code must retain the above copyright
8		- notice, this list of conditions and the following disclaimer.
9		- 2. Redistributions in binary form must reproduce the above
10		- copyright notice, this list of conditions and the following
11		- disclaimer in the documentation and/or other materials
12		- provided with the distribution.
13		-
14		- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15		- ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16		- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17		- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18		- CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19		- EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20		- PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21		- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22		- OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23		- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24		- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25		====================================================================/
26
27		/*!
28		* \file map.c
29		* <pre>
30		*
31		* This is an interface for map and set functions, based on using
32		* red-black binary search trees. Because these trees are sorted,
33		* they are O(nlogn) to build. They allow logn insertion, find
34		* and deletion of elements.
35		*
36		* Both the map and set are ordered by key value, with unique keys.
37		* For the map, the elements are key/value pairs.
38		* For the set we only store unique, ordered keys, and the value
39		* (set to 0 in the implementation) is ignored.
40		*
41		* The keys for the map and set can be any of the three types in the
42		* l_rbtree_keytype enum. The values stored can be any of the four
43		* types in the rb_type union.
44		*
45		* In-order forward and reverse iterators are provided for maps and sets.
46		* To forward iterate over the map for any type of key (in this example,
47		* uint32), extracting integer values:
48		*
49		* L_AMAP *m = l_amapCreate(L_UINT_TYPE);
50		* [add elements to the map ...]
51		* L_AMAP_NODE *n = l_amapGetFirst(m);
52		* while (n) {
53		* l_int32 val = n->value.itype;
54		* // do something ...
55		* n = l_amapGetNext(n);
56		* }
57		*
58		* If the nodes are deleted during the iteration:
59		*
60		* L_AMAP *m = l_amapCreate(L_UINT_TYPE);
61		* [add elements to the map ...]
62		* L_AMAP_NODE *n = l_amapGetFirst(m);
63		* L_AMAP_NODE *nn;
64		* while (n) {
65		* nn = l_amapGetNext(n);
66		* l_int32 val = n->value.itype;
67		* l_uint32 key = n->key.utype;
68		* // do something ...
69		* l_amapDelete(m, n->key);
70		* n = nn;
71		* }
72		*
73		* See prog/maptest.c and prog/settest.c for more examples of usage.
74		*
75		* Interface to (a) map using a general key and storing general values
76		* L_AMAP *l_amapCreate()
77		* RB_TYPE *l_amapFind()
78		* void l_amapInsert()
79		* void l_amapDelete()
80		* void l_amapDestroy()
81		* L_AMAP_NODE *l_amapGetFirst()
82		* L_AMAP_NODE *l_amapGetNext()
83		* L_AMAP_NODE *l_amapGetLast()
84		* L_AMAP_NODE *l_amapGetPrev()
85		* l_int32 l_amapSize()
86		*
87		* Interface to (a) set using a general key
88		* L_ASET *l_asetCreate()
89		* RB_TYPE *l_asetFind()
90		* void l_asetInsert()
91		* void l_asetDelete()
92		* void l_asetDestroy()
93		* L_ASET_NODE *l_asetGetFirst()
94		* L_ASET_NODE *l_asetGetNext()
95		* L_ASET_NODE *l_asetGetLast()
96		* L_ASET_NODE *l_asetGetPrev()
97		* l_int32 l_asetSize()
98		* </pre>
99		*/
100
101		#ifdef HAVE_CONFIG_H
102		#include <config_auto.h>
103		#endif /* HAVE_CONFIG_H */
104
105		#include "allheaders.h"
106
107		/* ------------------------------------------------------------- *
108		* Interface to Map *
109		* ------------------------------------------------------------- */
110		L_AMAP *
111		l_amapCreate(l_int32 keytype)
112	0	{
113	0	L_AMAP *m;
114
115	0	if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
116	0	keytype != L_FLOAT_TYPE)
117	0	return (L_AMAP *)ERROR_PTR("invalid keytype", __func__, NULL);
118
119	0	m = (L_AMAP *)LEPT_CALLOC(1, sizeof(L_AMAP));
120	0	m->keytype = keytype;
121	0	return m;
122	0	}
123
124		RB_TYPE *
125		l_amapFind(L_AMAP *m,
126		RB_TYPE key)
127	0	{
128	0	return l_rbtreeLookup(m, key);
129	0	}
130
131		void
132		l_amapInsert(L_AMAP *m,
133		RB_TYPE key,
134		RB_TYPE value)
135	0	{
136	0	l_rbtreeInsert(m, key, value);
137	0	}
138
139		void
140		l_amapDelete(L_AMAP *m,
141		RB_TYPE key)
142	0	{
143	0	l_rbtreeDelete(m, key);
144	0	}
145
146		void
147		l_amapDestroy(L_AMAP **pm)
148	0	{
149	0	l_rbtreeDestroy(pm);
150	0	}
151
152		L_AMAP_NODE *
153		l_amapGetFirst(L_AMAP *m)
154	0	{
155	0	return l_rbtreeGetFirst(m);
156	0	}
157
158		L_AMAP_NODE *
159		l_amapGetNext(L_AMAP_NODE *n)
160	0	{
161	0	return l_rbtreeGetNext(n);
162	0	}
163
164		L_AMAP_NODE *
165		l_amapGetLast(L_AMAP *m)
166	0	{
167	0	return l_rbtreeGetLast(m);
168	0	}
169
170		L_AMAP_NODE *
171		l_amapGetPrev(L_AMAP_NODE *n)
172	0	{
173	0	return l_rbtreeGetPrev(n);
174	0	}
175
176		l_int32
177		l_amapSize(L_AMAP *m)
178	0	{
179	0	return l_rbtreeGetCount(m);
180	0	}
181
182
183		/* ------------------------------------------------------------- *
184		* Interface to Set *
185		* ------------------------------------------------------------- */
186		L_ASET *
187		l_asetCreate(l_int32 keytype)
188	0	{
189	0	L_ASET *s;
190
191	0	if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE &&
192	0	keytype != L_FLOAT_TYPE)
193	0	return (L_ASET *)ERROR_PTR("invalid keytype", __func__, NULL);
194
195	0	s = (L_ASET *)LEPT_CALLOC(1, sizeof(L_ASET));
196	0	s->keytype = keytype;
197	0	return s;
198	0	}
199
200		/*
201		* l_asetFind()
202		*
203		* This returns NULL if not found, non-null if it is. In the latter
204		* case, the value stored in the returned pointer has no significance.
205		*/
206		RB_TYPE *
207		l_asetFind(L_ASET *s,
208		RB_TYPE key)
209	0	{
210	0	return l_rbtreeLookup(s, key);
211	0	}
212
213		void
214		l_asetInsert(L_ASET *s,
215		RB_TYPE key)
216	0	{
217	0	RB_TYPE value;
218
219	0	value.itype = 0; /* meaningless */
220	0	l_rbtreeInsert(s, key, value);
221	0	}
222
223		void
224		l_asetDelete(L_ASET *s,
225		RB_TYPE key)
226	0	{
227	0	l_rbtreeDelete(s, key);
228	0	}
229
230		void
231		l_asetDestroy(L_ASET **ps)
232	0	{
233	0	l_rbtreeDestroy(ps);
234	0	}
235
236		L_ASET_NODE *
237		l_asetGetFirst(L_ASET *s)
238	0	{
239	0	return l_rbtreeGetFirst(s);
240	0	}
241
242		L_ASET_NODE *
243		l_asetGetNext(L_ASET_NODE *n)
244	0	{
245	0	return l_rbtreeGetNext(n);
246	0	}
247
248		L_ASET_NODE *
249		l_asetGetLast(L_ASET *s)
250	0	{
251	0	return l_rbtreeGetLast(s);
252	0	}
253
254		L_ASET_NODE *
255		l_asetGetPrev(L_ASET_NODE *n)
256	0	{
257	0	return l_rbtreeGetPrev(n);
258	0	}
259
260		l_int32
261		l_asetSize(L_ASET *s)
262	0	{
263	0	return l_rbtreeGetCount(s);
264	0	}