bgetl() should return uns instead of u32

[libucw.git] / lib / url.c

diff --git a/lib/url.c b/lib/url.c
index da3074bf38429d7f2817c4129559760595a0d247..15a731fde164f2fab86a2707e77f0187d2a71927 100644 (file)
--- a/lib/url.c
+++ b/lib/url.c
@@ -29,9 +29,10 @@
 
 static uns url_ignore_spaces;
 static uns url_ignore_underflow;
-static byte *url_component_separators = "";
+static char *url_component_separators = "";
 static uns url_min_repeat_count = 0x7fffffff;
 static uns url_max_repeat_length = 0;
+static uns url_max_occurences = ~0U;
 
 static struct cf_section url_config = {
   CF_ITEMS {
@@ -40,6 +41,7 @@ static struct cf_section url_config = {
     CF_STRING("ComponentSeparators", &url_component_separators),
     CF_UNS("MinRepeatCount", &url_min_repeat_count),
     CF_UNS("MaxRepeatLength", &url_max_repeat_length),
+    CF_UNS("MaxOccurences", &url_max_occurences),
     CF_END
   }
 };
@@ -667,6 +669,7 @@ int main(int argc, char **argv)
 struct component {
        const byte *start;
        int length;
+       uns count;
        u32 hash;
 };
 
@@ -704,9 +707,9 @@ int
 url_has_repeated_component(const byte *url)
 {
        struct component *comp;
-       uns comps, comp_len, rep_prefix;
+       uns comps, comp_len, rep_prefix, hash_size, *hash, *next;
        const byte *c;
-       uns i;
+       uns i, j, k;
 
        for (comps=0, c=url; c; comps++)
        {
@@ -714,9 +717,9 @@ url_has_repeated_component(const byte *url)
                if (c)
                        c++;
        }
-       if (comps < url_min_repeat_count)
+       if (comps < url_min_repeat_count && comps <= url_max_occurences)
                return 0;
-       comp = alloca(comps * sizeof(struct component));
+       comp = alloca(comps * sizeof(*comp));
        for (i=0, c=url; c; i++)
        {
                comp[i].start = c;
@@ -732,6 +735,30 @@ url_has_repeated_component(const byte *url)
        ASSERT(i == comps);
        for (i=0; i<comps; i++)
                comp[i].hash = hashf(comp[i].start, comp[i].length);
+       if (comps > url_max_occurences)
+       {
+               hash_size = next_table_prime(comps);
+               hash = alloca(hash_size * sizeof(*hash));
+               next = alloca(comps * sizeof(*next));
+               memset(hash, 255, hash_size * sizeof(*hash));
+               for (i=0; i<comps; i++)
+               {
+                       j = comp[i].hash % hash_size;
+                       for (k = hash[j]; ~k && (comp[i].hash != comp[k].hash || comp[i].length != comp[k].length ||
+                           memcmp(comp[k].start, comp[i].start, comp[i].length)); k = next[k]);
+                       if (!~k)
+                       {
+                               next[i] = hash[j];
+                               hash[j] = i;
+                               comp[i].count = 1;
+                       }
+                       else
+                       {
+                               if (comp[k].count++ >= url_max_occurences)
+                                       return 1;
+                       }
+               }
+       }
        for (comp_len = 1; comp_len <= url_max_repeat_length && comp_len <= comps; comp_len++)
                for (rep_prefix = 0; rep_prefix <= comps - comp_len; rep_prefix++)
                        if (repeat_count(comp + rep_prefix, comps - rep_prefix, comp_len) >= url_min_repeat_count)