2 * Copyright © 2006 Keith Packard <keithp@keithp.com>
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.
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.
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.
21 compare_names (const void *a
, const void *b
)
23 const rev_file
*af
= a
, *bf
= b
;
25 return strcmp (af
->name
, bf
->name
);
28 #define REV_DIR_HASH 288361
30 typedef struct _rev_dir_hash
{
31 struct _rev_dir_hash
*next
;
36 static rev_dir_hash
*buckets
[REV_DIR_HASH
];
39 unsigned long hash_files (rev_file
**files
, int nfiles
)
44 for (i
= 0; i
< nfiles
; i
++)
45 h
= ((h
<< 1) | (h
>> (sizeof (h
) * 8 - 1))) ^ (unsigned long) files
[i
];
49 static int total_dirs
= 0;
52 * Take a collection of file revisions and pack them together
55 rev_pack_dir (rev_file
**files
, int nfiles
)
57 unsigned long hash
= hash_files (files
, nfiles
);
58 rev_dir_hash
**bucket
= &buckets
[hash
% REV_DIR_HASH
];
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
*)))
68 h
= malloc (sizeof (rev_dir_hash
) + nfiles
* sizeof (rev_file
*));
72 h
->dir
.nfiles
= nfiles
;
73 memcpy (h
->dir
.files
, files
, nfiles
* sizeof (rev_file
*));
79 static rev_dir
**rds
= NULL
;
86 for (hash
= 0; hash
< REV_DIR_HASH
; hash
++) {
87 rev_dir_hash
**bucket
= &buckets
[hash
];
90 while ((h
= *bucket
)) {
103 rev_pack_files (rev_file
**files
, int nfiles
, int *ndr
)
114 rds
= malloc ((sds
= 16) * sizeof (rev_dir
*));
117 qsort (files
, nfiles
, sizeof (rev_file
*), compare_names
);
119 /* pull out directories */
120 for (i
= 0; i
< nfiles
; i
++) {
121 if (!dir
|| strncmp (files
[i
]->name
, dir
, dirlen
) != 0)
124 rd
= rev_pack_dir (files
+ start
, i
- start
);
126 rds
= realloc (rds
, (sds
*= 2) * sizeof (rev_dir
*));
130 dir
= files
[i
]->name
;
131 slash
= strrchr (dir
, '/');
133 dirlen
= slash
- dir
;
138 rd
= rev_pack_dir (files
+ start
, nfiles
- start
);
140 rds
= realloc (rds
, (sds
*= 2) * sizeof (rev_dir
*));