Trier une SLIST

Trier avec qsort

Voici une méthode pour pouvoir trier une SLIST.

#include <sys/queue.h>
#include <stdlib.h>
 
struct Pr0n {
    char *name;
    time_t date_sortie;
    SLIST_ENTRY(struct Pr0n) next;
};
 
SLIST_HEAD(,struct Pr0n) pr0nhead;
 
/* C'est ici que l'on explique comment comparer le pr0n */
int
compare_pr0n_by_date_sortie(const void *a, const void *b)
{
  struct Pr0n *pr0n_a = *((struct Pr0n **)a);
  struct Pr0n *pr0n_b = *((struct Pr0n **)b);
  return pr0n_b->date_sortie - pr0n_a->date_sortie;
}
 
 
void
pr0n_fill()
{
  /* Ici tu remplis ta SLIST avec tout ton pr0n */
}
 
int
main(void)
{
  struct Pr0n* pr0n;
  int pr0n_count=0;
  int item=0;
  struct Pr0n **pr0n_sorted;
 
  SLIST_INIT(&pr0nhead);
 
 
  pr0n_fill();
 
  /* ... */
 
 
  SLIST_FOREACH(pr0n,&pr0nhead,next) {
    pr0n_count++;
  }
 
  pr0n_sorted = (struct Pr0n**))malloc(pr0n_count*sizeof(struct Pr0n *));
 
  SLIST_FOREACH(pr0n,&pronhead,next) {
    pr0n_sorted[item++]=pr0n;
  }  
 
  qsort(pr0n_sorted, pr0n_count, sizeof(struct Pr0n *), compare_pr0n_by_date_sortie);
 
  /* ... */
  return EXIT_SUCCESS;
}

Méthode plus rapide

voici deux autres méthodes qui évitent de passer par un pointeur intermédiaire et qui trie directement la SLIST.

plusieurs avantages aux méthodes suivantes :

  1. la SLIST est triée directement.
  2. la fonction de comparaison peut être typesafe.

Bubble Sort

#define SLIST_BUBBLE_SORT(type, head, field, cmp) do {         \
  int nelt;                                                    \
  type *prev, *elt, *next;                                     \
  nelt=0;                                                      \
  SLIST_FOREACH(elt,(head),field)                              \
    nelt++;                                                    \
                                                               \
  prev = NULL;                                                 \
  while (nelt--) {                                             \
    SLIST_FOREACH(elt, (head), field) {                        \
      next = SLIST_NEXT(elt, field);                           \
      if (next && cmp(elt, next) > 0) {                        \
        if (elt == SLIST_FIRST((head))) {                      \
          SLIST_REMOVE_HEAD(head, field);                      \
          SLIST_INSERT_AFTER(next, elt, field);                \
        } else {                                               \
          SLIST_NEXT(prev, field) = next;                      \
          SLIST_NEXT(elt, field) = SLIST_NEXT(next, field);    \
          SLIST_NEXT(next, field) = elt;                       \
        }                                                      \
        elt = next;                                            \
      }                                                        \
      prev=elt;                                                \
    }                                                          \
  }                                                            \
} while (0)

A utiliser de la manière suivante :

#include <sys/queue.h>
#include <stdlib.h>
 
struct Pr0n {
    char *name;
    time_t date_sortie;
    SLIST_ENTRY(struct Pr0n) next;
};
 
SLIST_HEAD(,struct Pr0n) pr0nhead;
 
/* C'est ici que l'on explique comment comparer le pr0n */
int
compare_pr0n_by_date_sortie(struct Pr0n *a, struct Pr0n *b)
{
  return b->date_sortie - a->date_sortie;
}
 
 
void
pr0n_fill()
{
  /* Ici tu remplis ta SLIST avec tout ton pr0n */
}
 
int
main(void)
{
  struct Pr0n* pr0n;
  int pr0n_count=0;
  int item=0;
  struct Pr0n **pr0n_sorted;
 
  SLIST_INIT(&pr0nhead);
 
 
  pr0n_fill();
 
  /* ... */
 
 
  SLIST_FOREACH(pr0n,&pr0nhead,next) {
    pr0n_count++;
  }
 
  SLIST_BUBBLE_SORT(struct Pr0n, &pr0nhead, next, compare_pr0n_by_date_sortie);
 
  /* ... */
  return EXIT_SUCCESS;
}

