123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 |
- /*
- * algorithm.c
- *
- * Copyright (C) 2017 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 <string.h>
- void qsort(void *base, size_t nmemb, size_t size, int (*compare)(const void*, const void*))
- {
- void *pivot = (void*)((uintptr_t)base + (nmemb / 2) * size);
- void *temp = __builtin_alloca(size);
- if (nmemb <= 1) return;
- size_t low = 0;
- size_t high = nmemb - 1;
- for (;;)
- {
- while (compare((void*)((uintptr_t)base + low * size), pivot) < 0) low++;
- while (compare((void*)((uintptr_t)base + high * size), pivot) > 0) high--;
- if (low >= high) break;
- memcpy(temp, (void*)((uintptr_t)base + low * size), size);
- memcpy((void*)((uintptr_t)base + low * size), (void*)((uintptr_t)base + high * size), size);
- memcpy((void*)((uintptr_t)base + high * size), temp, size);
- }
- qsort(base, high, size, compare);
- qsort((void*)((size_t)base + high * size), nmemb - high, size, compare);
- }
- void *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;
- }
|