[pcsx_rearmed.git] / deps / libchdr / deps / lzma-19.00 / src / Sort.c

/* Sort.c -- Sort functions
2014-04-05 : Igor Pavlov : Public domain */

#include "Precomp.h"

#include "Sort.h"

#define HeapSortDown(p, k, size, temp) \
  { for (;;) { \
    size_t s = (k << 1); \
    if (s > size) break; \
    if (s < size && p[s + 1] > p[s]) s++; \
    if (temp >= p[s]) break; \
    p[k] = p[s]; k = s; \
  } p[k] = temp; }

void HeapSort(UInt32 *p, size_t size)
{
  if (size <= 1)
    return;
  p--;
  {
    size_t i = size / 2;
    do
    {
      UInt32 temp = p[i];
      size_t k = i;
      HeapSortDown(p, k, size, temp)
    }
    while (--i != 0);
  }
  /*
  do
  {
    size_t k = 1;
    UInt32 temp = p[size];
    p[size--] = p[1];
    HeapSortDown(p, k, size, temp)
  }
  while (size > 1);
  */
  while (size > 3)
  {
    UInt32 temp = p[size];
    size_t k = (p[3] > p[2]) ? 3 : 2;
    p[size--] = p[1];
    p[1] = p[k];
    HeapSortDown(p, k, size, temp)
  }
  {
    UInt32 temp = p[size];
    p[size] = p[1];
    if (size > 2 && p[2] < temp)
    {
      p[1] = p[2];
      p[2] = temp;
    }
    else
      p[1] = temp;
  }
}

void HeapSort64(UInt64 *p, size_t size)
{
  if (size <= 1)
    return;
  p--;
  {
    size_t i = size / 2;
    do
    {
      UInt64 temp = p[i];
      size_t k = i;
      HeapSortDown(p, k, size, temp)
    }
    while (--i != 0);
  }
  /*
  do
  {
    size_t k = 1;
    UInt64 temp = p[size];
    p[size--] = p[1];
    HeapSortDown(p, k, size, temp)
  }
  while (size > 1);
  */
  while (size > 3)
  {
    UInt64 temp = p[size];
    size_t k = (p[3] > p[2]) ? 3 : 2;
    p[size--] = p[1];
    p[1] = p[k];
    HeapSortDown(p, k, size, temp)
  }
  {
    UInt64 temp = p[size];
    p[size] = p[1];
    if (size > 2 && p[2] < temp)
    {
      p[1] = p[2];
      p[2] = temp;
    }
    else
      p[1] = temp;
  }
}

/*
#define HeapSortRefDown(p, vals, n, size, temp) \
  { size_t k = n; UInt32 val = vals[temp]; for (;;) { \
    size_t s = (k << 1); \
    if (s > size) break; \
    if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
    if (val >= vals[p[s]]) break; \
    p[k] = p[s]; k = s; \
  } p[k] = temp; }

void HeapSortRef(UInt32 *p, UInt32 *vals, size_t size)
{
  if (size <= 1)
    return;
  p--;
  {
    size_t i = size / 2;
    do
    {
      UInt32 temp = p[i];
      HeapSortRefDown(p, vals, i, size, temp);
    }
    while (--i != 0);
  }
  do
  {
    UInt32 temp = p[size];
    p[size--] = p[1];
    HeapSortRefDown(p, vals, 1, size, temp);
  }
  while (size > 1);
}
*/
Commit	Line	Data
b24e7fce	1	/* Sort.c -- Sort functions
	2	2014-04-05 : Igor Pavlov : Public domain */
	3
	4	#include "Precomp.h"
	5
	6	#include "Sort.h"
	7
	8	#define HeapSortDown(p, k, size, temp) \
	9	{ for (;;) { \
	10	size_t s = (k << 1); \
	11	if (s > size) break; \
	12	if (s < size && p[s + 1] > p[s]) s++; \
	13	if (temp >= p[s]) break; \
	14	p[k] = p[s]; k = s; \
	15	} p[k] = temp; }
	16
	17	void HeapSort(UInt32 *p, size_t size)
	18	{
	19	if (size <= 1)
	20	return;
	21	p--;
	22	{
	23	size_t i = size / 2;
	24	do
	25	{
	26	UInt32 temp = p[i];
	27	size_t k = i;
	28	HeapSortDown(p, k, size, temp)
	29	}
	30	while (--i != 0);
	31	}
	32	/*
	33	do
	34	{
	35	size_t k = 1;
	36	UInt32 temp = p[size];
	37	p[size--] = p[1];
	38	HeapSortDown(p, k, size, temp)
	39	}
	40	while (size > 1);
	41	*/
	42	while (size > 3)
	43	{
	44	UInt32 temp = p[size];
	45	size_t k = (p[3] > p[2]) ? 3 : 2;
	46	p[size--] = p[1];
	47	p[1] = p[k];
	48	HeapSortDown(p, k, size, temp)
	49	}
	50	{
	51	UInt32 temp = p[size];
	52	p[size] = p[1];
	53	if (size > 2 && p[2] < temp)
	54	{
	55	p[1] = p[2];
	56	p[2] = temp;
	57	}
	58	else
	59	p[1] = temp;
	60	}
	61	}
	62
	63	void HeapSort64(UInt64 *p, size_t size)
	64	{
65	if (size <= 1)
66	return;
67	p--;
68	{
69	size_t i = size / 2;
70	do
71	{
72	UInt64 temp = p[i];
73	size_t k = i;
74	HeapSortDown(p, k, size, temp)
75	}
76	while (--i != 0);
77	}
78	/*
79	do
80	{
81	size_t k = 1;
82	UInt64 temp = p[size];
83	p[size--] = p[1];
84	HeapSortDown(p, k, size, temp)
85	}
86	while (size > 1);
87	*/
88	while (size > 3)
89	{
90	UInt64 temp = p[size];
91	size_t k = (p[3] > p[2]) ? 3 : 2;
92	p[size--] = p[1];
93	p[1] = p[k];
94	HeapSortDown(p, k, size, temp)
95	}
96	{
97	UInt64 temp = p[size];
98	p[size] = p[1];
99	if (size > 2 && p[2] < temp)
100	{
101	p[1] = p[2];
102	p[2] = temp;
103	}
104	else
105	p[1] = temp;
106	}
107	}
108
109	/*
110	#define HeapSortRefDown(p, vals, n, size, temp) \
111	{ size_t k = n; UInt32 val = vals[temp]; for (;;) { \
112	size_t s = (k << 1); \
113	if (s > size) break; \
114	if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \
115	if (val >= vals[p[s]]) break; \
116	p[k] = p[s]; k = s; \
117	} p[k] = temp; }
118
119	void HeapSortRef(UInt32 p, UInt32 vals, size_t size)
120	{
121	if (size <= 1)
122	return;
123	p--;
124	{
125	size_t i = size / 2;
126	do
127	{
128	UInt32 temp = p[i];
129	HeapSortRefDown(p, vals, i, size, temp);
130	}
131	while (--i != 0);
132	}
133	do
134	{
135	UInt32 temp = p[size];
136	p[size--] = p[1];
137	HeapSortRefDown(p, vals, 1, size, temp);
138	}
139	while (size > 1);
140	}
141	*/