keyset.c

C++ 编写的EROS RTOS

      /* We don't contain theirEntry -- copy it into my table */
      *STAT.end_of_table = *theirEntry;
      STAT.end_of_table++;
      STAT.numUnsorted++;

      /* now increment past it */
      theirEntry++;
      theirCount--;
    } else {
      /* They don't contain our entry -- increment mine */
      myEntry++;
      myCount--;
    }
  }

  /* copy any remaining items from them */
  while (theirCount) {
    *STAT.end_of_table = *theirEntry;
    STAT.end_of_table++;
    STAT.numUnsorted++;
    
    theirEntry++;
    theirCount--;
  }

  if (STAT.numUnsorted > MAX_UNSORTED) {
    /* too many unsorted -- sort them in */
    require_sorted_table();
  }
  
  /* Now, return the segment to the other guy. */
  ReturnSegment();
  return 0;
}

uint32_t
RemoveKeysNotInSet(uint32_t krOtherSet)
{
  uint32_t theirCount;
  uint32_t myCount = STAT.numSorted;
  uint32_t result;

  struct table_entry *myEntry = the_table;
  struct table_entry *theirEntry = other_table;

  struct table_entry *myNewEnd = the_table;
  uint32_t myNewCount = 0u;
  
  result = VerifyAndGetSegmentOfSet(krOtherSet, &theirCount);
  if (result == RC_Internal_KeyToSelf) 
    return RC_OK; /* We already contain ourself */
  else if (result == RC_KeySet_PassedSetInvalid)
    return RC_KeySet_PassedSetInvalid;
  else if (result != RC_OK) {
    /* nice try. */
    return RC_RequestError;
  }
  /* now we've got the other segment */

  /* search through my table for items not in theirs, and remove them.
     (note that both of the lists are sorted coming into this code) */
  
  while (theirCount && myCount) {
    int cmpres = compare(myEntry->w, theirEntry->w);
    
    if (cmpres == 0) {
      /* We match -- copy if necessary, then increment both */
      if (myEntry != myNewEnd) {
	/*this guy's position has changed -- copy him to new position*/

	*myNewEnd = *myEntry;	
      }
      myNewEnd++;
      myNewCount++;

      myEntry++;
      myCount--;
      
      theirEntry++;
      theirCount--;
    } else if (cmpres > 0) {
      /* We don't contain theirEntry -- skip it */
      theirEntry++;
      theirCount--;
    } else {
      /* They don't contain our entry -- skip it, removing it from our
	 ending list. */
      myEntry++;
      myCount--;
    }
  }

  STAT.end_of_table = myNewEnd;
  STAT.numSorted = myNewCount;
  STAT.numUnsorted = 0;

  /* Now, return the segment to the other guy. */
  ReturnSegment();
  return 0;
}

