objrtbld.c

一套美国国家宇航局人工智能中心NASA的专家系统工具源代码

      Process the bitmap node ONLY if it is
      the only node in the pattern
      ========================================= */
   do
     {
      if (thePattern->multifieldSlot)
        {
         tempPattern = thePattern;
         thePattern = thePattern->bottom;
        }
        
      /* ==========================================
         Determine if the last pattern field within
         a multifield slot is being processed.
         ========================================== */
         
      if (((thePattern->type == MF_WILDCARD) || 
           (thePattern->type == MF_VARIABLE)) &&
          (thePattern->right == NULL) && (tempPattern != NULL)) 
        endSlot = CLIPS_TRUE;
      else 
        endSlot = CLIPS_FALSE;
        
      /* ======================================
         Is there a node in the pattern network
         that can be reused (shared)?
         ====================================== */
      newNode = FindObjectPatternNode(currentLevel,thePattern,&nodeSlotGroup,endSlot);
   
      /* ==============================================
         If the pattern node cannot be shared, then add
         a new pattern node to the pattern network
         ============================================== */
      if (newNode == NULL)
        newNode = CreateNewObjectPatternNode(thePattern,nodeSlotGroup,lastLevel,endSlot);
      
      /* ====================================================
         Move on to the next field in the pattern to be added
         ==================================================== */
      if ((thePattern->right == NULL) && (tempPattern != NULL))
        {
         thePattern = tempPattern;
         tempPattern = NULL;
        }
        
      lastLevel = newNode;
      currentLevel = newNode->nextLevel;
      thePattern = thePattern->right;
     }
   while ((thePattern != NULL) ? (thePattern->userData == NULL) : CLIPS_FALSE);
   
   /* ===============================================
      Return the leaf node of the newly added pattern
      =============================================== */
   newAlphaNode = lastLevel->alphaNode;
   while (newAlphaNode != NULL)
     {
      if ((newClassBitMap == newAlphaNode->classbmp) &&
          (newSlotBitMap == newAlphaNode->slotbmp))
        return((struct patternNodeHeader *) newAlphaNode);
      newAlphaNode = newAlphaNode->nxtInGroup;
     }
   newAlphaNode = get_struct(objectAlphaNode);
   InitializePatternHeader(&newAlphaNode->header);
   newAlphaNode->matchTimeTag = 0L;
   newAlphaNode->patternNode = lastLevel;
   newAlphaNode->classbmp = newClassBitMap;
   IncrementBitMapCount(newClassBitMap);
   MarkBitMapClassesBusy(newClassBitMap,1);
   newAlphaNode->slotbmp = newSlotBitMap;
   if (newSlotBitMap != NULL)
     IncrementBitMapCount(newSlotBitMap);
   newAlphaNode->bsaveID = 0L;
   newAlphaNode->nxtInGroup = lastLevel->alphaNode;
   lastLevel->alphaNode = newAlphaNode;
   newAlphaNode->nxtTerminal = ObjectNetworkTerminalPointer();
   SetObjectNetworkTerminalPointer(newAlphaNode);
   return((struct patternNodeHeader *) newAlphaNode);
  }
  
/************************************************************************
  NAME         : FindObjectPatternNode
  DESCRIPTION  : Looks for a pattern node at a specified
                 level in the pattern network that can be reused (shared)
                 with a pattern field being added to the pattern network.
  INPUTS       : 1) The current layer of nodes being examined in the
                    object pattern network
                 2) The intermediate parse representation of the pattern
                    being added
                 3) A buffer for holding the first node of a group
                    of slots with the same name as the new node
                 4) An integer code indicating if this is the last
                    fiedl in a slot pattern or not
  RETURNS      : The old pattern network node matching the new node, or
                 NULL if there is none (nodeSlotGroup will hold the
                 place where to attach a new node)
  SIDE EFFECTS : nodeSlotGroup set
  NOTES        : None
 ************************************************************************/
