lists.c

AVR的USB文件

LNODEID 
lfirst ( LISTID lid )
{
  CKLMAGIC(((LIST *)lid));
  return ((LIST *)lid)->top;
}


LNODEID 
llast  ( LISTID lid )
{
  CKLMAGIC(((LIST *)lid));
  return ((LIST *)lid)->bottom;
}


LNODEID 
lnext  ( LNODEID lnid )
{
  CKMAGIC(((LISTNODE *)lnid));
  return ((LISTNODE *)lnid)->next;
}


LNODEID 
lprev  ( LNODEID lnid )
{
  CKMAGIC(((LISTNODE *)lnid));
  return ((LISTNODE *)lnid)->prev;
}


void * 
ldata ( LNODEID lnid )
{
  CKMAGIC(((LISTNODE *)lnid));
  return ((LISTNODE *)lnid)->data;
}



int
lsize ( LISTID lid )
{
  CKLMAGIC(((LIST *)lid));
  return ((LIST *)lid)->num;
}



/*------------------------------------------------------------
|  lcat
|
|  catenate - catenate l2 to l1, return pointer to l1.
 ------------------------------------------------------------*/
LISTID
lcat ( LISTID lid1, LISTID lid2 )
{
  CKLMAGIC(((LIST *)lid1));
  CKLMAGIC(((LIST *)lid2));
  while (lsize(lid2)) {
    ladd ( lid1, lrmv_n(lid2,1) );
  }

  CKLMAGIC(((LIST *)lid1));
  CKLMAGIC(((LIST *)lid2));

  return lid1;
}



/*----------------------------------------------------------------------
|  lget
|
|  get from list, last item - return pointer to the data of the last
|  item in the list, non-destructive
 ----------------------------------------------------------------------*/
void * 
lget ( LISTID lid )
{
  LIST * l;
  LISTNODE * p;

  l = (LIST *)lid;

  CKLMAGIC(l);

  p = l->bottom;

  if (p == NULL) {
    CKLMAGIC(l);
    return NULL;
  }
  else {
    CKLMAGIC(l);
    return p->data;
  }
}



/*---------------------------------------------------------------
|  lget_n
|
|  get from list, index - return the nth list item, 
|  non-destructive
 ---------------------------------------------------------------*/
void * 
lget_n ( LISTID lid, unsigned int n )
{
  int i;
  LIST * l;
  LISTNODE * ln;

  l = (LIST *)lid;

  CKLMAGIC(l);

  if ((n<1)||(n>lsize(l))) {
    return NULL;
  }

  ln = l->top;
  i = 1;
  while (ln && (i!=n)) {
    CKMAGIC(ln);
    ln = ln->next;
    i++;
  }

  if (ln) {
    CKLMAGIC(l);
    return ln->data;
  }
  else {
    CKLMAGIC(l);
    return NULL;
  }
}



/*---------------------------------------------------------------
|  lget_ln
|
|  get from list, listnode - return the nth list item, the
|  listnode is returned instead of the data, non-destructive
 ---------------------------------------------------------------*/
LNODEID
lget_ln ( LISTID lid, unsigned int n )
{
  int i;
  LIST * l;
  LISTNODE * ln;

  l = (LIST *)lid;

  CKLMAGIC(l);

  if ((n<1)||(n>lsize(l))) {
    return NULL;
  }

  ln = l->top;
  i = 1;
  while (i!=n) {
    CKMAGIC(ln);
    ln = ln->next;
    i++;
  }

  CKLMAGIC(l);
  return (LNODEID)ln;
}



/*----------------------------------------------------------------------
|  insert_ln
|
|  insert data, listnode - insert data just before the list item 
|  pointed to by 'ln'.
|
|  This routine is not intended to be called directly by the user
|  because the validity of ln is not checked.  This routine is called
|  by list manipulation routines within this module, in which ln is
|  known to point to a valid list node.
 ----------------------------------------------------------------------*/
static 
int 
insert_ln ( LIST * l, LISTNODE * ln, void * data_ptr )
{
  LISTNODE * lnptr;

  CKLMAGIC(l);

  if (ln==NULL) {
    ladd ( l, data_ptr );
    CKLMAGIC(l);
    return 0;
  }

  lnptr = get_listnode(l);
  if (lnptr == NULL) {
#ifdef BOS
    breakpoint();
#endif
    return -1;
  }

  CKMAGIC(lnptr);

  lnptr->data = data_ptr;

  if (ln==l->top) {
    /*------------------------------
    |  insert before the list head
     ------------------------------*/
    lnptr->next = ln;
    lnptr->prev = NULL;
    ln->prev = lnptr;
    l->top = lnptr;
  }
  else if (ln==NULL) {
    /*-----------------
    |  list was empty
     -----------------*/
    lnptr->next = NULL;
    lnptr->prev = l->bottom;
    l->bottom->next = lnptr;
    l->bottom = lnptr;
  }
  else {
    /*-----------------------------------
    |  insert in the middle of the list
     -----------------------------------*/
    lnptr->next = ln;
    lnptr->prev = ln->prev;
    lnptr->next->prev = lnptr;
    lnptr->prev->next = lnptr;
  }

  l->num++;

  CKLMAGIC(l);

  return 0;
}



