summaryrefslogtreecommitdiff
path: root/common/collection/collection_cmp.c
diff options
context:
space:
mode:
Diffstat (limited to 'common/collection/collection_cmp.c')
-rw-r--r--common/collection/collection_cmp.c436
1 files changed, 436 insertions, 0 deletions
diff --git a/common/collection/collection_cmp.c b/common/collection/collection_cmp.c
new file mode 100644
index 00000000..c1f9017d
--- /dev/null
+++ b/common/collection/collection_cmp.c
@@ -0,0 +1,436 @@
+/*
+ COLLECTION LIBRARY
+
+ Function to compare items.
+
+ Copyright (C) Dmitri Pal <dpal@redhat.com> 2009
+
+ Collection Library is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License as published by
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
+
+ Collection Library 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 Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with Collection Library. If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#define _GNU_SOURCE
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+#include <ctype.h>
+#include <time.h>
+#include "config.h"
+#include "trace.h"
+
+/* The collection should use the real structures */
+#include "collection_priv.h"
+#include "collection.h"
+
+#define NONZERO 1
+#define PROP_MSK 0x000000007
+
+
+#define TYPED_MATCH(type) \
+ do { \
+ if (*((type *)(first->data)) != *((type *)(second->data))) { \
+ result = NONZERO; \
+ if ((out_flags) && \
+ (*((type *)(first->data)) < *((type *)(second->data)))) { \
+ *out_flags |= COL_CMPOUT_DATA; \
+ } \
+ } \
+ } while(0)
+
+
+/* Function to compare two items */
+int col_compare_items(struct collection_item *first,
+ struct collection_item *second,
+ unsigned in_flags,
+ unsigned *out_flags)
+{
+ int result = 0;
+ unsigned mode;
+ int cmpres = 0;
+ char *substr;
+
+ TRACE_FLOW_STRING("col_compare_items", "Entry.");
+
+ /* If any of the arguments is NULL return
+ * that they are different.
+ */
+ if ((first == NULL) || (second == NULL)) {
+ TRACE_INFO_STRING("One of the items is NULL", "");
+ return NONZERO;
+ }
+
+ /* Check if we are told to compare something */
+ if (!in_flags) {
+ TRACE_INFO_NUMBER("No flags specified", in_flags);
+ return NONZERO;
+ }
+
+ if (out_flags) *out_flags = 0;
+
+ /* Start comparison */
+ mode = in_flags & PROP_MSK;
+ if (mode > 0 ) {
+ /* We are told to compare the properties */
+ switch(mode) {
+
+ case COL_CMPIN_PROP_EQU: /* looking for exact match */
+
+ /* Compare hashes and lengths first */
+ if ((first->phash == first->phash) &&
+ (first->property_len == second->property_len)) {
+ /* Collections are case insensitive, sorry... */
+ cmpres = strncasecmp(first->property,
+ second->property,
+ second->property_len);
+ if (cmpres != 0) {
+ result = NONZERO;
+ if (cmpres < 0) {
+ /* Second is greater */
+ if (out_flags) *out_flags |= COL_CMPOUT_PROP_STR;
+ }
+ }
+ }
+ else {
+ result = NONZERO;
+ /* They are different so check if we need to compare? */
+ if (out_flags) {
+ cmpres = strncasecmp(first->property,
+ second->property,
+ second->property_len);
+ if (cmpres < 0) {
+ /* Second is greater */
+ *out_flags |= COL_CMPOUT_PROP_STR;
+ }
+ }
+ }
+ break;
+
+ case COL_CMPIN_PROP_BEG: /* looking for beginning */
+
+ /* Compare lengths first */
+ if (first->property_len >= second->property_len) {
+ cmpres = strncasecmp(first->property,
+ second->property,
+ second->property_len);
+ if (cmpres == 0) {
+ /* Check we need to validate for dot */
+ if (in_flags & COL_CMPIN_PROP_DOT) {
+ if ((first->property[second->property_len] != '\0') &&
+ (first->property[second->property_len] != '.')) {
+ result = NONZERO;
+ }
+ }
+ }
+ else result = NONZERO;
+ }
+ else result = NONZERO;
+ break;
+
+ case COL_CMPIN_PROP_MID: /* looking for middle */
+
+ /* Compare lengths first */
+ if (first->property_len >= second->property_len) {
+ substr = strcasestr(first->property, second->property);
+ if (substr != NULL) {
+ /* Check we need to validate for dot */
+ if (in_flags & COL_CMPIN_PROP_DOT) {
+ /* Check if we have a dot before or after */
+ if (((substr != first->property) &&
+ (first->property[(substr - first->property) - 1] != '.')) ||
+ ((substr[second->property_len] != '\0') &&
+ (substr[second->property_len] != '.'))) {
+ result = NONZERO;
+ }
+ }
+ }
+ else result = NONZERO;
+ }
+ else result = NONZERO;
+ break;
+
+ case COL_CMPIN_PROP_END: /* looking for end */
+
+ /* Compare lengths first */
+ if (first->property_len >= second->property_len) {
+ substr = first->property + (first->property_len - second->property_len);
+ cmpres = strncasecmp(substr,
+ second->property,
+ second->property_len);
+ if (cmpres == 0) {
+ /* Check we need to validate for dot */
+ if (in_flags & COL_CMPIN_PROP_DOT) {
+ if ((substr != first->property) &&
+ (first->property[(substr - first->property) - 1] != '.')) {
+ result = NONZERO;
+ }
+ }
+ }
+ else result = NONZERO;
+ }
+ else result = NONZERO;
+ break;
+
+ default: result = NONZERO;
+ break;
+ }
+ }
+
+ /* Check if we are told to compare property lengths */
+ if (in_flags & COL_CMPIN_PROP_LEN) {
+ if (first->property_len != second->property_len) {
+ result = NONZERO;
+ /* Do we need to tell who is greater? */
+ if ((out_flags) && (first->property_len < second->property_len)) {
+ *out_flags |= COL_CMPOUT_PROP_LEN;
+ }
+ }
+ }
+
+ /* Check if we are told to compare types */
+ if (in_flags & COL_CMPIN_TYPE) {
+ if (first->type != second->type) result = NONZERO;
+ }
+
+ /* Check if we need to compare data length */
+ if (in_flags & COL_CMPIN_DATA_LEN) {
+ if (first->length != second->length) {
+ result = NONZERO;
+ /* Do we need to tell who is greater? */
+ if ((out_flags) && (first->length < second->length)) {
+ *out_flags |= COL_CMPOUT_DATA_LEN;
+ }
+ }
+ }
+
+ /* Check if we need to compare data */
+ if (in_flags & COL_CMPIN_DATA) {
+ if (first->type == second->type) {
+ switch(first->type) {
+
+ case COL_TYPE_STRING:
+ if (first->length == second->length) {
+ cmpres = strncmp((const char *)first->data,
+ (const char *)second->data,
+ first->length);
+
+ if (cmpres != 0) {
+ result = NONZERO;
+ if (cmpres < 0) {
+ /* Second is greater */
+ if (out_flags) *out_flags |= COL_CMPOUT_DATA;
+ }
+ }
+
+ }
+ else result = NONZERO;
+ break;
+
+ case COL_TYPE_BINARY:
+ if (first->length == second->length) {
+ cmpres = memcmp(first->data,
+ second->data,
+ first->length);
+
+ if (cmpres != 0) result = NONZERO;
+ }
+ else result = NONZERO;
+ break;
+
+ case COL_TYPE_INTEGER:
+ /* Use macro to match data */
+ TYPED_MATCH(int);
+ break;
+
+ case COL_TYPE_UNSIGNED:
+ /* Use macro to match data */
+ TYPED_MATCH(unsigned);
+ break;
+
+ case COL_TYPE_LONG:
+ /* Use macro to match data */
+ TYPED_MATCH(long);
+ break;
+
+ case COL_TYPE_ULONG:
+ /* Use macro to match data */
+ TYPED_MATCH(unsigned long);
+ break;
+
+ case COL_TYPE_DOUBLE:
+ /* Use macro to match data */
+ TYPED_MATCH(double);
+ break;
+
+ case COL_TYPE_BOOL:
+ /* Use macro to match data */
+ TYPED_MATCH(unsigned char);
+ break;
+
+ /* These are never same */
+ case COL_TYPE_COLLECTION:
+ case COL_TYPE_COLLECTIONREF:
+ case COL_TYPE_END:
+ default:
+ result = NONZERO;
+ break;
+ }
+
+ }
+ else result = NONZERO;
+ }
+
+ TRACE_FLOW_NUMBER("col_compare_items. Exit. Returning:", result);
+ return result;
+}
+
+/* Sort collection */
+int col_sort_collection(struct collection_item *col,
+ unsigned cmp_flags,
+ unsigned sort_flags)
+{
+ int error = EOK;
+
+ struct collection_item *current;
+ struct collection_header *header;
+ struct collection_item **array;
+ struct collection_item *temp_item;
+ struct collection_item *other;
+ size_t size;
+ int ind, last;
+ int i, j;
+ int res;
+ unsigned out_flags;
+
+ TRACE_FLOW_STRING("col_sort_collection", "Entry.");
+
+ TRACE_INFO_NUMBER("Comparison flags:", cmp_flags);
+ TRACE_INFO_NUMBER("Sort flags:", sort_flags);
+
+ if ((col == NULL) || (col->type != COL_TYPE_COLLECTION)) {
+ TRACE_ERROR_STRING("Collecton must not ne NULL", "");
+ return EINVAL;
+ }
+
+ /* This will be a fast and simple implementation for now */
+ header = (struct collection_header *)(col->data);
+
+ if ((sort_flags & COL_SORT_SUB) &&
+ (sort_flags & COL_SORT_MYSUB) &&
+ (header->reference_count > 1)) {
+ TRACE_FLOW_STRING("col_sort_collection", "Exit.");
+ return error;
+ }
+
+ size = sizeof(struct collection_item *) * (header->count - 1);
+ array = (struct collection_item **)malloc(size);
+ if (array == NULL) {
+ TRACE_ERROR_NUMBER("Failed to allocate memory", ENOMEM);
+ return ENOMEM;
+ }
+
+ /* Fill array */
+ current = col->next;
+ ind = 0;
+ while (current != NULL) {
+ TRACE_INFO_STRING("Item:", current->property);
+ array[ind] = current;
+ if ((sort_flags & COL_SORT_SUB) &&
+ (array[ind]->type == COL_TYPE_COLLECTIONREF)) {
+ /* If we found a subcollection and we need to sort it
+ * then sort it.
+ */
+ other = *((struct collection_item **)(array[ind]->data));
+ error = col_sort_collection(other, cmp_flags, sort_flags);
+ if (error) {
+ TRACE_ERROR_NUMBER("Subcollection sort failed", error);
+ free(array);
+ return error;
+ }
+ }
+ ind++;
+ current = current->next;
+ }
+
+ last = ind - 1;
+
+ for (i = 0; i < last; i++) {
+
+ TRACE_INFO_STRING("Arg1:", array[i]->property);
+ TRACE_INFO_STRING("Arg2:", array[i + 1]->property);
+
+ res = col_compare_items(array[i],
+ array[i + 1],
+ cmp_flags,
+ &out_flags);
+
+ TRACE_INFO_STRING("Result:", ((res == 0) ? "same" : "different"));
+ TRACE_INFO_NUMBER("Out flags", out_flags);
+
+ /* If they are not same and second is not greater
+ * in any way then we need to swap them */
+ if ((res != 0) && (out_flags == 0)) {
+ /* Swap */
+ TRACE_INFO_STRING("Swapping:", "");
+ TRACE_INFO_STRING("Item:", array[i]->property);
+ TRACE_INFO_STRING("Item:", array[i + 1]->property);
+
+ temp_item = array[i];
+ array[i] = array[i + 1];
+ array[i + 1] = temp_item;
+
+ /* But we need to go up bubbling this item
+ */
+ j = i;
+ while (j > 0) {
+ res = col_compare_items(array[j - 1],
+ array[j],
+ cmp_flags,
+ &out_flags);
+ /* If they are not same and second is not greater
+ * in any way then we need to swap them */
+ if ((res != 0) && (out_flags == 0)) {
+ /* Swap */
+ temp_item = array[j - 1];
+ array[j - 1] = array[j];
+ array[j] = temp_item;
+ }
+ else break;
+ j--;
+ }
+ }
+ }
+
+ /* Build the chain back */
+ if (sort_flags & COL_SORT_DESC) {
+ col->next = array[last];
+ for (i = last; i > 0 ; i--) {
+ array[i]->next = array[i - 1];
+ }
+ array[0]->next = NULL;
+ header->last = array[0];
+ }
+ else {
+ col->next = array[0];
+ for (i = 0; i < last ; i++) {
+ array[i]->next = array[i + 1];
+ }
+ array[last]->next = NULL;
+ header->last = array[last];
+ }
+
+ free(array);
+
+ TRACE_FLOW_STRING("col_sort_collection", "Exit.");
+ return error;
+
+}