12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 |
- /*
- * algorithm.c
- *
- * Copyright (C) 2019 Aleksandar Andrejevic <theflash@sdf.lonestar.org>
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Affero General Public License as
- * published by the Free Software Foundation, either version 3 of the
- * License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Affero General Public License for more details.
- *
- * You should have received a copy of the GNU Affero General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- */
- #include "crt_priv.h"
- #include <string.h>
- void __CRT_PUBLIC(qsort)(void *base, size_t nmemb, size_t size, int (*compare)(const void*, const void*))
- {
- char *bytes = base, pivot[size], temp[size];
- ptrdiff_t low = 0, high = nmemb - 1;
- if (nmemb <= 1) return;
- __builtin_memcpy(pivot, &bytes[(nmemb / 2 - 1) * size], size);
- for (;;)
- {
- while (compare(&bytes[low * size], pivot) < 0) low++;
- while (compare(&bytes[high * size], pivot) > 0) high--;
- if (low >= high) break;
- __builtin_memcpy(temp, &bytes[low * size], size);
- __builtin_memcpy(&bytes[low * size], &bytes[high * size], size);
- __builtin_memcpy(&bytes[high * size], temp, size);
- }
- __CRT_PUBLIC(qsort)(bytes, high + 1, size, compare);
- __CRT_PUBLIC(qsort)(&bytes[(high + 1) * size], nmemb - (high + 1), size, compare);
- }
- void *__CRT_PUBLIC(bsearch)(const void *key, const void *base, size_t nmemb, size_t size, int (*compare)(const void*, const void*))
- {
- long low = 0;
- long high = nmemb - 1;
- while (low <= high)
- {
- long mid = low + (high - low) / 2;
- void *current = (void*)((uintptr_t)base + mid * size);
- int comp = compare(current, key);
- if (comp < 0) low = mid + 1;
- else if (comp > 0) high = mid - 1;
- else return current;
- }
- return NULL;
- }
|