static OBJECT_PATTERN_NODE *FindObjectPatternNode(listOfNodes,thePattern,
                                                  nodeSlotGroup,endSlot)
  OBJECT_PATTERN_NODE *listOfNodes;
  struct lhsParseNode *thePattern;
  OBJECT_PATTERN_NODE **nodeSlotGroup;
  unsigned endSlot;
  {
   *nodeSlotGroup = NULL;

   /* ========================================================
      Loop through the nodes at the given level in the pattern
      network looking for a node that can be reused (shared)
      ======================================================== */
   while (listOfNodes != NULL)
     {
      /* =======================================================
         A object pattern node can be shared if the slot name is
         the same, the test is on the same field in the pattern,
         and the network test expressions are the same
         ======================================================= */
      if (((thePattern->type == MF_WILDCARD) || (thePattern->type == MF_VARIABLE)) ?
          listOfNodes->multifieldNode : (listOfNodes->multifieldNode == 0))
        {
         if ((thePattern->slotNumber == (int) listOfNodes->slotNameID) &&
             (thePattern->index == listOfNodes->whichField) && 
             (thePattern->singleFieldsAfter == listOfNodes->leaveFields) &&
             (endSlot == listOfNodes->endSlot) &&
             IdenticalExpression(listOfNodes->networkTest,thePattern->networkTest))
           return(listOfNodes);
        }
      
      /* ============================================
         Find the beginning of a group of nodes with
         the same slot name testing on the same field
         ============================================ */
      if ((*nodeSlotGroup == NULL) &&
          (thePattern->index == listOfNodes->whichField) &&
          (thePattern->slotNumber == (int) listOfNodes->slotNameID))
        *nodeSlotGroup = listOfNodes;
      listOfNodes = listOfNodes->rightNode;
     }

   /* ============================================
      A shareable pattern node could not be found.
      ============================================ */
   return(NULL);
  }

/*****************************************************************
  NAME         : CreateNewObjectPatternNode
  DESCRIPTION  : Creates a new pattern node and initializes
                   all of its values.
  INPUTS       : 1) The intermediate parse representation
                    of the new pattern node
                 2) A pointer to the network node after
                    which to add the new node
                 3) A pointer to the parent node on the
                    level above to link the new node
                 4) An integer code indicating if this is the last
                    fiedl in a slot pattern or not
  RETURNS      : A pointer to the new pattern node
  SIDE EFFECTS : Pattern node allocated, initialized and
                   attached
  NOTES        : None
 *****************************************************************/
static OBJECT_PATTERN_NODE *CreateNewObjectPatternNode(thePattern,nodeSlotGroup,
                                                       upperLevel,endSlot)
  struct lhsParseNode *thePattern;
  OBJECT_PATTERN_NODE *nodeSlotGroup;
  OBJECT_PATTERN_NODE *upperLevel;
  unsigned endSlot;
  {
   OBJECT_PATTERN_NODE *newNode,*prvNode,*curNode;
   
   newNode = get_struct(objectPatternNode);
   newNode->blocked = CLIPS_FALSE;
   newNode->multifieldNode = CLIPS_FALSE;
   newNode->alphaNode = NULL;
   newNode->matchTimeTag = 0L;
   newNode->nextLevel = NULL;
   newNode->rightNode = NULL;
   newNode->leftNode = NULL;
   newNode->bsaveID = 0L;
   
   /* ========================================================
      Install the expression associated with this pattern node
      ======================================================== */
   newNode->networkTest = AddHashedExpression((EXPRESSION *) thePattern->networkTest);
   newNode->whichField = thePattern->index;
   newNode->leaveFields = thePattern->singleFieldsAfter;
   
   /* ======================================
      Install the slot name for the new node
      ====================================== */
   newNode->slotNameID = (unsigned) thePattern->slotNumber;
   if ((thePattern->type == MF_WILDCARD) || (thePattern->type == MF_VARIABLE))
     newNode->multifieldNode = CLIPS_TRUE;
   newNode->endSlot = endSlot;
   
   /* ============================================
      Set the upper level pointer for the new node
      ============================================ */
   newNode->lastLevel = upperLevel;
   
   /* ============================================ 
      If there are no nodes with this slot name on
      this level, simply prepend it to the front
      ============================================ */
   if (nodeSlotGroup == NULL)
     {
      if (upperLevel == NULL)
        {
         newNode->rightNode = ObjectNetworkPointer();
         SetObjectNetworkPointer(newNode);
        }
      else
        {
         newNode->rightNode = upperLevel->nextLevel;
         upperLevel->nextLevel = newNode;
        }
      if (newNode->rightNode != NULL)
        newNode->rightNode->leftNode = newNode;
      return(newNode);
     }
     
   /* ===========================================================
      Group this node with other nodes of the same name
      testing on the same field in the pattern
      on this level.  This allows us to do some optimization
      with constant tests on a particular slots.  If we put
      all constant tests for a particular slot/field group at the
      end of that group, then when one of those test succeeds
      during pattern-matching, we don't have to test any
      more of the nodes with that slot/field name to the right.
      =========================================================== */
   prvNode = NULL;
   curNode = nodeSlotGroup;
   while ((curNode == NULL) ? CLIPS_FALSE :
          (curNode->slotNameID == nodeSlotGroup->slotNameID) &&
          (curNode->whichField == nodeSlotGroup->whichField))
     {
      if ((curNode->networkTest == NULL) ? CLIPS_FALSE :
          ((curNode->networkTest->type != OBJ_PN_CONSTANT) ? CLIPS_FALSE :
           ((struct ObjectCmpPNConstant *) ValueToBitMap(curNode->networkTest->value))->pass))
        break;
      prvNode = curNode;
      curNode = curNode->rightNode;
     }   
   if (curNode != NULL)
     {
      newNode->leftNode = curNode->leftNode;
      newNode->rightNode = curNode;
      if (curNode->leftNode != NULL)
        curNode->leftNode->rightNode = newNode;
      else if (curNode->lastLevel != NULL)
        curNode->lastLevel->nextLevel = newNode;
      else
        SetObjectNetworkPointer(newNode);
      curNode->leftNode = newNode;
     }
   else
     {
      newNode->leftNode = prvNode;
      prvNode->rightNode = newNode;
     }
   
   return(newNode);
  }

