1166 static inline void index_get_parents(indexObject *self, int rev, int *ps)

  1167 {

  1168 	if (rev >= self->length - 1) {

  1169 		PyObject *tuple = PyList_GET_ITEM(self->added,

  1170 						  rev - self->length + 1);

  1171 		ps[0] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 5));

  1172 		ps[1] = (int)PyInt_AS_LONG(PyTuple_GET_ITEM(tuple, 6));

  1173 	} else {

  1174 		const char *data = index_deref(self, rev);

  1175 		ps[0] = getbe32(data + 24);

  1176 		ps[1] = getbe32(data + 28);

  1177 	}

  1178 }

  1179 

  1180 typedef uint64_t bitmask;

  1181 

  1182 /*

  1183  * Given a disjoint set of revs, return all candidates for the

  1184  * greatest common ancestor. In revset notation, this is the set

  1185  * "heads(::a and ::b and ...)"

  1186  */

  1187 static PyObject *find_gca_candidates(indexObject *self, const int *revs,

  1188 				     int revcount)

  1189 {

  1190 	const bitmask allseen = (1ull << revcount) - 1;

  1191 	const bitmask poison = 1ull << revcount;

  1192 	PyObject *gca = PyList_New(0);

  1193 	int i, v, interesting, left;

  1194 	int maxrev = -1;

  1195 	bitmask *seen;

  1196 

  1197 	for (i = 0; i < revcount; i++) {

  1198 		if (revs[i] > maxrev)

  1199 			maxrev = revs[i];

  1200 	}

  1201 

  1202 	seen = calloc(sizeof(*seen), maxrev + 1);

  1203 	if (seen == NULL)

  1204 		return PyErr_NoMemory();

  1205 

  1206 	for (i = 0; i < revcount; i++)

  1207 		seen[revs[i]] = 1ull << i;

  1208 

  1209 	interesting = left = revcount;

  1210 

  1211 	for (v = maxrev; v >= 0 && interesting; v--) {

  1212 		long sv = seen[v];

  1213 		int parents[2];

  1214 

  1215 		if (!sv)

  1216 			continue;

  1217 

  1218 		if (sv < poison) {

  1219 			interesting -= 1;

  1220 			if (sv == allseen) {

  1221 				PyObject *obj = PyInt_FromLong(v);

  1222 				if (obj == NULL)

  1223 					goto bail;

  1224 				if (PyList_Append(gca, obj) == -1) {

  1225 					Py_DECREF(obj);

  1226 					goto bail;

  1227 				}

  1228 				sv |= poison;

  1229 				for (i = 0; i < revcount; i++) {

  1230 					if (revs[i] == v) {

  1231 						if (--left <= 1)

  1232 							goto done;

  1233 						break;

  1234 					}

  1235 				}

  1236 			}

  1237 		}

  1238 		index_get_parents(self, v, parents);

  1239 

  1240 		for (i = 0; i < 2; i++) {

  1241 			int p = parents[i];

  1242 			if (p == -1)

  1243 				continue;

  1244 			const long sp = seen[p];

  1245 			if (sv < poison) {

  1246 				if (sp == 0) {

  1247 					seen[p] = sv;

  1248 					interesting++;

  1249 				}

  1250 				else if (sp != sv)

  1251 					seen[p] |= sv;

  1252 			} else {

  1253 				if (sp && sp < poison)

  1254 					interesting--;

  1255 				seen[p] = sv;

  1256 			}

  1257 		}

  1258 	}

  1259 

  1260 done:

  1261 	free(seen);

  1262 	return gca;

  1263 bail:

  1264 	free(seen);

  1265 	Py_XDECREF(gca);

  1266 	return NULL;

  1267 }

  1268 

  1269 /*

  1270  * Given a disjoint set of revs, return the subset with the longest

  1271  * path to the root.

  1272  */

  1273 static PyObject *find_deepest(indexObject *self, PyObject *revs)

  1274 {

  1275 	const Py_ssize_t revcount = PyList_GET_SIZE(revs);

  1276 	static const Py_ssize_t capacity = 24;

  1277 	int *depth, *interesting = NULL;

  1278 	int i, j, v, ninteresting;

  1279 	PyObject *dict = NULL, *keys;

  1280 	long *seen = NULL;

  1281 	int maxrev = -1;

  1282 	long final;

  1283 

  1284 	if (revcount > capacity) {

  1285 		PyErr_Format(PyExc_OverflowError,

  1286 			     "bitset size (%ld) > capacity (%ld)",

  1287 			     revcount, capacity);

  1288 		return NULL;

  1289 	}

  1290 

  1291 	for (i = 0; i < revcount; i++) {

  1292 		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));

  1293 		if (n > maxrev)

  1294 			maxrev = n;

  1295 	}

  1296 

  1297 	depth = calloc(sizeof(*depth), maxrev + 1);

  1298 	if (depth == NULL)

  1299 		return PyErr_NoMemory();

  1300 

  1301 	seen = calloc(sizeof(*seen), maxrev + 1);

  1302 	if (seen == NULL) {

  1303 		PyErr_NoMemory();

  1304 		goto bail;

  1305 	}

  1306 

  1307 	interesting = calloc(sizeof(*interesting), 2 << revcount);

  1308 	if (interesting == NULL) {

  1309 		PyErr_NoMemory();

  1310 		goto bail;

  1311 	}

  1312 

  1313 	for (i = 0; i < revcount; i++) {

  1314 		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));

  1315 		long b = 1l << i;

  1316 		depth[n] = 1;

  1317 		seen[n] = b;

  1318 		interesting[b] = 1;

  1319 	}

  1320 

  1321 	ninteresting = (int)revcount;

  1322 

  1323 	for (v = maxrev; v >= 0 && ninteresting > 1; v--) {

  1324 		int dv = depth[v];

  1325 		int parents[2];

  1326 		long sv;

  1327 

  1328 		if (dv == 0)

  1329 			continue;

  1330 

  1331 		sv = seen[v];

  1332 		index_get_parents(self, v, parents);

  1333 

  1334 		for (i = 0; i < 2; i++) {

  1335 			int p = parents[i];

  1336 			long nsp, sp;

  1337 			int dp;

  1338 

  1339 			if (p == -1)

  1340 				continue;

  1341 

  1342 			dp = depth[p];

  1343 			nsp = sp = seen[p];

  1344 			if (dp <= dv) {

  1345 				depth[p] = dv + 1;

  1346 				if (sp != sv) {

  1347 					interesting[sv] += 1;

  1348 					nsp = seen[p] = sv;

  1349 					if (sp) {

  1350 						interesting[sp] -= 1;

  1351 						if (interesting[sp] == 0)

  1352 							ninteresting -= 1;

  1353 					}

  1354 				}

  1355 			}

  1356 			else if (dv == dp - 1) {

  1357 				nsp = sp | sv;

  1358 				if (nsp == sp)

  1359 					continue;

  1360 				seen[p] = nsp;

  1361 				interesting[nsp] += 1;

  1362 				interesting[sp] -= 1;

  1363 				if (interesting[sp] == 0)

  1364 					ninteresting -= 1;

  1365 			}

  1366 		}

  1367 		interesting[sv] -= 1;

  1368 		if (interesting[sv] == 0)

  1369 			ninteresting -= 1;

  1370 	}

  1371 

  1372 	final = 0;

  1373 	j = ninteresting;

  1374 	for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {

  1375 		if (interesting[i] == 0)

  1376 			continue;

  1377 		final |= i;

  1378 		j -= 1;

  1379 	}

  1380 	if (final == 0)

  1381 		return PyList_New(0);

  1382 

  1383 	dict = PyDict_New();

  1384 	if (dict == NULL)

  1385 		goto bail;

  1386 

  1387 	j = ninteresting;

  1388 	for (i = 0; i < revcount && j > 0; i++) {

  1389 		PyObject *key;

  1390 

  1391 		if ((final & (1 << i)) == 0)

  1392 			continue;

  1393 

  1394 		key = PyList_GET_ITEM(revs, i);

  1395 		Py_INCREF(key);

  1396 		Py_INCREF(Py_None);

  1397 		if (PyDict_SetItem(dict, key, Py_None) == -1) {

  1398 			Py_DECREF(key);

  1399 			Py_DECREF(Py_None);

  1400 			goto bail;

  1401 		}

  1402 		j -= 1;

  1403 	}

  1404 

  1405 	keys = PyDict_Keys(dict);

  1406 

  1407 	free(depth);

  1408 	free(seen);

  1409 	free(interesting);

  1410 	Py_DECREF(dict);

  1411 

  1412 	return keys;

  1413 bail:

  1414 	free(depth);

  1415 	free(seen);

  1416 	free(interesting);

  1417 	Py_XDECREF(dict);

  1418 

  1419 	return NULL;

  1420 }

  1421 

  1422 /*

  1423  * Given a (possibly overlapping) set of revs, return the greatest

  1424  * common ancestors: those with the longest path to the root.

  1425  */

  1426 static PyObject *index_ancestors(indexObject *self, PyObject *args)

  1427 {

  1428 	PyObject *ret = NULL, *gca = NULL;

  1429 	Py_ssize_t argcount, i, len;

  1430 	bitmask repeat = 0;

  1431 	int revcount = 0;

  1432 	int *revs;

  1433 

  1434 	argcount = PySequence_Length(args);

  1435 	revs = malloc(argcount * sizeof(*revs));

  1436 	if (argcount > 0 && revs == NULL)

  1437 		return PyErr_NoMemory();

  1438 	len = index_length(self) - 1;

  1439 

  1440 	for (i = 0; i < argcount; i++) {

  1441 		static const int capacity = 24;

  1442 		PyObject *obj = PySequence_GetItem(args, i);

  1443 		bitmask x;

  1444 		long val;

  1445 

  1446 		if (!PyInt_Check(obj)) {

  1447 			PyErr_SetString(PyExc_TypeError,

  1448 					"arguments must all be ints");

  1449 			goto bail;

  1450 		}

  1451 		val = PyInt_AsLong(obj);

  1452 		if (val == -1) {

  1453 			ret = PyList_New(0);

  1454 			goto done;

  1455 		}

  1456 		if (val < 0 || val >= len) {

  1457 			PyErr_SetString(PyExc_IndexError,

  1458 					"index out of range");

  1459 			goto bail;

  1460 		}

  1461 		/* this cheesy bloom filter lets us avoid some more

  1462 		 * expensive duplicate checks in the common set-is-disjoint

  1463 		 * case */

  1464 		x = 1ull << (val & 0x3f);

  1465 		if (repeat & x) {

  1466 			int k;

  1467 			for (k = 0; k < revcount; k++) {

  1468 				if (val == revs[k])

  1469 					goto duplicate;

  1470 			}

  1471 		}

  1472 		else repeat |= x;

  1473 		if (revcount >= capacity) {

  1474 			PyErr_Format(PyExc_OverflowError,

  1475 				     "bitset size (%d) > capacity (%d)",

  1476 				     revcount, capacity);

  1477 			goto bail;

  1478 		}

  1479 		revs[revcount++] = (int)val;

  1480 	duplicate:;

  1481 	}

  1482 

  1483 	if (revcount == 0) {

  1484 		ret = PyList_New(0);

  1485 		goto done;

  1486 	}

  1487 	if (revcount == 1) {

  1488 		PyObject *obj;

  1489 		ret = PyList_New(1);

  1490 		if (ret == NULL)

  1491 			goto bail;

  1492 		obj = PyInt_FromLong(revs[0]);

  1493 		if (obj == NULL)

  1494 			goto bail;

  1495 		PyList_SET_ITEM(ret, 0, obj);

  1496 		goto done;

  1497 	}

  1498 

  1499 	gca = find_gca_candidates(self, revs, revcount);

  1500 	if (gca == NULL)

  1501 		goto bail;

  1502 

  1503 	if (PyList_GET_SIZE(gca) <= 1) {

  1504 		ret = gca;

  1505 		Py_INCREF(gca);

  1506 	}

  1507 	else if (PyList_GET_SIZE(gca) == 1) {

  1508 		ret = PyList_GET_ITEM(gca, 0);

  1509 		Py_INCREF(ret);

  1510 	}

  1511 	else ret = find_deepest(self, gca);

  1512 

  1513 done:

  1514 	free(revs);

  1515 	Py_XDECREF(gca);

  1516 

  1517 	return ret;

  1518 

  1519 bail:

  1520 	free(revs);

  1521 	Py_XDECREF(gca);

  1522 	Py_XDECREF(ret);

  1523 	return NULL;

  1524 }

  1525 

  1769 	{"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,

  1770 	 "return the gca set of the given revs"},