octave-kai/gnulib-hg: lib/di-set.c annotate

annotate lib/di-set.c @ 17342:c75939cb6254

merge with default branch

author	Michael Goffioul <michael.goffioul@gmail.com>
date	Thu, 21 Feb 2013 14:57:31 +0000
parents	e542fd46ad6f
children

rev	line source
14276 6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	1 /* Set operations for device-inode pairs stored in a space-efficient manner.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	2
17249 e542fd46ad6f maint: update all copyright year number ranges Eric Blake <eblake@redhat.com> parents: 16201 diff changeset	3 Copyright 2009-2013 Free Software Foundation, Inc.
14276 6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	4
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	5 This program is free software: you can redistribute it and/or modify
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	6 it under the terms of the GNU General Public License as published by
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	7 the Free Software Foundation; either version 3 of the License, or
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	8 (at your option) any later version.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	9
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	10 This program is distributed in the hope that it will be useful,
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	11 but WITHOUT ANY WARRANTY; without even the implied warranty of
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	13 GNU General Public License for more details.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	14
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	15 You should have received a copy of the GNU General Public License
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	17
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	18 /* written by Paul Eggert and Jim Meyering */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	19
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	20 #include <config.h>
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	21 #include "di-set.h"
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	22
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	23 #include "hash.h"
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	24 #include "ino-map.h"
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	25
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	26 #include <limits.h>
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	27 #include <stdlib.h>
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	28
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	29 /* The hash package hashes "void *", but this package wants to hash
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	30 integers. Use integers that are as large as possible, but no
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	31 larger than void , so that they can be cast to void and back
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	32 without losing information. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	33 typedef size_t hashint;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	34 #define HASHINT_MAX ((hashint) -1)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	35
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	36 /* Integers represent inode numbers. Integers in the range
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	37 1..(LARGE_INO_MIN-1) represent inode numbers directly. (The hash
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	38 package does not work with null pointers, so inode 0 cannot be used
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	39 as a key.) To find the representations of other inode numbers, map
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	40 them through INO_MAP. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	41 #define LARGE_INO_MIN (HASHINT_MAX / 2)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	42
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	43 /* Set operations for device-inode pairs stored in a space-efficient
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	44 manner. Use a two-level hash table. The top level hashes by
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	45 device number, as there are typically a small number of devices.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	46 The lower level hashes by mapped inode numbers. In the typical
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	47 case where the inode number is positive and small, the inode number
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	48 maps to itself, masquerading as a void * value; otherwise, its
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	49 value is the result of hashing the inode value through INO_MAP. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	50
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	51 /* A pair that maps a device number to a set of inode numbers. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	52 struct di_ent
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	53 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	54 dev_t dev;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	55 struct hash_table *ino_set;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	56 };
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	57
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	58 /* A two-level hash table that manages and indexes these pairs. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	59 struct di_set
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	60 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	61 /* Map device numbers to sets of inode number representatives. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	62 struct hash_table *dev_map;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	63
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	64 /* If nonnull, map large inode numbers to their small
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	65 representatives. If null, there are no large inode numbers in
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	66 this set. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	67 struct ino_map *ino_map;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	68
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	69 /* Cache of the most recently allocated and otherwise-unused storage
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	70 for probing this table. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	71 struct di_ent *probe;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	72 };
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	73
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	74 /* Hash a device-inode-set entry. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	75 static size_t
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	76 di_ent_hash (void const *x, size_t table_size)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	77 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	78 struct di_ent const *p = x;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	79 dev_t dev = p->dev;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	80
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	81 /* When DEV is wider than size_t, exclusive-OR the words of DEV into H.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	82 This avoids loss of info, without applying % to the wider type,
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	83 which could be quite slow on some systems. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	84 size_t h = dev;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	85 unsigned int i;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	86 unsigned int n_words = sizeof dev / sizeof h + (sizeof dev % sizeof h != 0);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	87 for (i = 1; i < n_words; i++)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	88 h ^= dev >> CHAR_BIT * sizeof h * i;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	89
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	90 return h % table_size;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	91 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	92
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	93 /* Return true if two device-inode-set entries are the same. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	94 static bool
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	95 di_ent_compare (void const x, void const y)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	96 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	97 struct di_ent const *a = x;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	98 struct di_ent const *b = y;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	99 return a->dev == b->dev;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	100 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	101
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	102 /* Free a device-inode-set entry. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	103 static void
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	104 di_ent_free (void *v)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	105 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	106 struct di_ent *a = v;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	107 hash_free (a->ino_set);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	108 free (a);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	109 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	110
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	111 /* Create a set of device-inode pairs. Return NULL on allocation failure. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	112 struct di_set *
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	113 di_set_alloc (void)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	114 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	115 struct di_set dis = malloc (sizeof dis);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	116 if (dis)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	117 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	118 enum { INITIAL_DEV_MAP_SIZE = 11 };
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	119 dis->dev_map = hash_initialize (INITIAL_DEV_MAP_SIZE, NULL,
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	120 di_ent_hash, di_ent_compare,
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	121 di_ent_free);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	122 if (! dis->dev_map)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	123 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	124 free (dis);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	125 return NULL;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	126 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	127 dis->ino_map = NULL;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	128 dis->probe = NULL;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	129 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	130
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	131 return dis;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	132 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	133
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	134 /* Free a set of device-inode pairs. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	135 void
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	136 di_set_free (struct di_set *dis)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	137 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	138 hash_free (dis->dev_map);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	139 free (dis->ino_map);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	140 free (dis->probe);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	141 free (dis);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	142 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	143
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	144 /* Hash an encoded inode number I. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	145 static size_t
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	146 di_ino_hash (void const *i, size_t table_size)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	147 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	148 return (hashint) i % table_size;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	149 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	150
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	151 /* Using the DIS table, map a device to a hash table that represents
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	152 a set of inode numbers. Return NULL on error. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	153 static struct hash_table *
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	154 map_device (struct di_set *dis, dev_t dev)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	155 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	156 /* Find space for the probe, reusing the cache if available. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	157 struct di_ent *ent;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	158 struct di_ent *probe = dis->probe;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	159 if (probe)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	160 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	161 /* If repeating a recent query, return the cached result. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	162 if (probe->dev == dev)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	163 return probe->ino_set;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	164 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	165 else
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	166 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	167 dis->probe = probe = malloc (sizeof *probe);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	168 if (! probe)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	169 return NULL;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	170 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	171
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	172 /* Probe for the device. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	173 probe->dev = dev;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	174 ent = hash_insert (dis->dev_map, probe);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	175 if (! ent)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	176 return NULL;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	177
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	178 if (ent != probe)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	179 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	180 /* Use the existing entry. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	181 probe->ino_set = ent->ino_set;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	182 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	183 else
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	184 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	185 enum { INITIAL_INO_SET_SIZE = 1021 };
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	186
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	187 /* Prepare to allocate a new probe next time; this one is in use. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	188 dis->probe = NULL;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	189
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	190 /* DEV is new; allocate an inode set for it. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	191 probe->ino_set = hash_initialize (INITIAL_INO_SET_SIZE, NULL,
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	192 di_ino_hash, NULL, NULL);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	193 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	194
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	195 return probe->ino_set;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	196 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	197
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	198 /* Using the DIS table, map an inode number to a mapped value.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	199 Return INO_MAP_INSERT_FAILURE on error. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	200 static hashint
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	201 map_inode_number (struct di_set *dis, ino_t ino)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	202 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	203 if (0 < ino && ino < LARGE_INO_MIN)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	204 return ino;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	205
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	206 if (! dis->ino_map)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	207 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	208 dis->ino_map = ino_map_alloc (LARGE_INO_MIN);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	209 if (! dis->ino_map)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	210 return INO_MAP_INSERT_FAILURE;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	211 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	212
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	213 return ino_map_insert (dis->ino_map, ino);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	214 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	215
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	216 /* Attempt to insert the DEV,INO pair into the set DIS.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	217 If it matches a pair already in DIS, keep that pair and return 0.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	218 Otherwise, if insertion is successful, return 1.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	219 Upon any failure return -1. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	220 int
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	221 di_set_insert (struct di_set *dis, dev_t dev, ino_t ino)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	222 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	223 hashint i;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	224
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	225 /* Map the device number to a set of inodes. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	226 struct hash_table *ino_set = map_device (dis, dev);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	227 if (! ino_set)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	228 return -1;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	229
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	230 /* Map the inode number to a small representative I. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	231 i = map_inode_number (dis, ino);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	232 if (i == INO_MAP_INSERT_FAILURE)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	233 return -1;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	234
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	235 /* Put I into the inode set. */
16096 13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14307 diff changeset	236 return hash_insert_if_absent (ino_set, (void const *) i, NULL);
14276 6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	237 }
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	238
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	239 /* Look up the DEV,INO pair in the set DIS.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	240 If found, return 1; if not found, return 0.
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	241 Upon any failure return -1. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	242 int
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	243 di_set_lookup (struct di_set *dis, dev_t dev, ino_t ino)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	244 {
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	245 hashint i;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	246
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	247 /* Map the device number to a set of inodes. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	248 struct hash_table *ino_set = map_device (dis, dev);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	249 if (! ino_set)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	250 return -1;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	251
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	252 /* Map the inode number to a small representative I. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	253 i = map_inode_number (dis, ino);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	254 if (i == INO_MAP_INSERT_FAILURE)
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	255 return -1;
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	256
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	257 /* Perform the look-up. */
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	258 return !!hash_lookup (ino_set, (void const *) i);
6b7046963230 di-set, ino-map: new modules, from coreutils Jim Meyering <meyering@redhat.com> parents: diff changeset	259 }

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/di-set.c @ 17342:c75939cb6254