merge.c File Reference

#include "system.h"
#include <rpmiotypes.h>
#include <rpmtag.h>
#include <rpmdb.h>
#include "debug.h"

Include dependency graph for merge.c:

Go to the source code of this file.

Macros
#define	NATURAL
#define	THRESHOLD   16 /* Best choice for natural merge cut-off. */
#define	ISIZE   sizeof(int)
#define	PSIZE   sizeof(unsigned char *)
#define	ICOPY_LIST(src, dst, last)
#define	ICOPY_ELT(src, dst, i)
#define	CCOPY_LIST(src, dst, last)
#define	CCOPY_ELT(src, dst, i)
#define	EVAL(p)
#define	swap(a, b)
#define	reverse(bot, top)

Functions
static void	insertionsort (unsigned char *a, size_t n, size_t size, int(*cmp)(const void *, const void *))
static void	setup (unsigned char *list1, unsigned char *list2, size_t n, size_t size, int(*cmp)(const void *, const void *))
int	rpm_mergesort (void *base, size_t nmemb, size_t size, int(*cmp)(const void *, const void *))
	Mergesort, same arguments as qsort(2).

Macro Definition Documentation

#define CCOPY_ELT	(		src,
			dst,
			i
	)

Value:

do                                      \
                *dst++ = *src++;                \
        while (i -= 1)

Definition at line 79 of file merge.c.

Referenced by rpm_mergesort().

#define CCOPY_LIST	(		src,
			dst,
			last
	)

Value:

do                                      \
                *dst++ = *src++;                \
        while (src < last)

Definition at line 75 of file merge.c.

Referenced by rpm_mergesort().

#define EVAL

(

p

)

Value:

(unsigned char **)                                      \
    ((unsigned char *)0 +                                               \
        (((unsigned char *)p + PSIZE - 1 - (unsigned char *) 0) & ~(PSIZE - 1)))

Definition at line 90 of file merge.c.

Referenced by rpm_mergesort(), and setup().

#define ICOPY_ELT	(		src,
			dst,
			i
	)

Value:

do                                                      \
        *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE;  \
        while (i -= ISIZE)

Definition at line 70 of file merge.c.

Referenced by rpm_mergesort().

#define ICOPY_LIST	(		src,
			dst,
			last
	)

Value:

do                                                      \
        *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE;    \
        while(src < last)

Definition at line 66 of file merge.c.

Referenced by rpm_mergesort().

#define ISIZE   sizeof(int)

Definition at line 64 of file merge.c.

Referenced by rpm_mergesort().

#define NATURAL

Definition at line 49 of file merge.c.

#define PSIZE   sizeof(unsigned char *)

Definition at line 65 of file merge.c.

Referenced by rpm_mergesort().

#define reverse	(		bot,
			top
	)

Value:

{                               \
        s = top;                                        \
        do {                                            \
                i = (int) size;                         \
                do {                                    \
                        tmp = *bot; *bot++ = *s; *s++ = tmp; \
                } while (--i);                          \
                s -= size2;                             \
        } while(bot < s);                               \
}

Definition at line 102 of file merge.c.

Referenced by dnlInitIterator(), fsmSetup(), iosmSetup(), mapInitIterator(), and setup().

#define swap	(		a,
			b
	)

Value:

{                                       \
                s = b;                                  \
                i = (int) size;                         \
                do {                                    \
                        tmp = *a; *a++ = *s; *s++ = tmp; \
                } while (--i);                          \
                a -= size;                              \
        }

Definition at line 94 of file merge.c.

Referenced by insertionsort(), and setup().

#define THRESHOLD   16 /* Best choice for natural merge cut-off. */

Definition at line 50 of file merge.c.

Referenced by setup().

Function Documentation

static void insertionsort ( unsigned char *  a, size_t  n, size_t  size, int(*)(const void *, const void *)  cmp  )

static

Definition at line 118 of file merge.c.

References swap.

Referenced by setup().

int rpm_mergesort	(	void *	base,
		size_t	nmemb,
		size_t	size,
		int(*)(const void *, const void *)	cmp
	)

Mergesort, same arguments as qsort(2).

Definition at line 213 of file merge.c.

References CCOPY_ELT, CCOPY_LIST, errno, EVAL, ICOPY_ELT, ICOPY_LIST, ISIZE, PSIZE, and setup().

Referenced by rpmmiSort().

static void setup ( unsigned char *  list1, unsigned char *  list2, size_t  n, size_t  size, int(*)(const void *, const void *)  cmp  )

static

Definition at line 141 of file merge.c.

References EVAL, insertionsort(), reverse, swap, and THRESHOLD.

Referenced by rpm_mergesort().