SDDSlib
Loading...
Searching...
No Matches
binsert.c
Go to the documentation of this file.
1/**
2 * @file binsert.c
3 * @brief Binary search and insertion functions.
4 * @details This file provides implementations for binary search and insertion
5 * operations on arrays of pointers or data values.
6 *
7 * @copyright
8 * - (c) 2002 The University of Chicago, as Operator of Argonne National Laboratory.
9 * - (c) 2002 The Regents of the University of California, as Operator of Los Alamos National Laboratory.
10 *
11 * @license
12 * This file is distributed under the terms of the Software License Agreement
13 * found in the file LICENSE included with this distribution.
14 *
15 * @author M. Borland, C. Saunders, R. Soliday
16 */
17
18
19#include "mdb.h"
20
21/* The data for binaryInsert and binaryIndexSearch is an array of pointers to the
22 * values. To search a simple array of values, use binaryArraySearch.
23 */
24
25/**
26 * @brief Inserts a new member into a sorted array using binary search.
27 *
28 * This function performs a binary search to find the appropriate position
29 * for the new member in the sorted array. If a duplicate is found, it sets
30 * the duplicate flag and does not insert the new member.
31 *
32 * @param array Pointer to the array of pointers to members.
33 * @param members The number of members currently in the array.
34 * @param newMember Pointer to the new member to be inserted.
35 * @param compare Comparison function that defines the order of the elements.
36 * @param duplicate Pointer to an integer that is set to 1 if a duplicate is found.
37 * @return The index at which the new member was inserted, or the index of a duplicate.
38 */
39long binaryInsert(void **array, long members, void *newMember,
40 int (*compare)(const void *c1, const void *c2), int32_t *duplicate) {
41 long ih, il, im, comparison;
42
43 *duplicate = 0;
44 if (members == 0) {
45 *array = newMember;
46 return 0;
47 }
48
49 il = 0;
50 ih = members - 1;
51 if ((comparison = (*compare)(array[il], newMember)) >= 0) {
52 if (comparison == 0) {
53 *duplicate = 1;
54 return 0;
55 }
56 im = 0;
57 } else if ((comparison = (*compare)(array[ih], newMember)) <= 0) {
58 if (comparison == 0) {
59 *duplicate = 1;
60 return ih;
61 }
62 im = members;
63 } else {
64 while ((ih - il) > 1) {
65 im = (il + ih) / 2;
66 if ((comparison = (*compare)(array[im], newMember)) == 0) {
67 *duplicate = 1;
68 return im;
69 }
70 if (comparison > 0)
71 ih = im;
72 else
73 il = im;
74 }
75 im = ih;
76 }
77 for (il = members; il > im; il--)
78 array[il] = array[il - 1];
79 array[im] = newMember;
80 return im;
81}
82
83/**
84 * @brief Searches for a key in a sorted array of pointers using binary search.
85 *
86 * This function performs a binary search to find the index of the key in the array.
87 * If the key is not found and the bracket flag is set, it returns the index of the
88 * nearest element less than or equal to the key.
89 *
90 * @param array Pointer to the array of pointers to members.
91 * @param members The number of members in the array.
92 * @param key Pointer to the key to search for.
93 * @param compare Comparison function that defines the order of the elements.
94 * @param bracket If non-zero, returns the nearest index if the key is not found.
95 * @return The index of the key if found, the nearest index if bracket is set,
96 * or -1 if the key is not found and bracket is not set.
97 */
98long binaryIndexSearch(void **array, long members, void *key,
99 int (*compare)(const void *c1, const void *c2), long bracket) {
100 long ih, il, im, comparison;
101
102 if (members == 0)
103 return -1;
104
105 il = 0;
106 ih = members - 1;
107 if ((comparison = (*compare)(array[il], key)) >= 0) {
108 if (comparison == 0)
109 return il;
110 im = 0;
111 } else if ((comparison = (*compare)(array[ih], key)) <= 0) {
112 if (comparison == 0)
113 return ih;
114 im = members;
115 } else {
116 while ((ih - il) > 1) {
117 im = (il + ih) / 2;
118 if ((comparison = (*compare)(array[im], key)) == 0)
119 return im;
120 if (comparison > 0)
121 ih = im;
122 else
123 il = im;
124 }
125 im = ih;
126 }
127 if (!bracket)
128 return -1;
129
130 /* return index of nearest point less than or equal to the key */
131 comparison = (*compare)(array[im], key);
132 if (comparison <= 0)
133 return im;
134 comparison = (*compare)(array[il], key);
135 if (comparison <= 0)
136 return il;
137 return -1;
138}
139
140/**
141 * @brief Searches for a key in a sorted array of data values using binary search.
142 *
143 * This function performs a binary search on an array of data values (not pointers)
144 * to find the index of the key. If the key is not found and the bracket flag is set,
145 * it returns the index of the nearest element less than or equal to the key.
146 *
147 * @param array Pointer to the array of data values.
148 * @param elemSize The size of each element in the array.
149 * @param members The number of members in the array.
150 * @param key Pointer to the key to search for.
151 * @param compare Comparison function that defines the order of the elements.
152 * @param bracket If non-zero, returns the nearest index if the key is not found.
153 * @return The index of the key if found, the nearest index if bracket is set,
154 * or -1 if the key is not found and bracket is not set.
155 */
156long binaryArraySearch(void *array, size_t elemSize, long members, void *key,
157 int (*compare)(const void *c1, const void *c2), long bracket)
158/* Same as binaryIndexSearch, but the array is an array of data values,
159 * rather than an array of pointers
160 */
161{
162 long ih, il, im, comparison;
163
164 if (members == 0)
165 return -1;
166
167 il = 0;
168 ih = members - 1;
169 if ((comparison = (*compare)((void *)((char *)array + il * elemSize), key)) >= 0) {
170 if (comparison == 0)
171 return il;
172 im = 0;
173 } else if ((comparison = (*compare)((void *)((char *)array + ih * elemSize), key)) <= 0) {
174 if (comparison == 0)
175 return ih;
176 im = ih;
177 } else {
178 while ((ih - il) > 1) {
179 im = (il + ih) / 2;
180 if ((comparison = (*compare)((void *)((char *)array + im * elemSize), key)) == 0)
181 return im;
182 if (comparison > 0)
183 ih = im;
184 else
185 il = im;
186 }
187 im = ih;
188 }
189 if (!bracket)
190 return -1;
191
192 /* return index of nearest point less than or equal to the key */
193 comparison = (*compare)((void *)((char *)array + im * elemSize), key);
194 if (comparison <= 0)
195 return im;
196 comparison = (*compare)((void *)(((char *)array) + il * elemSize), key);
197 if (comparison <= 0)
198 return il;
199 return -1;
200}
binaryInsert
long binaryInsert(void **array, long members, void *newMember, int(*compare)(const void *c1, const void *c2), int32_t *duplicate)
Inserts a new member into a sorted array using binary search.
Definition binsert.c:39
binaryArraySearch
long binaryArraySearch(void *array, size_t elemSize, long members, void *key, int(*compare)(const void *c1, const void *c2), long bracket)
Searches for a key in a sorted array of data values using binary search.
Definition binsert.c:156
binaryIndexSearch
long binaryIndexSearch(void **array, long members, void *key, int(*compare)(const void *c1, const void *c2), long bracket)
Searches for a key in a sorted array of pointers using binary search.
Definition binsert.c:98
Generated by doxygen 1.12.0