reactos/drivers/bus/acpi/namespace/nssearch.c

   1 /*******************************************************************************
   2  *
   3  * Module Name: nssearch - Namespace search
   4  *              $Revision: 1.1 $
   5  *
   6  ******************************************************************************/
   7
   8 /*
   9  *  Copyright (C) 2000, 2001 R. Byron Moore
  10  *
  11  *  This program is free software; you can redistribute it and/or modify
  12  *  it under the terms of the GNU General Public License as published by
  13  *  the Free Software Foundation; either version 2 of the License, or
  14  *  (at your option) any later version.
  15  *
  16  *  This program is distributed in the hope that it will be useful,
  17  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19  *  GNU General Public License for more details.
  20  *
  21  *  You should have received a copy of the GNU General Public License
  22  *  along with this program; if not, write to the Free Software
  23  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  24  */
  25
  26
  27 #include <acpi.h>
  28
  29 #define _COMPONENT          ACPI_NAMESPACE
  30          MODULE_NAME         ("nssearch")
  31
  32
  33 /*******************************************************************************
  34  *
  35  * FUNCTION:    Acpi_ns_search_node
  36  *
  37  * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
  38  *              *Node               - Starting table where search will begin
  39  *              Type                - Object type to match
  40  *              **Return_node       - Where the matched Named obj is returned
  41  *
  42  * RETURN:      Status
  43  *
  44  * DESCRIPTION: Search a single namespace table.  Performs a simple search,
  45  *              does not add entries or search parents.
  46  *
  47  *
  48  *      Named object lists are built (and subsequently dumped) in the
  49  *      order in which the names are encountered during the namespace load;
  50  *
  51  *      All namespace searching is linear in this implementation, but
  52  *      could be easily modified to support any improved search
  53  *      algorithm.  However, the linear search was chosen for simplicity
  54  *      and because the trees are small and the other interpreter
  55  *      execution overhead is relatively high.
  56  *
  57  ******************************************************************************/
  58
  59 ACPI_STATUS
  60 acpi_ns_search_node (
  61         u32                     target_name,
  62         ACPI_NAMESPACE_NODE     *node,
  63         OBJECT_TYPE_INTERNAL    type,
  64         ACPI_NAMESPACE_NODE     **return_node)
  65 {
  66         ACPI_NAMESPACE_NODE     *next_node;
  67
  68
  69         /*
  70          * Search for name in this table, which is to say that we must search
  71          * for the name among the children of this object
  72          */
  73
  74         next_node = node->child;
  75         while (next_node) {
  76                 /* Check for match against the name */
  77
  78                 if (next_node->name == target_name) {
  79                         /*
  80                          * Found matching entry.  Capture the type if appropriate, before
  81                          * returning the entry.
  82                          *
  83                          * The Def_field_defn and Bank_field_defn cases are actually looking up
  84                          * the Region in which the field will be defined
  85                          */
  86
  87                         if ((INTERNAL_TYPE_DEF_FIELD_DEFN == type) ||
  88                                 (INTERNAL_TYPE_BANK_FIELD_DEFN == type)) {
  89                                 type = ACPI_TYPE_REGION;
  90                         }
  91
  92                         /*
  93                          * Scope, Def_any, and Index_field_defn are bogus "types" which do not
  94                          * actually have anything to do with the type of the name being
  95                          * looked up.  For any other value of Type, if the type stored in
  96                          * the entry is Any (i.e. unknown), save the actual type.
  97                          */
  98
  99                         if (type != INTERNAL_TYPE_SCOPE &&
 100                                 type != INTERNAL_TYPE_DEF_ANY &&
 101                                 type != INTERNAL_TYPE_INDEX_FIELD_DEFN &&
 102                                 next_node->type == ACPI_TYPE_ANY) {
 103                                 next_node->type = (u8) type;
 104                         }
 105
 106                         *return_node = next_node;
 107                         return (AE_OK);
 108                 }
 109
 110
 111                 /*
 112                  * The last entry in the list points back to the parent,
 113                  * so a flag is used to indicate the end-of-list
 114                  */
 115                 if (next_node->flags & ANOBJ_END_OF_PEER_LIST) {
 116                         /* Searched entire list, we are done */
 117
 118                         break;
 119                 }
 120
 121                 /* Didn't match name, move on to the next peer object */
 122
 123                 next_node = next_node->peer;
 124         }
 125
 126
 127         /* Searched entire table, not found */
 128
 129
 130         return (AE_NOT_FOUND);
 131 }
 132
 133
 134 /*******************************************************************************
 135  *
 136  * FUNCTION:    Acpi_ns_search_parent_tree
 137  *
 138  * PARAMETERS:  *Target_name        - Ascii ACPI name to search for
 139  *              *Node               - Starting table where search will begin
 140  *              Type                - Object type to match
 141  *              **Return_node       - Where the matched Named Obj is returned
 142  *
 143  * RETURN:      Status
 144  *
 145  * DESCRIPTION: Called when a name has not been found in the current namespace
 146  *              table.  Before adding it or giving up, ACPI scope rules require
 147  *              searching enclosing scopes in cases identified by Acpi_ns_local().
 148  *
 149  *              "A name is located by finding the matching name in the current
 150  *              name space, and then in the parent name space. If the parent
 151  *              name space does not contain the name, the search continues
 152  *              recursively until either the name is found or the name space
 153  *              does not have a parent (the root of the name space).  This
 154  *              indicates that the name is not found" (From ACPI Specification,
 155  *              section 5.3)
 156  *
 157  ******************************************************************************/
 158
 159 static ACPI_STATUS
 160 acpi_ns_search_parent_tree (
 161         u32                     target_name,
 162         ACPI_NAMESPACE_NODE     *node,
 163         OBJECT_TYPE_INTERNAL    type,
 164         ACPI_NAMESPACE_NODE     **return_node)
 165 {
 166         ACPI_STATUS             status;
 167         ACPI_NAMESPACE_NODE     *parent_node;
 168
 169
 170         parent_node = acpi_ns_get_parent_object (node);
 171
 172         /*
 173          * If there is no parent (at the root) or type is "local", we won't be
 174          * searching the parent tree.
 175          */
 176         if ((acpi_ns_local (type))  ||
 177                 (!parent_node)) {
 178
 179
 180                 return (AE_NOT_FOUND);
 181         }
 182
 183
 184         /* Search the parent tree */
 185
 186         /*
 187          * Search parents until found the target or we have backed up to
 188          * the root
 189          */
 190
 191         while (parent_node) {
 192                 /* Search parent scope */
 193                 /* TBD: [Investigate] Why ACPI_TYPE_ANY? */
 194
 195                 status = acpi_ns_search_node (target_name, parent_node,
 196                                    ACPI_TYPE_ANY, return_node);
 197
 198                 if (ACPI_SUCCESS (status)) {
 199                         return (status);
 200                 }
 201
 202                 /*
 203                  * Not found here, go up another level
 204                  * (until we reach the root)
 205                  */
 206
 207                 parent_node = acpi_ns_get_parent_object (parent_node);
 208         }
 209
 210
 211         /* Not found in parent tree */
 212
 213         return (AE_NOT_FOUND);
 214 }
 215
 216
 217 /*******************************************************************************
 218  *
 219  * FUNCTION:    Acpi_ns_search_and_enter
 220  *
 221  * PARAMETERS:  Target_name         - Ascii ACPI name to search for (4 chars)
 222  *              Walk_state          - Current state of the walk
 223  *              *Node               - Starting table where search will begin
 224  *              Interpreter_mode    - Add names only in MODE_Load_pass_x.
 225  *                                    Otherwise,search only.
 226  *              Type                - Object type to match
 227  *              Flags               - Flags describing the search restrictions
 228  *              **Return_node       - Where the Node is returned
 229  *
 230  * RETURN:      Status
 231  *
 232  * DESCRIPTION: Search for a name segment in a single name table,
 233  *              optionally adding it if it is not found.  If the passed
 234  *              Type is not Any and the type previously stored in the
 235  *              entry was Any (i.e. unknown), update the stored type.
 236  *
 237  *              In IMODE_EXECUTE, search only.
 238  *              In other modes, search and add if not found.
 239  *
 240  ******************************************************************************/
 241
 242 ACPI_STATUS
 243 acpi_ns_search_and_enter (
 244         u32                     target_name,
 245         ACPI_WALK_STATE         *walk_state,
 246         ACPI_NAMESPACE_NODE     *node,
 247         OPERATING_MODE          interpreter_mode,
 248         OBJECT_TYPE_INTERNAL    type,
 249         u32                     flags,
 250         ACPI_NAMESPACE_NODE     **return_node)
 251 {
 252         ACPI_STATUS             status;
 253         ACPI_NAMESPACE_NODE     *new_node;
 254
 255
 256         /* Parameter validation */
 257
 258         if (!node || !target_name || !return_node) {
 259                 REPORT_ERROR (("Ns_search_and_enter: bad (null) parameter\n"));
 260                 return (AE_BAD_PARAMETER);
 261         }
 262
 263
 264         /* Name must consist of printable characters */
 265
 266         if (!acpi_cm_valid_acpi_name (target_name)) {
 267                 REPORT_ERROR (("Ns_search_and_enter: Bad character in ACPI Name\n"));
 268                 return (AE_BAD_CHARACTER);
 269         }
 270
 271
 272         /* Try to find the name in the table specified by the caller */
 273
 274         *return_node = ENTRY_NOT_FOUND;
 275         status = acpi_ns_search_node (target_name, node,
 276                            type, return_node);
 277         if (status != AE_NOT_FOUND) {
 278                 /*
 279                  * If we found it AND the request specifies that a find is an error,
 280                  * return the error
 281                  */
 282                 if ((status == AE_OK) &&
 283                         (flags & NS_ERROR_IF_FOUND)) {
 284                         status = AE_EXIST;
 285                 }
 286
 287                 /*
 288                  * Either found it or there was an error
 289                  * -- finished either way
 290                  */
 291                 return (status);
 292         }
 293
 294
 295         /*
 296          * Not found in the table.  If we are NOT performing the
 297          * first pass (name entry) of loading the namespace, search
 298          * the parent tree (all the way to the root if necessary.)
 299          * We don't want to perform the parent search when the
 300          * namespace is actually being loaded.  We want to perform
 301          * the search when namespace references are being resolved
 302          * (load pass 2) and during the execution phase.
 303          */
 304
 305         if ((interpreter_mode != IMODE_LOAD_PASS1) &&
 306                 (flags & NS_SEARCH_PARENT)) {
 307                 /*
 308                  * Not found in table - search parent tree according
 309                  * to ACPI specification
 310                  */
 311
 312                 status = acpi_ns_search_parent_tree (target_name, node,
 313                                  type, return_node);
 314                 if (ACPI_SUCCESS (status)) {
 315                         return (status);
 316                 }
 317         }
 318
 319
 320         /*
 321          * In execute mode, just search, never add names.  Exit now.
 322          */
 323         if (interpreter_mode == IMODE_EXECUTE) {
 324                 return (AE_NOT_FOUND);
 325         }
 326
 327
 328         /* Create the new named object */
 329
 330         new_node = acpi_ns_create_node (target_name);
 331         if (!new_node) {
 332                 return (AE_NO_MEMORY);
 333         }
 334
 335         /* Install the new object into the parent's list of children */
 336
 337         acpi_ns_install_node (walk_state, node, new_node, type);
 338         *return_node = new_node;
 339
 340         return (AE_OK);
 341 }
 342