/********************************************************
  NAME         : DetachObjectPattern
  DESCRIPTION  : Removes a pattern node and all of its  
   parent nodes from the pattern network. Nodes are only   
   removed if they are no longer shared (i.e. a pattern    
   node that has more than one child node is shared). A    
   pattern from a rule is typically removed by removing    
   the bottom most pattern node used by the pattern and    
   then removing any parent nodes which are not shared by  
   other patterns.                                         
                                                           
   Example:                                                
     Patterns (a b c d) and (a b e f) would be represented 
     by the pattern net shown on the left.  If (a b c d)   
     was detached, the resultant pattern net would be the  
     one shown on the right. The '=' represents an         
     end-of-pattern node.                                  
                                                           
           a                  a                            
           |                  |                            
           b                  b                            
           |                  |                            
           c--e               e                            
           |  |               |                            
           d  f               f                            
           |  |               |                            
           =  =               =           
  INPUTS       : The pattern to be removed
  RETURNS      : Nothing useful
  SIDE EFFECTS : All non-shared nodes associated with the
                 pattern are removed
  NOTES        : None
 ********************************************************/                 
static VOID DetachObjectPattern(thePattern)
  struct patternNodeHeader *thePattern;
  {
   OBJECT_ALPHA_NODE *alphaPtr,*prv,*terminalPtr;
   OBJECT_PATTERN_NODE *patternPtr,*upperLevel;
   
   /* ==================================================
      Get rid of any matches stored in the alpha memory.
      ================================================== */
   alphaPtr = (OBJECT_ALPHA_NODE *) thePattern;
   ClearObjectPatternMatches(alphaPtr);
   
   /* =======================================
      Unmark the classes to which the pattern
      is applicable and unmark the class and
      slot id maps so that they can become
      ephemeral
      ======================================= */
   MarkBitMapClassesBusy(alphaPtr->classbmp,-1);
   DeleteClassBitMap(alphaPtr->classbmp);
   if (alphaPtr->slotbmp != NULL)
     DecrementBitMapCount(alphaPtr->slotbmp);
   
   /* ======================================
      Only continue deleting this pattern if
      this is the last alpha memory attached
      ====================================== */
   prv = NULL;
   terminalPtr = ObjectNetworkTerminalPointer();
   while (terminalPtr != alphaPtr)
     {
      prv = terminalPtr;
      terminalPtr = terminalPtr->nxtTerminal;
     }
   if (prv == NULL)
     SetObjectNetworkTerminalPointer(terminalPtr->nxtTerminal);
   else
     prv->nxtTerminal = terminalPtr->nxtTerminal;
   
   prv = NULL;
   terminalPtr = alphaPtr->patternNode->alphaNode;
   while (terminalPtr != alphaPtr)
     {
      prv = terminalPtr;
      terminalPtr = terminalPtr->nxtInGroup;
     }
   if (prv == NULL)
     {
      if (alphaPtr->nxtInGroup != NULL)
        {