← Back to branch summary

~snowball-yiddish-dev/snowball-yiddish/trunk

« back to all changes in this revision

Viewing changes to snowball/compiler/sort.c

  • Committer: richard
  • Date: 2003-03-30 12:08:09 UTC
  • Revision ID: svn-v4:633ccae0-01f4-0310-8c99-d3591da6f01f:trunk:216
This module will contain only the code and build system, and documentation
for building and running the stemming library.
All sample data will be in a separate module, and the website will be in
its own module too.

Show diffs side-by-side

added added

removed removed

Lines of Context:
snowball/compiler/sort.c
 
1
 
 
2
#include <stdio.h>
 
3
#include <stdlib.h>   /* malloc, free */
 
4
#include <string.h>   /* memmove */
 
5
 
 
6
#include "header.h"
 
7
 
 
8
static void merge_part(char * p1, char * p1_end,  /* source 1 */
 
9
                       char * p2, char * p2_end,  /* source 2 */
 
10
                       char * s,                  /* destination */
 
11
                       int unit,                  /* size of each item */
 
12
                       int (*f)())                /* comparison routine */
 
13
 
 
14
{   repeat
 
15
    {   if (p1 >= p1_end) { memmove(s, p2, p2_end - p2); return; }
 
16
        if (p2 >= p2_end) { memmove(s, p1, p1_end - p1); return; }
 
17
        if (f(p1, p2) <= 0)
 
18
        {   memmove(s, p1, unit);
 
19
            p1 += unit;
 
20
        } else
 
21
        {   memmove(s, p2, unit);
 
22
            p2 += unit;
 
23
        }
 
24
        s += unit;
 
25
    }
 
26
}
 
27
 
 
28
static void merge_all(char * p, char * p_end,  /* source */
 
29
                      char * s,                /* destination */
 
30
                      int width,               /* size of blocks to merge */
 
31
                      int unit,                /* size of each item */
 
32
                      int (*f)())              /* comparison routine */
 
33
{   repeat
 
34
    {   char * p2 = p + width;
 
35
        char * p3 = p2 + width;
 
36
        if (p3 > p_end)
 
37
        {   p3 = p_end;
 
38
            if (p2 > p_end) p2 = p_end;
 
39
        }
 
40
        merge_part(p, p2, p2, p3, s, unit, f);
 
41
        if (p3 == p_end) return;
 
42
        p = p3; s += width + width;
 
43
    }
 
44
}
 
45
 
 
46
extern void sort(void * p, void * p_end, int unit, int (*f)())
 
47
{   int size = (char *) p_end - (char *) p;
 
48
    char * s = (char *) MALLOC(size);
 
49
    char * s_end = s + size;
 
50
    int width = unit;
 
51
    repeat
 
52
    {   merge_all((char *) p, (char *) p_end, s, width, unit, f); width += width;
 
53
        if (width >= size) { memmove(p, s, size); break; }
 
54
        merge_all(s, s_end, (char *) p, width, unit, f); width += width;
 
55
        if (width >= size) break;
 
56
    }
 
57
    FREE(s);
 
58
}
 
59