fsckdtre.c

在Linux内核从2.4升级到2.6时需要升级的软件包

								highidx =
								    mididx;
							}
						}
					}
				}
			}
		}
	}
	return (dbip_rc);
}

/*****************************************************************************
 * NAME: dTree_binsrch_leaf
 *
 * FUNCTION: Perform a binary search, on the given dTree leaf node, for the
 *           entry (if any) which contains the given filename.
 *
 * PARAMETERS:
 *      dtiptr            - input - pointer to an fsck record describing the
 *                                  directory tree
 *      given_name        - input - pointer to the name to search for
 *      given_name_len    - input - number of characters in given_name
 *      is_root           - input - !0 => specified node is a B+ Tree root
 *                                   0 => specified node is not a B+ Tree root
 *      no_key_match      - input - pointer to a variable in which to return
 *                                  an indication of whether the search has
 *                                  been completed because it has been
 *                                  determined that no entry in the directory
 *                                  matches given_name
 *                                  !0 if the search should be ended, No
 *                                     match found
 *                                   0 if either the search should continue or
 *                                     a match has been found
 *      key_matched       - input - pointer to a variable in which to return
 *                                   !0 if an exact match has been found
 *                                    0 if no match has been found
 *      slot_selected     - input - pointer to a variable in which to return
 *                                  an indication of whether the search has
 *                                  been completed at this level by finding
 *                                  a match or reason to reason to believe
 *                                  we may still find a match.
 *                                  !0 if a slot has been selected
 *                                   0 if either the search should continue or
 *                                     it has been determined that there is
 *                                     no match in the directory
 *      selected_slotidx  - input - pointer to a variable in which to return
 *                                  the number n such that slot[n] contains
 *                                  (or begins) the key which is a match for
 *                                  given_name
 *      inorecptr         - input - pointer to an fsck inode record describing
 *                                  the inode
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_binsrch_leaf(struct fsck_Dtree_info *dtiptr,
		       UniChar * given_name,
		       uint32_t given_name_len,
		       int8_t is_root,
		       int8_t * no_key_match,
		       int8_t * key_matched,
		       int8_t * slot_selected,
		       int8_t * selected_slotidx,
		       struct fsck_inode_record *inorecptr)
{
	int dbl_rc = FSCK_OK;

	UniChar *this_name;
	uint32_t *this_name_len;
	int lowidx, mididx, highidx;
	int prev_idx, next_idx;
	int8_t is_leaf = -1;
	int outcome;

	this_name = &(key[1][0]);
	this_name_len = &(key_len[1]);

	*no_key_match = 0;
	*slot_selected = 0;
	*selected_slotidx = 0;

	lowidx = 0;
	highidx = dtiptr->last_dtidx;

	dbl_rc =
	    dTree_key_extract(dtiptr, lowidx, this_name, this_name_len, is_root,
			      is_leaf, inorecptr);
	/*
	 * note that we can proceed with (some) confidence since we never
	 * search a directory until after we've verified it's structure
	 */

	if (dbl_rc == FSCK_OK) {
		/*
		 * If this is a case insensitive search, we need to fold the
		 * extracted key to upper case before doing the comparison.
		 * The given key should already be in all upper case.
		 */
		dTree_key_to_upper(this_name, &(ukey[0][0]), (*this_name_len));
		dbl_rc = dTree_key_compare(given_name, given_name_len,
					   &(ukey[0][0]), (*this_name_len),
					   &outcome);

		if (outcome == LEFT_KEY_LOWER) {
			/* given key < 1st in this node */
			*no_key_match = -1;
		} else if (outcome == KEYS_MATCH) {
			/* given key == 1st in this node */
			*no_key_match = 0;
			*key_matched = -1;
			*slot_selected = -1;
			*selected_slotidx = dtiptr->dtstbl[lowidx];
		} else {
			/* given key > 1st in this node */
			dbl_rc =
			    dTree_key_extract(dtiptr, highidx, this_name,
					      this_name_len, is_root, is_leaf,
					      inorecptr);
			/*
			 * note that we can proceed with (some)
			 * confidence since we never search a directory
			 * until after we've verified it's structure
			 */
			if (dbl_rc == FSCK_OK) {
				/*
				 * If this is a case insensitive search, we need to fold the
				 * extracted key to upper case before doing the comparison.
				 * The given key should already be in all upper case.
				 */
				dTree_key_to_upper(this_name, &(ukey[0][0]),
						   (*this_name_len));
				dbl_rc =
				    dTree_key_compare(given_name,
						      given_name_len,
						      &(ukey[0][0]),
						      (*this_name_len),
						      &outcome);
				if (outcome == LEFT_KEY_HIGHER) {
					/* given key > last in the node */
					*no_key_match = -1;
				} else if (outcome == KEYS_MATCH) {
					*no_key_match = 0;
					*key_matched = -1;
					*slot_selected = -1;
					*selected_slotidx =
					    dtiptr->dtstbl[highidx];
				}
			}
		}
	}
	/*
	 * Try to find a name match
	 */
	while ((!(*slot_selected)) && (!(*no_key_match)) && (dbl_rc == FSCK_OK)) {
		/*
		 * haven't chosen one, haven't seen a match,
		 * but haven't ruled anything out
		 */
		mididx = ((highidx - lowidx) >> 1) + lowidx;
		dbl_rc =
		    dTree_key_extract(dtiptr, mididx, this_name, this_name_len,
				      is_root, is_leaf, inorecptr);
		/*
		 * note that we can proceed with (some) confidence since we never
		 * search a directory until after we've verified it's structure
		 */
		if (dbl_rc == FSCK_OK) {
			/*
			 * If this is a case insensitive search, we need to fold the
			 * extracted key to upper case before doing the comparison.
			 * The given key should already be in all upper case.
			 */
			dTree_key_to_upper(this_name, &(ukey[0][0]),
					   (*this_name_len));
			dbl_rc =
			    dTree_key_compare(given_name, given_name_len,
					      &(ukey[0][0]), (*this_name_len),
					      &outcome);

			if (dbl_rc == FSCK_OK) {
				if (outcome == KEYS_MATCH) {
					/* given name == mid key */
					*no_key_match = 0;
					*key_matched = -1;
					*slot_selected = -1;
					*selected_slotidx =
					    dtiptr->dtstbl[mididx];
				} else if (outcome == LEFT_KEY_HIGHER) {
					/* given name > mid key */
					next_idx = mididx + 1;
					dbl_rc =
					    dTree_key_extract(dtiptr, next_idx,
							      this_name,
							      this_name_len,
							      is_root, is_leaf,
							      inorecptr);
					/*
					 * note that we can proceed with (some)
					 * confidence since we never search a directory
					 * until after we've verified it's structure
					 */
					if (dbl_rc == FSCK_OK) {
						/*
						 * If this is a case insensitive search, we need to fold the
						 * extracted key to upper case before doing the comparison.
						 * The given key should already be in all upper case.
						 */
						dTree_key_to_upper(this_name,
								   &(ukey[0]
								     [0]),
								   (*this_name_len));
						dbl_rc =
						    dTree_key_compare
						    (given_name, given_name_len,
						     &(ukey[0][0]),
						     (*this_name_len),
						     &outcome);
						if (dbl_rc == FSCK_OK) {
							if (outcome ==
							    LEFT_KEY_LOWER) {
								/* the next one is higher */
								*no_key_match =
								    -1;
							} else if (outcome ==
								   KEYS_MATCH) {
								/* since we've done the
								 * extract and compare might as well see if
								 * we lucked into a match
								 */
								*no_key_match =
								    0;
								*key_matched =
								    -1;
								*slot_selected =
								    -1;
								*selected_slotidx
								    =
								    dtiptr->
								    dtstbl
								    [next_idx];
							} else {
								/* not on or just before the money */
								/* this key is higher than the middle */
								lowidx = mididx;
							}
						}	/* end nothing untoward */
					}
				} else {
					/* given name < mid key */
					prev_idx = mididx - 1;
					dbl_rc =
					    dTree_key_extract(dtiptr, prev_idx,
							      this_name,
							      this_name_len,
							      is_root, is_leaf,
							      inorecptr);
					/*
					 * note that we can proceed with (some)
					 * confidence since we never search a directory
					 * until after we've verified it's structure
					 */
					if (dbl_rc == FSCK_OK) {
						/*
						 * If this is a case insensitive search, we need to fold the
						 * extracted key to upper case before doing the comparison.
						 * The given key should already be in all upper case.
						 */
						dTree_key_to_upper(this_name,
								   &(ukey[0]
								     [0]),
								   (*this_name_len));
						dbl_rc =
						    dTree_key_compare
						    (given_name, given_name_len,
						     &(ukey[0][0]),
						     (*this_name_len),
						     &outcome);
						if (dbl_rc == FSCK_OK) {
							if (outcome ==
							    LEFT_KEY_HIGHER) {
								/* the prev one is lower */
								*no_key_match =
								    -1;
							} else if (outcome ==
								   KEYS_MATCH) {
								/* since we've done the
								 * extract and compare might as well see if
								 * we stumbled onto a match
								 */
								*no_key_match =
								    0;
								*key_matched =
								    -1;
								*slot_selected =
								    -1;
								*selected_slotidx
								    =
								    dtiptr->
								    dtstbl
								    [prev_idx];
							} else {
								/* not on or just after the money */
								/* this key is lower than the middle */
								highidx =
								    mididx;
							}
						}
					}
				}
			}
		}
	}
	return (dbl_rc);
}