/*-----------------------------------------------------------------
|  lins_n
|
|  Insert data before the nth item in the list.
 -----------------------------------------------------------------*/
int 
lins_n ( LISTID lid, void * data_ptr, unsigned int n )
{
  int i;
  LIST * l;
  LISTNODE * ln;

  l = (LIST *)lid;

  CKLMAGIC(l);

  if ((n<1)||(n>(l->num+1))) {
    return -1;
  }

  if (l->num == 0) {
    return ladd ( lid, data_ptr );
  }

  /*----------------------------------
  |  locate the nth item in the list
   ----------------------------------*/
  ln = l->top;
  i = 1;
  while (ln && (i!=n)) {
    CKMAGIC(ln);
    ln = ln->next;
    i++;
  }

  if (!ln) {
    CKLMAGIC(l);
    return -1;
  }

  CKLMAGIC(l);

  /*-----------------------------------------
  |  insert before the nth item in the list
   -----------------------------------------*/
  return insert_ln ( l, ln, data_ptr );
}


/*-----------------------------------------------------------------
|  lins_ln
|
|  Insert data before the list node pointed to by ln.
 -----------------------------------------------------------------*/
int 
lins_ln ( LISTID lid, LNODEID lnid, void * data_ptr )
{
  LIST * l;
  LISTNODE * ln;
  LISTNODE * ln_ptr;

  l = (LIST *)lid;
  ln = (LISTNODE *)lnid;

  CKLMAGIC(l);

  CKMAGIC(ln);

  /*-----------------------------------------
  |  validate that ln is indeed in the list
   -----------------------------------------*/
  ln_ptr = l->top;
  while ((ln_ptr!=NULL)&&(ln_ptr!=ln)) {
    CKMAGIC(ln_ptr);
    ln_ptr = ln_ptr->next;
  }

  if (ln_ptr == NULL) {
    CKLMAGIC(l);
    return -1;
  }

  CKLMAGIC(l);

  /*--------------------------------
  |  insert the data into the list
   --------------------------------*/
  return insert_ln ( l, ln, data_ptr );
}



/*----------------------------------------------------------------------
|  remove_ln
|
|  Remove the item in the list pointed to by ln.  This routine is not
|  intended to be called directly by the user because the validity
|  of ln is not checked.  This routine is called by list manipulation
|  routines within this module, in which ln is known to point to a
|  valid list node.
 ----------------------------------------------------------------------*/
static
void * 
remove_ln ( LIST * l, LISTNODE * ln )
{
  void * r;

  CKLMAGIC(l);

  CKMAGIC(ln);

  if (ln==l->top) {
    /*------------------------------
    |  remove the head of the list
     ------------------------------*/
    l->top = ln->next;
    if (l->top != NULL) {
      l->top->prev = NULL;
    }
    else {
      /*----------------------------------------
      |  this was the only item in the list
       ----------------------------------------*/
      l->bottom = NULL;
    }
  }
  else if (ln==l->bottom) {
    /*------------------------------
    |  remove the tail of the list
     ------------------------------*/
    l->bottom = ln->prev;
    if (l->bottom != NULL) {
      l->bottom->next = NULL;
    }
  }
  else {
    /*-------------------------------------
    |  remove from the middle of the list
     -------------------------------------*/
    ln->prev->next = ln->next;
    ln->next->prev = ln->prev;
  }

  /*-----------------------------
  |  prepare to return the data
   -----------------------------*/
  r = ln->data;

  /*-----------------------------------------------
  |  free the listnode for re-use
   -----------------------------------------------*/
  free_listnode(l,ln);

  /*------------------------------------
  |  adjust the item count of the list
   ------------------------------------*/
  l->num--;

  CKLMAGIC(l);

  return r;
}



/*-------------------------------------------------------------------------
|  lrmv_d
|
|  remove from list, data - removes the data element from the list,
|  destructive
 -------------------------------------------------------------------------*/
void * 
lrmv_d ( LISTID lid, void * data_ptr )
{
  LIST * l;
  LISTNODE * ln;
  int i;

  l = (LIST *)lid;

  CKLMAGIC(l);

  i = 0;
  ln = l->top;
  while (ln && (ln->data != data_ptr)) {
    i++;
    CKMAGIC(ln);
    ln = ln->next;
  }

  if (ln == NULL) {
    CKLMAGIC(l);
    return NULL;
  }
  else {
    CKLMAGIC(l);
    return remove_ln ( l, ln );
  }
}



/*-------------------------------------------------------------------------
|  lrmv_ln
|
|  remove from list, by list node - remove the data element pointed to
|  by 'ln' from the list, destructive
 -------------------------------------------------------------------------*/
