Populate 'entry' with the element at the specified zero-based index * where 0 is the head, 1 is the element next to head * and so on. Negative integers are used in order to count * from the tail, -1 is the last element, -2 the penultimate * and so on. If the index is out of range 0 is returned. * * Returns 1 if element found * Returns 0 if element not found */
| 1247 | * Returns 1 if element found |
| 1248 | * Returns 0 if element not found */ |
| 1249 | int quicklistIndex(const quicklist *quicklist, const long long idx, |
| 1250 | quicklistEntry *entry) { |
| 1251 | quicklistNode *n; |
| 1252 | unsigned long long accum = 0; |
| 1253 | unsigned long long index; |
| 1254 | int forward = idx < 0 ? 0 : 1; /* < 0 -> reverse, 0+ -> forward */ |
| 1255 | |
| 1256 | initEntry(entry); |
| 1257 | entry->qlist = quicklist; |
| 1258 | |
| 1259 | if (!forward) { |
| 1260 | index = (-idx) - 1; |
| 1261 | n = quicklist->tail; |
| 1262 | } else { |
| 1263 | index = idx; |
| 1264 | n = quicklist->head; |
| 1265 | } |
| 1266 | |
| 1267 | if (index >= quicklist->count) |
| 1268 | return 0; |
| 1269 | |
| 1270 | while (likely(n)) { |
| 1271 | if ((accum + n->count) > index) { |
| 1272 | break; |
| 1273 | } else { |
| 1274 | D("Skipping over (%p) %u at accum %lld", (void *)n, n->count, |
| 1275 | accum); |
| 1276 | accum += n->count; |
| 1277 | n = forward ? n->next : n->prev; |
| 1278 | } |
| 1279 | } |
| 1280 | |
| 1281 | if (!n) |
| 1282 | return 0; |
| 1283 | |
| 1284 | D("Found node: %p at accum %llu, idx %llu, sub+ %llu, sub- %llu", (void *)n, |
| 1285 | accum, index, index - accum, (-index) - 1 + accum); |
| 1286 | |
| 1287 | entry->node = n; |
| 1288 | if (forward) { |
| 1289 | /* forward = normal head-to-tail offset. */ |
| 1290 | entry->offset = index - accum; |
| 1291 | } else { |
| 1292 | /* reverse = need negative offset for tail-to-head, so undo |
| 1293 | * the result of the original if (index < 0) above. */ |
| 1294 | entry->offset = (-index) - 1 + accum; |
| 1295 | } |
| 1296 | |
| 1297 | quicklistDecompressNodeForUse(entry->node); |
| 1298 | entry->zi = ziplistIndex(entry->node->zl, entry->offset); |
| 1299 | if (!ziplistGet(entry->zi, &entry->value, &entry->sz, &entry->longval)) |
| 1300 | assert(0); /* This can happen on corrupt ziplist with fake entry count. */ |
| 1301 | /* The caller will use our result, so we don't re-compress here. |
| 1302 | * The caller can recompress or delete the node as needed. */ |
| 1303 | return 1; |
| 1304 | } |
| 1305 | |
| 1306 | /* Rotate quicklist by moving the tail element to the head. */ |
no test coverage detected