218  * A list-like object that decodes the contents of a RevlogNG index

   218  * A base-16 trie for fast node->rev mapping.

   219  * file on demand. It has limited support for insert and delete at the

   219  *

   220  * last element before the end.  The last entry is always a sentinel

   220  * Positive value is index of the next node in the trie

   221  * nullid.

   221  * Negative value is a leaf: -(rev + 1)

   222  * Zero is empty

   223  */

   224 typedef struct {

   225 	int children[16];

   226 } nodetree;

   227 

   228 /*

   229  * This class has two behaviours.

   230  *

   231  * When used in a list-like way (with integer keys), we decode an

   232  * entry in a RevlogNG index file on demand. Our last entry is a

   233  * sentinel, always a nullid.  We have limited support for

   234  * integer-keyed insert and delete, only at elements right before the

   235  * sentinel.

   236  *

   237  * With string keys, we lazily perform a reverse mapping from node to

   238  * rev, using a base-16 trie.

   235 static Py_ssize_t index_length(indexObject *self)

   260 static Py_ssize_t index_length(const indexObject *self)

   252 /* RevlogNG format (all in big endian, data may be inlined):

   278 /*

   279  * Return a pointer to the beginning of a RevlogNG record.

   280  */

   281 static const char *index_deref(indexObject *self, Py_ssize_t pos)

   282 {

   283 	if (self->inlined && pos > 0) {

   284 		if (self->offsets == NULL) {

   285 			self->offsets = malloc(self->raw_length *

   286 					       sizeof(*self->offsets));

   287 			if (self->offsets == NULL)

   288 				return (const char *)PyErr_NoMemory();

   289 			inline_scan(self, self->offsets);

   290 		}

   291 		return self->offsets[pos];

   292 	}

   293 

   294 	return PyString_AS_STRING(self->data) + pos * 64;

   295 }

   296 

   297 /*

   298  * RevlogNG format (all in big endian, data may be inlined):

   273 	if (pos >= length) {

   319 	if (pos < 0)

   320 		pos += length;

   321 

   322 	if (pos < 0 || pos >= length) {

   301 	if (self->inlined && pos > 0) {

   350 	data = index_deref(self, pos);

   302 		if (self->offsets == NULL) {

   351 	if (data == NULL)

   303 			self->offsets = malloc(self->raw_length *

   352 		return NULL;

   304 					       sizeof(*self->offsets));

   305 			if (self->offsets == NULL)

   306 				return PyErr_NoMemory();

   307 			inline_scan(self, self->offsets);

   308 		}

   309 		data = self->offsets[pos];

   310 	} else

   311 		data = PyString_AS_STRING(self->data) + pos * 64;

   346 	PyObject *obj, *node;

   424 	PyObject *obj;

   425 	char *node;

   348 	Py_ssize_t len;

   427 	Py_ssize_t len, nodelen;

   354 		PyErr_SetString(PyExc_ValueError, "8-tuple required");

   433 		PyErr_SetString(PyExc_TypeError, "8-tuple required");

   355 		return NULL;

   434 		return NULL;

   356 	}

   435 	}

   357 

   436 

   358 	node = PyTuple_GET_ITEM(obj, 7);

   437 	if (node_check(PyTuple_GET_ITEM(obj, 7), &node, &nodelen) == -1)

   359 	if (!PyString_Check(node) || PyString_GET_SIZE(node) != 20) {

   438 		return NULL;

   360 		PyErr_SetString(PyExc_ValueError,

   361 				"20-byte hash required as last element");

   362 		return NULL;

   363 	}

   412 static int index_assign_subscript(indexObject *self, PyObject *item,

   504 static PyObject *index_stats(indexObject *self)

   413 				  PyObject *value)

   505 {

   506 	PyObject *obj = PyDict_New();

   507 

   508 	if (obj == NULL)

   509 		return NULL;

   510 

   511 #define istat(__n, __d) \

   512 	if (PyDict_SetItemString(obj, __d, PyInt_FromLong(self->__n)) == -1) \

   513 		goto bail;

   514 

   515 	if (self->added) {

   516 		Py_ssize_t len = PyList_GET_SIZE(self->added);

   517 		if (PyDict_SetItemString(obj, "index entries added",

   518 					 PyInt_FromLong(len)) == -1)

   519 			goto bail;

   520 	}

   521 

   522 	if (self->raw_length != self->length - 1)

   523 		istat(raw_length, "revs on disk");

   524 	istat(length, "revs in memory");

   525 	istat(ntcapacity, "node trie capacity");

   526 	istat(ntdepth, "node trie depth");

   527 	istat(ntlength, "node trie count");

   528 	istat(ntlookups, "node trie lookups");

   529 	istat(ntmisses, "node trie misses");

   530 	istat(ntrev, "node trie last rev scanned");

   531 	istat(ntsplits, "node trie splits");

   532 

   533 #undef istat

   534 

   535 	return obj;

   536 

   537 bail:

   538 	Py_XDECREF(obj);

   539 	return NULL;

   540 }

   541 

   542 static inline int nt_level(const char *node, int level)

   543 {

   544 	int v = node[level>>1];

   545 	if (!(level & 1))

   546 		v >>= 4;

   547 	return v & 0xf;

   548 }

   549 

   550 static int nt_find(indexObject *self, const char *node, Py_ssize_t nodelen)

   551 {

   552 	int level, off;

   553 

   554 	if (nodelen == 20 && node[0] == '\0' && memcmp(node, nullid, 20) == 0)

   555 		return -1;

   556 

   557 	if (self->nt == NULL)

   558 		return -2;

   559 

   560 	for (level = off = 0; level < nodelen; level++) {

   561 		int k = nt_level(node, level);

   562 		nodetree *n = &self->nt[off];

   563 		int v = n->children[k];

   564 

   565 		if (v < 0) {

   566 			const char *n;

   567 			v = -v - 1;

   568 			n = index_node(self, v);

   569 			if (n == NULL)

   570 				return -2;

   571 			return memcmp(node, n, nodelen > 20 ? 20 : nodelen)

   572 				? -2 : v;

   573 		}

   574 		if (v == 0)

   575 			return -2;

   576 		off = v;

   577 	}

   578 	return -2;

   579 }

   580 

   581 static int nt_new(indexObject *self)

   582 {

   583 	if (self->ntlength == self->ntcapacity) {

   584 		self->ntcapacity *= 2;

   585 		self->nt = realloc(self->nt,

   586 				   self->ntcapacity * sizeof(nodetree));

   587 		if (self->nt == NULL) {

   588 			PyErr_SetString(PyExc_MemoryError, "out of memory");

   589 			return -1;

   590 		}

   591 		memset(&self->nt[self->ntlength], 0,

   592 		       sizeof(nodetree) * (self->ntcapacity - self->ntlength));

   593 	}

   594 	return self->ntlength++;

   595 }

   596 

   597 static int nt_insert(indexObject *self, const char *node, int rev)

   598 {

   599 	int level = 0;

   600 	int off = 0;

   601 

   602 	while (level < 20) {

   603 		int k = nt_level(node, level);

   604 		nodetree *n;

   605 		int v;

   606 

   607 		n = &self->nt[off];

   608 		v = n->children[k];

   609 

   610 		if (v == 0) {

   611 			n->children[k] = -rev - 1;

   612 			return 0;

   613 		}

   614 		if (v < 0) {

   615 			const char *oldnode = index_node(self, -v - 1);

   616 			int noff;

   617 

   618 			if (!oldnode || !memcmp(oldnode, node, 20)) {

   619 				n->children[k] = -rev - 1;

   620 				return 0;

   621 			}

   622 			noff = nt_new(self);

   623 			if (noff == -1)

   624 				return -1;

   625 			/* self->nt may have been changed by realloc */

   626 			self->nt[off].children[k] = noff;

   627 			off = noff;

   628 			n = &self->nt[off];

   629 			n->children[nt_level(oldnode, ++level)] = v;

   630 			if (level > self->ntdepth)

   631 				self->ntdepth = level;

   632 			self->ntsplits += 1;

   633 		} else {

   634 			level += 1;

   635 			off = v;

   636 		}

   637 	}

   638 

   639 	return -1;

   640 }

   641 

   642 /*

   643  * Return values:

   644  *

   645  *   -3: error (exception set)

   646  *   -2: not found (no exception set)

   647  * rest: valid rev

   648  */

   649 static int index_find_node(indexObject *self,

   650 			   const char *node, Py_ssize_t nodelen)

   651 {

   652 	int rev;

   653 

   654 	self->ntlookups++;

   655 	rev = nt_find(self, node, nodelen);

   656 	if (rev >= -1)

   657 		return rev;

   658 

   659 	if (self->nt == NULL) {

   660 		self->ntcapacity = self->raw_length < 4

   661 			? 4 : self->raw_length / 2;

   662 		self->nt = calloc(self->ntcapacity, sizeof(nodetree));

   663 		if (self->nt == NULL) {

   664 			PyErr_SetString(PyExc_MemoryError, "out of memory");

   665 			return -3;

   666 		}

   667 		self->ntlength = 1;

   668 		self->ntrev = (int)index_length(self) - 1;

   669 		self->ntlookups = 1;

   670 		self->ntmisses = 0;

   671 	}

   672 

   673 	/*

   674 	 * For the first handful of lookups, we scan the entire index,

   675 	 * and cache only the matching nodes. This optimizes for cases

   676 	 * like "hg tip", where only a few nodes are accessed.

   677 	 *

   678 	 * After that, we cache every node we visit, using a single

   679 	 * scan amortized over multiple lookups.  This gives the best

   680 	 * bulk performance, e.g. for "hg log".

   681 	 */

   682 	if (self->ntmisses++ < 4) {

   683 		for (rev = self->ntrev - 1; rev >= 0; rev--) {

   684 			const char *n = index_node(self, rev);

   685 			if (n == NULL)

   686 				return -2;

   687 			if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {

   688 				if (nt_insert(self, n, rev) == -1)

   689 					return -3;

   690 				break;

   691 			}

   692 		}

   693 	} else {

   694 		for (rev = self->ntrev - 1; rev >= 0; rev--) {

   695 			const char *n = index_node(self, rev);

   696 			if (n == NULL)

   697 				return -2;

   698 			if (nt_insert(self, n, rev) == -1)

   699 				return -3;

   700 			if (memcmp(node, n, nodelen > 20 ? 20 : nodelen) == 0) {

   701 				break;

   702 			}

   703 		}

   704 		self->ntrev = rev;

   705 	}

   706 

   707 	if (rev >= 0)

   708 		return rev;

   709 	return -2;

   710 }

   711 

   712 static PyObject *raise_revlog_error(void)

   713 {

   714 	static PyObject *errclass;

   715 	PyObject *mod = NULL, *errobj;

   716 

   717 	if (errclass == NULL) {

   718 		PyObject *dict;

   719 

   720 		mod = PyImport_ImportModule("mercurial.error");

   721 		if (mod == NULL)

   722 			goto classfail;

   723 

   724 		dict = PyModule_GetDict(mod);

   725 		if (dict == NULL)

   726 			goto classfail;

   727 

   728 		errclass = PyDict_GetItemString(dict, "RevlogError");

   729 		if (errclass == NULL) {

   730 			PyErr_SetString(PyExc_SystemError,

   731 					"could not find RevlogError");

   732 			goto classfail;

   733 		}

   734 		Py_INCREF(errclass);

   735 	}

   736 

   737 	errobj = PyObject_CallFunction(errclass, NULL);

   738 	if (errobj == NULL)

   739 		return NULL;

   740 	PyErr_SetObject(errclass, errobj);

   741 	return errobj;

   742 

   743 classfail:

   744 	Py_XDECREF(mod);

   745 	return NULL;

   746 }

   747 

   748 static PyObject *index_getitem(indexObject *self, PyObject *value)

   749 {

   750 	char *node;

   751 	Py_ssize_t nodelen;

   752 	int rev;

   753 

   754 	if (PyInt_Check(value))

   755 		return index_get(self, PyInt_AS_LONG(value));

   756 

   757 	if (PyString_AsStringAndSize(value, &node, &nodelen) == -1)

   758 		return NULL;

   759 	rev = index_find_node(self, node, nodelen);

   760 	if (rev >= -1)

   761 		return PyInt_FromLong(rev);

   762 	if (rev == -2)

   763 		raise_revlog_error();

   764 	return NULL;

   765 }

   766 

   767 static PyObject *index_m_get(indexObject *self, PyObject *args)

   768 {

   769 	char *node;

   770 	int nodelen, rev;

   771 

   772 	if (!PyArg_ParseTuple(args, "s#", &node, &nodelen))

   773 		return NULL;

   774 

   775 	rev = index_find_node(self, node, nodelen);

   776 	if (rev ==  -3)

   777 		return NULL;

   778 	if (rev == -2)

   779 		Py_RETURN_NONE;

   780 	return PyInt_FromLong(rev);

   781 }

   782 

   783 static int index_contains(indexObject *self, PyObject *value)

   784 {

   785 	char *node;

   786 	Py_ssize_t nodelen;

   787 

   788 	if (PyInt_Check(value)) {

   789 		long rev = PyInt_AS_LONG(value);

   790 		return rev >= -1 && rev < index_length(self);

   791 	}

   792 

   793 	if (!PyString_Check(value))

   794 		return 0;

   795 

   796 	node = PyString_AS_STRING(value);

   797 	nodelen = PyString_GET_SIZE(value);

   798 

   799 	switch (index_find_node(self, node, nodelen)) {

   800 	case -3:

   801 		return -1;

   802 	case -2:

   803 		return 0;

   804 	default:

   805 		return 1;

   806 	}

   807 }

   808 

   809 /*

   810  * Invalidate any trie entries introduced by added revs.

   811  */

   812 static void nt_invalidate_added(indexObject *self, Py_ssize_t start)

   813 {

   814 	Py_ssize_t i, len = PyList_GET_SIZE(self->added);

   815 

   816 	for (i = start; i < len; i++) {

   817 		PyObject *tuple = PyList_GET_ITEM(self->added, i);

   818 		PyObject *node = PyTuple_GET_ITEM(tuple, 7);

   819 

   820 		nt_insert(self, PyString_AS_STRING(node), -1);

   821 	}

   822 

   823 	if (start == 0) {

   824 		Py_DECREF(self->added);

   825 		self->added = NULL;

   826 	}

   827 }

   828 

   829 /*

   830  * Delete a numeric range of revs, which must be at the end of the

   831  * range, but exclude the sentinel nullid entry.

   832  */

   833 static int index_slice_del(indexObject *self, PyObject *item)

   452 	if (start < self->length) {

   866 	if (start < self->length - 1) {

   867 		if (self->nt) {

   868 			Py_ssize_t i;

   869 

   870 			for (i = start + 1; i < self->length - 1; i++) {

   871 				const char *node = index_node(self, i);

   872 

   873 				if (node)

   874 					nt_insert(self, node, -1);

   875 			}

   876 			if (self->added)

   877 				nt_invalidate_added(self, 0);

   878 			if (self->ntrev > start)

   879 				self->ntrev = (int)start;

   880 		}

   461 	return PyList_SetSlice(self->added, start - self->length + 1,

   885 	if (self->nt) {

   462 			       PyList_GET_SIZE(self->added),

   886 		nt_invalidate_added(self, start - self->length + 1);

   463 			       NULL);

   887 		if (self->ntrev > start)

   464 }

   888 			self->ntrev = (int)start;

   465 

   889 	}

   890 	return self->added

   891 		? PyList_SetSlice(self->added, start - self->length + 1,

   892 				  PyList_GET_SIZE(self->added), NULL)

   893 		: 0;

   894 }

   895 

   896 /*

   897  * Supported ops:

   898  *

   899  * slice deletion

   900  * string assignment (extend node->rev mapping)

   901  * string deletion (shrink node->rev mapping)

   902  */

   903 static int index_assign_subscript(indexObject *self, PyObject *item,

   904 				  PyObject *value)

   905 {

   906 	char *node;

   907 	Py_ssize_t nodelen;

   908 	long rev;

   909 

   910 	if (PySlice_Check(item) && value == NULL)

   911 		return index_slice_del(self, item);

   912 

   913 	if (node_check(item, &node, &nodelen) == -1)

   914 		return -1;

   915 

   916 	if (value == NULL)

   917 		return self->nt ? nt_insert(self, node, -1) : 0;

   918 	rev = PyInt_AsLong(value);

   919 	if (rev > INT_MAX || rev < 0) {

   920 		if (!PyErr_Occurred())

   921 			PyErr_SetString(PyExc_ValueError, "rev out of range");

   922 		return -1;

   923 	}

   924 	return nt_insert(self, node, (int)rev);

   925 }

   926 

   927 /*

   928  * Find all RevlogNG entries in an index that has inline data. Update

   929  * the optional "offsets" table with those entries.

   930  */

   561 	NULL,                                  /* mp_subscript */

  1040 	(binaryfunc)index_getitem,             /* mp_subscript */

   604 	0,                         /* tp_getset */

  1092 	index_getset,              /* tp_getset */

   616  * returns a tuple of the form (index, None, cache) with elements as

  1104  * returns a tuple of the form (index, index, cache) with elements as

   619  * index: an index object that lazily parses the RevlogNG records

  1107  * index: an index object that lazily parses RevlogNG records