Line data Source code
1 : /*
2 : COLLECTION LIBRARY
3 :
4 : Function to compare items.
5 :
6 : Copyright (C) Dmitri Pal <dpal@redhat.com> 2009
7 :
8 : Collection Library is free software: you can redistribute it and/or modify
9 : it under the terms of the GNU Lesser General Public License as published by
10 : the Free Software Foundation, either version 3 of the License, or
11 : (at your option) any later version.
12 :
13 : Collection Library is distributed in the hope that it will be useful,
14 : but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : GNU Lesser General Public License for more details.
17 :
18 : You should have received a copy of the GNU Lesser General Public License
19 : along with Collection Library. If not, see <http://www.gnu.org/licenses/>.
20 : */
21 :
22 : #include "config.h"
23 : #include <string.h>
24 : #include <stdlib.h>
25 : #include <errno.h>
26 : #include <ctype.h>
27 : #include <time.h>
28 : #include "trace.h"
29 :
30 : /* The collection should use the real structures */
31 : #include "collection_priv.h"
32 : #include "collection.h"
33 :
34 : #define NONZERO 1
35 : #define PROP_MSK 0x000000007
36 :
37 :
38 : #define TYPED_MATCH(type) \
39 : do { \
40 : if (*((type *)(first->data)) != *((type *)(second->data))) { \
41 : result = NONZERO; \
42 : if ((out_flags) && \
43 : (*((type *)(first->data)) < *((type *)(second->data)))) { \
44 : *out_flags |= COL_CMPOUT_DATA; \
45 : } \
46 : } \
47 : } while(0)
48 :
49 :
50 : /* Function to compare two items */
51 1330 : int col_compare_items(struct collection_item *first,
52 : struct collection_item *second,
53 : unsigned in_flags,
54 : unsigned *out_flags)
55 : {
56 1330 : int result = 0;
57 : unsigned mode;
58 1330 : int cmpres = 0;
59 : char *substr;
60 :
61 : TRACE_FLOW_STRING("col_compare_items", "Entry.");
62 :
63 : /* If any of the arguments is NULL return
64 : * that they are different.
65 : */
66 1330 : if ((first == NULL) || (second == NULL)) {
67 : TRACE_INFO_STRING("One of the items is NULL", "");
68 0 : return NONZERO;
69 : }
70 :
71 : /* Check if we are told to compare something */
72 1330 : if (!in_flags) {
73 : TRACE_INFO_NUMBER("No flags specified", in_flags);
74 0 : return NONZERO;
75 : }
76 :
77 1330 : if (out_flags) *out_flags = 0;
78 :
79 : /* Start comparison */
80 1330 : mode = in_flags & PROP_MSK;
81 1330 : if (mode > 0 ) {
82 : /* We are told to compare the properties */
83 256 : switch(mode) {
84 :
85 : case COL_CMPIN_PROP_EQU: /* looking for exact match */
86 :
87 : /* Compare hashes and lengths first */
88 256 : if ((first->phash == second->phash) &&
89 0 : (first->property_len == second->property_len)) {
90 : /* Collections are case insensitive, sorry... */
91 0 : cmpres = strncasecmp(first->property,
92 0 : second->property,
93 0 : second->property_len);
94 0 : if (cmpres != 0) {
95 0 : result = NONZERO;
96 0 : if (cmpres < 0) {
97 : /* Second is greater */
98 0 : if (out_flags) *out_flags |= COL_CMPOUT_PROP_STR;
99 : }
100 : }
101 : }
102 : else {
103 256 : result = NONZERO;
104 : /* They are different so check if we need to compare? */
105 256 : if (out_flags) {
106 512 : cmpres = strncasecmp(first->property,
107 256 : second->property,
108 256 : second->property_len);
109 256 : if (cmpres < 0) {
110 : /* Second is greater */
111 61 : *out_flags |= COL_CMPOUT_PROP_STR;
112 : }
113 : }
114 : }
115 256 : break;
116 :
117 : case COL_CMPIN_PROP_BEG: /* looking for beginning */
118 :
119 : /* Compare lengths first */
120 0 : if (first->property_len >= second->property_len) {
121 0 : cmpres = strncasecmp(first->property,
122 0 : second->property,
123 0 : second->property_len);
124 0 : if (cmpres == 0) {
125 : /* Check we need to validate for dot */
126 0 : if (in_flags & COL_CMPIN_PROP_DOT) {
127 0 : if ((first->property[second->property_len] != '\0') &&
128 0 : (first->property[second->property_len] != '.')) {
129 0 : result = NONZERO;
130 : }
131 : }
132 : }
133 0 : else result = NONZERO;
134 : }
135 0 : else result = NONZERO;
136 0 : break;
137 :
138 : case COL_CMPIN_PROP_MID: /* looking for middle */
139 :
140 : /* Compare lengths first */
141 0 : if (first->property_len >= second->property_len) {
142 0 : substr = strcasestr(first->property, second->property);
143 0 : if (substr != NULL) {
144 : /* Check we need to validate for dot */
145 0 : if (in_flags & COL_CMPIN_PROP_DOT) {
146 : /* Check if we have a dot before or after */
147 0 : if (((substr != first->property) &&
148 0 : (first->property[(substr - first->property) - 1] != '.')) ||
149 0 : ((substr[second->property_len] != '\0') &&
150 0 : (substr[second->property_len] != '.'))) {
151 0 : result = NONZERO;
152 : }
153 : }
154 : }
155 0 : else result = NONZERO;
156 : }
157 0 : else result = NONZERO;
158 0 : break;
159 :
160 : case COL_CMPIN_PROP_END: /* looking for end */
161 :
162 : /* Compare lengths first */
163 0 : if (first->property_len >= second->property_len) {
164 0 : substr = first->property + (first->property_len - second->property_len);
165 0 : cmpres = strncasecmp(substr,
166 0 : second->property,
167 0 : second->property_len);
168 0 : if (cmpres == 0) {
169 : /* Check we need to validate for dot */
170 0 : if (in_flags & COL_CMPIN_PROP_DOT) {
171 0 : if ((substr != first->property) &&
172 0 : (first->property[(substr - first->property) - 1] != '.')) {
173 0 : result = NONZERO;
174 : }
175 : }
176 : }
177 0 : else result = NONZERO;
178 : }
179 0 : else result = NONZERO;
180 0 : break;
181 :
182 0 : default: result = NONZERO;
183 0 : break;
184 : }
185 : }
186 :
187 : /* Check if we are told to compare property lengths */
188 1330 : if (in_flags & COL_CMPIN_PROP_LEN) {
189 352 : if (first->property_len != second->property_len) {
190 313 : result = NONZERO;
191 : /* Do we need to tell who is greater? */
192 313 : if ((out_flags) && (first->property_len < second->property_len)) {
193 4 : *out_flags |= COL_CMPOUT_PROP_LEN;
194 : }
195 : }
196 : }
197 :
198 : /* Check if we are told to compare types */
199 1330 : if (in_flags & COL_CMPIN_TYPE) {
200 0 : if (first->type != second->type) result = NONZERO;
201 : }
202 :
203 : /* Check if we need to compare data length */
204 1330 : if (in_flags & COL_CMPIN_DATA_LEN) {
205 228 : if (first->length != second->length) {
206 181 : result = NONZERO;
207 : /* Do we need to tell who is greater? */
208 181 : if ((out_flags) && (first->length < second->length)) {
209 4 : *out_flags |= COL_CMPOUT_DATA_LEN;
210 : }
211 : }
212 : }
213 :
214 : /* Check if we need to compare data */
215 1330 : if (in_flags & COL_CMPIN_DATA) {
216 494 : if (first->type == second->type) {
217 53 : switch(first->type) {
218 :
219 : case COL_TYPE_STRING:
220 0 : if (first->length == second->length) {
221 0 : cmpres = strncmp((const char *)first->data,
222 0 : (const char *)second->data,
223 0 : first->length);
224 :
225 0 : if (cmpres != 0) {
226 0 : result = NONZERO;
227 0 : if (cmpres < 0) {
228 : /* Second is greater */
229 0 : if (out_flags) *out_flags |= COL_CMPOUT_DATA;
230 : }
231 : }
232 :
233 : }
234 0 : else result = NONZERO;
235 0 : break;
236 :
237 : case COL_TYPE_BINARY:
238 0 : if (first->length == second->length) {
239 0 : cmpres = memcmp(first->data,
240 0 : second->data,
241 0 : first->length);
242 :
243 0 : if (cmpres != 0) result = NONZERO;
244 : }
245 0 : else result = NONZERO;
246 0 : break;
247 :
248 : case COL_TYPE_INTEGER:
249 : /* Use macro to match data */
250 9 : TYPED_MATCH(int);
251 9 : break;
252 :
253 : case COL_TYPE_UNSIGNED:
254 : /* Use macro to match data */
255 9 : TYPED_MATCH(unsigned);
256 9 : break;
257 :
258 : case COL_TYPE_LONG:
259 : /* Use macro to match data */
260 9 : TYPED_MATCH(long);
261 9 : break;
262 :
263 : case COL_TYPE_ULONG:
264 : /* Use macro to match data */
265 9 : TYPED_MATCH(unsigned long);
266 9 : break;
267 :
268 : case COL_TYPE_DOUBLE:
269 : /* Use macro to match data */
270 9 : TYPED_MATCH(double);
271 9 : break;
272 :
273 : case COL_TYPE_BOOL:
274 : /* Use macro to match data */
275 7 : TYPED_MATCH(unsigned char);
276 7 : break;
277 :
278 : /* These are never same */
279 : case COL_TYPE_COLLECTION:
280 : case COL_TYPE_COLLECTIONREF:
281 : case COL_TYPE_END:
282 : default:
283 1 : result = NONZERO;
284 1 : break;
285 : }
286 :
287 : }
288 441 : else result = NONZERO;
289 : }
290 :
291 : TRACE_FLOW_NUMBER("col_compare_items. Exit. Returning:", result);
292 1330 : return result;
293 : }
294 :
295 : /* Sort collection */
296 23 : int col_sort_collection(struct collection_item *col,
297 : unsigned cmp_flags,
298 : unsigned sort_flags)
299 : {
300 23 : int error = EOK;
301 :
302 : struct collection_item *current;
303 : struct collection_header *header;
304 : struct collection_item **array;
305 : struct collection_item *temp_item;
306 : struct collection_item *other;
307 : size_t size;
308 : int ind, last;
309 : int i, j;
310 : int res;
311 : unsigned out_flags;
312 :
313 : TRACE_FLOW_STRING("col_sort_collection", "Entry.");
314 :
315 : TRACE_INFO_NUMBER("Comparison flags:", cmp_flags);
316 : TRACE_INFO_NUMBER("Sort flags:", sort_flags);
317 :
318 23 : if ((col == NULL) || (col->type != COL_TYPE_COLLECTION)) {
319 : TRACE_ERROR_STRING("Collecton must not ne NULL", "");
320 0 : return EINVAL;
321 : }
322 :
323 : /* This will be a fast and simple implementation for now */
324 23 : header = (struct collection_header *)(col->data);
325 :
326 46 : if ((sort_flags & COL_SORT_SUB) &&
327 26 : (sort_flags & COL_SORT_MYSUB) &&
328 3 : (header->reference_count > 1)) {
329 : TRACE_FLOW_STRING("col_sort_collection", "Exit.");
330 2 : return error;
331 : }
332 :
333 21 : size = sizeof(struct collection_item *) * (header->count - 1);
334 21 : array = (struct collection_item **)malloc(size);
335 21 : if (array == NULL) {
336 : TRACE_ERROR_NUMBER("Failed to allocate memory", ENOMEM);
337 0 : return ENOMEM;
338 : }
339 :
340 : /* Fill array */
341 21 : current = col->next;
342 21 : ind = 0;
343 294 : while (current != NULL) {
344 : TRACE_INFO_STRING("Item:", current->property);
345 252 : array[ind] = current;
346 504 : if ((sort_flags & COL_SORT_SUB) &&
347 252 : (array[ind]->type == COL_TYPE_COLLECTIONREF)) {
348 : /* If we found a subcollection and we need to sort it
349 : * then sort it.
350 : */
351 18 : other = *((struct collection_item **)(array[ind]->data));
352 18 : error = col_sort_collection(other, cmp_flags, sort_flags);
353 18 : if (error) {
354 : TRACE_ERROR_NUMBER("Subcollection sort failed", error);
355 0 : free(array);
356 0 : return error;
357 : }
358 : }
359 252 : ind++;
360 252 : current = current->next;
361 : }
362 :
363 21 : last = ind - 1;
364 :
365 252 : for (i = 0; i < last; i++) {
366 :
367 : TRACE_INFO_STRING("Arg1:", array[i]->property);
368 : TRACE_INFO_STRING("Arg2:", array[i + 1]->property);
369 :
370 231 : res = col_compare_items(array[i],
371 231 : array[i + 1],
372 : cmp_flags,
373 : &out_flags);
374 :
375 : TRACE_INFO_STRING("Result:", ((res == 0) ? "same" : "different"));
376 : TRACE_INFO_NUMBER("Out flags", out_flags);
377 :
378 : /* If they are not same and second is not greater
379 : * in any way then we need to swap them */
380 231 : if ((res != 0) && (out_flags == 0)) {
381 : /* Swap */
382 : TRACE_INFO_STRING("Swapping:", "");
383 : TRACE_INFO_STRING("Item:", array[i]->property);
384 : TRACE_INFO_STRING("Item:", array[i + 1]->property);
385 :
386 139 : temp_item = array[i];
387 139 : array[i] = array[i + 1];
388 139 : array[i + 1] = temp_item;
389 :
390 : /* But we need to go up bubbling this item
391 : */
392 139 : j = i;
393 1303 : while (j > 0) {
394 1099 : res = col_compare_items(array[j - 1],
395 1099 : array[j],
396 : cmp_flags,
397 : &out_flags);
398 : /* If they are not same and second is not greater
399 : * in any way then we need to swap them */
400 1099 : if ((res != 0) && (out_flags == 0)) {
401 : /* Swap */
402 1025 : temp_item = array[j - 1];
403 1025 : array[j - 1] = array[j];
404 1025 : array[j] = temp_item;
405 : }
406 : else break;
407 1025 : j--;
408 : }
409 : }
410 : }
411 :
412 : /* Build the chain back */
413 21 : if (sort_flags & COL_SORT_DESC) {
414 15 : col->next = array[last];
415 174 : for (i = last; i > 0 ; i--) {
416 159 : array[i]->next = array[i - 1];
417 : }
418 15 : array[0]->next = NULL;
419 15 : header->last = array[0];
420 : }
421 : else {
422 6 : col->next = array[0];
423 78 : for (i = 0; i < last ; i++) {
424 72 : array[i]->next = array[i + 1];
425 : }
426 6 : array[last]->next = NULL;
427 6 : header->last = array[last];
428 : }
429 :
430 21 : free(array);
431 :
432 : TRACE_FLOW_STRING("col_sort_collection", "Exit.");
433 21 : return error;
434 :
435 : }
|
