patch-2.4.0-test9 linux/drivers/acpi/namespace/nssearch.c

• Lines: 737
• Date: Fri Sep 15 14:30:30 2000
• Orig file: v2.4.0-test8/linux/drivers/acpi/namespace/nssearch.c
• Orig date: Wed Jul 5 11:23:12 2000

diff -u --recursive --new-file v2.4.0-test8/linux/drivers/acpi/namespace/nssearch.c linux/drivers/acpi/namespace/nssearch.c
@@ -1,9 +1,9 @@
-
-/******************************************************************************
+/*******************************************************************************
  *
  * Module Name: nssearch - Namespace search
+ *              $Revision: 57 $
  *
- *****************************************************************************/
+ ******************************************************************************/
 
 /*
  *  Copyright (C) 2000 R. Byron Moore
@@ -26,192 +26,132 @@
 
 #include "acpi.h"
 #include "amlcode.h"
-#include "interp.h"
-#include "namesp.h"
+#include "acinterp.h"
+#include "acnamesp.h"
 
 
 #define _COMPONENT          NAMESPACE
-	 MODULE_NAME         ("nssearch");
+	 MODULE_NAME         ("nssearch")
 
 
-/****************************************************************************
+/*******************************************************************************
  *
- * FUNCTION:    Acpi_ns_search_one_scope
+ * FUNCTION:    Acpi_ns_search_node
  *
- * PARAMETERS:  *Entry_name         - Ascii ACPI name to search for
- *              *Name_table         - Starting table where search will begin
+ * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
+ *              *Node           - Starting table where search will begin
  *              Type                - Object type to match
- *              **Ret_entry         - Where the matched NTE is returned
- *              *Ret_info           - Where info about the search is returned
+ *              **Return_node   - Where the matched Named obj is returned
  *
- * RETURN:      Status and return information via NS_SEARCH_DATA
+ * RETURN:      Status
  *
  * DESCRIPTION: Search a single namespace table.  Performs a simple search,
  *              does not add entries or search parents.
  *
- ***************************************************************************/
+ *
+ *      Named object lists are built (and subsequently dumped) in the
+ *      order in which the names are encountered during the namespace load;
+ *
+ *      All namespace searching is linear in this implementation, but
+ *      could be easily modified to support any improved search
+ *      algorithm.  However, the linear search was chosen for simplicity
+ *      and because the trees are small and the other interpreter
+ *      execution overhead is relatively high.
+ *
+ ******************************************************************************/
 
 ACPI_STATUS
