comparison mercurial/manifest.c @ 24228:542c891274b2

lazymanifest: use a binary search to do an insertion

This makes insertions log(n) plus some memmove() overhead, rather than
doing an append followed by an n*log(n) sort. There's probably a lot
of performance to be gained by adding a batch-add method, which could
be smarter about the memmove()s performed.

Includes a couple of extra tests that should help prevent bugs.

Thanks to Martin for some significant pre-mail cleanup of this change.

24227:8ec2df32bd39

	hit->deleted = true;
	self->livelines--;
	return 0;
}

static int lazymanifest_setitem(
	lazymanifest *self, PyObject *key, PyObject *value)
{
	char *path;
	Py_ssize_t plen;

	Py_ssize_t flen;
	size_t dlen;
	char *dest;
	int i;
	line new;
	line *hit;
	if (!PyString_Check(key)) {
		PyErr_Format(PyExc_TypeError,
			     "setitem: manifest keys must be a string.");
		return -1;
	}

	if (hlen > 20) {
		new.hash_suffix = hash[20];
	}
	new.from_malloc = true;     /* is `start` a pointer we allocated? */
	new.deleted = false;        /* is this entry deleted? */
	hit = bsearch(&new, self->lines, self->numlines,
		      sizeof(line), &linecmp);
	self->dirty = true;
	if (hit) {
		/* updating a line we already had */
		if (hit->from_malloc) {
			free(hit->start);
		}
		if (hit->deleted) {
			self->livelines++;
		}
		*hit = new;
	} else {
		/* new line */
		if (!realloc_if_full(self)) {
			PyErr_NoMemory();
			return -1;
		}
		self->lines[self->numlines++] = new;
		self->livelines++;
		/* TODO: do a binary search and insert rather than
		 * append and qsort. Also offer a batch-insert
		 * interface, which should be a nice little
		 * performance win.
		 */
		qsort(self->lines, self->numlines, sizeof(line), &linecmp);
	}
	return 0;
}

static PyMappingMethods lazymanifest_mapping_methods = {

24228:542c891274b2

	hit->deleted = true;
	self->livelines--;
	return 0;
}

/* Do a binary search for the insertion point for new, creating the
 * new entry if needed. */
static int internalsetitem(lazymanifest *self, line *new) {
	int start = 0, end = self->numlines;
	while (start < end) {
		int pos = start + (end - start) / 2;
		int c = linecmp(new, self->lines + pos);
		if (c < 0)
			end = pos;
		else if (c > 0)
			start = pos + 1;
		else {
			if (self->lines[pos].deleted)
				self->livelines++;
			start = pos;
			goto finish;
		}
	}
	/* being here means we need to do an insert */
	if (!realloc_if_full(self)) {
		PyErr_NoMemory();
		return -1;
	}
	memmove(self->lines + start + 1, self->lines + start,
		(self->numlines - start) * sizeof(line));
	self->numlines++;
	self->livelines++;
finish:
	self->lines[start] = *new;
	self->dirty = true;
	return 0;
}

static int lazymanifest_setitem(
	lazymanifest *self, PyObject *key, PyObject *value)
{
	char *path;
	Py_ssize_t plen;

	Py_ssize_t flen;
	size_t dlen;
	char *dest;
	int i;
	line new;
	if (!PyString_Check(key)) {
		PyErr_Format(PyExc_TypeError,
			     "setitem: manifest keys must be a string.");
		return -1;
	}

	if (hlen > 20) {
		new.hash_suffix = hash[20];
	}
	new.from_malloc = true;     /* is `start` a pointer we allocated? */
	new.deleted = false;        /* is this entry deleted? */
	if (internalsetitem(self, &new)) {
		return -1;
	}
	return 0;
}

static PyMappingMethods lazymanifest_mapping_methods = {