void * 
lrmv_ln ( LISTID lid, LNODEID lnid )
{
  LIST * l;
  LISTNODE * ln;
  LISTNODE * p;

  l = (LIST *)lid;
  ln = (LISTNODE *)lnid;

  CKLMAGIC(l);

  CKMAGIC(ln);

  p = l->top;
  while ((p!=NULL)&&(p!=ln)) {
    CKMAGIC(p);
    p = p->next;
  }
  
  if (p==NULL) {
    CKLMAGIC(l);
    return NULL;
  }
  else {
    CKLMAGIC(l);
    return remove_ln ( l, p );
  }
}



/*----------------------------------------------------------------------
|  lrmv_n
|
|  remove from list, by item number - remove the nth element from
|  the list.
 ----------------------------------------------------------------------*/
void * 
lrmv_n ( LISTID lid, unsigned int n )
{
  int i;
  LIST * l;
  LISTNODE * ln;

  l = (LIST *)lid;

  CKLMAGIC(l);

  if ((n<1)||(n>l->num)) {
    return NULL;
  }

  ln = l->top;
  i = 1;
  while (ln && (i!=n)) {
    CKMAGIC(ln);
    ln = ln->next;
    i++;
  }

  if (ln) {
    CKLMAGIC(l);
    return remove_ln ( l, ln );
  }
  else {
    CKLMAGIC(l);
    return NULL;
  }
}


/*----------------------------------------------------------------------
|  lrmv
|
|  remove from list, last item - remove the last item from the list,
|  destructive
 ----------------------------------------------------------------------*/
void * 
lrmv ( LISTID lid )
{
  LIST * l;
  LISTNODE * p;

  l = (LIST *)lid;

  CKLMAGIC(l);

  p = l->bottom;

  if (p == NULL) {
    CKLMAGIC(l);
    return NULL;
  }
  else {
    CKLMAGIC(l);
    return remove_ln ( l, p );
  }
}



/*----------------------------------------------------------------------
|  lsrch
|
|  search list - return data element pointed to by 'p', NULL if not
|  found
 ----------------------------------------------------------------------*/
void * 
lsrch ( LISTID lid, void * p, int (* compare)(void * p1, void * p2) )
{
  LIST * l;
  LISTNODE * ln;

  l = (LIST *)lid;

  CKLMAGIC(l);

  ln = l->top;

  while (ln!=NULL) {
    CKMAGIC(ln);
    if (compare(p,ln->data) == 0) {
      CKLMAGIC(l);
      return ln->data;
    }
    else {
      ln = ln->next;
    }
  }

  CKLMAGIC(l);
  return NULL;
}


int lprint ( FILE * f, LISTID lid )
{
  LIST * l;
  LISTNODE * ln;
  NODEPOOL * np;
  int count;

  l = (LIST *)lid;

  fprintf ( f, "list id 0x%08x internal data structures:\n", 
            (unsigned int)lid );
#if CHECK_MAGIC
  if ((l->magic1 != MAGIC) || (l->magic2 != MAGIC)) {
    fprintf ( f, "  *** WARNING: LIST MAGIC IS CORRUPT ***\n" );
  }
  fprintf ( f, 
            "  magic1=0x%08x\n"
            "  magic2=0x%08x\n",
            l->magic1, l->magic2 );
#endif
  fprintf ( f, "   num f pool n_ln        top     bottom    next_ln     np_top  np_bottom\n" );
  fprintf ( f, "  ---- - ---- ---- ---------- ---------- ---------- ---------- ----------\n" );
  fprintf ( f, "  %4d %1d %4d %4d %10p %10p %10p %10p %10p\n",
            l->num, l->free_on_close, l->poolsize, l->n_ln_pool, 
            l->top, l->bottom,
            l->next_ln, l->np_top, l->np_bottom );
  

  fprintf ( f, 
            "  node pools:\n"
            "     idx         np     magic1       next       prev     magic2\n"
            "    ---- ---------- ---------- ---------- ---------- ----------\n" );
  count = 0;
  np = l->np_top;
  while (np != NULL) {
    count++;
    fprintf ( f, "    %4d %10p 0x%08x %10p %10p 0x%08x\n", 
              count, np, 
#if CHECK_MAGIC
              np->magic1, 
#else
              0,
#endif
              np->chain_next, np->chain_prev, 
#if CHECK_MAGIC
              np->magic2
#else
              0
#endif
      );
    np = np->chain_next;
  }

  if (f) {
    fprintf ( f, 
              "  list elements:\n"
              "       n         ln     magic1       next       prev       data     magic2\n"
              "    ---- ---------- ---------- ---------- ---------- ---------- ----------\n" );
    count = 0;
    ln = l->top;
    while (ln != NULL) {
      count++;
      fprintf ( f, "    %4d %10p %10x %10p %10p %10p %10x\n", 
                count, ln, 
#if CHECK_MAGIC
                ln->magic1,
#else
                0,
#endif
                ln->next, ln->prev, ln->data, 
#if CHECK_MAGIC
                ln->magic2
#else
                0
#endif
        );
      ln = lnext(ln);
    }
    if (count != l->num) {
      fprintf ( f, 
                "  *** list count is not correct\n"
                "  *** list id indicates %d, counted items = %d\n", 
                l->num, count );
    }
  }

  return 0;
}