uint32_t
CompareSets(uint32_t krOtherSet, uint32_t compareData)
{
  uint32_t theirCount;
  uint32_t myCount = STAT.numSorted;
  uint32_t result;

  uint32_t emptyintersect = 1; /* ME intersect HIM == 0 */
  uint32_t othermissing = 0;   /* he's missing something I have */
  uint32_t memissing = 0;      /* I'm missing something he has */
  uint32_t datamismatch = 0;   /* data fields mismatch -- only if
				  compareData */

  struct table_entry *myEntry = the_table;
  struct table_entry *theirEntry = other_table;

  result = VerifyAndGetSegmentOfSet(krOtherSet, &theirCount);
  if (result == RC_Internal_KeyToSelf)
    return RC_KeySet_SetsEqual; /* We equal ourself, thank you */
  else if (result == RC_KeySet_PassedSetInvalid)
    return RC_KeySet_PassedSetInvalid;
  else if (result != RC_OK) {
    /* nice try. */
    return RC_RequestError;
  }
  /* now we've got the other segment */

  /* walk through both (sorted) tables, comparing the current pointers in
     each:
     If the keys are equal, we increment both counters to get past them.
     If *myEntry < *theirEntry, increment myEntry.
     if *myEntry > *theirEntry, we can't contain them, so break.
   */
  
  while (theirCount && myCount) {
    int cmpres;
    
#if 0
    kdprintf(KR_OSTREAM,
	     "Comparing 0x%08x %08x %08x %08x\n"
	     "       to 0x%08x %08x %08x %08x\n",
	     myEntry->w[0], myEntry->w[1], myEntry->w[2], myEntry->w[3],
	     theirEntry->w[0], theirEntry->w[1], theirEntry->w[2],
	     theirEntry->w[3]);
#endif
    
    cmpres = compare(myEntry->w, theirEntry->w);
    
    if (cmpres == 0) {
      emptyintersect = 0;
      if (compareData) {
	if (myEntry->w[4] != theirEntry->w[4]) {
	  datamismatch = 1;
	  break;
	}
      }
      /* increment both */
      myEntry++;
      myCount--;
      
      theirEntry++;
      theirCount--;
    } else if (cmpres > 0) {
      /* Can't contain their item */
      memissing = 1;

      theirEntry++;
      theirCount--;
    } else {
      /* increment mine */
      othermissing = 1;

      myEntry++;
      myCount--;
    }
  }

  if (!datamismatch) {
    if (myCount != 0)
      othermissing = 1;
    if (theirCount != 0)
      memissing = 1;
  }
  /* Now, return the segment to the other guy. */
  ReturnSegment();

#if 0
  kdprintf(KR_OSTREAM, "Contains completes. theirCount = %d\n", theirCount);
#endif
  
  if (compareData && datamismatch) 
    return RC_KeySet_DataMismatch;

  if (!memissing && !othermissing)
    return RC_KeySet_SetsEqual;

  if (emptyintersect)  /* both empty is taken care of by Equal case */
    return RC_KeySet_SetsDisjoint;

  if (!memissing && othermissing) /* I contain him */
    return RC_KeySet_SetContainsOtherSet;

  if (memissing && !othermissing) /* He contains me */
    return RC_KeySet_OtherSetContainsSet;

  /* none of the above */
  return RC_KeySet_SetsDifferent;
}

