regex_internal.c

硬盘各项性能的测试,如温度容量版本健康度型号

      if (BE (new_array == NULL, 0))
	return -1;
      /* Copy the elements they are followed by the new element.  */
      if (idx > 0)
	memcpy (new_array, set->elems, sizeof (int) * (idx));
      /* Copy the elements which follows the new element.  */
      if (set->nelem - idx > 0)
	memcpy (new_array + idx + 1, set->elems + idx,
		sizeof (int) * (set->nelem - idx));
      re_free (set->elems);
      set->elems = new_array;
    }
  else
    {
      /* Move the elements which follows the new element.  */
      if (set->nelem - idx > 0)
	memmove (set->elems + idx + 1, set->elems + idx,
		 sizeof (int) * (set->nelem - idx));
    }
  /* Insert the new element.  */
  set->elems[idx] = elem;
  ++set->nelem;
  return 1;
}

/* Compare two node sets SET1 and SET2.
   return 1 if SET1 and SET2 are equivalent, retrun 0 otherwise.  */

static int
re_node_set_compare (set1, set2)
     const re_node_set *set1, *set2;
{
  int i;
  if (set1 == NULL || set2 == NULL || set1->nelem != set2->nelem)
    return 0;
  for (i = 0 ; i < set1->nelem ; i++)
    if (set1->elems[i] != set2->elems[i])
      return 0;
  return 1;
}

/* Return (idx + 1) if SET contains the element ELEM, return 0 otherwise.  */

static int
re_node_set_contains (set, elem)
     const re_node_set *set;
     int elem;
{
  int idx, right, mid;
  if (set->nelem <= 0)
    return 0;

  /* Binary search the element.  */
  idx = 0;
  right = set->nelem - 1;
  while (idx < right)
    {
      mid = (idx + right) / 2;
      if (set->elems[mid] < elem)
	idx = mid + 1;
      else
	right = mid;
    }
  return set->elems[idx] == elem ? idx + 1 : 0;
}

static void
re_node_set_remove_at (set, idx)
     re_node_set *set;
     int idx;
{
  if (idx < 0 || idx >= set->nelem)
    return;
  if (idx < set->nelem - 1)
    memmove (set->elems + idx, set->elems + idx + 1,
	     sizeof (int) * (set->nelem - idx - 1));
  --set->nelem;
}


/* Add the token TOKEN to dfa->nodes, and return the index of the token.
   Or return -1, if an error will be occured.  */

static int
re_dfa_add_node (dfa, token, mode)
     re_dfa_t *dfa;
     re_token_t token;
     int mode;
{
  if (dfa->nodes_len >= dfa->nodes_alloc)
    {
      re_token_t *new_array;
      dfa->nodes_alloc *= 2;
      new_array = re_realloc (dfa->nodes, re_token_t, dfa->nodes_alloc);
      if (BE (new_array == NULL, 0))
	return -1;
      else
	dfa->nodes = new_array;
      if (mode)
	{
	  int *new_nexts, *new_indices;
	  re_node_set *new_edests, *new_eclosures, *new_inveclosures;

	  new_nexts = re_realloc (dfa->nexts, int, dfa->nodes_alloc);
	  new_indices = re_realloc (dfa->org_indices, int, dfa->nodes_alloc);
	  new_edests = re_realloc (dfa->edests, re_node_set, dfa->nodes_alloc);
	  new_eclosures = re_realloc (dfa->eclosures, re_node_set,
				      dfa->nodes_alloc);
	  new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
					 dfa->nodes_alloc);
	  if (BE (new_nexts == NULL || new_indices == NULL
		  || new_edests == NULL || new_eclosures == NULL
		  || new_inveclosures == NULL, 0))
	    return -1;
	  dfa->nexts = new_nexts;
	  dfa->org_indices = new_indices;
	  dfa->edests = new_edests;
	  dfa->eclosures = new_eclosures;
	  dfa->inveclosures = new_inveclosures;
	}
    }
  dfa->nodes[dfa->nodes_len] = token;
  dfa->nodes[dfa->nodes_len].duplicated = 0;
  dfa->nodes[dfa->nodes_len].constraint = 0;
  return dfa->nodes_len++;
}

static unsigned int inline
calc_state_hash (nodes, context)
     const re_node_set *nodes;
     unsigned int context;
{
  unsigned int hash = nodes->nelem + context;
  int i;
  for (i = 0 ; i < nodes->nelem ; i++)
    hash += nodes->elems[i];
  return hash;
}

