revdir.c

   1 /*
   2  *  Copyright © 2006 Keith Packard <keithp@keithp.com>
   3  *
   4  *  This program is free software; you can redistribute it and/or modify
   5  *  it under the terms of the GNU General Public License version 2 as
   6  *  published by the Free Software Foundation.
   7  *
   8  *  This program is distributed in the hope that it will be useful, but
   9  *  WITHOUT ANY WARRANTY; without even the implied warranty of
  10  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  *  General Public License for more details.
  12  *
  13  *  You should have received a copy of the GNU General Public License along
  14  *  with this program; if not, write to the Free Software Foundation, Inc.,
  15  *  59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  16  */
  17
  18 #include "cvs.h"
  19
  20 static int
  21 compare_names (const void *a, const void *b)
  22 {
  23     const rev_file      *af = a, *bf = b;
  24
  25     return strcmp (af->name, bf->name);
  26 }
  27
  28 #define REV_DIR_HASH    288361
  29
  30 typedef struct _rev_dir_hash {
  31     struct _rev_dir_hash    *next;
  32     unsigned long           hash;
  33     rev_dir                 dir;
  34 } rev_dir_hash;
  35
  36 static rev_dir_hash     *buckets[REV_DIR_HASH];
  37
  38 static
  39 unsigned long hash_files (rev_file **files, int nfiles)
  40 {
  41     unsigned long   h = 0;
  42     int             i;
  43
  44     for (i = 0; i < nfiles; i++)
  45         h = ((h << 1) | (h >> (sizeof (h) * 8 - 1))) ^ (unsigned long) files[i];
  46     return h;
  47 }
  48
  49 static int      total_dirs = 0;
  50
  51 /*
  52  * Take a collection of file revisions and pack them together
  53  */
  54 static rev_dir *
  55 rev_pack_dir (rev_file **files, int nfiles)
  56 {
  57     unsigned long   hash = hash_files (files, nfiles);
  58     rev_dir_hash    **bucket = &buckets[hash % REV_DIR_HASH];
  59     rev_dir_hash    *h;
  60
  61     for (h = *bucket; h; h = h->next) {
  62         if (h->hash == hash && h->dir.nfiles == nfiles &&
  63             !memcmp (files, h->dir.files, nfiles * sizeof (rev_file *)))
  64         {
  65             return &h->dir;
  66         }
  67     }
  68     h = malloc (sizeof (rev_dir_hash) + nfiles * sizeof (rev_file *));
  69     h->next = *bucket;
  70     *bucket = h;
  71     h->hash = hash;
  72     h->dir.nfiles = nfiles;
  73     memcpy (h->dir.files, files, nfiles * sizeof (rev_file *));
  74     total_dirs++;
  75     return &h->dir;
  76 }
  77
  78 static int          sds = 0;
  79 static rev_dir **rds = NULL;
  80
  81 void
  82 rev_free_dirs (void)
  83 {
  84     unsigned long   hash;
  85
  86     for (hash = 0; hash < REV_DIR_HASH; hash++) {
  87         rev_dir_hash    **bucket = &buckets[hash];
  88         rev_dir_hash    *h;
  89
  90         while ((h = *bucket)) {
  91             *bucket = h->next;
  92             free (h);
  93         }
  94     }
  95     if (rds) {
  96         free (rds);
  97         rds = NULL;
  98         sds = 0;
  99     }
 100 }
 101
 102 rev_dir **
 103 rev_pack_files (rev_file **files, int nfiles, int *ndr)
 104 {
 105     char    *dir = 0;
 106     char    *slash;
 107     int     dirlen = 0;
 108     int     i;
 109     int     start = 0;
 110     int     nds = 0;
 111     rev_dir *rd;
 112
 113     if (!rds)
 114         rds = malloc ((sds = 16) * sizeof (rev_dir *));
 115
 116     /* order by name */
 117     qsort (files, nfiles, sizeof (rev_file *), compare_names);
 118
 119     /* pull out directories */
 120     for (i = 0; i < nfiles; i++) {
 121         if (!dir || strncmp (files[i]->name, dir, dirlen) != 0)
 122         {
 123             if (i > start) {
 124                 rd = rev_pack_dir (files + start, i - start);
 125                 if (nds == sds)
 126                     rds = realloc (rds, (sds *= 2) * sizeof (rev_dir *));
 127                 rds[nds++] = rd;
 128             }
 129             start = i;
 130             dir = files[i]->name;
 131             slash = strrchr (dir, '/');
 132             if (slash)
 133                 dirlen = slash - dir;
 134             else
 135                 dirlen = 0;
 136         }
 137     }
 138     rd = rev_pack_dir (files + start, nfiles - start);
 139     if (nds == sds)
 140             rds = realloc (rds, (sds *= 2) * sizeof (rev_dir *));
 141     rds[nds++] = rd;
 142
 143     *ndr = nds;
 144     return rds;
 145 }