/*****************************************************************************
 * NAME: dTree_key_compare
 *
 * FUNCTION: Compare the two strings which are given.
 *
 * PARAMETERS:
 *      left_key       - input - pointer to the first in a pair of keys to
 *                               compare
 *      left_key_len   - input - number of UniChars in left_key
 *      right_key      - input - pointer to the second in a pair of keys to
 *                               compare
 *      right_key_len  - input - number of UniChars in right_key
 *      keys_relation  - input - pointer to a variable in which to return
 *                               { LEFT_KEY_LOWER | KEYS_MATCH | LEFT_KEY_HIGHER }
 *
 *
 * RETURNS:
 *      success: FSCK_OK
 *      failure: something else
 */
int dTree_key_compare(UniChar * left_key,
		      uint8_t left_key_num_unichars,
		      UniChar * right_key,
		      uint8_t right_key_num_unichars, int *keys_relation)
{
	int dkc_rc = FSCK_OK;
	int outcome;
	int left_key_len, right_key_len;

	left_key_len = left_key_num_unichars;
	right_key_len = right_key_num_unichars;

	if (right_key_len < left_key_len) {
		/* right key is shorter */

		outcome =
		    UniStrncmp((void *) left_key, (void *) right_key,
			       right_key_len);
		if (outcome < 0) {
			/* right key is alphabetically greater */
			*keys_relation = LEFT_KEY_LOWER;
		} else {
			*keys_relation = LEFT_KEY_HIGHER;
		}

	} else if (right_key_len > left_key_len) {
		/* right key is longer */

		outcome =
		    UniStrncmp((void *) left_key, (void *) right_key,
			       left_key_len);
		if (outcome <= 0) {
			/* right key is alphabetically greater */
			*keys_relation = LEFT_KEY_LOWER;
		} else {
			*keys_relation = LEFT_KEY_HIGHER;
		}
	} else {
		/* keys same length */
		outcome =
		    UniStrncmp((void *) left_key, (void *) right_key,
			       left_key_len);

		if (outcome < 0)
			*keys_relation = LEFT_KEY_LOWER;
		else if (outcome > 0)
			*keys_relation = LEFT_KEY_HIGHER;
		else
			*keys_relation = KEYS_MATCH;

	}

	return (dkc_rc);
}

/*****************************************************************************
 * NAME: dTree_key_compare_leaflvl
 *
 * FUNCTION: Compare the 2 given strings according to the rules for
 *           sibling entries in a leaf node.
 *
 * PARAMETERS:
 *      left_key       - input - pointer to the first in a pair of keys to
 *                               compare
 *      left_key_len   - input - number of UniChars in left_key
 *      right_key      - input - pointer to the second in a pair of keys to
 *                               compare
 *      right_key_len  - input - number of UniChars in right_key
 *      keys_ok        - input - pointer to a variable in which to return
 *                               !0 if the relation between left_key and
 *                                  right_key, on the dTree leaf level,
 *                                  is valid
 *                                0 if the relation between left_key and