-acpi_ns_search_one_scope (
-	u32                     entry_name,
-	ACPI_NAME_TABLE         *name_table,
+acpi_ns_search_node (
+	u32                     target_name,
+	ACPI_NAMESPACE_NODE     *node,
 	OBJECT_TYPE_INTERNAL    type,
-	ACPI_NAMED_OBJECT       **ret_entry,
-	NS_SEARCH_DATA          *ret_info)
+	ACPI_NAMESPACE_NODE     **return_node)
 {
-	u32                     position;
-	ACPI_NAME_TABLE         *this_table;
-	ACPI_NAME_TABLE         *previous_table = name_table;
-	ACPI_NAMED_OBJECT       *entries;
-	u8                      table_full = TRUE;
-	ACPI_NAME_TABLE         *table_with_empty_slots = NULL;
-	u32                     empty_slot_position = 0;
+	ACPI_NAMESPACE_NODE     *next_node;
 
 
 
-	/*
-	 * Name tables are built (and subsequently dumped) in the
-	 * order in which the names are encountered during the namespace load;
-	 *
-	 * All namespace searching will be linear;  If a table overflows an
-	 * additional segment will be allocated and added (chained).
-	 *
-	 * Start linear search at top of table
-	 */
-	position = 0;
-	this_table = name_table;
-	entries = this_table->entries;
-
-
-	/* Init return data */
-
-	if (ret_info) {
-		ret_info->name_table = this_table;
-	}
-
 
 	/*
-	 * Search entire name table, including all linked appendages
+	 * Search for name in this table, which is to say that we must search
+	 * for the name among the children of this object
 	 */
 
-	while (this_table) {
-		/*
-		 * Search for name in table, starting at Position.  Stop
-		 * searching upon examining all entries in the table.
-		 *
-		 */
+	next_node = node->child;
+	while (next_node) {
+		/* Check for match against the name */
 
-		entries = this_table->entries;
-		while (position < NS_TABLE_SIZE) {
-			/* Check for a valid entry */
-
-			if (!entries[position].name) {
-				if (table_full) {
-					/*
-					 * There is room in the table for more
-					 * entries, if necessary
-					 */
-
-					table_full = FALSE;
-					table_with_empty_slots = this_table;
-					empty_slot_position = position;
-				}
-			}
-
-			/* Search for name in table */
+		if (next_node->name == target_name) {
+			/*
+			 * Found matching entry.  Capture type if
+			 * appropriate before returning the entry.
+			 */
 
-			else if (entries[position].name == entry_name) {
-				/*
-				 * Found matching entry.  Capture type if
-				 * appropriate before returning the entry.
-				 */
-
-				/*
-				 * The Def_field_defn and Bank_field_defn cases
-				 * are actually looking up the Region in which
-				 * the field will be defined
-				 */
-
-				if ((INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
-					(INTERNAL_TYPE_BANK_FIELD_DEFN == type))
-				{
-					type = ACPI_TYPE_REGION;
-				}
-
-				/*
-				 * Scope, Def_any, and Index_field_defn are bogus
-				 * "types" which do not actually have anything
-				 * to do with the type of the name being looked
-				 * up.  For any other value of Type, if the type
-				 * stored in the entry is Any (i.e. unknown),
-				 * save the actual type.
-				 */
-
-				if (type != INTERNAL_TYPE_SCOPE &&
-					type != INTERNAL_TYPE_DEF_ANY &&
-					type != INTERNAL_TYPE_INDEX_FIELD_DEFN &&
-					entries[position].type == ACPI_TYPE_ANY)
-				{
-					entries[position].type = (u8) type;
-				}
+			/*
+			 * The Def_field_defn and Bank_field_defn cases
+			 * are actually looking up the Region in which
+			 * the field will be defined
+			 */
 
-				*ret_entry = &entries[position];
-				return (AE_OK);
+			if ((INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
+				(INTERNAL_TYPE_BANK_FIELD_DEFN == type))
+			{
+				type = ACPI_TYPE_REGION;
 			}
 
+			/*
+			 * Scope, Def_any, and Index_field_defn are bogus
+			 * "types" which do not actually have anything
+			 * to do with the type of the name being looked
+			 * up.  For any other value of Type, if the type
+			 * stored in the entry is Any (i.e. unknown),
+			 * save the actual type.
+			 */
 
-			/* Didn't match name, move on to the next entry */
+			if (type != INTERNAL_TYPE_SCOPE &&
+				type != INTERNAL_TYPE_DEF_ANY &&
+				type != INTERNAL_TYPE_INDEX_FIELD_DEFN &&
+				next_node->type == ACPI_TYPE_ANY)
+			{
+				next_node->type = (u8) type;
+			}
 
-			position++;
+			*return_node = next_node;
+			return (AE_OK);
 		}
 
 
 		/*
-		 * Just examined last slot in this table, move on
-		 *  to next appendate.
-		 * All appendages, even to the root NT, contain
-		 *  NS_TABLE_SIZE entries.
+		 * The last entry in the list points back to the parent,
+		 * so a flag is used to indicate the end-of-list
 		 */
+		if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
+			/* Searched entire list, we are done */
+
+			break;
+		}
 
-		previous_table = this_table;
-		this_table = this_table->next_table;
+		/* Didn't match name, move on to the next peer object */
 
-		position = 0;
+		next_node = next_node->peer;
 	}
 
 
 	/* Searched entire table, not found */
 
 
-	if (ret_info) {
-		/*
-		 * Save info on if/where a slot is available
-		 * (name was not found)
-		 */
-
-		ret_info->table_full = table_full;
-		if (table_full) {
-			ret_info->name_table = previous_table;
-		}
-
-		else {
-			ret_info->position  = empty_slot_position;
-			ret_info->name_table = table_with_empty_slots;
-		}
-	}
-
 	return (AE_NOT_FOUND);
 }
 
 
-/****************************************************************************
+/*******************************************************************************
  *
  * FUNCTION:    Acpi_ns_search_parent_tree
  *
- * PARAMETERS:  *Entry_name         - Ascii ACPI name to search for
- *              *Name_table         - Starting table where search will begin
+ * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
+ *              *Node           - Starting table where search will begin
  *              Type                - Object type to match
- *              **Ret_entry         - Where the matched NTE is returned
+ *              **Return_node   - Where the matched Named Obj is returned
  *
  * RETURN:      Status
  *
@@ -227,274 +167,79 @@
  *              indicates that the name is not found" (From ACPI Specification,
  *              section 5.3)
  *
- ***************************************************************************/
-
+ ******************************************************************************/
 
 ACPI_STATUS
 acpi_ns_search_parent_tree (
-	u32                     entry_name,
-	ACPI_NAME_TABLE         *name_table,
+	u32                     target_name,
+	ACPI_NAMESPACE_NODE     *node,
 	OBJECT_TYPE_INTERNAL    type,
-	ACPI_NAMED_OBJECT       **ret_entry)
+	ACPI_NAMESPACE_NODE     **return_node)
 {
 	ACPI_STATUS             status;
-	ACPI_NAMED_OBJECT       *parent_entry;
-	ACPI_NAMED_OBJECT       *entries;
+	ACPI_NAMESPACE_NODE     *parent_node;
 
 
-	entries = name_table->entries;
+	parent_node = acpi_ns_get_parent_object (node);
 
 	/*
-	 * If no parent or type is "local", we won't be searching the
-	 * parent tree.
+	 * If there is no parent (at the root) or type is "local", we won't be
+	 * searching the parent tree.
 	 */
-
-	if (!acpi_ns_local (type) &&
-		name_table->parent_entry)
+	if ((acpi_ns_local (type))  ||
+		(!parent_node))
 	{
-		parent_entry = name_table->parent_entry;
-		/*
-		 * Search parents until found or we have backed up to
-		 * the root
-		 */
-
-		while (parent_entry) {
-			/* Search parent scope */
-			/* TBD: [Investigate] Why ACPI_TYPE_ANY? */
-
-			status = acpi_ns_search_one_scope (entry_name,
-					   parent_entry->child_table,
-					   ACPI_TYPE_ANY,
-					   ret_entry, NULL);
 
-			if (status == AE_OK) {
-				return (status);
-			}
-
-			/*
-			 * Not found here, go up another level
-			 * (until we reach the root)
-			 */
-
-			parent_entry = acpi_ns_get_parent_entry (parent_entry);
-		}
-
-		/* Not found in parent tree */
-	}
-
-
-	return (AE_NOT_FOUND);
-}
-
-
-/****************************************************************************
- *
- * FUNCTION:    Acpi_ns_create_and_link_new_table
- *
- * PARAMETERS:  *Name_table         - The table that is to be "extended" by
- *                                    the creation of an appendage table.
- *
- * RETURN:      Status
- *
- * DESCRIPTION: Allocate a new namespace table, initialize it, and link it
- *              into the parent table.
- *
- *              NOTE: We are in the first or second pass load mode, want to
- *              add a new table entry, and the current table is full.
- *
- ***************************************************************************/
-
-ACPI_STATUS
-acpi_ns_create_and_link_new_table (
-	ACPI_NAME_TABLE         *name_table)
-{
-	ACPI_NAME_TABLE         *new_table;
-	ACPI_NAMED_OBJECT       *parent_entry;
-	ACPI_STATUS             status = AE_OK;
-
-
-	/* Sanity check on the data structure */
-
-	if (name_table->next_table) {
-		/* We should never get here (an appendage already allocated) */
-
-		return (AE_AML_INTERNAL);
-	}
-
-
-	/*
-	 * We can use the parent entries from the current table
-	 * Since the parent information remains the same.
-	 */
-	parent_entry = name_table->parent_entry;
-
-
-	/* Allocate and chain an appendage to the filled table */
-
-	new_table = acpi_ns_allocate_name_table (NS_TABLE_SIZE);
-	if (!new_table) {
-		REPORT_ERROR ("Name Table appendage allocation failure");
-		return (AE_NO_MEMORY);
-	}
 
-	/*
-	 * Allocation successful. Init the new table.
-	 */
-	name_table->next_table = new_table;
-	acpi_ns_initialize_table (new_table, parent_entry->child_table,
-			 parent_entry);
-
-	return (status);
-}
-
-
-/****************************************************************************
- *
- * FUNCTION:    Acpi_ns_initialize_table
- *
- * PARAMETERS:  New_table           - The new table to be initialized
- *              Parent_table        - The parent (owner) scope
- *              Parent_entry        - The NTE for the parent
- *
- * RETURN:      None
- *
- * DESCRIPTION: Initialize a new namespace table.  Simple, but called
- *              from several places -- code should be kept in one place.
- *
- ***************************************************************************/
-
-void
-acpi_ns_initialize_table (
-	ACPI_NAME_TABLE         *new_table,
-	ACPI_NAME_TABLE         *parent_table,
-	ACPI_NAMED_OBJECT       *parent_entry)
-{
-	u8                     i;
-
-
-	new_table->parent_entry = parent_entry;
-	new_table->parent_table = parent_table;
-
-
-	/* Init each named object entry in the table */
-
-	for (i = 0; i < NS_TABLE_SIZE; i++) {
-		new_table->entries[i].this_index = i;
-		new_table->entries[i].data_type = ACPI_DESC_TYPE_NAMED;
+		return (AE_NOT_FOUND);
 	}
 
-}
-
-
-/****************************************************************************
- *
- * FUNCTION:    Acpi_ns_initialize_entry
- *
- * PARAMETERS:  Name_table      - The containing table for the new NTE
- *              Position        - Position (index) of the new NTE in the table
- *              Entry_name      - ACPI name of the new entry
- *              Type            - ACPI object type of the new entry
- *              Previous_entry  - Link back to the previous entry (can span
- *                                multiple tables)
- *
- * RETURN:      None
- *
- * DESCRIPTION: Initialize a new entry within a namespace table.
- *
- ***************************************************************************/
-
-void
-acpi_ns_initialize_entry (
-	ACPI_WALK_STATE         *walk_state,
-	ACPI_NAME_TABLE         *name_table,
-	u32                     position,
-	u32                     entry_name,
-	OBJECT_TYPE_INTERNAL    type)
-{
-	ACPI_NAMED_OBJECT       *new_entry;
-	u16                     owner_id = TABLE_ID_DSDT;
-	ACPI_NAMED_OBJECT       *entries;
 
+	/* Search the parent tree */
 
 	/*
-	 * Get the owner ID from the Walk state
-	 * The owner ID is used to track table deletion and
-	 * deletion of objects created by methods
+	 * Search parents until found the target or we have backed up to
+	 * the root
 	 */
-	if (walk_state) {
-		owner_id = walk_state->owner_id;
-	}
-
-	/* The new entry is given by two parameters */
-
-	entries = name_table->entries;
-	new_entry = &entries[position];
-
-	/* Init the new entry */
 
-	new_entry->data_type     = ACPI_DESC_TYPE_NAMED;
-	new_entry->name          = entry_name;
-	new_entry->owner_id      = owner_id;
-	new_entry->reference_count = 1;
+	while (parent_node) {
+		/* Search parent scope */
+		/* TBD: [Investigate] Why ACPI_TYPE_ANY? */
 
+		status = acpi_ns_search_node (target_name, parent_node,
+				   ACPI_TYPE_ANY, return_node);
 
-	/*
-	 * If adding a name with unknown type, or having to
-	 * add the region in order to define fields in it, we
-	 * have a forward reference.
-	 */
+		if (ACPI_SUCCESS (status)) {
+			return (status);
+		}
 
-	if ((ACPI_TYPE_ANY == type) ||
-		(INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
-		(INTERNAL_TYPE_BANK_FIELD_DEFN == type))
-	{
 		/*
-		 * We don't want to abort here, however!
-		 * We will fill in the actual type when the
-		 * real definition is found later.
+		 * Not found here, go up another level
+		 * (until we reach the root)
 		 */
 
+		parent_node = acpi_ns_get_parent_object (parent_node);
 	}
 
-	/*
-	 * The Def_field_defn and Bank_field_defn cases are actually
-	 * looking up the Region in which the field will be defined
-	 */
-
-	if ((INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
-		(INTERNAL_TYPE_BANK_FIELD_DEFN == type))
-	{
-		type = ACPI_TYPE_REGION;
-	}
 
-	/*
-	 * Scope, Def_any, and Index_field_defn are bogus "types" which do
-	 * not actually have anything to do with the type of the name
-	 * being looked up.  Save any other value of Type as the type of
-	 * the entry.
-	 */
+	/* Not found in parent tree */
 
-	if ((type != INTERNAL_TYPE_SCOPE) &&
-		(type != INTERNAL_TYPE_DEF_ANY) &&
-		(type != INTERNAL_TYPE_INDEX_FIELD_DEFN))
-	{
-		new_entry->type = (u8) type;
-	}
-
-	return;
+	return (AE_NOT_FOUND);
 }
 
 
-/****************************************************************************
+/*******************************************************************************
  *
  * FUNCTION:    Acpi_ns_search_and_enter
  *
- * PARAMETERS:  Entry_name          - Ascii ACPI name to search for (4 chars)
- *              *Name_table         - Starting table where search will begin
- *              Interpreter_mode    - Add names only in MODE_Load_pass_x. Otherwise,
- *                                    search only.
+ * PARAMETERS:  Target_name         - Ascii ACPI name to search for (4 chars)
+ *              Walk_state          - Current state of the walk
+ *              *Node           - Starting table where search will begin
+ *              Interpreter_mode    - Add names only in MODE_Load_pass_x.
+ *                                    Otherwise,search only.
  *              Type                - Object type to match
- *              **Ret_entry         - Where the matched NTE is returned
+ *              Flags               - Flags describing the search restrictions
+ *              **Return_node   - Where the Node is returned
  *
  * RETURN:      Status
  *
@@ -506,51 +251,48 @@
  *              In IMODE_EXECUTE, search only.
  *              In other modes, search and add if not found.
  *
- ***************************************************************************/
+ ******************************************************************************/
 
 ACPI_STATUS
 acpi_ns_search_and_enter (
-	u32                     entry_name,
+	u32                     target_name,
 	ACPI_WALK_STATE         *walk_state,
-	ACPI_NAME_TABLE         *name_table,
+	ACPI_NAMESPACE_NODE     *node,
 	OPERATING_MODE          interpreter_mode,
 	OBJECT_TYPE_INTERNAL    type,
 	u32                     flags,
-	ACPI_NAMED_OBJECT       **ret_entry)
+	ACPI_NAMESPACE_NODE     **return_node)
 {
-	u32                     position;       /* position in table */
 	ACPI_STATUS             status;
-	NS_SEARCH_DATA          search_info;
-	ACPI_NAMED_OBJECT       *entry;
-	ACPI_NAMED_OBJECT       *entries;
+	ACPI_NAMESPACE_NODE     *new_node;
 
 
 	/* Parameter validation */
 
-	if (!name_table || !entry_name || !ret_entry) {
-		REPORT_ERROR ("Ns_search_and_enter: bad parameter");
+	if (!node || !target_name || !return_node) {
+		REPORT_ERROR ("Ns_search_and_enter: bad (null)parameter");
 		return (AE_BAD_PARAMETER);
 	}
 
 
 	/* Name must consist of printable characters */
 
-	if (!acpi_cm_valid_acpi_name (entry_name)) {
+	if (!acpi_cm_valid_acpi_name (target_name)) {
+		REPORT_ERROR ("Ns_search_and_enter: Bad character in ACPI Name");
 		return (AE_BAD_CHARACTER);
 	}
 
 
 	/* Try to find the name in the table specified by the caller */
 
-	*ret_entry = ENTRY_NOT_FOUND;
-	status = acpi_ns_search_one_scope (entry_name, name_table,
-			   type, ret_entry, &search_info);
+	*return_node = ENTRY_NOT_FOUND;
+	status = acpi_ns_search_node (target_name, node,
+			   type, return_node);
 	if (status != AE_NOT_FOUND) {
 		/*
 		 * Either found it or there was an error
 		 * -- finished either way
 		 */
-
 		return (status);
 	}
 
@@ -573,10 +315,9 @@
 		 * to ACPI specification
 		 */
 
-		status = acpi_ns_search_parent_tree (entry_name, name_table,
-				 type, ret_entry);
-
-		if (status == AE_OK) {
+		status = acpi_ns_search_parent_tree (target_name, node,
+				 type, return_node);
+		if (ACPI_SUCCESS (status)) {
 			return (status);
 		}
 	}
@@ -585,61 +326,22 @@
 	/*
 	 * In execute mode, just search, never add names.  Exit now.
 	 */
-
 	if (interpreter_mode == IMODE_EXECUTE) {
 		return (AE_NOT_FOUND);
 	}
 
 
-	/*
-	 * Extract the pertinent info from the search result struct.
-	 * Name_table and position might now point to an appendage
-	 */
-	name_table = search_info.name_table;
-	position = search_info.position;
+	/* Create the new named object */
 
-
-	/*
-	 * This block handles the case where the existing table is full.
-	 * we must allocate a new table before we can initialize a new entry
-	 */
-
-	if (search_info.table_full) {
-		status = acpi_ns_create_and_link_new_table (name_table);
-		if (status != AE_OK) {
-			return (status);
-		}
-
-		/* Point to the first slot in the new table */
-
-		name_table = name_table->next_table;
-		position = 0;
+	new_node = acpi_ns_create_node (target_name);
+	if (!new_node) {
+		return (AE_NO_MEMORY);
 	}
 
+	/* Install the new object into the parent's list of children */
 
-	/*
-	 * There is room in the table (or we have just allocated a new one.)
-	 * Initialize the new entry
-	 */
-
-	acpi_ns_initialize_entry (walk_state, name_table, position,
-			 entry_name, type);
-
-
-	entries     = name_table->entries;
-	*ret_entry  = &entries[position];
-	entry       = &entries[position];
-
-	/*
-	 * Increment the reference count(s) of all parents up to
-	 * the root!
-	 */
-
-	while (acpi_ns_get_parent_entry (entry)) {
-		entry = acpi_ns_get_parent_entry (entry);
-		entry->reference_count++;
-	}
-
+	acpi_ns_install_node (walk_state, node, new_node, type);
+	*return_node = new_node;
 
 	return (AE_OK);
 }