objrtmch.c

VC嵌入式CLips专家系统,实现战场环境的目标识别

  NAME         : CompareSlotBitMaps
  DESCRIPTION  : Compares two slot bitmaps by
                 bitwising and'ing byte per byte up
                 to the length of the smaller map.
  INPUTS       : The two slot bitmaps
  RETURNS      : TRUE if any common bits
                 are set in both maps, FALSE
                 otherwise
  SIDE EFFECTS : None
  NOTES        : None
 ***************************************************/
static intBool CompareSlotBitMaps(
  SLOT_BITMAP *smap1,
  SLOT_BITMAP *smap2)
  {
   unsigned short i,maxByte;

   maxByte = (unsigned short)
             (((smap1->maxid < smap2->maxid) ?
              smap1->maxid : smap2->maxid) / BITS_PER_BYTE);
   for (i = 0 ; i <= maxByte ; i++)
     if (smap1->map[i] & smap2->map[i])
       return(TRUE);
   return(FALSE);
  }

/**********************************************************************************
  NAME         : ObjectPatternMatch
  DESCRIPTION  : Iterates through all the pattern nodes on one level
                 in the pattern network.  A node is only processed
                 if it can lead to a terminating class bitmap node
                 which applies to the object being matched.  This
                 allows for a significant reduction in the number of
                 patterns considered.
  INPUTS       : 1) The offset of the slot position from the pattern index
                 2) The pattern node being examined
                 3) The end of the list of multifield markers for the pattern
  RETURNS      : Nothing useful
  SIDE EFFECTS : The pattern tests are evaluated and the child nodes may
                 be processed (which may cause a whole series of Rete network
                 updates).
  NOTES        : Several globals are used to keep track of the current
                 slot being examined:
                 CurrentPatternMarks - the series of multifield markers
                 CurrentPatternObject - the object being pattern-matched
                 CurrentPatternObjectSlot - the current slot being examined
                 CurrentObjectSlotLength - the cardinality of the slot value

                 An optimization is performed when evaluating
                 constant tests on a slot value field.  All
                 pattern nodes on a level which restrict the same slot
                 are grouped together.  Those which are constant
                 tests are placed at the far right.  Thus, as soon
                 as one of these constant tests succeeds, the remaining
                 nodes for that slot on this level can be skipped
 **********************************************************************************/
static void ObjectPatternMatch(
  void *theEnv,
  int offset,
  OBJECT_PATTERN_NODE *patternTop,
  struct multifieldMarker *endMark)
  {
   register unsigned saveSlotLength;
   register INSTANCE_SLOT *saveSlot;
   OBJECT_PATTERN_NODE *blockedNode;

   while (patternTop != NULL)
     {
      /* ===========================================================
         MarkObjectPatternNetwork() has already marked pattern nodes
         which need processing according to the class bitmaps,
         slot updates and incremental reset status
         =========================================================== */
      if (patternTop->matchTimeTag == ObjectReteData(theEnv)->CurrentObjectMatchTimeTag)
        {
         /* ========================================
            Make sure we are examining the correct
            slot of the object for this pattern node
            ======================================== */
         if ((patternTop->slotNameID == ISA_ID) ||
             (patternTop->slotNameID == NAME_ID))
           {
            ObjectReteData(theEnv)->CurrentPatternObjectSlot = NULL;
            ObjectReteData(theEnv)->CurrentObjectSlotLength = 1;
            offset = 0;
           }
         else if ((ObjectReteData(theEnv)->CurrentPatternObjectSlot == NULL) ? TRUE :
                  (ObjectReteData(theEnv)->CurrentPatternObjectSlot->desc->slotName->id != patternTop->slotNameID))
           {
            /* ====================================================
               Need to reset the indices for the multifield
               markers now that we have moved onto a different slot
                  ==================================================== */
            ObjectReteData(theEnv)->CurrentPatternObjectSlot =
             ObjectReteData(theEnv)->CurrentPatternObject->slotAddresses[ObjectReteData(theEnv)->CurrentPatternObject->cls->slotNameMap
                                             [patternTop->slotNameID] - 1];
            offset = 0;
            if (ObjectReteData(theEnv)->CurrentPatternObjectSlot->desc->multiple)
              ObjectReteData(theEnv)->CurrentObjectSlotLength =
                GetInstanceSlotLength(ObjectReteData(theEnv)->CurrentPatternObjectSlot);
            else
              ObjectReteData(theEnv)->CurrentObjectSlotLength = 1;
           }

         /* ========================================================
            Process the pattern node.  If it is satisfied by the
            the instance, ProcessPatternNode() will recursively pass
            all of its children nodes through ObjectPatternMatch()
            ======================================================== */
         saveSlotLength = ObjectReteData(theEnv)->CurrentObjectSlotLength;
         saveSlot = ObjectReteData(theEnv)->CurrentPatternObjectSlot;
         ProcessPatternNode(theEnv,offset,patternTop,endMark);
         ObjectReteData(theEnv)->CurrentObjectSlotLength = saveSlotLength;
         ObjectReteData(theEnv)->CurrentPatternObjectSlot = saveSlot;
        }

      /* ==============================================================
         Move on to the siblings of this node - if the current node was
         a constant test that succeeded, skip further sibling nodes
         (which test on the same field in the pattern)
         which match on the same slot since they are all constant tests
         as well and will, of course fail.
         ============================================================== */
      if (patternTop->blocked == TRUE)
        {
         patternTop->blocked = FALSE;
         blockedNode = patternTop;
         patternTop = patternTop->rightNode;
         while (patternTop != NULL)
           {
            if ((patternTop->slotNameID != blockedNode->slotNameID) ||
                (patternTop->whichField != blockedNode->whichField))
              break;
            patternTop = patternTop->rightNode;
           }
        }
      else
        patternTop = patternTop->rightNode;
     }
  }

