libparanoia/isort.c

   1 /*
   2  * This file has been modified for the cdrkit suite.
   3  *
   4  * The behaviour and appearence of the program code below can differ to a major
   5  * extent from the version distributed by the original author(s).
   6  *
   7  * For details, see Changelog file distributed with the cdrkit package. If you
   8  * received this file from another source then ask the distributing person for
   9  * a log of modifications.
  10  *
  11  */
  12
  13 /* @(#)isort.c  1.14 04/02/20 J. Schilling from cdparanoia-III-alpha9.8 */
  14 /*
  15  *      Modifications to make the code portable Copyright (c) 2002 J. Schilling
  16  */
  17 /*
  18  * CopyPolicy: GNU Public License 2 applies
  19  * Copyright (C) by Monty (xiphmont@mit.edu)
  20  *
  21  * sorted vector abstraction for paranoia
  22  *
  23  */
  24
  25 /*
  26  * Old isort got a bit complex.  This re-constrains complexity to
  27  * give a go at speed through a more alpha-6-like mechanism.
  28  */
  29
  30 #include <mconfig.h>
  31 #include <stdxlib.h>
  32 #include <standard.h>
  33 #include <utypes.h>
  34 #include <strdefs.h>
  35 #include "p_block.h"
  36 #include "isort.h"
  37 #include "pmalloc.h"
  38
  39 sort_info *sort_alloc(long size);
  40 void sort_unsortall(sort_info * i);
  41 void sort_free(sort_info * i);
  42 void sort_sort(sort_info * i, long sortlo, long sorthi);
  43 void sort_setup(sort_info * i, Int16_t * vector, long *abspos, long size,
  44                                          long sortlo, long sorthi);
  45 sort_link *sort_getmatch(sort_info * i, long post, long overlap, int value);
  46 sort_link *sort_nextmatch(sort_info * i, sort_link * prev);
  47
  48
  49 sort_info *sort_alloc(long size)
  50 {
  51         sort_info       *ret = _pcalloc(1, sizeof (sort_info));
  52
  53         ret->vector = NULL;
  54         ret->sortbegin = -1;
  55         ret->size = -1;
  56         ret->maxsize = size;
  57
  58         ret->head = _pcalloc(65536, sizeof (sort_link *));
  59         ret->bucketusage = _pmalloc(65536 * sizeof (long));
  60         ret->revindex = _pcalloc(size, sizeof (sort_link));
  61         ret->lastbucket = 0;
  62
  63         return (ret);
  64 }
  65
  66 void sort_unsortall(sort_info *i)
  67 {
  68         if (i->lastbucket > 2000) {     /* a guess */
  69                 memset(i->head, 0, 65536 * sizeof (sort_link *));
  70         } else {
  71                 long    b;
  72
  73                 for (b = 0; b < i->lastbucket; b++)
  74                         i->head[i->bucketusage[b]] = NULL;
  75         }
  76
  77         i->lastbucket = 0;
  78         i->sortbegin = -1;
  79 }
  80
  81 void sort_free(sort_info *i)
  82 {
  83         _pfree(i->revindex);
  84         _pfree(i->head);
  85         _pfree(i->bucketusage);
  86         _pfree(i);
  87 }
  88
  89 void sort_sort(sort_info *i, long sortlo, long sorthi)
  90 {
  91         long    j;
  92
  93         for (j = sorthi - 1; j >= sortlo; j--) {
  94                 sort_link       **hv = i->head + i->vector[j] + 32768;
  95                 sort_link        *l = i->revindex + j;
  96
  97                 if (*hv == NULL) {
  98                         i->bucketusage[i->lastbucket] = i->vector[j] + 32768;
  99                         i->lastbucket++;
 100                 }
 101                 l->next = *hv;
 102                 *hv = l;
 103         }
 104         i->sortbegin = 0;
 105 }
 106
 107 /*
 108  * size *must* be less than i->maxsize
 109  */
 110 void sort_setup(sort_info *i, Int16_t *vector, long *abspos, long size,
 111                 long sortlo, long sorthi)
 112 {
 113         if (i->sortbegin != -1)
 114                 sort_unsortall(i);
 115
 116         i->vector = vector;
 117         i->size = size;
 118         i->abspos = abspos;
 119
 120         i->lo = min(size, max(sortlo - *abspos, 0));
 121         i->hi = max(0, min(sorthi - *abspos, size));
 122 }
 123
 124 sort_link *sort_getmatch(sort_info *i, long post, long overlap, int value)
 125 {
 126         sort_link       *ret;
 127
 128         if (i->sortbegin == -1)
 129                 sort_sort(i, i->lo, i->hi);
 130         /*
 131          * Now we reuse lo and hi
 132          */
 133         post = max(0, min(i->size, post));
 134         i->val = value + 32768;
 135         i->lo = max(0, post - overlap);         /* absolute position */
 136         i->hi = min(i->size, post + overlap);   /* absolute position */
 137
 138         ret = i->head[i->val];
 139         while (ret) {
 140                 if (ipos(i, ret) < i->lo) {
 141                         ret = ret->next;
 142                 } else {
 143                         if (ipos(i, ret) >= i->hi)
 144                                 ret = NULL;
 145                         break;
 146                 }
 147         }
 148 /*      i->head[i->val]=ret; */
 149         return (ret);
 150 }
 151
 152 sort_link *sort_nextmatch(sort_info *i, sort_link *prev)
 153 {
 154         sort_link       *ret = prev->next;
 155
 156         if (!ret || ipos(i, ret) >= i->hi)
 157                 return (NULL);
 158         return (ret);
 159 }