开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > Telnet服务器 > 查看源码
hlst.c
资源名称：nessus-libraries_2.2.10.orig.tar.gz　[点击查看]
上传用户：tjescc
上传日期：2021-02-23
资源大小：419k
文件大小：23k
源码类别：

Telnet服务器

开发平台：

Unix_Linux

hlst.c：源码内容
  1. /*
  2.  *          Copyright (c) mjh-EDV Beratung, 1996-1999
  3.  *     mjh-EDV Beratung - 63263 Neu-Isenburg - Rosenstrasse 12
  4.  *          Tel +49 6102 328279 - Fax +49 6102 328278
  5.  *                Email info@mjh.teddy-net.com
  6.  *
  7.  *       Author: Jordan Hrycaj <jordan@mjh.teddy-net.com>
  8.  *
  9.  *    $Id: hlst.c,v 1.33 2003/02/27 10:09:57 renaud Exp $ 
  10.  *
  11.  *   This library is free software; you can redistribute it and/or
  12.  *   modify it under the terms of the GNU Library General Public
  13.  *   License as published by the Free Software Foundation; either
  14.  *   version 2 of the License, or (at your option) any later version.
  15.  *
  16.  *   This library is distributed in the hope that it will be useful,
  17.  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19.  *   Library General Public License for more details.
  20.  *
  21.  *   You should have received a copy of the GNU Library General Public
  22.  *   License along with this library; if not, write to the Free
  23.  *   Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  24.  *
  25.  *   HLST - a simple hash list manager
  26.  */
  28. #include <includes.h>
  30. #define __HLST_INTERNAL__
  31. #include "hlst.h"
  33. #ifdef HAVE_ERRNO_H
  34. #include <errno.h>
  35. #endif
  37. /* ------------------------------------------------------------------------- *
  38.  *                      private definitions                                  *
  39.  * ------------------------------------------------------------------------- */
  41. /* XMALLOC returns memory initialized to zero */
  42. #define XMALLOC(x) emalloc(x)
  43. #define XFREE(x)   efree(&(x))
  45. /* default number of hash buckets per list */
  46. #define DEFAULT_BUCKETS 53
  48. /* global factor to be applied internally to any estimated_size_hint */
  49. #define DEFAULT_PERCENTAGE_COMPRESSOR 80
  51. typedef
  52. struct _sorter {
  53.   int                  dirty ;
  54.   unsigned              size ;
  55.   struct _hashqueue *inx [1] ;
  56.   /* varable length, pointer aligned  */
  57. } sorter ;
  59. typedef 
  60. struct _hashqueue { /* linked list of bucket entries */
  61.   void           *contents;
  62.   struct _hashqueue  *next;
  63.   unsigned          keylen; /* length of current key */
  64.   int               locked; /* currently visited my some hash walk */
  65.   struct _sorter *backlink; /* there might be an index on that list */
  66. # ifdef ENABLE_RHLST
  67.   int               tranum; /* transaction id, used for caching */
  68. # endif /* ENABLE_RHLST */
  69.   char             key [1]; /* varable size key */
  70.   /* varable length, pointer aligned  */
  71. } hashqueue ;
  73. /* get the byte offset of a field */
  74. #define STRUCT_OFFSET(type, field) 
  75. ((char*)(&((type*)0)->field)-(char*)0)
  77. /* given a pointer to field "field" from a structure of type "type",
  78.    get the structure pointer */
  79. #define REVERT_FIELD_PTR(p, type, field)  
  80. ((type*)(((char*)p) - STRUCT_OFFSET (type,field)))
  82. /* ------------------------------------------------------------------------- *
  83.  *                      private variables                                    *
  84.  * ------------------------------------------------------------------------- */
  86. /* non-empty, 0-terminated sorted list in the first entry:
  87.    possible table sizes and hash factors (rel prime to the table size) */
  89. /* FIXME: parameters need to be double ckecked, here */
  90. static const hash_defs hints [] = {
  91.   { 11,   7},
  92.   { 23,  11},
  93.   { 53,  31},
  94.   { 73,  37},
  95.   {101,  40},
  96.   {151,  43},
  97.   {269,  97},
  98.   {509, 101},
  99.   {577, 107},
  100.   {0,0}
  101. };
  103. static unsigned 
  104. size_hint_percentage_compressor = DEFAULT_PERCENTAGE_COMPRESSOR ;
  106. /* used for custum sorting -- not thread safe */
  107. static void *sorter_desc ;
  108. static int (*sorter_fn)(void*,const char*,unsigned,const char*,unsigned);
  110. #ifdef USE_PTHREADS
  111. /* some global sync for logging etc  -- make custum sorting thread safe */
  112. static int glob_mutex_initialized = 0;
  113. static pthread_mutex_t glob_mutex; 
  114. #endif
  116. /* ------------------------------------------------------------------------- *
  117.  *               hashed index ank key length calculation                     *
  118.  * ------------------------------------------------------------------------- */
  120. /* make a hash from the argument key string */
  121. #define _GET_HASH_AND_STRLEN( h, H, L, key) {
  122.   const char *s = (key) ;
  123.   (H) = *s ;
  124.   (L) =  1 ;
  125.   goto S; do {                 
  126.       (H) *= (h)->z.fac ; /* shift accu  */
  127.       (H) +=        * s ; /* get char    */
  128.       (L) ++            ; /* word length */
  129.     S:(H) %= (h)->z.mod ; /* module size */
  130.   } while (*s ++) ; }
  132. /* make a hash from a generic argument key of given length */
  133. #define _GET_HASH( h, H, len, key) {
  134.   const char *s = (key) ;
  135.   int l = (len) ;
  136.   (H)   =    *s ;
  137.   goto T; do {
  138.       (H) *= (h)->z.fac ; /* shift accu  */
  139.       (H) +=     * ++ s ; /* get char    */
  140.     T:(H) %= (h)->z.mod ; /* module size */
  141.   } while (-- l); }
  143. /* combine that methods, above */
  144. #define GET_HASH_AND_LEN( h, H, len, key)
  145.   { if (len) _GET_HASH (h,H,len,key) else _GET_HASH_AND_STRLEN(h,H,len,key) }
  148. #ifdef USE_PTHREADS
  149. # define mutex_init(x)     pthread_mutex_init    (x, 0)
  150. # define mutex_destroy(x)  pthread_mutex_destroy (x)
  151. # define mutex_lock(x)     pthread_mutex_lock    (x)
  152. # define mutex_unlock(x)   pthread_mutex_unlock  (x)
  153. # define globally_lock()   _glob_lock ()
  154. # define globally_unlock() mutex_unlock (&glob_mutex)
  155. static void
  156. _glob_lock
  157.   (void)
  158. {
  159.   if (glob_mutex_initialized == 0) {
  160.     mutex_init (&glob_mutex);
  161.     glob_mutex_initialized = 1;
  162.   }
  163.   mutex_lock (&glob_mutex);
  164. }
  165.  #else
  166. # define mutex_init(x)     /* empty */
  167. # define mutex_lock(x)     /* empty */
  168. # define mutex_unlock(x)   /* empty */
  169. # define mutex_destroy(x)  /* empty */
  170. # define globally_lock()   /* empty */
  171. # define globally_unlock() /* empty */
  172. #endif
  174. /* ------------------------------------------------------------------------- *
  175.  *                      private functions                                    *
  176.  * ------------------------------------------------------------------------- */
  178. #define XMCOPY(p,len) memcpy (XMALLOC (len), (p), (len))
  180. static hashqueue **
  181. find_bucket_ptr
  182.   (hashqueue   **Q,
  183.    const char *key,
  184.    unsigned    len)
  185. {
  186.   hashqueue *q ;
  187.   while (q = *Q, q != 0) {
  188.     if (len == q->keylen && memcmp (q->key, key, len) == 0)
  189.       return Q ;
  190.     Q = &q->next ;
  191.   }
  192.   errno = ENOENT ;
  193.   return 0;
  194. }
  196. /* qsort call back functions */
  197. static int 
  198. __comp
  199.   (hashqueue**  left, 
  200.    hashqueue** right)
  201. {
  202.   int n, min ;
  203.   
  204.   if ((min = (*left)->keylen) > (*right)->keylen)
  205.     min = (*right)->keylen ;
  206.   
  207.   if ((n = memcmp ((*left)->key, (*right)->key, min)) != 0)
  208.     return n;
  209.   
  210.   return (*left)->keylen - (*right)->keylen ;
  211. }
  213. static int 
  214. __comp_custom
  215.   (hashqueue**  left, 
  216.    hashqueue** right)
  217. {
  218.   return (*sorter_fn) (sorter_desc,
  219.        (*left)->key,
  220.        (*left)->keylen,
  221.        (*right)->key,
  222.        (*right)->keylen);
  223. }
  225. /* ------------------------------------------------------------------------- *
  226.  *                 public functions: open/close management                   *
  227.  * ------------------------------------------------------------------------- */
  229. hlst *
  230. create_hlst
  231.   (unsigned estimated_size_hint,
  232.    void (*clup)(void*,void*,char*,unsigned),
  233.    void *state)
  234. {
  235.   const hash_defs *hd = hints ;
  236.   hlst *h ;
  238.   if (estimated_size_hint == 0)
  239.     estimated_size_hint = DEFAULT_BUCKETS ;
  240.   
  241.   /* adjust accoording to policy */
  242.   estimated_size_hint *= size_hint_percentage_compressor ;
  243.   estimated_size_hint /= 100 ;
  245.   /* find appropriate list size, will stop at the last entry */
  246. # ifdef _WIN32
  247.   for (;;) {
  248.     const hash_defs *hd1 = hd+1 ;
  249.     if (hd1->mod == 0 || hd1->mod > estimated_size_hint)
  250.       break ;
  251.     ++ hd ;
  252.   }
  253. # else
  254.   while (hd [1].mod != 0 && hd [1].mod <= estimated_size_hint)
  255.     ++ hd ;
  256. # endif
  258.   h = XMALLOC (sizeof (hlst) + (hd->mod - 1) * sizeof (void*));
  259.   h->z          =   *hd ;
  260.   h->clup       =  clup ;
  261.   h->clup_state = state ;
  262.   return h;
  263. }
  267. hlst *
  268. copy_hlst
  269.   (hlst                     *h,
  270.    unsigned estimated_size_hint,
  271.    void *(*copy)(void*,void*,char*,unsigned),
  272.    void           *cpstate,
  273.    void (*clup)(void*,void*,char*,unsigned),
  274.    void             *state)
  275. {
  276.   const hash_defs *hd = hints ;
  277.   hlst *new ;
  278.   unsigned i, copy_only ;
  279.   
  280.   /* sanity check */
  281.   if (h == 0) {
  282.     errno = EINVAL;
  283.     return 0 ;
  284.   }
  285.   if (estimated_size_hint == 0)
  286.     /* get default from list to copy */
  287.     hd = &h->z ;
  289.   else {
  290.     /* adjust accoording to policy */
  291.     estimated_size_hint *= size_hint_percentage_compressor ;
  292.     estimated_size_hint /= 100 ;
  294.     if (estimated_size_hint != h->z.mod) {
  295.       /* find appropriate list size, will stop at the last entry */
  296. #     ifdef _WIN32
  297.       for (;;) {
  298. const hash_defs *hd1 = hd+1 ;
  299. if (hd1->mod == 0 || hd1->mod > estimated_size_hint)
  300.   break ;
  301. ++ hd ;
  302.       }
  303. #     else
  304.       while (hd [1].mod != 0 && hd [1].mod <= estimated_size_hint)
  305. ++ hd ;
  306. #     endif
  307.     }
  308.   }
  310.   new = (copy_only = (hd->mod == h->z.mod && copy == 0)) == 0
  312.     /* create a new list */
  313.     ? XMALLOC (sizeof (hlst) + (hd->mod - 1) * sizeof (void*))
  315.     /* in this case, we can simply copy blocks, later on */
  316.     : XMCOPY (h, sizeof (hlst) + (h->z.mod - 1) * sizeof (void*))
  317.     ;
  318.   
  319.   new->walk          =                0 ;
  320.   new->clup          =             clup ;
  321.   new->clup_state    =            state ;
  322.   new->total_entries = h->total_entries ;
  323.   
  324.   /* we organize the new list while looping over the old one */
  325.   for (i = 0; i < h->z.mod; i ++) {
  326.     
  327.     /* get hash queue */
  328.     hashqueue *p = h->bucket [i] ;
  329.     new->bucket [i] = 0 ;
  330.  
  331.     while (p != 0) {
  332.       hashqueue *q ;
  333.       void **Q ;
  334.       
  335.       if (copy_only) {
  337. /* copy entry */
  338. q = XMCOPY (p, sizeof (hashqueue) + p->keylen-1) ;
  339. q->locked = 0 ;
  341. /* link to bucket queue */
  342. q->next         = ((hashqueue*)new->bucket [i]) ;
  343. new->bucket [i] = q ;
  345. /* get contents pointer */
  346. Q = &q->contents ;
  348.       } else {
  350. /* create new entry */
  351. if ((Q = make_hlst ((hlst*)new, p->key, p->keylen)) == 0) {
  352.   fprintf (stderr, __FILE__ 
  353.    "(%d): [make_hlst() == 0] serious bug, "
  354.    "corrupt target list -- please report, aborting.n",
  355.    __LINE__);
  356.   exit (2) ;
  357. }
  358.       }
  360.       if (copy != 0 && /* duplicate user contents */
  361.   (*Q = (*copy) (cpstate, p->contents, p->key, p->keylen)) == 0 &&
  362.   errno != 0) {
  363. int e = errno ;
  364. /* stop: clean up */
  365. destroy_hlst (new);
  366. errno = e ;
  367. return 0;
  368.       }
  369.       
  370.       /* get next template */
  371.       p = p->next ;
  372.     }
  373.   }
  374.   
  375.   return new ;
  376. }
  379. void 
  380. flush_hlst 
  381.   (hlst *h,
  382.    void (*clup)(void*desc,void*,char*,unsigned),
  383.    void*             desc)
  384. {
  385.   unsigned i;
  386.   hsrch *s ;
  388.   /* sanity check */
  389.   if (h == 0) return ;
  391.   if (clup == 0) {
  392.     clup = h->clup ;
  393.     desc = h->clup_state ;
  394.   }
  395.   /* remove sorter */
  396.   if (h->access != 0) {
  397.     XFREE (h->access);
  398.     h->access = 0;
  399.   }
  400.   for (i = 0; i < h->z.mod; i ++) {
  401.     /* do with this bucket */
  402.     hashqueue *p, **P = (hashqueue**)h->bucket + i ;
  403.     while ((p = *P) != 0) {
  404.       /* unlink that node, so even circular sublists would not loop */
  405.       *P = p->next ;
  406.       if (clup != 0 && p->contents != 0)
  407. (*clup) (desc, p->contents, p->key, p->keylen);
  408.       XFREE (p);
  409.     }
  410.   } /* for */
  412.   /* cannot visit any node, anymore */
  413.   for (s = h->walk; s != 0; s = s->next) {
  414.     s->hlist = 0 ;      /* next_hlst_search() will stop, that way */
  415. #   ifdef ENABLE_RHLST
  416.     if (s->clup != 0) { /* clean up by call back as early as possible */
  417.       (*s->clup)(s->clup_state);
  418.       s->clup = 0 ;
  419.     }
  420. #   endif
  421.   }
  422.   /* statistics */
  423.   h->total_entries = 0 ;
  424. }
  427. void 
  428. destroy_hlst 
  429.   (hlst *h)
  430. {
  431.   /* sanity check */
  432.   if (h == 0) return ;
  434.   flush_hlst (h, 0, 0);
  435.   if (h->clup != 0) 
  436.     (*h->clup) (h->clup_state,0,0,0);
  437.   XFREE (h);
  438. }
  440. /* ------------------------------------------------------------------------- *
  441.  *                 public functions: manipulate slots                        *
  442.  * ------------------------------------------------------------------------- */
  444. void** 
  445. find_hlst
  446.   (hlst         *h,
  447.    const char *key,
  448.    unsigned    len)
  449. {
  450.   hashqueue **Q;
  451.   int inx ;
  453.   /* sanity check */
  454.   if (h == 0 || key == 0) {
  455.     errno = EINVAL;
  456.     return 0;
  457.   }
  458.   
  459.   GET_HASH_AND_LEN (h, inx, len, key);
  461.   if ((Q = find_bucket_ptr ((hashqueue**)h->bucket + inx, key, len)) != 0)
  462.     return &(*Q)->contents ;
  464.   errno = ENOENT;
  465.   return 0;
  466. }
  469. void** 
  470. make_hlst
  471.   (hlst        *_h,
  472.    const char *key,
  473.    unsigned    len)
  474. {
  475.   hlst *h = (hlst *)_h ;
  476.   hashqueue *q ;
  477.   int inx ;
  479.   /* sanity check */
  480.   if (h == 0 || key == 0) {
  481.     errno = EINVAL;
  482.     return 0;
  483.   }
  484.   
  485.   GET_HASH_AND_LEN (h, inx, len, key);
  487.   /* cannot have duplicate entries */
  488.   if (find_bucket_ptr ((hashqueue**)h->bucket + inx, key, len) != 0) {
  489.     errno = EEXIST;
  490.     return 0;
  491.   }
  493.   /* make entry */
  494.   q = XMALLOC (sizeof (hashqueue) + len - 1);
  495.   memcpy (q->key, key, q->keylen = len);
  497.   /* link entry */
  498.   q->next = h->bucket [inx] ;
  499.   h->bucket [inx] = q ;
  501.   /* statistics */
  502.   h->total_entries ++ ;
  504.   if (h->access != 0)
  505.     /* mark the sorter ready for rebuilt */
  506.     h->access->dirty = 1 ;
  508.   /* always returns some pointer */
  509.   return &q->contents ;
  510. }
  513. int
  514. delete_hlst
  515.   (hlst         *h, 
  516.    const char *key,
  517.    unsigned    len)
  518. {
  519.   hashqueue *q, **Q;
  520.   hsrch *s;
  521.   unsigned inx ;
  523.   /* sanity check */
  524.   if (h == 0 || key == 0) {
  525.     errno = EINVAL;
  526.     return -1;
  527.   }
  528.   
  529.   GET_HASH_AND_LEN (h, inx, len, key);
  531.   if ((Q = find_bucket_ptr ((hashqueue**)h->bucket + inx, key, len)) == 0) {
  532.     errno = ENOENT ;
  533.     return -1 ;
  534.   }
  536.   q = *Q ;
  538.   if (q->locked) 
  539.     /* cannot visit that node, anymore so update the walk decriptors */
  540.     for (s = h->walk; s != 0; s = s->next)  
  541.       if (s->ntry == q) /* find find descriptor */
  542. s->ntry = q->next ; /* visit successor, instead */
  544.   /* set that index link idle */
  545.   if (h->access != 0)
  546.     if (q->backlink != 0) {
  547.       *q->backlink->inx = 0 ;
  548.       h->access->dirty = 1;
  549.     }
  551.   /* unlink */
  552.   *Q = q->next ;
  554.   /* statistics */
  555.   h->total_entries -- ;
  557.   if (h->clup != 0 && q->contents != 0) /* clean up call back */
  558.     (*h->clup) (h->clup_state, q->contents, q->key, q->keylen);
  559.   
  560.   XFREE (q);
  561.   return 0;
  562. }
  564. /* ------------------------------------------------------------------------- *
  565.  *                 public functions: misc                                    *
  566.  * ------------------------------------------------------------------------- */
  568. /* global factor to be applied internally to any estimated_size_hint */
  569. unsigned 
  570. compress_hlst_index 
  571.   (unsigned size_hint_percentage)
  572. {
  573.   unsigned o_index = size_hint_percentage_compressor ;
  574.   if ((size_hint_percentage_compressor = size_hint_percentage) > 100)
  575.     size_hint_percentage_compressor = 100 ;
  576.   return o_index;
  577. }
  579. char *
  580. query_key_hlst
  581.   (void **t)
  582. {
  583.   if (t == 0) {
  584.     errno = EINVAL;
  585.     return 0;
  586.   }
  587.   return REVERT_FIELD_PTR (t, hashqueue, contents)->key ;
  588. }
  590. unsigned
  591. query_keylen_hlst
  592.   (void **t)
  593. {
  594.   if (t == 0) {
  595.     errno = EINVAL;
  596.     return 0;
  597.   }
  598.   return  REVERT_FIELD_PTR (t, hashqueue, contents)->keylen ;
  599. }
  602. #ifdef ENABLE_RHLST
  603. int
  604. query_tranum_hlst
  605.   (void **t)
  606. {
  607.   if (t == 0) {
  608.     errno = EINVAL;
  609.     return 0;
  610.   }
  611.   errno = 0 ;
  612.   return REVERT_FIELD_PTR (t, hashqueue, contents)->tranum ;
  613. }
  615. int
  616. set_tranum_hlst
  617.   (void **t,
  618.    int    n)
  619. {
  620.   int last ;
  621.   if (t == 0) {
  622.     errno = EINVAL;
  623.     return 0;
  624.   }
  625.   errno = 0 ;
  626.   last = REVERT_FIELD_PTR (t, hashqueue, contents)->tranum ;
  627.   REVERT_FIELD_PTR (t, hashqueue, contents)->tranum = n ;
  628.   return last;
  629. }
  630. #endif /* ENABLE_RHLST */
  632. unsigned
  633. query_hlst_size
  634.   (hlst *h)
  635. {
  636.   if (h == 0) {
  637.     errno = EINVAL;
  638.     return 0;
  639.   }
  640.   errno = 0 ;
  641.   return h->total_entries ;
  642. }
  645. /* ------------------------------------------------------------------------- *
  646.  *                 public functions: search that list, itemwise              *
  647.  * ------------------------------------------------------------------------- */
  649. hsrch* 
  650. open_hlst_search 
  651.  (hlst *h)
  652. {
  653.   hsrch *s ;
  655.   /* sanity check */
  656.   if (h == 0) {
  657.     errno = EINVAL;
  658.     return 0;
  659.   }
  660.   
  661.   s = XMALLOC (sizeof (hsrch));
  662.   s->hlist     =       h ; /* current hash list, to walk on */
  663.   s->bucket_id =      -1 ;
  664.   s->ntry      =       0 ; /* before the first entry */
  665.   s->next      = h->walk ; /* more such entries */
  667.   h->walk = s ;
  668.   return s;
  669. }
  671. void **
  672. next_hlst_search 
  673.   (hsrch *s)
  674. {
  675.   hlst *h ;
  676.   void ** V ;
  678.   /* sanity check */
  679.   if (s == 0) {
  680.     errno = EINVAL;
  681.     return 0;
  682.   }
  683.   /* get the hash list */
  684.   if ((h = s->hlist) == 0) {
  685.     /* list has been flushed */
  686.     errno = ENOENT ;
  687.     return 0;
  688.   }
  689.   if (s->ntry != 0)
  690.     s->ntry->locked -- ; /* release that node */
  691.   else
  692.     do { /* find next node */
  693.       /* get bucket, check for end-of-list */
  694.       if (++ s->bucket_id >= h->z.mod) {
  695. errno = 0;
  696. return 0 ;
  697.       }
  698.       s->ntry = h->bucket [s->bucket_id] ;
  699.     } while (s->ntry == 0) ;
  700.   
  701.   /* get node contents as return value */
  702.   V = &s->ntry->contents ;
  704.   /* set to next value */
  705.   if ((s->ntry = s->ntry->next) != 0)
  706.     s->ntry->locked ++ ;    /* mark it visited */
  708.   return V;
  709. }
  712. void
  713. close_hlst_search
  714.   (hsrch *s)
  715. {
  716.   hsrch **U, *u;
  717.   /* sanity check */
  718.   if (s == 0) return ;
  720.   /* is this a stale walk descriptor? */
  721.   if (s->hlist == 0) {
  722.     XFREE (s);
  723.     return ;
  724.   }
  725.   /* unlink current walk descriptor */
  726.   U = &s->hlist->walk ;
  727.   while (u = *U, u != 0) {
  728.     if (u == s) {        /* find the link pointer for that record */
  729.       if (u->ntry != 0)  /* release that particular node */
  730. u->ntry->locked -- ;
  731.       *U = u->next ;     /* unlink the walk descriptor */
  732. #     ifdef ENABLE_RHLST
  733.       if (u->clup != 0)  /* clean up peripheral my call back fn */
  734. (*u->clup)(u->clup_state);
  735. #     endif
  736.       XFREE (u);         /* done */
  737.       return ;
  738.     }
  739.     if (u->next == u) { /* XXXXXXXXXXXXX Grrr - should not happen (jh) */
  740.       fprintf (stderr, 
  741.        "%s (%d): [u->next == u] serious bug -- please reportn",
  742.        __FILE__,
  743.        __LINE__);
  744.       u->next = 0 ;
  745.       return;
  746.     }
  747.     U = &u->next; /* set to successor link */
  748.   }
  749. }
  752. int
  753. for_hlst_do
  754.   (hlst     *h,
  755.    int (*fn)(void*,void*,char*,unsigned),
  756.    void *state)
  757. {
  758.   unsigned i ;
  759.   int n ;
  760.   
  761.   /* sanity check */
  762.   if (h == 0 || fn == 0) {
  763.     errno = EINVAL;
  764.     return -1;
  765.   }
  766.   /* looping over the buckets */
  767.   for (i = 0; i < h->z.mod; i ++) {
  768.     
  769.     /* get hash queue */
  770.     hashqueue *p = h->bucket [i] ;
  771.     
  772.     while (p != 0) {
  773.       /* get next, the cb function could delete the current entry */
  774.       hashqueue *q = p->next ;
  775.       if ((n = (*fn) (state, p->contents, p->key, p->keylen)) < 0)
  776. return -1;
  777.       if (n)
  778. return n;
  779.       p = q ;
  780.     }
  781.   }
  782.   
  783.   return 0;
  784. }
  786. /* ------------------------------------------------------------------------- *
  787.  *                 public functions: sorter index                            *
  788.  * ------------------------------------------------------------------------- */
  790. void
  791. sort_hlst
  792.   (hlst *h)
  793. {
  794.   unsigned i;
  795.   hashqueue **ix ;
  796.   int (*sorter_cb)(const void*,const void*);
  798.   if (h == 0) return ;
  800.   /* create an access array with entry pointers */
  801.   if (h->access != 0) {
  802.     /* nothing has changed, yet */
  803.     if (h->access->dirty == 0)
  804.       return ;
  805.     XFREE (h->access) ;
  806.   }
  807.   h->access = XMALLOC 
  808.     (sizeof (sorter) + (h->total_entries - 1) * sizeof (hashqueue*));
  809.   h->access->size = h->total_entries ;
  811.   /* link that array somehow to the list entries */
  812.   ix = h->access->inx ;
  814.   /* looping over the buckets */
  815.   for (i = 0; i < h->z.mod; i ++) {
  816.     
  817.     /* looping over the hash queue */
  818.     hashqueue *p = h->bucket [i] ;
  819.     while (p != 0) {
  820.       /* link into access array */
  821.       * ix ++ = p ;
  822.       /* get next */
  823.       p = p->next ;
  824.     }
  825.   }
  827.   /* check comparison function */
  828.   if (h->sorter_fn != 0) {
  829.     globally_lock () ; /* not thread safe, otherwise */
  830.     sorter_fn   = h->sorter_fn   ;
  831.     sorter_desc = h->sorter_desc ;
  832.     sorter_cb   = (int(*)(const void*, const void*))__comp_custom ;
  833.   } else {
  834.     sorter_cb   = (int(*)(const void*, const void*))__comp ;
  835.   }
  836.   /* sort that access array */
  837.   qsort (h->access->inx, h->total_entries, sizeof (hashqueue*), sorter_cb);
  838.   
  839.   if (h->sorter_fn != 0)
  840.   {
  841.     globally_unlock () ;
  842.   }
  843. }
  846. int
  847. csort_hlst
  848.   (hlst *h,
  849.    int (*fn)(void*,const char*,unsigned,const char*,unsigned),
  850.    void *fn_desc)
  851. {
  852.   if (h == 0) {
  853.     errno = EINVAL;
  854.     return 0;
  855.   }
  856.   h->sorter_fn   = fn;
  857.   h->sorter_desc = fn_desc;
  858.   return 0;
  859. }
  861. void **
  862. inx_hlst
  863.   (hlst    *h,
  864.    unsigned n)
  865. {
  866.   hashqueue *p ;
  868.   if (h == 0) {
  869.     errno = EINVAL;
  870.     return 0;
  871.   }
  872.   if (h->access == 0) {
  873.     errno = ESRCH;
  874.     return 0;
  875.   }
  876.   if (n < h->access->size && (p = h->access->inx [n]) != 0)
  877.     return &p->contents ;
  878.   errno = ENOENT;
  879.   return 0 ;
  880. }
  883. void
  884. unsort_hlst
  885.   (hlst *h)
  886. {
  887.   if (h == 0 || h->access == 0) return ;
  888.   XFREE (h->access) ;
  889.   h->access = 0;
  890. }
  892. /* ------------------------------------------------------------------------- *
  893.  *                 public functions: statistics                              *
  894.  * ------------------------------------------------------------------------- */
  896. int
  897. hlst_buckets
  898.   (hlst *h)
  899. {
  900.   if (h == 0) {
  901.     errno = EINVAL;
  902.     return -1;
  903.   }
  904.   return h->z.mod;
  905. }
  908. typedef
  909. struct _hstatistics {
  910.   struct {
  911.     unsigned busy, idle ;
  912.     struct { unsigned entries, squares ; } sum ;
  913.   } buckets ;
  914.   struct {
  915.     unsigned min, max ;
  916.   } fill ;
  917. } hstatistics ;
  920. static void
  921. __hstatistics_fn
  922.  (hstatistics *state, 
  923.   unsigned      fill)
  924. {
  925.   if (fill == 0) {
  926.     state->buckets.idle ++ ;
  927.     return ;
  928.   }
  930.   state->buckets.busy ++ ;  
  931.   state->buckets.sum.entries += fill ;
  932.   fill *= fill ;
  933.   state->buckets.sum.squares += fill ;
  935.   if (fill > state->fill.max)
  936.     state->fill.max = fill ;
  938.   if (fill < state->fill.min)
  939.     state->fill.min = fill ;
  940. }
  943. void
  944. hlst_statistics
  945.   (hlst *h,
  946.    void (*fn) (void*, unsigned),
  947.    void *state)
  948. {
  949.   unsigned i, sum;
  950.   float var, mu ;
  951.   hstatistics hs;  
  953.   /* sanity check */
  954.   if (h == 0) return ;
  956.   if (fn == 0) {
  957.     fn = (void(*)(void*,unsigned))__hstatistics_fn ;
  958.     hs.fill.min = -1 ;
  959.     state = &hs ;
  960.   }
  961.   
  962.   /* looping over the buckets */
  963.   for (i = 0; i < h->z.mod; i ++) {
  964.     
  965.     /* get hash queue */
  966.     hashqueue *p = h->bucket [i] ;
  967.     unsigned   n = 0;
  968.     
  969.     while (p != 0)
  970.       ++ n, p = p->next ;
  972.     (*fn) (state, n);
  973.   }
  975.   if (fn != (void(*)(void*,unsigned))__hstatistics_fn) 
  976.     return ;
  977.  
  978.   sum = hs.buckets.idle + hs.buckets.busy ;  
  979.   if (hs.buckets.busy <= 1) {
  980.     return ;
  981.   }
  983.   sum = hs.buckets.sum.entries + hs.buckets.idle ;
  984.   fprintf (stderr, "Buckets: %u out of %u are busy, min/max fill: %u/%un",  
  985.    hs.buckets.busy, sum, hs.fill.min, hs.fill.max);
  986.   
  987.   /* busy buckets */
  988.   mu  = hs.buckets.sum.entries / hs.buckets.busy ;
  989.   var = hs.buckets.sum.squares / hs.buckets.busy  - mu * mu ;
  990.   fprintf (stderr, "Busy statistics (mean/stddev): %f/%fn", mu, var);
  992.   /* all buckets */
  993.   mu  = hs.buckets.sum.entries / sum ;
  994.   var = hs.buckets.sum.squares / sum  - mu * mu ;
  995.   fprintf (stderr, "Total statistics (mean/stddev): %f/%fn", mu, var);
  996. }