Lines Matching refs:list
31 * These are the subroutines that manage the skip-list data structures used for the
39 * distributed random number. Every mapping is on the first list. Ideally, each
40 * successive list has only 1/F as many nodes on it as the previous, where F is the
43 * Searching, adding, and deleting from a skip-list can all be done in O(ln(n)) time.
44 * Because the first skip-list is just a sorted list of all mappings, it is also
56 * 64-byte nodes with 4 list links, and 128-byte nodes with 12. Only one in every
67 ; set nonzero to accumulate skip-list stats on a per-map basis:
70 ; cr7 bit set when mapSearchFull() finds a match on a high list:
110 addic. r7,r7,-1 ; get base-0 number of last list, and test for 0
112 slwi r7,r7,3 ; get offset of last list in use
114 lwzx r3,r8,r7 ; get 32-bit ptr to 1st mapping in highest list
118 ldx r3,r8,r7 ; get 64-bit ptr to 1st mapping in highest list
128 ; r7 = current skip list number * 8
129 ; r8 = ptr to skip list vector of mapping pointed to by r9 (or pmap, if r9==0)
138 blt cr1,mapSrch64d ; key is less, try next list
139 la r8,mpList0(r3) ; point to skip list vector in this mapping
142 ldx r3,r7,r8 ; get ptr to next mapping in current list
144 mr. r3,r3 ; was there another mapping on current list?
147 subic. r7,r7,8 ; move on to next list offset
148 ldx r3,r7,r8 ; get next mapping on next list (if any)
149 bge++ mapSrch64c ; loop to try next list
216 ; r7 = current skip list number * 8
217 ; r8 = ptr to skip list vector of mapping pointed to by r9 (or pmap, if r9==0)
226 blt cr1,mapSrch32d ; key is less, try next list
227 la r8,mpList0+4(r3) ; point to skip list vector in this mapping
230 lwzx r3,r7,r8 ; get ptr to next mapping in current list
232 mr. r3,r3 ; was there another mapping on current list?
235 subic. r7,r7,8 ; move on to next list offset
236 lwzx r3,r7,r8 ; get next mapping on next list (if any)
237 bge+ mapSrch32c ; loop to try next list
322 * (or to the pmap, if there is no previous node) for each list that the mapping
347 addic. r7,r7,-1 ; get base-0 number of last list, and test for 0
349 slwi r7,r7,3 ; get (offset*8) of last list
352 lwzx r3,r8,r7 ; get 32-bit ptr to 1st mapping in highest list
358 ldx r3,r8,r7 ; get 64-bit ptr to 1st mapping in highest list
368 ; r7 = current skip list number * 8
369 ; r8 = ptr to skip list vector of mapping pointed to by r9
393 blt cr1,mapSrchFull64d ; key is less, try next list
397 la r8,mpList0(r3) ; point to skip list vector in this mapping
399 ldx r3,r7,r8 ; get ptr to next mapping in current list
402 mr. r3,r3 ; was there another mapping on current list?
406 subic. r7,r7,8 ; move on to next list offset
407 ldx r3,r7,r8 ; get next mapping on next list (if any)
408 bge++ mapSrchFull64c ; loop to try next list
413 bt-- bFullFound,mapSkipListPanic ; panic if it was on earlier list
430 ; r7 = current skip list number * 8
431 ; r8 = ptr to prev mappings (ie, r9) skip-list vector
437 cmpwi r7,0 ; are we in the last skip-list?
441 stdx r9,r7,r12 ; save prev ptr in last list
448 ; r3 = ptr to next mapping in current list
451 ; r7 = current skip list number * 8
452 ; r8 = ptr to skip list vector of mapping pointed to by r9
476 blt cr1,mapSrchFull32d ; key is less than this va, try next list
480 la r8,mpList0+4(r3) ; point to skip list vector in this mapping
482 lwzx r3,r7,r8 ; get ptr to next mapping in current list
489 subic. r7,r7,8 ; move on to next list offset
490 lwzx r3,r7,r8 ; get next mapping on lower list (if any)
491 bge+ mapSrchFull32c ; loop to try next list
496 bt- bFullFound,mapSkipListPanic ; panic if it was on an earlier list
513 ; r7 = current skip list number * 8
519 cmpwi r7,0 ; are we in the last skip-list?
523 stwx r9,r7,r12 ; save prev ptr in last list
536 * previous ptrs for each skip list. When called:
553 la r10,pmapSkipLists+4(r3) ; r10 <-- base of pmap list headers, assuming 32-bit machine
554 la r11,mpList0+4(r4) ; r11 <-- base of this mappings list vector
560 subi r8,r8,8 ; get offset to topmost (last) list in use
569 ; point to the pmap. While we are at it, we verify that the unused list hdrs in
575 mr r5,r8 ; copy offset to last list
579 ldx r6,r5,r10 ; get pmap list head
581 subi r5,r5,8 ; get next list offset
582 cmpdi r6,0 ; was list hdr null?
583 bdnzt cr0_eq,mapIns64NewList ; loop if more lists to initialize and list hdr was 0
584 bne-- mapSkipListPanic ; die if pmap list hdr was not null
587 ; 64-bit processor: loop over each list this mapping is on
589 ; r8 = next list offset
590 ; r10 = ptr to base of pmap list header vector
591 ; r11 = ptr to base of new mappings list vector
598 la r7,mpList0(r5) ; get base of prev mappings list vector
600 stdx r4,r8,r7 ; * insert new mapping in middle of this list
602 subi r8,r8,8 ; get next list offset
609 ; While we are at it, we verify that the unused list hdrs in the pmap are 0.
616 mr r5,r8 ; copy offset to last list
620 lwzx r6,r5,r10 ; get pmap list head
622 subi r5,r5,8 ; get next list offset
623 cmpwi r6,0 ; was list hdr null?
624 bdnzt cr0_eq,mapIns32NewList ; loop if more lists to initialize and list hdr was 0
625 bne- mapSkipListPanic ; die if pmap list hdr was not null
628 ; 32-bit processor: loop over each list this mapping is on
630 ; r8 = next list offset
631 ; r10 = ptr to base of pmap list header vector
632 ; r11 = ptr to base of new mappings list vector
639 la r7,mpList0+4(r5) ; get base of prev mappings list vector
641 stwx r4,r8,r7 ; * insert new mapping in middle of this list
643 subi r8,r8,8 ; get next list offset
655 * ptrs for each skip list. When called:
672 la r11,mpList0+4(r4) ; r11 <-- base of this mappings list vector
679 subi r8,r8,8 ; get offset to topmast (last) list this mapping is in
681 subi r11,r11,4 ; we use all 64 bits of list links on 64-bit machines
685 ; 64-bit processor: loop over each list this mapping is on
688 ; r8 = offset to next list
690 ; r11 = ptr to base of mapping list vector
699 la r7,mpList0(r5) ; get base of prev mappings list vector
701 subi r8,r8,8 ; get next list offset
702 bne++ cr1,mapRem64a ; loop if another list to unlink from
704 ; Did we reduce #lists in use by removing last mapping in last list?
707 la r5,pmapSkipLists(r3) ; point to vector of list hdrs
709 subic. r10,r10,1 ; get base-0 list#
710 slwi r8,r10,3 ; get offset to last list
711 ldx r0,r8,r5 ; get last list ptr
715 bgt mapRem64b ; loop to see if more than one list was emptied
719 ; 32-bit processor: loop over each list this mapping is on
722 ; r8 = offset to next list
724 ; r11 = ptr to base of mapping list vector
733 la r7,mpList0+4(r5) ; get base of prev mappings list vector
735 subi r8,r8,8 ; get next list offset
736 bne+ cr1,mapRem32a ; loop if another list to unlink from
738 ; Did we reduce #lists in use by removing last mapping in last list?
741 la r5,pmapSkipLists+4(r3) ; point to vector of list hdrs
743 subic. r10,r10,1 ; get base-0 list#
744 slwi r8,r10,3 ; get offset to last list
745 lwzx r0,r8,r5 ; get last list ptr
749 bgt mapRem32b ; loop to see if more than one list was emptied
773 * Also, we modify the "simple" trailing-0-based list count, to account for an important
777 * pmap. This means the simple list count will often be larger than justified by the number of
778 * mappings in the pmap. To avoid this common situation, we clamp the list count to be no more
781 * Finally, we also clamp the list count to kSkipListMaxLists.
806 addi r3,r11,1 ; every mapping is on at least one list
815 * This does a fairly thorough sweep through a pmaps skip-list data structure, doing
1010 ; Since we walk each list this is the max number of mappings we could visit.
1018 li r22,kSkipListMaxLists ; initialize list#
1023 ; Loop over each list, counting mappings in each. We first check whether or not
1024 ; the list is empty (ie, if the pmapSlipLists ptr is null.) All lists above
1025 ; pmapCurLists should be empty, and no list at or below pmapCurLists should be.
1028 ; r22 = next list# (1...kSkipListMaxLists)
1035 ldx r26,r25,r26 ; get 1st mapping on this list, if any
1037 cmpdi cr6,r26,0 ; set cr6_eq if this list is null ("null")
1038 cmpw cr7,r22,r28 ; set cr7_gt if this list is > pmapCurLists ("high")
1040 beql-- mapVerifyDie ; die if this list is null when it should not be, etc
1043 ; Loop over each node in the list.
1046 ; r22 = this list# (1...kSkipListMaxLists)
1059 cmpw cr1,r27,r22 ; is it supposed to be on this list?
1064 bne++ cr1,mapVer64f ; jump if this is not highest list for this node
1066 ; This is the "highest" (last) list this mapping is on.
1088 li r27,kSkipListMaxLists*8-8 ; initialize list offset for inner loop
1090 ; Inner loop over each list link in this mappingss mpList vector.
1092 ; r27 = offset for next list in inner loop
1093 ; r28 = base of this mappings list links
1100 bgtl-- cr1,mapVerifyDie ; a mapping has a non-null list higher than its mpLists
1106 subic. r27,r27,8 ; move on to next list
1109 ; Next node on current list, or next list if current done, or return if no more lists.
1113 ldx r26,r25,r28 ; get next mapping on this list
1117 subic. r22,r22,1 ; is there another list?
1131 la r30,pmapSkipLists(r20) ; first, check the pmap list hdrs
1133 bl mapVerUpperWordsAre0 ; are the upper words of each list all 0?
1135 ; Loop over each list, counting mappings in each. We first check whether or not
1136 ; the list is empty. All lists above pmapCurLists should be empty, and no list
1141 ; r22 = next list# (1...kSkipListMaxLists)
1149 lwzx r26,r25,r26 ; get the 1st mapping on this list, or 0
1150 cmpw cr7,r22,r28 ; set cr7_gt if this list is > pmapCurLists ("high")
1151 cmpwi cr6,r26,0 ; set cr6_eq if this list is null ("null")
1153 beql- mapVerifyDie ; die if this list is null when it should not be, etc
1156 ; Loop over each node in the list.
1159 ; r22 = this list# (1...kSkipListMaxLists)
1175 cmpw cr1,r27,r22 ; is it supposed to be on this list?
1180 bne+ cr1,mapVer32f ; jump if this is not highest list for this node
1182 ; This is the "highest" (last) list this mapping is on.
1209 li r27,kSkipListMaxLists*8-8 ; initialize list offset for inner loop
1211 ; Inner loop over each list in this mappings mpList vector.
1213 ; r27 = offset for next list in inner loop
1214 ; r28 = base of this mappings list links
1223 bgtl- cr1,mapVerifyDie ; a mapping has a non-null list higher than its mpLists
1229 subic. r27,r27,8 ; move on to next list
1232 ; Next node on current list, or next list if current done, or return if no more lists.
1236 lwzx r26,r25,r28 ; get next mapping on this list
1240 subic. r22,r22,1 ; is there another list?
1287 * to the original caller of the skip-list function.