commit d55636a2084ea8c28a6b58d310e86c8a36a5d710
parent 053934bc19eebd3b7cb44312d451cfe8789d4dd4
Author: Plat <plat@stellar-nexus.ru>
Date: Tue, 25 Nov 2025 15:08:19 +0000
Made the code compile
Diffstat:
13 files changed, 317 insertions(+), 22 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,3 +1,4 @@
+include config.mk
BIN1 =\
bell \
greed \
@@ -9,18 +10,23 @@ BIN2 =\
insert \
shell
-include config.mk
-
+LIBS = ${wildcard libutil/*.c}
+OBJS = ${LIBS:.c=.o}
all: ${BIN1} ${BIN2}
-${BIN1}:
- ${CC} ${CFLAGS} ${LDFLAGS} -D"$@" knapsack_single.c knapsack.c -o "$@"
- strip "$@"
+${BIN1}: ${OBJS}
+ ${CC} ${CFLAGS} -D$@ -o $@ knapsack_single.c knapsack.c ${OBJS} ${LDFLAGS}
+ strip $@
${BIN2}:
- ${CC} ${CFLAGS} ${LDFLAGS} -D"$@" sort_single.c sort.c -o "$@"
- strip "$@"
+ ${CC} ${CFLAGS} -D$@ -o $@ sort_single.c sort.c ${OBJS} ${LDFLAGS}
+ strip $@
+
+%.o: %.c
+ ${CC} ${CFLAGS} -c $< -o $@
clean:
- rm -f ${BIN1} ${BIN2}
+ rm -f ${BIN1} ${BIN2} ${OBJS}
+
+.PHONY: all clean
diff --git a/config.mk b/config.mk
@@ -0,0 +1,3 @@
+CC = gcc-cc
+CFLAGS = -pipe -Ofast -march=native -flto -fomit-frame-pointer -ffunction-sections -fdata-sections -fmerge-all-constants -fno-tree-vectorize
+LDFLAGS = -Wl,--gc-sections -static
diff --git a/knapsack.c b/knapsack.c
@@ -7,7 +7,7 @@
int
knapsack_bell(unsigned int k, unsigned int w, int m[k], int c[k], int out[k])
{
- int (*opt)[w+1] = malloc(sizeof(*opt * (k+1)));
+ int (*opt)[w+1] = malloc(sizeof(*opt) * (k+1));
if (!opt) {
errno = ENOMEM;
return -1;
diff --git a/knapsack.h b/knapsack.h
@@ -1,3 +1,4 @@
+#define KNAPSACK_NAME "knapsack"
int knapsack_bell(unsigned int k, unsigned int w, int m[k], int c[k], int out[k]);
int knapsack_greed(unsigned int k, unsigned int w, int m[k], int c[k], int out[k]);
int knapsack_full(unsigned int k, unsigned int w, int m[k], int c[k], int out[k]);
diff --git a/knapsack_single.c b/knapsack_single.c
@@ -17,7 +17,7 @@
#endif
static long long int
-input(long long mivnal, long long maxval)
+input(long long minval, long long maxval)
{
unsigned char len = 0, arr[UCHAR_MAX];
@@ -31,6 +31,7 @@ input(long long mivnal, long long maxval)
int
main(void)
{
+ argv0 = KNAPSACK_NAME;
unsigned int k = input(0, UINT_MAX),
w = input(0, UINT_MAX);
int *m = emalloc(sizeof(*m) * k),
@@ -41,15 +42,13 @@ main(void)
m[len] = input(0, INT_MAX);
for (len = 0; len < k; ++len)
c[len] = input(0, INT_MAX);
- if (getchar() != EOF)
- weprintf("More than %d numbers provided - ignoring them\n", k);
int *out = emalloc(sizeof(*out) * k);
clock_t solve_time = clock();
if (knapsack(k, w, m, c, out) < 0)
eprintf("knapsack:");
solve_time = clock() - solve_time;
- printf("%f\n", solve_time / CLOCKS_PER_SEC);
+ printf("%f\n", (double)solve_time / CLOCKS_PER_SEC);
for (len = 0; len + 1 < k && out[len+1] > 0; ++len)
printf("%d ", out[len]);
printf("%d\n", out[len]);
diff --git a/libutil/LICENSE b/libutil/LICENSE
@@ -0,0 +1,63 @@
+MIT License
+
+© 2011 Connor Lane Smith <cls@lubutu.com>
+© 2011-2016 Dimitris Papastamos <sin@2f30.org>
+© 2014-2016 Laslo Hunhold <dev@frign.de>
+
+Permission is hereby granted, free of charge, to any person obtaining a
+copy of this software and associated documentation files (the "Software"),
+to deal in the Software without restriction, including without limitation
+the rights to use, copy, modify, merge, publish, distribute, sublicense,
+and/or sell copies of the Software, and to permit persons to whom the
+Software is furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
+
+Authors/contributors include:
+
+© 2011 Kamil Cholewiński <harry666t@gmail.com>
+© 2011 Rob Pilling <robpilling@gmail.com>
+© 2011 Hiltjo Posthuma <hiltjo@codemadness.org>
+© 2011 pancake <pancake@youterm.com>
+© 2011 Random832 <random832@fastmail.us>
+© 2012 William Haddon <william@haddonthethird.net>
+© 2012 Kurt H. Maier <khm@sciops.net>
+© 2012 Christoph Lohmann <20h@r-36.net>
+© 2012 David Galos <galosd83@students.rowan.edu>
+© 2012 Robert Ransom <rransom.8774@gmail.com>
+© 2013 Jakob Kramer <jakob.kramer@gmx.de>
+© 2013 Anselm R Garbe <anselm@garbe.us>
+© 2013 Truls Becken <truls.becken@gmail.com>
+© 2013 dsp <dsp@2f30.org>
+© 2013 Markus Teich <markus.teich@stusta.mhn.de>
+© 2013 Jesse Ogle <jesse.p.ogle@gmail.com>
+© 2013 Lorenzo Cogotti <miciamail@hotmail.it>
+© 2013 Federico G. Benavento <benavento@gmail.com>
+© 2013 Roberto E. Vargas Caballero <k0ga@shike2.com>
+© 2013 Christian Hesse <mail@eworm.de>
+© 2013 Markus Wichmann <nullplan@gmx.net>
+© 2014 Silvan Jegen <s.jegen@gmail.com>
+© 2014 Daniel Bainton <dpb@driftaway.org>
+© 2014 Tuukka Kataja <stuge@xor.fi>
+© 2014 Jeffrey Picard <jeff@jeffreypicard.com>
+© 2014 Evan Gates <evan.gates@gmail.com>
+© 2014 Michael Forney <mforney@mforney.org>
+© 2014 Ari Malinen <ari.malinen@gmail.com>
+© 2014 Brandon Mulcahy <brandon@jangler.info>
+© 2014 Adria Garriga <rhaps0dy@installgentoo.com>
+© 2014-2015 Greg Reagle <greg.reagle@umbc.edu>
+© 2015 Tai Chi Minh Ralph Eastwood <tcmreastwood@gmail.com>
+© 2015 Quentin Rameau <quinq@quinq.eu.org>
+© 2015 Dionysis Grigoropoulos <info@erethon.com>
+© 2015 Wolfgang Corcoran-Mathe <wcm@sigwinch.xyz>
+© 2016 Mattias Andrée <maandree@kth.se>
+© 2016 Eivind Uggedal <eivind@uggedal.com>
diff --git a/libutil/ealloc.c b/libutil/ealloc.c
@@ -0,0 +1,46 @@
+#include <stdlib.h>
+#include <string.h>
+
+#include "../util.h"
+
+void *
+ecalloc(size_t nmemb, size_t size)
+{
+ void *p;
+
+ p = calloc(nmemb, size);
+ if (!p)
+ eprintf("calloc: out of memory\n");
+ return p;
+}
+
+void *
+emalloc(size_t size)
+{
+ void *p;
+
+ p = malloc(size);
+ if (!p)
+ eprintf("malloc: out of memory\n");
+ return p;
+}
+
+void *
+erealloc(void *p, size_t size)
+{
+ p = realloc(p, size);
+ if (!p)
+ eprintf("realloc: out of memory\n");
+ return p;
+}
+
+char *
+estrdup(const char *s)
+{
+ char *p;
+
+ p = strdup(s);
+ if (!p)
+ eprintf("strdup: out of memory\n");
+ return p;
+}
diff --git a/libutil/eprintf.c b/libutil/eprintf.c
@@ -0,0 +1,64 @@
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "../util.h"
+
+char *argv0;
+
+static void venprintf(int, const char *, va_list);
+
+void
+eprintf(const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ venprintf(1, fmt, ap);
+ va_end(ap);
+}
+
+void
+enprintf(int status, const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ venprintf(status, fmt, ap);
+ va_end(ap);
+}
+
+void
+venprintf(int status, const char *fmt, va_list ap)
+{
+ if (strncmp(fmt, "usage", strlen("usage")))
+ fprintf(stderr, "%s: ", argv0);
+
+ vfprintf(stderr, fmt, ap);
+
+ if (fmt[0] && fmt[strlen(fmt)-1] == ':') {
+ fputc(' ', stderr);
+ perror(NULL);
+ }
+
+ exit(status);
+}
+
+void
+weprintf(const char *fmt, ...)
+{
+ va_list ap;
+
+ if (strncmp(fmt, "usage", strlen("usage")))
+ fprintf(stderr, "%s: ", argv0);
+
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+
+ if (fmt[0] && fmt[strlen(fmt)-1] == ':') {
+ fputc(' ', stderr);
+ perror(NULL);
+ }
+}
diff --git a/libutil/strtonum.c b/libutil/strtonum.c
@@ -0,0 +1,85 @@
+/* $OpenBSD: strtonum.c,v 1.7 2013/04/17 18:40:58 tedu Exp $ */
+
+/*
+ * Copyright (c) 2004 Ted Unangst and Todd Miller
+ * All rights reserved.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <limits.h>
+#include <stdlib.h>
+
+#include "../util.h"
+
+#define INVALID 1
+#define TOOSMALL 2
+#define TOOLARGE 3
+
+long long
+strtonum(const char *numstr, long long minval, long long maxval,
+ const char **errstrp)
+{
+ long long ll = 0;
+ int error = 0;
+ char *ep;
+ struct errval {
+ const char *errstr;
+ int err;
+ } ev[4] = {
+ { NULL, 0 },
+ { "invalid", EINVAL },
+ { "too small", ERANGE },
+ { "too large", ERANGE },
+ };
+
+ ev[0].err = errno;
+ errno = 0;
+ if (minval > maxval) {
+ error = INVALID;
+ } else {
+ ll = strtoll(numstr, &ep, 10);
+ if (numstr == ep || *ep != '\0')
+ error = INVALID;
+ else if ((ll == LLONG_MIN && errno == ERANGE) || ll < minval)
+ error = TOOSMALL;
+ else if ((ll == LLONG_MAX && errno == ERANGE) || ll > maxval)
+ error = TOOLARGE;
+ }
+ if (errstrp != NULL)
+ *errstrp = ev[error].errstr;
+ errno = ev[error].err;
+ if (error)
+ ll = 0;
+
+ return (ll);
+}
+
+long long
+enstrtonum(int status, const char *numstr, long long minval, long long maxval)
+{
+ const char *errstr;
+ long long ll;
+
+ ll = strtonum(numstr, minval, maxval, &errstr);
+ if (errstr)
+ enprintf(status, "strtonum %s: %s\n", numstr, errstr);
+ return ll;
+}
+
+long long
+estrtonum(const char *numstr, long long minval, long long maxval)
+{
+ return enstrtonum(1, numstr, minval, maxval);
+}
diff --git a/sort.c b/sort.c
@@ -36,7 +36,8 @@ insert_sort(unsigned int n, int a[n])
int key;
for (unsigned int i = 1; i < n; ++i) {
key = a[i];
- for (unsigned int j = i - 1; j >= 0 && a[j] > key; --j)
+ long j = i - 1; /* j has to be signed - use long */
+ for (; j >= 0 && a[j] > key; --j)
a[j+1] = a[j];
a[j+1] = key;
}
@@ -49,7 +50,8 @@ shell_sort(unsigned int n, int a[n])
for (unsigned int gap = n/2; gap > 0; gap /= 2) {
for (unsigned int i = gap; i < n; ++i) {
tmp = a[i];
- for (unsigned int j = i; j >= gap && a[j-gap] > tmp; j -= gap)
+ unsigned int j = i;
+ for (; j >= gap && a[j-gap] > tmp; j -= gap)
a[j] = a[j-gap];
a[j] = tmp;
}
diff --git a/sort.h b/sort.h
@@ -1,3 +1,4 @@
+#define SORT_NAME "sort"
void bubble_sort(unsigned int n, int a[n]);
void choice_sort(unsigned int n, int a[n]);
void insert_sort(unsigned int n, int a[n]);
diff --git a/sort_single.c b/sort_single.c
@@ -19,7 +19,7 @@
#endif
static long long int
-input(long long mivnal, long long maxval)
+input(long long minval, long long maxval)
{
unsigned char len = 0, arr[UCHAR_MAX];
@@ -33,19 +33,18 @@ input(long long mivnal, long long maxval)
int
main(void)
{
- unsigned int n = input(0, UINT_MAX),
+ argv0 = SORT_NAME;
+ unsigned int n = input(0, UINT_MAX);
int *arr = emalloc(sizeof(*arr) * n);
unsigned int len;
for (len = 0; len < n; ++len)
arr[len] = input(0, INT_MAX);
- if (getchar() != EOF)
- weprintf("More than %d numbers provided - ignoring them\n", n);
clock_t solve_time = clock();
sort(n, arr);
solve_time = clock() - solve_time;
- printf("%f\n", solve_time / CLOCKS_PER_SEC);
- for (len = 0; len < k; ++len)
- printf("%d\n", out[len]);
+ printf("%f\n", (double)solve_time / CLOCKS_PER_SEC);
+ for (len = 0; len < n; ++len)
+ printf("%d\n", arr[len]);
}
diff --git a/util.h b/util.h
@@ -0,0 +1,26 @@
+#undef MIN
+#define MIN(x,y) ((x) < (y) ? (x) : (y))
+#undef MAX
+#define MAX(x,y) ((x) > (y) ? (x) : (y))
+
+#define LEN(x) (sizeof (x) / sizeof *(x))
+
+/* eprintf.c */
+extern char *argv0;
+
+/* ealloc.c */
+void *ecalloc(size_t, size_t);
+void *emalloc(size_t size);
+void *erealloc(void *, size_t);
+char *estrdup(const char *);
+
+/* eprintf.c */
+void enprintf(int, const char *, ...);
+void eprintf(const char *, ...);
+void weprintf(const char *, ...);
+
+#undef strtonum
+#define strtonum xstrtonum
+long long strtonum(const char *, long long, long long, const char **);
+long long enstrtonum(int, const char *, long long, long long);
+long long estrtonum(const char *, long long, long long);
