home *** CD-ROM | disk | FTP | other *** search
/ ARM Club 3 / TheARMClub_PDCD3.iso / hensa / internet / tcpip / src205 / TCPIP_Src / NNTP / c / nntpidhist < prev    next >
Encoding:
Text File  |  1995-03-12  |  12.7 KB  |  609 lines
  1. /*
  2.  * Title:   nntp/idhist.c
  3.  * Version: 0.01 (02-Feb-1995)
  4.  *
  5.  * Author:  Adam Goodfellow
  6.  * Contact: adam@comptech.demon.co.uk
  7.  *
  8.  * A set of primatives for providing global duplicate article
  9.  * detection for NNTP clients. This version for use in !TCPIPv2
  10.  *
  11.  * Copyright (c) Adam Goodfellow 1995. All Rights Reserved.
  12.  *
  13.  * This software is provided AS-IS.  The author gives no warranty,
  14.  * real or assumed, and takes no responsibility whatsoever for any 
  15.  * use or misuse of this software, or any damage created by its use
  16.  * or misuse.
  17.  *
  18.  * This software may be freely copied and distributed provided that
  19.  * no part of this NOTICE is deleted or edited in any manner.
  20.  */
  21.  
  22. #include <stdio.h>
  23. #include <stdlib.h>
  24. #include <string.h>
  25. #include <ctype.h>
  26. #include <time.h>
  27.  
  28. #include "flex.h"
  29.  
  30. #define ID_ISTEMP 10 /* ID with a time stamp below the are not saved */
  31. #define ID_ISDEAD  0 /* This time stamp value mean this ID does not exist */
  32.  
  33. typedef struct idhist_str
  34. {
  35.   char *store;        /* Pointer to ID store memory */
  36.   int next;           /* Next free location in store */
  37.   int start;          /* Start of chain of newly added IDs */
  38.   int end;            /* End of chain of newly added IDs */
  39.   int count;          /* Total number of ID in store */
  40.   int hashsize;       /* Hash table size */
  41. } idhist_str;
  42.  
  43. typedef struct idhist_str *idhistory;
  44.  
  45. time_t time_aton(char *s);
  46. char *time_ntoa(char *buf, time_t t);
  47.  
  48. time_t time_readgmt(void);
  49. void time_timetoordinals(time_t t, struct tm *tp);
  50. time_t time_ordinalstotime(struct tm *tp);
  51.  
  52. idhistory idhist_init(int size);
  53. void idhist_kill(idhistory hist);
  54. int idhist_addid(idhistory hist, char *id, time_t t);
  55. int idhist_checkid(idhistory hist, char *id);
  56. int idhist_save(idhistory hist, char *file, int maxage);
  57. idhistory idhist_load(char *file /*, int maxage */);
  58. char *idhist_trimstr(char *s);
  59. char *idhist_msgid(idhistory hist, int id, char *buf);
  60. int idhist_numids(idhistory hist);
  61.  
  62. static int alignup(int n, int bits);
  63. static int hashof(idhistory hist, char *id);
  64. static int ensure_store(idhistory hist, int n);
  65.  
  66.  
  67. /*
  68.  * The ID store consist of a hash table followed
  69.  * by structures as follows:
  70.  *   int      Next ID in hash chain
  71.  *   int      Next ID in chonological order
  72.  *   time_t   The ID's time stamp
  73.  *   char[]   The actual ID string
  74.  */
  75. #define ID_CHAIN   0      /* Next object on hash chain */
  76. #define ID_NEXT    4      /* Next object as added */
  77. #define ID_TIME    8      /* Time of news feed that this object was fetched */
  78. #define ID_STRING  12     /* Actual ID string without the "<" and ">" */
  79.  
  80. #define ID_HASH(h) (h*4)  /* Another legibility aid */
  81.  
  82. /*
  83.  * Align a number up to a power of 2
  84.  */
  85. static int alignup(int n, int bits)
  86. {
  87.   return n-1+(1<<bits) & (0xffffffff<<bits);
  88. }
  89.  
  90. /*
  91.  * Calculate a hash value of an 
  92.  * article ID string
  93.  */
  94. static int hashof(idhistory hist, char *id)
  95. {
  96.   int h;
  97.  
  98.   for (h=0; *id; id++)
  99.     h = ((h<<6)+*id) % hist->hashsize;
  100.  
  101.   return h;
  102. }
  103.  
  104. /*
  105.  * Initialise the article ID store
  106.  * Hash table size is selected based upon starting 
  107.  * number of IDs given in size
  108.  */
  109. idhistory idhist_init(int size)
  110. {
  111.   int i, *p;
  112.   idhistory hist;
  113.  
  114.   /*
  115.    * Prime numbers for hash table sizes
  116.    */
  117.   int hashsizetab[] = 
  118.       { 0x0101, 0x0209, 0x0407, 0x0805, 0x1003, 0x2011, 0x401b, 0 };
  119.  
  120.   if (hist = (idhistory)malloc(sizeof(idhist_str)), hist==NULL)
  121.     return NULL;
  122.  
  123.   /*
  124.    * From the size (ie number of id in file) work out a suitable
  125.    * hash table size. The size chosen that which is at least 
  126.    * size/2, or the highest in the hash sizes list above.
  127.    */
  128.   for (i=0; hashsizetab[i]!=0 && hashsizetab[i]<size; i++);
  129.   if (i) --i;
  130.   hist->hashsize = hashsizetab[i];
  131.  
  132.   /*
  133.    * Allocate some memory, rounded up to a multiple of 1K
  134.    */
  135.   if (!flex_alloc((flex_ptr)&hist->store, alignup(hist->hashsize*4,10)))
  136.   {
  137.     idhist_kill(hist);
  138.     return NULL;
  139.   }
  140.     
  141.   /*
  142.    * clear the hash table
  143.    */
  144.   for (i = 0, p = (int *)hist->store; i<hist->hashsize; i++)
  145.     p[i] = 0;
  146.  
  147.   /*
  148.    * Set the next store marker and
  149.    * initialise list offsets
  150.    */
  151.   hist->next = hist->hashsize*4;
  152.   hist->start = 0;
  153.   hist->end = 0;
  154.   hist->count = 0;
  155.   
  156.   return hist;
  157. }
  158.  
  159.  
  160. /*
  161.  * Ensure that the total ID store size
  162.  * is at least n.
  163.  */
  164. static int ensure_store(idhistory hist, int n)
  165. {
  166.   if (n>=flex_size((flex_ptr)&hist->store))
  167.     return flex_extend((flex_ptr)&hist->store, alignup(n, 10));
  168.  
  169.   return 1;
  170. }
  171.  
  172.  
  173. /*
  174.  * Add an ID to the store.
  175.  * Returns <0 if ID allready present.
  176.  *         =0 if can't add it
  177.  *         >0 if added the id
  178.  * t is time of news feed starting
  179.  */
  180. int idhist_addid(idhistory hist, char *id, time_t t)
  181. {
  182.   int p, h, n;
  183.  
  184.   if (hist==NULL)
  185.     return 0;
  186.  
  187.   h = hashof(hist, id);
  188.  
  189.   /*
  190.    * Scan an ID chain looking for an ID
  191.    * If a duplicate exists, it is more likely to be near the head
  192.    */
  193.   for (p = *(int *)(hist->store+ID_HASH(h)); p!=0; p = *(int *)(hist->store+p+ID_CHAIN))
  194.   {
  195.     if (!strcmp(id, hist->store+p+ID_STRING))
  196.     {
  197.       time_t ot;
  198.       /*
  199.        * If time stamp is a temp, then update this entry
  200.        * with the given time stamp
  201.        */
  202.       if (ot = *(int *)(hist->store+p+ID_TIME), ot<ID_ISTEMP)
  203.       {
  204.         *(int *)(hist->store+p+ID_TIME) = t;
  205.         if (t>=ID_ISTEMP)
  206.           hist->count += 1;
  207.         return (ot!=ID_ISDEAD) ? -p : p;
  208.       }
  209.       return -p;
  210.     }
  211.   }
  212.  
  213.   /*
  214.    * Word aligned length of ID
  215.    */
  216.   n = alignup(strlen(id)+1, 2);
  217.  
  218.   /*
  219.    * Ensure space for ID we are adding
  220.    */
  221.   if (!ensure_store(hist, hist->next+n+ID_STRING))
  222.     return 0;
  223.   
  224.   /*
  225.    * Copy in the ID with a empty chain link
  226.    */
  227.   *(int *)(hist->store+hist->next) = 0;
  228.   strcpy(hist->store+hist->next+ID_STRING,id);
  229.   
  230.   /*
  231.    * Now link into the hash chain
  232.    * Optimisation: usually, a duplicate will be a fairly recently
  233.    * Stored ID, so allways link at head of a chain rather than end
  234.    * This also saves scanning for end of chain
  235.    */
  236.   p = *(int *)(hist->store+ID_HASH(h));
  237.   *(int *)(hist->store+ID_HASH(h)) = hist->next;
  238.  
  239.   if (p)
  240.     *(int *)(hist->store+hist->next+ID_CHAIN) = p;
  241.  
  242.   /*
  243.    * Now link onto global chain and store the time
  244.    * to keep in order when they are saved
  245.    */
  246.   *(int *)(hist->store+hist->next+ID_NEXT) = 0;
  247.   *(int *)(hist->store+hist->next+ID_TIME) = t;
  248.  
  249.   if (!hist->start)
  250.   {
  251.     hist->start = hist->next;
  252.     hist->end = hist->start;
  253.   }
  254.   else
  255.   {
  256.     *(int *)(hist->store+hist->end+ID_NEXT) = hist->next;
  257.     hist->end = hist->next;
  258.   }
  259.  
  260.   /*
  261.    * Update end marker
  262.    * And return original end marker
  263.    */
  264.   p = hist->next;
  265.   hist->next += (n+ID_STRING);
  266.  
  267.   /*
  268.    * Only count IDs with non zero timestamps
  269.    */
  270.   hist->count += (t!=0);
  271.  
  272.   return p;
  273. }
  274.  
  275.  
  276. /*
  277.  * Check if allready have the given ID
  278.  */
  279. int idhist_checkid(idhistory hist, char *id)
  280. {
  281.   int h, p;
  282.  
  283.   if (hist==NULL)
  284.     return 0;
  285.  
  286.   h = hashof(hist, id);
  287.  
  288.   /*
  289.    * Scan an ID chain looking for an ID
  290.    * If a duplicate exists, it is more likely to be near the head
  291.    */
  292.   for (p = *(int *)(hist->store+ID_HASH(h)); p!=0; p = *(int *)(hist->store+p+ID_CHAIN))
  293.   {
  294.     if (!strcmp(id, hist->store+p+ID_STRING) && *(int *)(hist->store+p+ID_TIME!=ID_ISDEAD))
  295.       return 1;
  296.   }
  297.  
  298.   return 0;
  299. }
  300.  
  301. /*
  302.  * Return the ID string associated with an ID handle
  303.  */
  304. char *idhist_msgid(idhistory hist, int id, char *buf)
  305. {
  306.   int n;
  307.  
  308.   if (!hist || id==0)
  309.     return 0;
  310.   
  311.   if (!buf)
  312.   {
  313.     n = strlen(hist->store+id+ID_STRING);
  314.     if (buf = (char *)malloc(n+1), buf==NULL)
  315.       return NULL;
  316.   }
  317.   
  318.   strcpy(buf, hist->store+id+ID_STRING);
  319.   return buf;
  320. }
  321.  
  322. /*
  323.  * Updates the time stamp only
  324.  */
  325. void idhist_stamp(idhistory hist, int id, time_t t)
  326. {
  327.   if (!hist || id==0)
  328.     return;
  329.   
  330.   *(int *)(hist->store+id+ID_TIME) = t;
  331. }
  332.  
  333. /*
  334.  * Clean the history so that all temp ID are marked as dead
  335.  */
  336. void idhist_clean(idhistory hist)
  337. {
  338.   int p;
  339.  
  340.   for (p = hist->start; p!=0; p = *(int *)(hist->store+p+ID_NEXT))
  341.   {
  342.     if (*(int *)(hist->store+p+ID_TIME)<ID_ISTEMP)
  343.       *(int *)(hist->store+p+ID_TIME) = ID_ISDEAD;
  344.   }
  345. }
  346.  
  347.  
  348. /*
  349.  * Extract IDs from ID store in order they were added
  350.  * and write to the history file.
  351.  */
  352. int idhist_save(idhistory hist, char *file, int maxage)
  353. {
  354.   FILE *fp;
  355.   int p;
  356.   time_t t, last_t = 0;
  357.   time_t oldest;
  358.   int count;
  359.   char buf[256];
  360.   struct tm tm;
  361.   
  362.   if (hist==NULL)
  363.     return 0;
  364.  
  365.   if (fp = fopen(file, "w"), fp==NULL)
  366.     return 0;
  367.     
  368.   /*
  369.    * IDs older than this are expired
  370.    */
  371.   oldest = time_readgmt()-(maxage*60*60);
  372.  
  373.   /*
  374.    * Count the number of IDs that will be written
  375.    */
  376.   count = 0;
  377.   for (p = hist->start; p!=0; p = *(int *)(hist->store+p+ID_NEXT))
  378.   {
  379.     if (*(int *)(hist->store+p+ID_TIME)>=oldest)
  380.     ++count;
  381.   }
  382.  
  383.   /*
  384.    * Write out the number of IDs for hash size selection when re-loading
  385.    */
  386.   fprintf(fp, "# size %d\n", count);
  387.  
  388.   /*
  389.    * Write out IDs and fetch times
  390.    */
  391.   for (p = hist->start; p!=0; p = *(int *)(hist->store+p+ID_NEXT))
  392.   {
  393.     /*
  394.      * If time stamp of this ID not same as previous one
  395.      * write out a new time stamp, unless it is zero
  396.      */
  397.     if (t = *(int *)(hist->store+p+ID_TIME), t>=oldest)
  398.     {
  399.       if (t!=last_t)
  400.       {
  401.         time_timetoordinals(t, &tm);
  402.         fprintf(fp, "# time %.2d%.2d%.2d %.2d%.2d%.2d\n",
  403.                      tm.tm_year, tm.tm_mon+1, tm.tm_mday,
  404.                      tm.tm_hour, tm.tm_min, tm.tm_sec);
  405.         last_t = t;
  406.       }
  407.       /*
  408.        * Dont write out IDs with a zero time stamp
  409.        * or timestamp older than maxage
  410.        */
  411.       if (last_t>=oldest)
  412.       {
  413.         /* Copy string out due to danger of flex block moving
  414.          * when fprintf() is called.
  415.          */
  416.         idhist_msgid(hist, p, buf);
  417.         fprintf(fp, "%s\n", buf);
  418.       }
  419.     }
  420.   }
  421.  
  422.   fclose(fp);
  423.  
  424.   return 1;
  425. }
  426.  
  427. /*
  428.  * Dispose of the ID store
  429.  */
  430. void idhist_kill(idhistory hist)
  431. {
  432.   if (hist)
  433.   {
  434.     if (hist->store!=NULL)
  435.       flex_free((flex_ptr)&hist->store);
  436.     free(hist->store);
  437.   }
  438. }
  439.  
  440.  
  441. /*
  442.  * Load ID store with ids from a file
  443.  * ignoring 'expired' IDs. ie ID older than maxage hours
  444.  */
  445. idhistory idhist_load(char *file /*, int maxage */)
  446. {
  447.   char *p;
  448.   FILE *fp;
  449.   time_t t = 0;
  450. /*
  451.   time_t oldest;
  452. */
  453.   char buf[256];
  454.  
  455.   idhistory hist;
  456.  
  457.   /*
  458.    * IDs older than this are expired
  459.    */
  460. /*
  461.   oldest = time_readgmt()-(maxage*60*60);
  462. */
  463.   if (fp = fopen(file, "r"), fp==NULL)
  464.     return 0;
  465.  
  466.   /*
  467.    * If a new style history, the first line will
  468.    * contain the number if IDs in the history file
  469.    *
  470.    * Use this value to allow init() to work out the has table size.
  471.    * For old history files, this line wont present, so init with a
  472.    * default size.
  473.    *
  474.    * As this size represent the pre-expirey size, then after expirely,
  475.    * the hash table will still usually be adequate to efficiently
  476.    * accomodate new IDs.
  477.    */
  478.   if (fgets(buf, 255, fp)!=NULL && !strncmp(buf+2, "# size ", 7))
  479.   {
  480.     /*
  481.      * New style history
  482.      */
  483.     hist = idhist_init(atoi(buf+7));
  484.   }
  485.   else
  486.   {
  487.     /*
  488.      * Old style history
  489.      */
  490.     rewind(fp);
  491.     hist = idhist_init(0);
  492.   }
  493.  
  494.   if (hist==NULL)
  495.     return NULL;
  496.  
  497.   while (fgets(buf, 255, fp)!=NULL)
  498.   {
  499.     if (*buf=='#')
  500.     {
  501.       if (!strncmp(buf+2, "time ", 5))
  502.         t = time_aton(buf+7);
  503.       /*
  504.        * Old style history file time stamp in the form "# yymmdd hhmmss"
  505.        */
  506.       else
  507.         t = time_aton(buf+2);
  508.     }
  509.     else
  510.     {
  511.       /*
  512.        * Expirey process consists of ignoring IDs that are
  513.        * stamped with a time/date prior to 'oldest'.
  514.        */
  515. /*
  516.       if (t>=oldest)
  517.       {
  518. */
  519.         p = idhist_trimstr(buf);
  520.         if (!idhist_checkid(hist, p))
  521.         {
  522.           if (!idhist_addid(hist, p, t))
  523.           {
  524.             fclose(fp);
  525.             idhist_kill(hist);
  526.             return NULL;
  527.           }
  528.         }
  529. /*
  530.       }
  531. */
  532.     }
  533.   }
  534.  
  535.   fclose(fp);
  536.   
  537.   return hist;
  538. }
  539.  
  540. /*
  541.  * Skip junk at start of ID
  542.  * Strip junk off end of ID
  543.  * Return pointer to start of ID
  544.  * Done in place, so original string is 'corrupted'
  545.  */
  546. char *idhist_trimstr(char *s)
  547. {
  548.   char *p;
  549.   
  550.   if (*s=='<')
  551.     ++s;
  552.     
  553.   for (p = s; *p!='>' && *p>' '; p++);
  554.   *p = '\0';
  555.   
  556.   return s;
  557. }
  558.  
  559. int idhist_numids(idhistory hist)
  560. {
  561.   if (!hist)
  562.     return -1;
  563.     
  564.   return hist->count;
  565. }
  566.  
  567. /*
  568.  * Convert string with time in form yymmdd hhmmss into
  569.  * a ANSI C time_t value
  570.  */
  571. time_t time_aton(char *s)
  572. {
  573.   struct tm tm;
  574.   
  575.   while (*s && !isdigit(*s))
  576.     ++s;
  577.  
  578.   tm.tm_year = (s[0]-'0')*10 + (s[1]-'0');
  579.   tm.tm_mon  = ((s[2]-'0')*10 + (s[3]-'0'))-1;
  580.   tm.tm_mday = (s[4]-'0')*10 + (s[5]-'0');
  581.   tm.tm_hour = (s[7]-'0')*10 + (s[8]-'0');
  582.   tm.tm_min  = (s[9]-'0')*10 + (s[10]-'0');
  583.   tm.tm_sec  = (s[11]-'0')*10 + (s[12]-'0');
  584.  
  585.   tm.tm_isdst = 0;
  586.   tm.tm_wday  = 0;
  587.   tm.tm_yday  = 0;
  588.  
  589.   return time_ordinalstotime(&tm);
  590. }
  591.  
  592. /*
  593.  * Convert time into string yymmdd hhmmss
  594.  * t will usually be in GMT
  595.  * buf should be at least 16 chars
  596.  */
  597. char *time_ntoa(char *buf, time_t t)
  598. {
  599.   struct tm tm;
  600.  
  601.   time_timetoordinals(t, &tm);
  602.  
  603.   sprintf(buf, "%.2d%.2d%.2d %.2d%.2d%.2d",
  604.           tm.tm_year%100, tm.tm_mon+1, tm.tm_mday,
  605.           tm.tm_hour, tm.tm_min, tm.tm_sec);
  606.  
  607.   return buf;
  608. }
  609.