/* Search for the state whose node_set is equivalent to NODES.
   Return the pointer to the state, if we found it in the DFA.
   Otherwise create the new one and return it.  In case of an error
   return NULL and set the error code in ERR.
   Note: - We assume NULL as the invalid state, then it is possible that
	   return value is NULL and ERR is REG_NOERROR.
	 - We never return non-NULL value in case of any errors, it is for
	   optimization.  */

static re_dfastate_t*
re_acquire_state (err, dfa, nodes)
     reg_errcode_t *err;
     re_dfa_t *dfa;
     const re_node_set *nodes;
{
  unsigned int hash;
  re_dfastate_t *new_state;
  struct re_state_table_entry *spot;
  int i;
  if (BE (nodes->nelem == 0, 0))
    {
      *err = REG_NOERROR;
      return NULL;
    }
  hash = calc_state_hash (nodes, 0);
  spot = dfa->state_table + (hash & dfa->state_hash_mask);

  for (i = 0 ; i < spot->num ; i++)
    {
      re_dfastate_t *state = spot->array[i];
      if (hash != state->hash)
	continue;
      if (re_node_set_compare (&state->nodes, nodes))
	return state;
    }

  /* There are no appropriate state in the dfa, create the new one.  */
  new_state = create_ci_newstate (dfa, nodes, hash);
  if (BE (new_state != NULL, 1))
    return new_state;
  else
    {
      *err = REG_ESPACE;
      return NULL;
    }
}

/* Search for the state whose node_set is equivalent to NODES and
   whose context is equivalent to CONTEXT.
   Return the pointer to the state, if we found it in the DFA.
   Otherwise create the new one and return it.  In case of an error
   return NULL and set the error code in ERR.
   Note: - We assume NULL as the invalid state, then it is possible that
	   return value is NULL and ERR is REG_NOERROR.
	 - We never return non-NULL value in case of any errors, it is for
	   optimization.  */

static re_dfastate_t*
re_acquire_state_context (err, dfa, nodes, context)
     reg_errcode_t *err;
     re_dfa_t *dfa;
     const re_node_set *nodes;
     unsigned int context;
{
  unsigned int hash;
  re_dfastate_t *new_state;
  struct re_state_table_entry *spot;
  int i;
  if (nodes->nelem == 0)
    {
      *err = REG_NOERROR;
      return NULL;
    }
  hash = calc_state_hash (nodes, context);
  spot = dfa->state_table + (hash & dfa->state_hash_mask);

  for (i = 0 ; i < spot->num ; i++)
    {
      re_dfastate_t *state = spot->array[i];
      if (hash != state->hash)
	continue;
      if (re_node_set_compare (state->entrance_nodes, nodes)
	  && state->context == context)
	return state;
    }
  /* There are no appropriate state in `dfa', create the new one.  */
  new_state = create_cd_newstate (dfa, nodes, context, hash);
  if (BE (new_state != NULL, 1))
    return new_state;
  else
    {
      *err = REG_ESPACE;
      return NULL;
    }
}

/* Allocate memory for DFA state and initialize common properties.
   Return the new state if succeeded, otherwise return NULL.  */

static re_dfastate_t *
create_newstate_common (dfa, nodes, hash)
     re_dfa_t *dfa;
     const re_node_set *nodes;
     unsigned int hash;
{
  re_dfastate_t *newstate;
  reg_errcode_t err;
  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
  if (BE (newstate == NULL, 0))
    return NULL;
  err = re_node_set_init_copy (&newstate->nodes, nodes);
  if (BE (err != REG_NOERROR, 0))
    {
      re_free (newstate);
      return NULL;
    }
  newstate->trtable = NULL;
  newstate->trtable_search = NULL;
  newstate->hash = hash;
  return newstate;
}

/* Store the new state NEWSTATE whose hash value is HASH in appropriate
   position.  Return value indicate the error code if failed.  */

static reg_errcode_t
register_state (dfa, newstate, hash)
     re_dfa_t *dfa;
     re_dfastate_t *newstate;
     unsigned int hash;
{
  struct re_state_table_entry *spot;
  spot = dfa->state_table + (hash & dfa->state_hash_mask);

  if (spot->alloc <= spot->num)
    {
      re_dfastate_t **new_array;
      spot->alloc = 2 * spot->num + 2;
      new_array = re_realloc (spot->array, re_dfastate_t *, spot->alloc);
      if (BE (new_array == NULL, 0))
	return REG_ESPACE;
      spot->array = new_array;
    }
  spot->array[spot->num++] = newstate;
  return REG_NOERROR;
}

