fast getline for busybox (proof of concept, untested)

Rich Felker dalias at aerifal.cx
Thu Jun 1 02:24:30 UTC 2006


Here is the improved version (actually 2 versions) which should be
marginally faster in the common case where lines are short and eof is
not reached.

Rich

-------------- next part --------------
#include <stdio.h>
#include <string.h>
#include <libbb.h>

size_t fgets_embedded_nul(char *s, size_t n, FILE *f)
{
#if 0
	// Optimal if and only if scanf for %[ is optimized well
	char tmp[sizeof "%[^\n]%zn" + 3*sizeof(size_t)];
	size_t l = 0;
	int c;
	if (n < 2) {
		if (n) *s = 0;
		return 0;
	}
	if (n > 2) { // Zero field width to scanf is illegal
		sprintf(tmp, "%%%zu[^\n]%%zn", n-2);
		fscanf(f, tmp, s, &l);
	}
	if ((c = getc(f)) >= 0) s[l++] = c;
	s[l] = 0;
	return l;
#else
	// Probably fastest in all actual implementations
	char *p;
	memset(s, 0, n);
	if (!fgets(s, n, f)) return 0;
	if ((p = memchr(s, '\n', n))) return p-s+1;
	return n-1;
#endif
}

char *bb_getline_embedded_nul(FILE *f, size_t *n)
{
	size_t len = 0, size = 127, l;
	char *buf = bb_xmalloc(size);

	for (;;) {
		if (!(l = fgets_embedded_nul(buf+len, size-len, f))) break;
		if (l < size-len-1 || buf[size-2] == '\n') {
			len += l;
			break;
		} else len = size - 1;
		// safe: SIZE_MAX allocation will fail before overflow
		size = 2*size+1;
		buf = bb_xrealloc(buf, size);
	}

	if (!(*n = len)) {
		free(buf);
		return NULL;
	}

	return buf;
}

char *bb_getline(FILE *f)
{
	size_t len = 0, size = 127;
	char *buf = bb_xmalloc(size);

	for (;;) {
		buf[size-1] = 1;
		if (!fgets(buf+len, size-len, f)) break;
		if (buf[size-1] || buf[size-2] == '\n') {
			len += strlen(buf+len);
			break;
		} else len = size - 1;
		// safe: SIZE_MAX allocation will fail before overflow
		size = 2*size+1;
		buf = bb_xrealloc(buf, size);
	}

	if (!len) {
		free(buf);
		return NULL;
	}

	return buf;
}


More information about the busybox mailing list