Lines Matching defs:llist
1035 #define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do { \
1047 vm_map_entry_max_free_left(root, llist), \
1050 if (max_free - 1 < vm_map_entry_max_free_left(root, llist)) \
1052 if (y != llist && (test)) { \
1073 root = y != llist ? y : NULL; \
1076 #define SPLAY_RIGHT_STEP(root, y, llist, rlist, test) do { \
1088 vm_map_entry_max_free_left(root, llist), \
1092 max_free = vm_map_entry_max_free_left(root, llist); \
1108 /* Copy left->max_free. Put root on llist. */ \
1110 KASSERT(max_free == vm_map_entry_max_free_left(root, llist), \
1112 root->right = llist; \
1113 llist = root; \
1120 * subtrees with root->max_free < length as empty trees. llist and rlist are
1121 * the two sides in reverse order (bottom-up), with llist linked by the right
1129 vm_map_entry_t *llist, vm_map_entry_t *rlist)
1148 *llist = left;
1169 vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *llist)
1173 left = *llist;
1180 *llist = left;
1195 * subtrees of the root go at the bottom of llist and rlist.
1199 vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t llist)
1203 * The max_free values of the children of llist are in
1204 * llist->max_free and max_free. Update with the
1207 llist->max_free = max_free =
1208 vm_size_max(llist->max_free, max_free);
1209 vm_map_entry_swap(&llist->right, &tail);
1210 vm_map_entry_swap(&tail, &llist);
1211 } while (llist != header);
1217 * When llist is known to be the predecessor of root.
1221 vm_map_entry_t llist)
1225 max_free = root->start - llist->end;
1226 if (llist != header) {
1228 root, max_free, llist);
1237 * When llist may or may not be the predecessor of root.
1241 vm_map_entry_t llist)
1245 max_free = vm_map_entry_max_free_left(root, llist);
1246 if (llist != header) {
1248 root->left == llist ? root : root->left,
1249 max_free, llist);
1339 vm_map_entry_t header, llist, rlist, root;
1343 root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
1345 max_free_left = vm_map_splay_merge_left(header, root, llist);
1347 } else if (llist != header) {
1352 root = llist;
1353 llist = root->right;
1354 max_free_left = vm_map_splay_merge_left(header, root, llist);
1363 max_free_left = vm_map_splay_merge_pred(header, root, llist);
1387 vm_map_entry_t header, llist, rlist, root;
1396 root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1402 max_free_left = vm_map_splay_merge_pred(header, entry, llist);
1413 vm_map_splay_findprev(root, &llist);
1417 max_free_left = vm_map_splay_merge_pred(header, entry, llist);
1435 vm_map_splay_merge_left(header, root, llist),
1453 vm_map_entry_t header, llist, rlist, root;
1458 root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1462 vm_map_splay_findprev(root, &llist);
1469 if (llist != header) {
1470 root = llist;
1471 llist = root->right;
1472 max_free_left = vm_map_splay_merge_left(header, root, llist);
1477 max_free_left = vm_map_splay_merge_pred(header, root, llist);
1503 vm_map_entry_t header, llist, rlist, root;
1507 root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
1512 vm_map_splay_merge_left(header, root, llist),
1869 vm_map_entry_t header, llist, rlist, root, y;
1895 root = vm_map_splay_split(map, start, length, &llist, &rlist);
1901 max_free_left = vm_map_splay_merge_left(header, root, llist);
1906 max_free_left = vm_map_splay_merge_pred(header, root, llist);
1909 root = llist;
1910 llist = root->right;
1911 max_free_left = vm_map_splay_merge_left(header, root, llist);
1927 llist = rlist = header;
1929 left_length = vm_map_entry_max_free_left(root, llist)) {
1931 SPLAY_LEFT_STEP(root, y, llist, rlist,
1932 length <= vm_map_entry_max_free_left(y, llist));
1934 SPLAY_RIGHT_STEP(root, y, llist, rlist,
1939 root = llist;
1940 llist = root->right;
1941 max_free_left = vm_map_splay_merge_left(header, root, llist);