fitz/heap.h

Index

struct

• fz_int2
• fz_intptr

macro

• HEAP_CMP
• HEAP_CONTAINER_TYPE
• HEAP_DUMP
• HEAP_TYPE_NAME
• MUPDF_FITZ_HEAP_I_KNOW_WHAT_IM_DOING

Heap

This file has preprocessor magic in it to instantiate both prototypes and implementations for heap sorting structures of various different types. Effectively, it’s templating for C.

If you are including this file directly without intending to be instantiating a new set of heap sort functions, you are doing the wrong thing.

This header file declares some useful heap functions. (Heap as in heap sort, not as in memory heap). It uses some clever (read “hacky”) multiple inclusion techniques to allow us to generate multiple different versions of this code. This is kinda like ‘templating’ in C++, but without language support.

For every instance of this code, we end up a heap structure:

typedef struct { int max; int len; *heap; } fz__heap;

This can be created and initialised on the stack in user code using:

fz__heap heap = { 0 };

and some functions.

When is a simple int (or float or similar), the ordering required is obvious, and so the functions are simple (Form 1):

First some to insert elements into the heap:

void fz__heap_insert(fz_context *ctx, fz__heap *heap, v);

Once all the elements have been inserted, the heap can be sorted:

void fz__heap_sort(fz_context *ctx, fz__heap *heap);

Once sorted, repeated elements can be removed:

void fz__heap_uniq(fz_context *ctx, fz__heap *heap);

For more complex TYPEs (such as pointers) the ordering may not be implicit within the , but rather depends upon the data found by dereferencing those pointers. For such types, the functions are modified with a function, of the form used by qsort etc:

int (x, y) that returns 0 for x == y, +ve for x > y, and -ve for x < y.

The functions are modified thus (Form 2):

void fz__heap_insert(fz_context *ctx, fz__heap *heap, v, t); void fz__heap_sort(fz_context *ctx, fz__heap *heap, t); void fz__heap_uniq(fz_context *ctx, fz__heap *heap, t);

Currently, we define:

fz_int_heap Operates on ‘int’ values. Form 1. fz_ptr_heap Operates on ‘void ’ values. Form 2. fz_int2_heap Operates on ’typedef struct { int a; int b} fz_int2’ values, with the sort/uniq being done based on ’a’ alone. Form 1. fz_intptr_heap Operates on ’typedef struct { int a; void b} fz_intptr’ values, with the sort/uniq being done based on ‘a’ alone. Form 1.

Private

Everything after this point is preprocessor magic. Ignore it, and just read the above unless you are wanting to instantiate a new set of functions.

macro MUPDF_FITZ_HEAP_I_KNOW_WHAT_IM_DOING

#define MUPDF_FITZ_HEAP_I_KNOW_WHAT_IM_DOING

macro HEAP_TYPE_NAME

#define HEAP_TYPE_NAME

The name of the heap type to define: fz_TYPE_NAME_heap

macro HEAP_CONTAINER_TYPE

#define HEAP_CONTAINER_TYPE

The type of the container values

macro HEAP_CMP

#define HEAP_CMP(a,b)

The expression to compare two heap values.

macro HEAP_DUMP

#define HEAP_DUMP(CTX, OUT, I, A)

A fz_write_print statement to dump a heap value.

struct fz_int2

struct fz_int2
{
        int a;
        int b;
}

The type for values in a fz_int2_heap.

struct fz_intptr

struct fz_intptr
{
        int a;
        void *b;
}

The type for values in a fz_intptr_heap.