← Back to branch summary

~ubuntu-branches/ubuntu/karmic/unsort/karmic

« back to all changes in this revision

Viewing changes to msort.c

  • Committer: Bazaar Package Importer
  • Author(s): Guus Sliepen
  • Date: 2008-06-08 12:53:54 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20080608125354-yizugn2e7fxzxuix
Tags: 1.1.0-1
New upstream release.

Show diffs side-by-side

added added

removed removed

Lines of Context:
msort.c
 
1
/*****************************************************************************
 
2
 
 
3
        unsort - reorder files semi-randomly
 
4
        Copyright (C) 2007, 2008  Wessel Dankers <wsl@fruit.je>
 
5
 
 
6
        This program is free software: you can redistribute it and/or modify
 
7
        it under the terms of the GNU General Public License as published by
 
8
        the Free Software Foundation, either version 3 of the License, or
 
9
        (at your option) any later version.
 
10
 
 
11
        This program is distributed in the hope that it will be useful,
 
12
        but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
        GNU General Public License for more details.
 
15
 
 
16
        You should have received a copy of the GNU General Public License
 
17
        along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
18
 
 
19
        $Id: msort.c 1323 2008-06-07 19:58:01Z wsl $
 
20
        $URL: http://rot.zo.oi/svn/wsl/src/unsort/msort.c $
 
21
 
 
22
*****************************************************************************/
 
23
 
 
24
#include <stdlib.h>
 
25
#include <math.h>
 
26
 
 
27
#include <stdio.h>
 
28
#include <stdint.h>
 
29
#include <inttypes.h>
 
30
 
 
31
#include "msort.h"
 
32
 
 
33
static void msort32_update(uint32_t *dd, uint32_t count, uint32_t o) {
 
34
        uint32_t d, d1, d2;
 
35
        uint32_t o1, o2;
 
36
 
 
37
        if(!count)
 
38
                return;
 
39
 
 
40
        d = dd[o];
 
41
 
 
42
        for(;;) {
 
43
                o1 = o * 2 + 1;
 
44
                if(o1 >= count)
 
45
                        break;
 
46
                d1 = dd[o1];
 
47
 
 
48
                o2 = o * 2 + 2;
 
49
                if(o2 < count) {
 
50
                        d2 = dd[o2];
 
51
                        if(d2 > d1) {
 
52
                                o1 = o2;
 
53
                                d1 = d2;
 
54
                        }
 
55
                }
 
56
 
 
57
                if(d > d1)
 
58
                        break;
 
59
 
 
60
                dd[o1] = d;
 
61
                dd[o] = d1;
 
62
                o = o1;
 
63
        }
 
64
}
 
65
 
 
66
void msort32(uint32_t *dd, uint32_t count) {
 
67
        uint32_t u;
 
68
 
 
69
        if(!dd || !count)
 
70
                return;
 
71
 
 
72
        for(u = count / 2; u; u--)
 
73
                msort32_update(dd, count, u);
 
74
        msort32_update(dd, count, u);
 
75
 
 
76
        while(count-- > 1) {
 
77
                u = dd[0];
 
78
                dd[0] = dd[count];
 
79
                dd[count] = u;
 
80
                msort32_update(dd, count, 0);
 
81
        }
 
82
}