/**********************************************************************************
  NAME         : ProcessPatternNode
  DESCRIPTION  : Determines if a pattern node satsifies the corresponding
                 slot value field(s) in an object.  If it does,
                 ObjectPatternMatch() is recursively called to process
                 the child nodes of this node.  In this mutual recursion
                 between ObjectPatternMatch() and ProcessPatternNode(),
                 the nodes of all applicable patterns are processed
                 to completion.  ObjectPatternMatch() enters an object
                 into a pattern's aplha memory when the traversal reaches
                 a terminal class bitmap node.
  INPUTS       : 1) The offset of the slot index from the pattern index
                 2) The pattern node being examined
                 3) The end of the list of multifield markers for the pattern
  RETURNS      : Nothing useful
  SIDE EFFECTS : The pattern tests are evaluated and the child nodes may
                 be processed (which may cause a whole series of Rete network
                 updates).
  NOTES        : Several globals are used to keep track of the current
                 slot being examined:
                 CurrentPatternMarks - the series of multifield markers
                 CurrentPatternObject - the object being pattern-matched
                 CurrentPatternObjectSlot - the current slot being examined
                 CurrentObjectSlotLength - the cardinality of the slot value
 **********************************************************************************/
static void ProcessPatternNode(
  void *theEnv,
  int offset,
  OBJECT_PATTERN_NODE *patternNode,
  struct multifieldMarker *endMark)
  {
   int patternSlotField,objectSlotField;
   unsigned objectSlotLength;
   int repeatCount;
   INSTANCE_SLOT *objectSlot;
   struct multifieldMarker *newMark;

   patternSlotField = patternNode->whichField;
   objectSlotField = patternSlotField + offset;

   /* ==========================================
      If this is a test on the class or the name
      of the object, process it separately.
      ========================================== */
   if (ObjectReteData(theEnv)->CurrentPatternObjectSlot == NULL)
     {
      if ((patternNode->networkTest == NULL) ? TRUE :
          (EvaluateObjectPatternTest(theEnv,objectSlotField,NULL,
                                     (EXPRESSION *) patternNode->networkTest,patternNode)))
        {
         if (patternNode->alphaNode != NULL)
           CreateObjectAlphaMatch(theEnv,patternNode->alphaNode);
         ObjectPatternMatch(theEnv,offset,patternNode->nextLevel,endMark);
        }
      return;
     }

   /* ================================
      Check a single-field restriction
      ================================ */
   if (patternNode->multifieldNode == 0)
     {
      if ((patternNode->networkTest == NULL) ? TRUE :
          EvaluateObjectPatternTest(theEnv,objectSlotField,NULL,
                                    (EXPRESSION *) patternNode->networkTest,patternNode))
        {
         if (patternNode->alphaNode != NULL)
           CreateObjectAlphaMatch(theEnv,patternNode->alphaNode);
         ObjectPatternMatch(theEnv,offset,patternNode->nextLevel,endMark);
        }
      return;
     }

   /* ==================================================================
      Check a multifield restriction.  Add a marker for this field which
      has indices indicating to which values in the object slot the
      multifield pattern node is bound
      ================================================================== */
   newMark = get_struct(theEnv,multifieldMarker);
   newMark->whichField = patternSlotField;
   newMark->where.whichSlot = (void *) ObjectReteData(theEnv)->CurrentPatternObjectSlot->desc->slotName->name;
   newMark->startPosition = objectSlotField;
   newMark->next = NULL;
   if (ObjectReteData(theEnv)->CurrentPatternObjectMarks == NULL)
     ObjectReteData(theEnv)->CurrentPatternObjectMarks = newMark;
   else
     endMark->next = newMark;

   /* ==========================================================
      If there are further pattern restrictions on this slot,
      try pattern-matching for all possible bound values of the
      multifield pattern node: from no values to all values from
      the starting position of the multifield to the end of the
      object slot.  Otherwise, bind the multifield to all the
      remaining fields in the slot value and continue with
      pattern-matching
      ========================================================== */
   if (patternNode->endSlot == FALSE)
     {
      objectSlotLength = ObjectReteData(theEnv)->CurrentObjectSlotLength;
      objectSlot = ObjectReteData(theEnv)->CurrentPatternObjectSlot;
      newMark->endPosition = newMark->startPosition - 1;
      repeatCount = (int) (objectSlotLength - newMark->startPosition
                    - patternNode->leaveFields + 2);
      while (repeatCount > 0)
        {
         if ((patternNode->networkTest == NULL) ? TRUE :
              EvaluateObjectPatternTest(theEnv,objectSlotField,newMark,
                        (EXPRESSION *) patternNode->networkTest,patternNode))
           {
            if (patternNode->alphaNode != NULL)
              CreateObjectAlphaMatch(theEnv,patternNode->alphaNode);
            ObjectPatternMatch(theEnv,(int) (offset + (newMark->endPosition - objectSlotField)),
                               patternNode->nextLevel,newMark);
            ObjectReteData(theEnv)->CurrentObjectSlotLength = objectSlotLength;
            ObjectReteData(theEnv)->CurrentPatternObjectSlot = objectSlot;
           }
         newMark->endPosition++;
         repeatCount--;
        }
     }
   else
     {
      newMark->endPosition = (long) ObjectReteData(theEnv)->CurrentObjectSlotLength;
      if ((patternNode->networkTest == NULL) ? TRUE :
          EvaluateObjectPatternTest(theEnv,objectSlotField,newMark,
                                    (EXPRESSION *) patternNode->networkTest,patternNode))
        {
         if (patternNode->alphaNode != NULL)
           CreateObjectAlphaMatch(theEnv,patternNode->alphaNode);
         ObjectPatternMatch(theEnv,0,patternNode->nextLevel,newMark);
        }
     }

   /* ======================================
      Delete the temporary multifield marker
      ====================================== */

   if (ObjectReteData(theEnv)->CurrentPatternObjectMarks == newMark)
     ObjectReteData(theEnv)->CurrentPatternObjectMarks = NULL;
   else
     endMark->next = NULL;
   rtn_struct(theEnv,multifieldMarker,newMark);
  }