uint32_t
ProcessRequest(Message *msg)
{
  Bits curBits;
  uint32_t kbVersion;

  uint32_t rdOnly = (msg->rcv_keyInfo == ReadOnly_KeyData);

  uint32_t setInvalid = 0;

  GetKeyBits(KR_KEYBITS, KR_ARG0, &kbVersion, &curBits);

  if (kbVersion != STAT.startKeyBitsVersion
      && (STAT.numSorted || STAT.numUnsorted)) {
    /* we aren't empty, and keybits version changed */
    kdprintf(KR_OSTREAM, "Hey! Keybits version changed!\n");
    setInvalid = 1; /* everything should check readonly first, then
		       setInvalid */
  }


  DEBUG(cmds) {
    kprintf(KR_OSTREAM,
	    "KeySet: Got request 0x%08x, w1 = 0x%08x\n",
	    msg->rcv_code,
	    msg->rcv_w1);
    kprintf(KR_OSTREAM,
	    "Slot %d Keybits 0x%08x %08x %08x %08x\n",
	    KR_ARG0,
	    curBits.w[0],
	    curBits.w[1],
	    curBits.w[2],
	    curBits.w[3]);
  }
  
  msg->snd_code = RC_UnknownRequest;
  msg->snd_w1 = 0;
  msg->snd_w2 = 0;
  msg->snd_w3 = 0;

  switch(msg->rcv_code) {
  case OC_KeySet_AddKey:
    {
      struct table_entry *the_entry;

      if (rdOnly) {
	msg->snd_code = RC_UnknownRequest;
	break;
      } else if (setInvalid) {
	msg->snd_code = RC_KeySet_SetInvalid;
	break;
      }

      the_entry = FIND(the_table, curBits.w,STAT);

      DEBUG(add) kprintf(KR_OSTREAM,
			 "AddKey:  FIND returned %08x\n",
			 the_entry);
      
      if (the_entry != NULL) {
	/* already there, just update the entry. */
	msg->snd_w1 = the_entry->w[4];
	the_entry->w[4] = msg->rcv_w1;
	
	msg->snd_code = RC_OK;
      } else {
	/* not there -- insert it */
	the_entry = STAT.end_of_table;

	STAT.end_of_table++;
	STAT.numUnsorted++;
      
	DEBUG(add) kprintf(KR_OSTREAM,
			   "AddKey:  Writing new entry at 0x%08x\n",
			   the_entry);
      
	the_entry->w[0] = curBits.w[0];
	the_entry->w[1] = curBits.w[1];
	the_entry->w[2] = curBits.w[2];
	the_entry->w[3] = curBits.w[3];
	the_entry->w[4] = msg->rcv_w1; /* data field gets w1 */

	if (STAT.numUnsorted > MAX_UNSORTED) {
	  /* too many unsorted -- sort them in */
	  require_sorted_table();
	}
	msg->snd_code = RC_OK;
      }
      break;
    }
  case OC_KeySet_RemoveKey:
    {
      struct table_entry *entry;

      if (rdOnly) {
	msg->snd_code = RC_UnknownRequest;
	break;
      } else if (setInvalid) {
	msg->snd_code = RC_KeySet_SetInvalid;
	break;
      }

      entry = FIND(the_table, curBits.w,STAT);
      if (entry == NULL) {
	msg->snd_code = RC_KeySet_KeyNotInSet;
	break;
      } else {
	uint32_t x = the_table - entry;
	uint32_t max = STAT.numSorted + STAT.numUnsorted;

	/* copy out the stored uint32_t */
	msg->snd_w1 = entry->w[4];

	/* update the counts -- moving blows away x */
	if (x < STAT.numSorted) {
	  STAT.numSorted--;
	} else {
	  STAT.numUnsorted--;
	}
	
	/* move everything back 1 slot */
#if 0 /* USE_MEMCPY */	
	memcpy(&the_table[x],   /* to */
	       &the_table[x+1], /*from*/
	       ((max - x) - 1)*sizeof(struct table_entry)); /* bytes */
#else /* ! USE_MEMCPY */
	for (x++ ; x < max; x++) {
	  the_table[x-1] = the_table[x];
	}
#endif
	msg->snd_code = RC_OK;
      }
    }
  case OC_KeySet_ContainsKey:
    {
      struct table_entry *entry;
      
      if (setInvalid) {
	msg->snd_code = RC_KeySet_SetInvalid;
	break;
      }

      entry = FIND(the_table, curBits.w,STAT);
      DEBUG(contains)
	kprintf(KR_OSTREAM,
		"KeySet: FIND returns 0x%08x\n", entry);
      if (entry == NULL) {
	msg->snd_code = RC_KeySet_KeyNotInSet;
	break;
      } else {
	msg->snd_w1 = entry->w[4]; /* give back the word */
	msg->snd_code = RC_OK;
	break;
      }
    }
  case OC_KeySet_IsEmpty:
    if (setInvalid) {
      msg->snd_code = RC_UnknownRequest;
      break;
    }
    /* return 0 if we have entries, 1 if not */
    msg->snd_code = (STAT.numSorted || STAT.numUnsorted)?0:1;

  case OC_KeySet_Empty:

    if (rdOnly) {
      msg->snd_code = RC_UnknownRequest;
      break;
    }
    /* if we are not valid, emptying the set makes us valid, so... */
    STAT.numSorted = 0;
    STAT.numUnsorted = 0;
    
    msg->snd_code = RC_OK;
    /* if shap ever gets around to implementing FreshSpace's truncate,
       We'll use it to free all of the allocated space.  Until
       then... */
    break;
    
  case OC_KeySet_MakeReadOnlyKey:
    
    /* FIXME: check return code */
    process_make_start_key(KR_SELF,
			  ReadOnly_KeyData,
			  KR_SCRATCH);
    
    msg->snd_key0 = KR_SCRATCH;
    msg->snd_code = RC_OK;
    break;
    
  case OC_KeySet_AddKeysFromSet:

    if (rdOnly) {
      msg->snd_code = RC_UnknownRequest;
      break;
    } else if (setInvalid) {
      msg->snd_code = RC_KeySet_SetInvalid;
      break;
    }

    require_sorted_table();

    msg->snd_code = AddKeysFromSet(KR_ARG0);
    break;
  case OC_KeySet_RemoveKeysNotInSet:

    if (rdOnly) {
      msg->snd_code = RC_UnknownRequest;
      break;
    } else if (setInvalid) {
      msg->snd_code = RC_KeySet_SetInvalid;
      break;
    }

    require_sorted_table();

    msg->snd_code = RemoveKeysNotInSet(KR_ARG0);
    break;

#if 1 /* IsSubsetOfSet */
  case OC_KeySet_IsSubsetOfSet:
#else
  case OC_KeySet_CompareSets: /* does expanded CompareSets imply a
				 security problem for Constructors? */
#endif
    if (setInvalid) {    
      msg->snd_code = RC_KeySet_SetInvalid;
      break;
    }

    require_sorted_table();

#if 1 /* isSubSetOfSet */
    msg->snd_code = CompareSets(KR_ARG0,
				0);
    msg->snd_code = (msg->snd_code == RC_KeySet_SetsEqual
		     || msg->snd_code == RC_KeySet_SetContainsOtherSet
		    ) ? RC_OK : 1;
#else
    msg->snd_code = CompareSets(KR_ARG0,
				msg->rcv_w1);
#endif

    break;
  case OC_KeySet_Internal_GetSegment:
    
    if (setInvalid) {
      msg->snd_code = RC_KeySet_SetInvalid;
      break;
    }

    msg->snd_code = SlaveProtocol();
    break;
  case OC_Destroy:
    if (rdOnly) {
      msg->snd_code = RC_UnknownRequest;
      break;
    }
    teardown();
    return 0; /* CAN'T HAPPEN */
  }
  DEBUG(cmds)
    kprintf(KR_OSTREAM,
	    "KeySet: Returning result 0x%08x\n",
	    msg->snd_code);
  /* update keyData field, if appropriate (i.e. we were empty and
     something was added to us) -- This happens if the keyDatas don't
     match, we are valid, and we are now non-empty */

  if (kbVersion != STAT.startKeyBitsVersion
      && !setInvalid
      && (STAT.numSorted || STAT.numUnsorted)) {
    STAT.startKeyBitsVersion = kbVersion;
  }
  return 1;
}

