list_compare.c

   1 #define _GNU_SOURCE
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <sched.h>
   5 #include <unistd.h>
   6 #include <time.h>
   7 #include <sys/types.h>
   8 #include <sys/stat.h>
   9 #include <fcntl.h>
  10 #include <errno.h>
  11 #include <string.h>
  12 #include <sys/wait.h>
  13 #include <sys/socket.h>
  14 #include <sys/time.h>
  15
  16 static struct timeval tp1,tp2;
  17
  18 static void start_timer()
  19 {
  20         gettimeofday(&tp1,NULL);
  21 }
  22
  23 static double end_timer()
  24 {
  25         gettimeofday(&tp2,NULL);
  26         return (tp2.tv_sec + (tp2.tv_usec*1.0e-6)) -
  27                 (tp1.tv_sec + (tp1.tv_usec*1.0e-6));
  28 }
  29
  30
  31
  32 /* hook into the front of the list */
  33 #define DLIST_ADD(list, p) \
  34 do { \
  35         if (!(list)) { \
  36                 (list) = (p); \
  37                 (p)->next = (p)->prev = NULL; \
  38         } else { \
  39                 (list)->prev = (p); \
  40                 (p)->next = (list); \
  41                 (p)->prev = NULL; \
  42                 (list) = (p); \
  43         }\
  44 } while (0)
  45
  46 /* remove an element from a list - element doesn't have to be in list. */
  47 #define DLIST_REMOVE(list, p) \
  48 do { \
  49         if ((p) == (list)) { \
  50                 (list) = (p)->next; \
  51                 if (list) (list)->prev = NULL; \
  52         } else { \
  53                 if ((p)->prev) (p)->prev->next = (p)->next; \
  54                 if ((p)->next) (p)->next->prev = (p)->prev; \
  55         } \
  56         if ((p) != (list)) (p)->next = (p)->prev = NULL; \
  57 } while (0)
  58
  59 /* promote an element to the top of the list */
  60 #define DLIST_PROMOTE(list, p) \
  61 do { \
  62           DLIST_REMOVE(list, p); \
  63           DLIST_ADD(list, p); \
  64 } while (0)
  65
  66
  67 struct foo {
  68         struct foo *next, *prev;
  69         const char *name;
  70 };
  71
  72 static struct foo *list;
  73
  74 static struct foo *findit(const char *name)
  75 {
  76         struct foo *f;
  77         for (f=list;f;f=f->next) {
  78                 if (strcmp(name, f->name) == 0) {
  79 //                      if (f != list) DLIST_PROMOTE(list, f);
  80                         return f;
  81                 }
  82         }
  83         return NULL;
  84 }
  85
  86 int main(void)
  87 {
  88         int i;
  89
  90         for (i=0;i<20;i++) {
  91                 struct foo *f;
  92                 f = malloc(sizeof(*f));
  93                 asprintf(&f->name, "%u%s", i, "foobar");
  94                 DLIST_ADD(list, f);
  95         }
  96
  97
  98         for (i=0;i<20;i++) {
  99                 char *name;
 100                 int j;
 101                 asprintf(&name, "%u%s", i, "foobar");
 102                 start_timer();
 103                 for (j=0;j<100000;j++) {
 104                         findit(name);
 105                 }
 106                 printf("%s: %.2f usec/op\n", name, 1.0e6*end_timer()/j);
 107                 free(name);
 108         }
 109
 110         return 0;
 111 }