/***************************************************
  NAME         : CreateObjectAlphaMatch
  DESCRIPTION  : Places an instance in the alpha
                 memory of a pattern and drives the
                 partial match through the join
                 network
  INPUTS       : The alpha memory node
  RETURNS      : Nothing useful
  SIDE EFFECTS : Join network updated
  NOTES        : None
 ***************************************************/
static void CreateObjectAlphaMatch(
  void *theEnv,
  OBJECT_ALPHA_NODE *alphaPtr)
  {
   struct joinNode *listOfJoins;
   struct partialMatch *theMatch;
   struct patternMatch *newMatch;

   while (alphaPtr != NULL)
     {
      if (alphaPtr->matchTimeTag == ObjectReteData(theEnv)->CurrentObjectMatchTimeTag)
        {
         /* ===================================================
            If we have reached the class bitmap of the pattern,
            place the object in the alpha memory of each of
            the terminal nodes underneath and drive
            the partial matches through the join network.

            Insert the instance into the alpha memory
            of this pattern and mark it as busy
            =================================================== */
         ObjectReteData(theEnv)->CurrentPatternObject->busy++;
         theMatch = CreateAlphaMatch(theEnv,(void *) ObjectReteData(theEnv)->CurrentPatternObject,
                                     ObjectReteData(theEnv)->CurrentPatternObjectMarks,
                                     (struct patternNodeHeader *) alphaPtr);

         /* ======================================
            Attach the partial match to the object
            to ease later retraction
            ====================================== */
         newMatch = get_struct(theEnv,patternMatch);
         newMatch->next = (struct patternMatch *) ObjectReteData(theEnv)->CurrentPatternObject->partialMatchList;
         newMatch->matchingPattern = (struct patternNodeHeader *) alphaPtr;
         newMatch->theMatch = theMatch;
         ObjectReteData(theEnv)->CurrentPatternObject->partialMatchList = (void *) newMatch;

         /* ================================================
            Drive the partial match through the join network
            ================================================ */
         listOfJoins = alphaPtr->header.entryJoin;
         while (listOfJoins != NULL)
           {
            NetworkAssert(theEnv,theMatch,listOfJoins,RHS);
            listOfJoins = listOfJoins->rightMatchNode;