← Back to branch summary

~ubuntu-branches/debian/experimental/cups-filters/experimental

« back to all changes in this revision

Viewing changes to filter/fontembed/frequent.c

  • Committer: Package Import Robot
  • Author(s): Till Kamppeter
  • Date: 2012-07-22 18:57:32 UTC
  • mfrom: (1.1.17)
  • Revision ID: package-import@ubuntu.com-20120722185732-26kkte5p1lth3rt5
Tags: 1.0.20-0bzr1
https://launchpad.net/bugs/1026974
http://bugs.debian.org/670055
* New upstream release
   - pdftops: Added another workaround for Kyocera printers: Some
     models get very slow on images which request interpolation,
     so now we remove the image interpolation requests by additional
     PostScript code only inserted for Kyocera printers (LP: #1026974).
   - Made the Poppler-based filters pdftopdf and pdftoopvp build with
     both Poppler 0.18.x and 0.20.x (Upstream bug #1055).
   - Fixes according to Coverity scan results (Upstream bug #1054).
   - Switched build system to autotools. This especially fixes several
     build problems in Gentoo. Also build-tested with CUPS 1.6.0b1.
   - Fixes for compatibility with clang/gcc-4.7.
   - textonly: Filter did not work as a pipe with copies=1 (Upstream bug
     #1032).
   - texttopdf: Avoid trimming the results of FcFontSort(), as this may
     miss some reasonable candidates under certain circumstances. BTW,
     fix passing a non-pointer as a pointer to "result" (Closes: #670055).
   - Corrected documentation. The option for the maximum image rendering
     resolution in pdftops is "pdftops-max-image-resolution", not
     "pdftops-max-image-resolution-default".
* debian/patches/fcfontsort-no-trim.patch: Removed, fixed upstream.
* debian/rules: Updated options for ./configure and make for the new autotools
  build system.
* debian/watch: Switched to bz2 upstream packages.
* debian/rules, debian/copyright, debian/cups-filters.docs: Updated for
  renamed documentation files.
* debian/control, debian/libfontembed1.install,
  debian/libfontembed-dev.install: Added new binary packages for libfontembed.
* debian/copyright: Updated for recent file additions, and rearrangement of
  directories.

Show diffs side-by-side

added added

removed removed

Lines of Context:
filter/fontembed/frequent.c
1
 
#include "frequent.h"
2
 
#include <assert.h>
3
 
#include <stdlib.h>
4
 
 
5
 
// misra-gries
6
 
// http://www2.research.att.com/~marioh/papers/vldb08-2.pdf
7
 
 
8
 
struct _FREQUENT {
9
 
  int size,czero;
10
 
  char sorted;
11
 
  struct { intptr_t key; int count,zero; } pair[];
12
 
};
13
 
 
14
 
// size is the precision/return size: in sequence with n _add(), it will find at most >size elements with occurence > n/(size+1) times
15
 
FREQUENT *frequent_new(int size) // {{{ - just free() it
16
 
{
17
 
  assert(size>0);
18
 
  FREQUENT *ret=malloc(sizeof(ret[0])+sizeof(ret->pair[0])*size);
19
 
  if (!ret) {
20
 
    return NULL;
21
 
  }
22
 
  ret->size=size;
23
 
  ret->czero=0;
24
 
  ret->sorted=1;
25
 
  int iA;
26
 
  for (iA=0;iA<size;iA++) {
27
 
    ret->pair[iA].key=INTPTR_MIN;
28
 
    ret->pair[iA].count=0;
29
 
    ret->pair[iA].zero=0;
30
 
  }
31
 
 
32
 
  return ret;
33
 
}
34
 
// }}}
35
 
 
36
 
void frequent_add(FREQUENT *freq,intptr_t key) // {{{
37
 
{
38
 
  assert(freq);
39
 
  int iA,zero=-1;
40
 
  for (iA=freq->size-1;iA>=0;iA--) {
41
 
    if (freq->pair[iA].key==key) {
42
 
      freq->pair[iA].count++;
43
 
      freq->sorted=0;
44
 
      return;
45
 
    } else if (freq->pair[iA].count==freq->czero) {
46
 
      zero=iA;
47
 
    }
48
 
  }
49
 
  if (zero>=0) { // insert into set
50
 
    freq->pair[zero].key=key;
51
 
    freq->pair[zero].count++; // i.e. czero+1
52
 
    freq->pair[zero].zero=freq->czero;
53
 
    // if it was sorted, the free entries are at the end. zero points to the first free entry, because of the loop direction
54
 
  } else { // out-of-set count
55
 
    freq->czero++;
56
 
  }
57
 
}
58
 
// }}}
59
 
 
60
 
static int frequent_cmp(const void *a,const void *b) // {{{
61
 
{
62
 
  const typeof(((FREQUENT *)0)->pair[0]) *aa=a;
63
 
  const typeof(((FREQUENT *)0)->pair[0]) *bb=b;
64
 
  return (bb->count-bb->zero)-(aa->count-aa->zero);
65
 
}
66
 
// }}}
67
 
 
68
 
// true frequency is somewhere between (count-zero) and count
69
 
intptr_t frequent_get(FREQUENT *freq,int pos) // {{{
70
 
{
71
 
  assert(freq);
72
 
  if (!freq->sorted) {
73
 
    // sort by (count-zero)
74
 
    qsort(freq->pair,freq->size,sizeof(freq->pair[0]),frequent_cmp);
75
 
    freq->sorted=1;
76
 
  }
77
 
  if ( (pos<0)||(pos>=freq->size) ) {
78
 
    return INTPTR_MIN;
79
 
  }
80
 
  return freq->pair[pos].key;
81
 
}
82
 
// }}}
83