Merge Sort

#define TAKE_LEFT 0
#define TAKE_RIGHT 1
 
#define SLIST_MSORT( type, head, field, cmp) do {                                     \
  type *first, *tail;     /* head / tail of the sorted list */                        \
  type *e;                /* element taken to add to the sorted list */               \
  size_t partsz;          /* size of one partition */                                 \
  size_t nmerges;         /* # of merge performed of partsz */                        \
  type *left, *right;     /* current left / right pointers */                         \
  size_t nleft, nright;   /* # of elt to merge starting from left / right pointers */ \
                                                                                      \
  first = SLIST_FIRST(head);                                                          \
  if (first == NULL || SLIST_NEXT(first, field) == NULL)                              \
    /* 0 or 1 element */                                                              \
    break;                                                                            \
                                                                                      \
  nmerges = 42; /* just to enter the for loop */                                      \
  for (partsz = 1; nmerges > 1; partsz *= 2) {                                        \
    nmerges = 0; /* number of merge performed of partsz */                            \
    left = first;                                                                     \
    tail = NULL;                                                                      \
    while (left) {                                                                    \
      /* divide into [???][left][right][???] */                                       \
      right = left;                                                                   \
      for (nleft = 0; right && nleft < partsz; nleft++)                               \
        right = SLIST_NEXT(right, field);                                             \
        nright = partsz; /* we merge at most partsz from right */                     \
        while (nleft > 0 || (nright > 0 && right)) {                                  \
          int takefrom;                                                               \
          if (nleft == 0)                                                             \
            takefrom = TAKE_RIGHT;                                                    \
          else if (nright == 0 || right == NULL)                                      \
            takefrom = TAKE_LEFT;                                                     \
          else if (cmp(left, right) > 0)                                              \
            takefrom = TAKE_RIGHT;                                                    \
          else                                                                        \
            takefrom = TAKE_LEFT;                                                     \
                                                                                      \
          /* pick e from the right list */                                            \
          if (takefrom == TAKE_RIGHT) {                                               \
            e = right;                                                                \
            right = SLIST_NEXT(right, field);                                         \
            nright--;                                                                 \
          } else {                                                                    \
            e = left;                                                                 \
            left = SLIST_NEXT(left, field);                                           \
            nleft--;                                                                  \
          }                                                                           \ 
                                                                                      \
          if (tail == NULL)                                                           \
            first = e;                                                                \
          else                                                                        \
            SLIST_NEXT(tail, field) = e;                                              \
                                                                                      \
          tail = e;                                                                   \
        }                                                                             \
        left = right;                                                                 \
        nmerges++;                                                                    \
      }                                                                               \
      SLIST_NEXT(tail, field) = NULL;                                                 \
    }                                                                                 \
    SLIST_FIRST(head) = first;                                                        \
} while (0)

A utiliser de la manière suivante :

#include <sys/queue.h>
#include <stdlib.h>
 
struct Pr0n {
    char *name;
    time_t date_sortie;
    SLIST_ENTRY(struct Pr0n) next;
};
 
SLIST_HEAD(,struct Pr0n) pr0nhead;
 
/* C'est ici que l'on explique comment comparer le pr0n */
int
compare_pr0n_by_date_sortie(struct Pr0n *a, struct Pr0n *b)
{
  return b->date_sortie - a->date_sortie;
}
 
 
void
pr0n_fill()
{
  /* Ici tu remplis ta SLIST avec tout ton pr0n */
}
 
int
main(void)
{
  struct Pr0n* pr0n;
  int pr0n_count=0;
  int item=0;
  struct Pr0n **pr0n_sorted;
 
  SLIST_INIT(&pr0nhead);
 
 
  pr0n_fill();
 
  /* ... */
 
 
  SLIST_FOREACH(pr0n,&pr0nhead,next) {
    pr0n_count++;
  }
 
  SLIST_MSORT(struct Pr0n, &pr0nhead, next, compare_pr0n_by_date_sortie);
 
  /* ... */
  return EXIT_SUCCESS;
}
c/trier_une_slist.txt · Last modified: 2010/01/12 13:29 (external edit)
www.chimeric.de Creative Commons License Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0