/* Create the new state which is independ of contexts.
   Return the new state if succeeded, otherwise return NULL.  */

static re_dfastate_t *
create_ci_newstate (dfa, nodes, hash)
     re_dfa_t *dfa;
     const re_node_set *nodes;
     unsigned int hash;
{
  int i;
  reg_errcode_t err;
  re_dfastate_t *newstate;
  newstate = create_newstate_common (dfa, nodes, hash);
  if (BE (newstate == NULL, 0))
    return NULL;
  newstate->entrance_nodes = &newstate->nodes;

  for (i = 0 ; i < nodes->nelem ; i++)
    {
      re_token_t *node = dfa->nodes + nodes->elems[i];
      re_token_type_t type = node->type;
      if (type == CHARACTER && !node->constraint)
	continue;

      /* If the state has the halt node, the state is a halt state.  */
      else if (type == END_OF_RE)
	newstate->halt = 1;
#ifdef RE_ENABLE_I18N
      else if (type == COMPLEX_BRACKET
	       || (type == OP_PERIOD && MB_CUR_MAX > 1))
	newstate->accept_mb = 1;
#endif /* RE_ENABLE_I18N */
      else if (type == OP_BACK_REF)
	newstate->has_backref = 1;
      else if (type == ANCHOR || node->constraint)
	newstate->has_constraint = 1;
    }
  err = register_state (dfa, newstate, hash);
  if (BE (err != REG_NOERROR, 0))
    {
      free_state (newstate);
      newstate = NULL;
    }
  return newstate;
}

/* Create the new state which is depend on the context CONTEXT.
   Return the new state if succeeded, otherwise return NULL.  */

static re_dfastate_t *
create_cd_newstate (dfa, nodes, context, hash)
     re_dfa_t *dfa;
     const re_node_set *nodes;
     unsigned int context, hash;
{
  int i, nctx_nodes = 0;
  reg_errcode_t err;
  re_dfastate_t *newstate;

  newstate = create_newstate_common (dfa, nodes, hash);
  if (BE (newstate == NULL, 0))
    return NULL;
  newstate->context = context;
  newstate->entrance_nodes = &newstate->nodes;

  for (i = 0 ; i < nodes->nelem ; i++)
    {
      unsigned int constraint = 0;
      re_token_t *node = dfa->nodes + nodes->elems[i];
      re_token_type_t type = node->type;
      if (node->constraint)
	constraint = node->constraint;

      if (type == CHARACTER && !constraint)
	continue;
      /* If the state has the halt node, the state is a halt state.  */
      else if (type == END_OF_RE)
	newstate->halt = 1;
#ifdef RE_ENABLE_I18N
      else if (type == COMPLEX_BRACKET
	       || (type == OP_PERIOD && MB_CUR_MAX > 1))
	newstate->accept_mb = 1;
#endif /* RE_ENABLE_I18N */
      else if (type == OP_BACK_REF)
	newstate->has_backref = 1;
      else if (type == ANCHOR)
	constraint = node->opr.ctx_type;

      if (constraint)
	{
	  if (newstate->entrance_nodes == &newstate->nodes)
	    {
	      newstate->entrance_nodes = re_malloc (re_node_set, 1);
	      if (BE (newstate->entrance_nodes == NULL, 0))
		{
		  free_state (newstate);
		  return NULL;
		}
	      re_node_set_init_copy (newstate->entrance_nodes, nodes);
	      nctx_nodes = 0;
	      newstate->has_constraint = 1;
	    }

	  if (NOT_SATISFY_PREV_CONSTRAINT (constraint,context))
	    {
	      re_node_set_remove_at (&newstate->nodes, i - nctx_nodes);
	      ++nctx_nodes;
	    }
	}
    }
  err = register_state (dfa, newstate, hash);
  if (BE (err != REG_NOERROR, 0))
    {
      free_state (newstate);
      newstate = NULL;
    }
  return  newstate;
}

static void
free_state (state)
     re_dfastate_t *state;
{
  if (state->entrance_nodes != &state->nodes)
    {
      re_node_set_free (state->entrance_nodes);
      re_free (state->entrance_nodes);
    }
  re_node_set_free (&state->nodes);
  re_free (state->trtable);
  re_free (state->trtable_search);
  re_free (state);
}