From beaf631292bd74050a57b86aa3042ebaa12cf840 Mon Sep 17 00:00:00 2001 From: Jim Meyering Date: Mon, 7 Feb 2011 16:24:10 +0100 Subject: maint: move di-set and ino-map modules from ./gl to gnulib * gl/lib/di-set.c: Remove file. * gl/lib/di-set.h: Likewise. * gl/lib/ino-map.c: Likewise. * gl/lib/ino-map.h: Likewise. * gl/modules/di-set: Likewise. * gl/modules/di-set-tests: Likewise. * gl/modules/ino-map: Likewise. * gl/modules/ino-map-tests: Likewise. * gl/tests/test-di-set.c: Likewise. * gl/tests/test-ino-map.c: Likewise. * gnulib: Update to latest, now that these two modules are there. --- gl/lib/di-set.c | 259 -------------------------------------------------------- 1 file changed, 259 deletions(-) delete mode 100644 gl/lib/di-set.c (limited to 'gl/lib/di-set.c') diff --git a/gl/lib/di-set.c b/gl/lib/di-set.c deleted file mode 100644 index 5e839a311..000000000 --- a/gl/lib/di-set.c +++ /dev/null @@ -1,259 +0,0 @@ -/* Set operations for device-inode pairs stored in a space-efficient manner. - - Copyright 2009-2011 Free Software Foundation, Inc. - - This program is free software: you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program. If not, see . */ - -/* written by Paul Eggert and Jim Meyering */ - -#include -#include "di-set.h" - -#include "hash.h" -#include "ino-map.h" - -#include -#include - -/* The hash package hashes "void *", but this package wants to hash - integers. Use integers that are as large as possible, but no - larger than void *, so that they can be cast to void * and back - without losing information. */ -typedef size_t hashint; -#define HASHINT_MAX ((hashint) -1) - -/* Integers represent inode numbers. Integers in the range - 1..(LARGE_INO_MIN-1) represent inode numbers directly. (The hash - package does not work with null pointers, so inode 0 cannot be used - as a key.) To find the representations of other inode numbers, map - them through INO_MAP. */ -#define LARGE_INO_MIN (HASHINT_MAX / 2) - -/* Set operations for device-inode pairs stored in a space-efficient - manner. Use a two-level hash table. The top level hashes by - device number, as there are typically a small number of devices. - The lower level hashes by mapped inode numbers. In the typical - case where the inode number is positive and small, the inode number - maps to itself, masquerading as a void * value; otherwise, its - value is the result of hashing the inode value through INO_MAP. */ - -/* A pair that maps a device number to a set of inode numbers. */ -struct di_ent -{ - dev_t dev; - struct hash_table *ino_set; -}; - -/* A two-level hash table that manages and indexes these pairs. */ -struct di_set -{ - /* Map device numbers to sets of inode number representatives. */ - struct hash_table *dev_map; - - /* If nonnull, map large inode numbers to their small - representatives. If null, there are no large inode numbers in - this set. */ - struct ino_map *ino_map; - - /* Cache of the most recently allocated and otherwise-unused storage - for probing this table. */ - struct di_ent *probe; -}; - -/* Hash a device-inode-set entry. */ -static size_t -di_ent_hash (void const *x, size_t table_size) -{ - struct di_ent const *p = x; - dev_t dev = p->dev; - - /* When DEV is wider than size_t, exclusive-OR the words of DEV into H. - This avoids loss of info, without applying % to the wider type, - which could be quite slow on some systems. */ - size_t h = dev; - unsigned int i; - unsigned int n_words = sizeof dev / sizeof h + (sizeof dev % sizeof h != 0); - for (i = 1; i < n_words; i++) - h ^= dev >> CHAR_BIT * sizeof h * i; - - return h % table_size; -} - -/* Return true if two device-inode-set entries are the same. */ -static bool -di_ent_compare (void const *x, void const *y) -{ - struct di_ent const *a = x; - struct di_ent const *b = y; - return a->dev == b->dev; -} - -/* Free a device-inode-set entry. */ -static void -di_ent_free (void *v) -{ - struct di_ent *a = v; - hash_free (a->ino_set); - free (a); -} - -/* Create a set of device-inode pairs. Return NULL on allocation failure. */ -struct di_set * -di_set_alloc (void) -{ - struct di_set *dis = malloc (sizeof *dis); - if (dis) - { - enum { INITIAL_DEV_MAP_SIZE = 11 }; - dis->dev_map = hash_initialize (INITIAL_DEV_MAP_SIZE, NULL, - di_ent_hash, di_ent_compare, - di_ent_free); - if (! dis->dev_map) - { - free (dis); - return NULL; - } - dis->ino_map = NULL; - dis->probe = NULL; - } - - return dis; -} - -/* Free a set of device-inode pairs. */ -void -di_set_free (struct di_set *dis) -{ - hash_free (dis->dev_map); - free (dis->ino_map); - free (dis->probe); - free (dis); -} - -/* Hash an encoded inode number I. */ -static size_t -di_ino_hash (void const *i, size_t table_size) -{ - return (hashint) i % table_size; -} - -/* Using the DIS table, map a device to a hash table that represents - a set of inode numbers. Return NULL on error. */ -static struct hash_table * -map_device (struct di_set *dis, dev_t dev) -{ - /* Find space for the probe, reusing the cache if available. */ - struct di_ent *ent; - struct di_ent *probe = dis->probe; - if (probe) - { - /* If repeating a recent query, return the cached result. */ - if (probe->dev == dev) - return probe->ino_set; - } - else - { - dis->probe = probe = malloc (sizeof *probe); - if (! probe) - return NULL; - } - - /* Probe for the device. */ - probe->dev = dev; - ent = hash_insert (dis->dev_map, probe); - if (! ent) - return NULL; - - if (ent != probe) - { - /* Use the existing entry. */ - probe->ino_set = ent->ino_set; - } - else - { - enum { INITIAL_INO_SET_SIZE = 1021 }; - - /* Prepare to allocate a new probe next time; this one is in use. */ - dis->probe = NULL; - - /* DEV is new; allocate an inode set for it. */ - probe->ino_set = hash_initialize (INITIAL_INO_SET_SIZE, NULL, - di_ino_hash, NULL, NULL); - } - - return probe->ino_set; -} - -/* Using the DIS table, map an inode number to a mapped value. - Return INO_MAP_INSERT_FAILURE on error. */ -static hashint -map_inode_number (struct di_set *dis, ino_t ino) -{ - if (0 < ino && ino < LARGE_INO_MIN) - return ino; - - if (! dis->ino_map) - { - dis->ino_map = ino_map_alloc (LARGE_INO_MIN); - if (! dis->ino_map) - return INO_MAP_INSERT_FAILURE; - } - - return ino_map_insert (dis->ino_map, ino); -} - -/* Attempt to insert the DEV,INO pair into the set DIS. - If it matches a pair already in DIS, keep that pair and return 0. - Otherwise, if insertion is successful, return 1. - Upon any failure return -1. */ -int -di_set_insert (struct di_set *dis, dev_t dev, ino_t ino) -{ - hashint i; - - /* Map the device number to a set of inodes. */ - struct hash_table *ino_set = map_device (dis, dev); - if (! ino_set) - return -1; - - /* Map the inode number to a small representative I. */ - i = map_inode_number (dis, ino); - if (i == INO_MAP_INSERT_FAILURE) - return -1; - - /* Put I into the inode set. */ - return hash_insert0 (ino_set, (void *) i, NULL); -} - -/* Look up the DEV,INO pair in the set DIS. - If found, return 1; if not found, return 0. - Upon any failure return -1. */ -int -di_set_lookup (struct di_set *dis, dev_t dev, ino_t ino) -{ - hashint i; - - /* Map the device number to a set of inodes. */ - struct hash_table *ino_set = map_device (dis, dev); - if (! ino_set) - return -1; - - /* Map the inode number to a small representative I. */ - i = map_inode_number (dis, ino); - if (i == INO_MAP_INSERT_FAILURE) - return -1; - - /* Perform the look-up. */ - return !!hash_lookup (ino_set, (void const *) i); -} -- cgit v1.2.3-54-g00ecf