##// END OF EJS Templates
parsers: a C implementation of the new ancestors algorithm...
Bryan O'Sullivan -
r18988:5bae9367 default
parent child Browse files
Show More
@@ -1163,6 +1163,366 b' static int index_contains(indexObject *s'
1163 }
1163 }
1164 }
1164 }
1165
1165
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
1166 /*
1526 /*
1167 * Invalidate any trie entries introduced by added revs.
1527 * Invalidate any trie entries introduced by added revs.
1168 */
1528 */
@@ -1406,6 +1766,8 b' static PyMappingMethods index_mapping_me'
1406 };
1766 };
1407
1767
1408 static PyMethodDef index_methods[] = {
1768 static PyMethodDef index_methods[] = {
1769 {"ancestors", (PyCFunction)index_ancestors, METH_VARARGS,
1770 "return the gca set of the given revs"},
1409 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
1771 {"clearcaches", (PyCFunction)index_clearcaches, METH_NOARGS,
1410 "clear the index caches"},
1772 "clear the index caches"},
1411 {"get", (PyCFunction)index_m_get, METH_VARARGS,
1773 {"get", (PyCFunction)index_m_get, METH_VARARGS,
@@ -706,7 +706,13 b' class revlog(object):'
706 """calculate the least common ancestor of nodes a and b"""
706 """calculate the least common ancestor of nodes a and b"""
707
707
708 a, b = self.rev(a), self.rev(b)
708 a, b = self.rev(a), self.rev(b)
709 ancs = ancestor.ancestors(self.parentrevs, a, b)
709 try:
710 ancs = self.index.ancestors(a, b)
711 old = ancestor.ancestors(self.parentrevs, a, b)
712 assert set(ancs) == old, ('opinions differ over ancestor(%d, %d)' %
713 (a, b))
714 except (AttributeError, OverflowError):
715 ancs = ancestor.ancestors(self.parentrevs, a, b)
710 if ancs:
716 if ancs:
711 # choose a consistent winner when there's a tie
717 # choose a consistent winner when there's a tie
712 return min(map(self.node, ancs))
718 return min(map(self.node, ancs))
General Comments 0
You need to be logged in to leave comments. Login now