Index: quotas.c =================================================================== --- quotas.c (revision 4677) +++ quotas.c (working copy) @@ -23,11 +23,11 @@ * * Contents: * - * AddQuota() - Add a quota record for this printer and user. - * FindQuota() - Find a quota record. - * FreeQuotas() - Free quotas for a printer. - * UpdateQuota() - Update quota data for the specified printer and user. - * compare() - Compare two quota records... + * AddQuota() - Add a quota record for this printer and user. + * FindQuota() - Find a quota record. + * FreeQuotas() - Free quotas for a printer. + * UpdateQuota() - Update quota data for the specified printer and user. + * compare_quotas() - Compare two quota records... */ /* @@ -41,7 +41,7 @@ * Local functions... */ -static int compare(const quota_t *q1, const quota_t *q2); +static int compare_quotas(const quota_t *q1, const quota_t *q2); /* @@ -75,7 +75,7 @@ if (p->num_quotas > 1) qsort(p->quotas, p->num_quotas, sizeof(quota_t), - (int (*)(const void *, const void *))compare); + (int (*)(const void *, const void *))compare_quotas); return (FindQuota(p, username)); } @@ -103,7 +103,7 @@ strlcpy(match.username, username, sizeof(match.username)); q = bsearch(&match, p->quotas, p->num_quotas, sizeof(quota_t), - (int(*)(const void *, const void *))compare); + (int(*)(const void *, const void *))compare_quotas); } if (q) @@ -222,12 +222,12 @@ /* - * 'compare()' - Compare two quota records... + * 'compare_quotas()' - Compare two quota records... */ static int /* O - Result of comparison */ -compare(const quota_t *q1, /* I - First quota record */ - const quota_t *q2) /* I - Second quota record */ +compare_quotas(const quota_t *q1, /* I - First quota record */ + const quota_t *q2) /* I - Second quota record */ { return (strcasecmp(q1->username, q2->username)); } Index: type.c =================================================================== --- type.c (revision 4677) +++ type.c (working copy) @@ -27,7 +27,7 @@ * mimeAddTypeRule() - Add a detection rule for a file type. * mimeFileType() - Determine the type of a file. * mimeType() - Lookup a file type. - * compare() - Compare two MIME super/type names. + * compare_mimes() - Compare two MIME super/type names. * checkrules() - Check each rule in a list. * patmatch() - Pattern matching... */ @@ -50,7 +50,7 @@ * Local functions... */ -static int compare(mime_type_t **, mime_type_t **); +static int compare_mimes(mime_type_t **, mime_type_t **); static int checkrules(const char *, cups_file_t *, mime_magic_t *); static int patmatch(const char *, const char *); @@ -118,7 +118,7 @@ if (mime->num_types > 1) qsort(mime->types, mime->num_types, sizeof(mime_type_t *), - (int (*)(const void *, const void *))compare); + (int (*)(const void *, const void *))compare_mimes); return (temp); } @@ -636,7 +636,7 @@ match = (mime_type_t **)bsearch(&keyptr, mime->types, mime->num_types, sizeof(mime_type_t *), - (int (*)(const void *, const void *))compare); + (int (*)(const void *, const void *))compare_mimes); if (match == NULL) return (NULL); @@ -646,12 +646,12 @@ /* - * 'compare()' - Compare two MIME super/type names. + * 'compare_mimes()' - Compare two MIME super/type names. */ static int /* O - Result of comparison */ -compare(mime_type_t **t0, /* I - First type */ - mime_type_t **t1) /* I - Second type */ +compare_mimes(mime_type_t **t0, /* I - First type */ + mime_type_t **t1) /* I - Second type */ { int i; /* Result of comparison */ Index: testmime.c =================================================================== --- testmime.c (revision 4677) +++ testmime.c (working copy) @@ -107,7 +107,7 @@ sscanf(argv[i], "%15[^/]/%31s", super, type); dst = mimeType(mime, super, type); - filters = mimeFilter(mime, src, dst, &num_filters, 10); + filters = mimeFilter(mime, src, dst, &num_filters, NULL); if (filters == NULL) { Index: banners.c =================================================================== --- banners.c (revision 4677) +++ banners.c (working copy) @@ -23,10 +23,10 @@ * * Contents: * - * AddBanner() - Add a banner to the array. - * FindBanner() - Find a named banner. - * LoadBanners() - Load all available banner files... - * compare() - Compare two banners. + * AddBanner() - Add a banner to the array. + * FindBanner() - Find a named banner. + * LoadBanners() - Load all available banner files... + * compare_banners() - Compare two banners. */ /* @@ -41,7 +41,7 @@ * Local functions... */ -static int compare(const banner_t *b0, const banner_t *b1); +static int compare_banners(const banner_t *b0, const banner_t *b1); /* @@ -109,7 +109,7 @@ strlcpy(key.name, name, sizeof(key.name)); return ((banner_t *)bsearch(&key, Banners, NumBanners, sizeof(banner_t), - (int (*)(const void *, const void *))compare)); + (int (*)(const void *, const void *))compare_banners)); } @@ -187,17 +187,17 @@ if (NumBanners > 1) qsort(Banners, NumBanners, sizeof(banner_t), - (int (*)(const void *, const void *))compare); + (int (*)(const void *, const void *))compare_banners); } /* - * 'compare()' - Compare two banners. + * 'compare_banners()' - Compare two banners. */ -static int /* O - -1 if name0 < name1, etc. */ -compare(const banner_t *b0, /* I - First banner */ - const banner_t *b1) /* I - Second banner */ +static int /* O - -1 if name0 < name1, etc. */ +compare_banners(const banner_t *b0, /* I - First banner */ + const banner_t *b1) /* I - Second banner */ { return (strcasecmp(b0->name, b1->name)); } Index: job.c =================================================================== --- job.c (revision 4677) +++ job.c (working copy) @@ -1436,7 +1436,7 @@ */ filters = mimeFilter(MimeDatabase, current->filetypes[current->current_file], - printer->filetype, &num_filters, MAX_FILTERS - 1); + printer->filetype, &num_filters, NULL); if (num_filters == 0) { Index: filter.c =================================================================== --- filter.c (revision 4677) +++ filter.c (working copy) @@ -23,10 +23,10 @@ * * Contents: * - * mimeAddFilter() - Add a filter to the current MIME database. - * mimeFilter() - Find the fastest way to convert from one type to another. - * compare() - Compare two filter types... - * lookup() - Lookup a filter... + * mimeAddFilter() - Add a filter to the current MIME database. + * mimeFilter() - Find the fastest way to convert from one type to another. + * compare_filters() - Compare two filter types... + * lookup() - Lookup a filter... */ /* @@ -46,7 +46,7 @@ * Local functions... */ -static int compare(mime_filter_t *, mime_filter_t *); +static int compare_filters(mime_filter_t *, mime_filter_t *); static mime_filter_t *lookup(mime_t *, mime_type_t *, mime_type_t *); @@ -120,8 +120,8 @@ strlcpy(temp->filter, filter, sizeof(temp->filter)); if (mime->num_filters > 1) - qsort(mime->filters, mime->num_filters, sizeof(mime_filter_t), - (int (*)(const void *, const void *))compare); + mergesort(mime->filters, mime->num_filters, sizeof(mime_filter_t), + (int (*)(const void *, const void *))compare_filters); } /* @@ -136,21 +136,23 @@ * 'mimeFilter()' - Find the fastest way to convert from one type to another. */ -mime_filter_t * /* O - Array of filters to run */ -mimeFilter(mime_t *mime, /* I - MIME database */ - mime_type_t *src, /* I - Source file type */ - mime_type_t *dst, /* I - Destination file type */ - int *num_filters, /* O - Number of filters to run */ - int max_depth) /* I - Maximum depth of search */ +mime_filter_t * /* O - Array of filters to run */ +mimeFilter(mime_t *mime, /* I - MIME database */ + mime_type_t *src, /* I - Source file type */ + mime_type_t *dst, /* I - Destination file type */ + int *num_filters, /* O - Number of filters to run */ + mime_type_list_t *list) /* I - List of current solution path */ { - int i, j, /* Looping vars */ - num_temp, /* Number of temporary filters */ - num_mintemp, /* Number of filters in the minimum */ - cost, /* Current cost */ - mincost; /* Current minimum */ - mime_filter_t *temp, /* Temporary filter */ - *mintemp, /* Current minimum */ - *current; /* Current filter */ + int i, j, /* Looping vars */ + num_temp, /* Number of temporary filters */ + num_mintemp, /* Number of filters in the minimum */ + cost, /* Current cost */ + mincost; /* Current minimum */ + mime_filter_t *temp, /* Temporary filter */ + *mintemp, /* Current minimum */ + *current; /* Current filter */ + mime_type_list_t leaf, /* Current leaf node in solution path */ + *p; /* List walking var */ /* @@ -162,8 +164,7 @@ dst, dst ? dst->super : "?", dst ? dst->type : "?", num_filters, num_filters ? *num_filters : 0)); - if (mime == NULL || src == NULL || dst == NULL || num_filters == NULL || - max_depth <= 0) + if (mime == NULL || src == NULL || dst == NULL || num_filters == NULL) return (NULL); *num_filters = 0; @@ -200,59 +201,84 @@ } /* + * The leaf is the head of the stack based soultion list... + */ + + leaf.next = list; + + /* * OK, now look for filters from the source type to any other type... */ for (i = mime->num_filters, current = mime->filters; i > 0; i --, current ++) - if (current->src == src) + { + if (current->src != src) + continue; + + /* + * Walk the current solution list to see if this destination type is already + * used as a source type; if it is then avoid the resulting mutual recursion. + */ + + for (p = list; p != NULL; p = p->next) + if (current->dst == p->src) + break; + + if (p) { - /* - * See if we have any filters that can convert from the destination type - * of this filter to the final type... - */ + DEBUG_printf(("short circuiting the %s/%s mutual recursion loop\n", p->src->super, p->src->type)); + continue; + } - if ((temp = mimeFilter(mime, current->dst, dst, &num_temp, - max_depth - 1)) == NULL) - continue; + /* + * See if we have any filters that can convert from the destination type + * of this filter to the final type... + */ - /* - * Found a match; see if this one is less costly than the last (if - * any...) - */ + leaf.src = current->src; - for (j = 0, cost = 0; j < num_temp; j ++) - cost += temp[j].cost; + if ((temp = mimeFilter(mime, current->dst, dst, &num_temp, + &leaf)) == NULL) + continue; - if (cost < mincost) - { - if (mintemp != NULL) - free(mintemp); + /* + * Found a match; see if this one is less costly than the last (if + * any...) + */ - /* - * Hey, we got a match! Add the current filter to the beginning of the - * filter list... - */ + for (j = 0, cost = 0; j < num_temp; j ++) + cost += temp[j].cost; - mintemp = (mime_filter_t *)realloc(temp, sizeof(mime_filter_t) * - (num_temp + 1)); + if (cost < mincost) + { + if (mintemp != NULL) + free(mintemp); - if (mintemp == NULL) - { - *num_filters = 0; - return (NULL); - } + /* + * Hey, we got a match! Add the current filter to the beginning of the + * filter list... + */ - memmove(mintemp + 1, mintemp, num_temp * sizeof(mime_filter_t)); - memcpy(mintemp, current, sizeof(mime_filter_t)); + mintemp = (mime_filter_t *)realloc(temp, sizeof(mime_filter_t) * + (num_temp + 1)); - num_mintemp = num_temp + 1; - mincost = cost; + if (mintemp == NULL) + { + *num_filters = 0; + return (NULL); } - else - free(temp); + + memmove(mintemp + 1, mintemp, num_temp * sizeof(mime_filter_t)); + memcpy(mintemp, current, sizeof(mime_filter_t)); + + num_mintemp = num_temp + 1; + mincost = cost; } + else + free(temp); + } if (mintemp != NULL) { @@ -278,14 +304,14 @@ /* - * 'compare()' - Compare two filter types... + * 'compare_filters()' - Compare two filter types... */ -static int /* O - Comparison result */ -compare(mime_filter_t *f0, /* I - First filter */ - mime_filter_t *f1) /* I - Second filter */ +static int /* O - Comparison result */ +compare_filters(mime_filter_t *f0, /* I - First filter */ + mime_filter_t *f1) /* I - Second filter */ { - int i; /* Result of comparison */ + int i; /* Result of comparison */ if ((i = strcmp(f0->src->super, f1->src->super)) == 0) @@ -317,7 +343,7 @@ return ((mime_filter_t *)bsearch(&key, mime->filters, mime->num_filters, sizeof(mime_filter_t), - (int (*)(const void *, const void *))compare)); + (int (*)(const void *, const void *))compare_filters)); } Index: mime.h =================================================================== --- mime.h (revision 4677) +++ mime.h (working copy) @@ -114,7 +114,13 @@ mime_filter_t *filters; /* Type conversion filters */ } mime_t; +typedef struct mime_type_list_str /**** MIME Type List ****/ +{ + mime_type_t *src; /* Source type */ + struct mime_type_list_str *next; /* Next type */ +} mime_type_list_t; + /* * Functions... */ @@ -135,7 +141,7 @@ extern mime_filter_t *mimeAddFilter(mime_t *mime, mime_type_t *src, mime_type_t *dst, int cost, const char *filter); extern mime_filter_t *mimeFilter(mime_t *mime, mime_type_t *src, mime_type_t *dst, - int *num_filters, int max_depth); + int *num_filters, mime_type_list_t *list); # ifdef _cplusplus }