int
main()
{
  Message msg;
  
  Initialize();

  /* make a write key and return it. */
  process_make_start_key(KR_SELF, Normal_KeyData, KR_ARG0);

  DEBUG(init) kdprintf(KR_OSTREAM,
		       "KeySet: Got start key. Ready to rock and roll\n");

  msg.snd_invKey = KR_RETURN;
  msg.snd_key0 = KR_ARG0;
  msg.snd_key1 = KR_VOID;
  msg.snd_key2 = KR_VOID;
  msg.snd_key3 = KR_VOID;
  msg.snd_data = 0;
  msg.snd_len = 0;
  msg.snd_code = 0;
  msg.snd_w1 = 0;
  msg.snd_w2 = 0;
  msg.snd_w3 = 0;

  msg.rcv_key0 = KR_ARG0;
  msg.rcv_key1 = KR_VOID;
  msg.rcv_key2 = KR_VOID;
  msg.rcv_key3 = KR_RETURN;
  msg.rcv_len = 0;
  msg.rcv_code = 0;
  msg.rcv_w1 = 0;
  msg.rcv_w2 = 0;
  msg.rcv_w3 = 0;

  do {
    RETURN(&msg);

    /* clear all of the slots we might use for sending */
    msg.snd_key0 = KR_VOID;              /* until otherwise proven */

    ProcessRequest(&msg);
  } while(1); /*forever*/
}

#ifndef NDEBUG
int __assert(const char *expr, const char *file, int line)
{
  kdprintf(KR_OSTREAM, "%s:%d: Assertion failed: '%s'\n",
           file, line, expr);
  return 0;
}
#endif