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/ino-map.c | 164 ------------------------------------------------------- 1 file changed, 164 deletions(-) delete mode 100644 gl/lib/ino-map.c (limited to 'gl/lib/ino-map.c') diff --git a/gl/lib/ino-map.c b/gl/lib/ino-map.c deleted file mode 100644 index 9133a19b2..000000000 --- a/gl/lib/ino-map.c +++ /dev/null @@ -1,164 +0,0 @@ -/* Map an ino_t inode number to a small integer. - - 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 "ino-map.h" - -#include "hash.h" -#include "verify.h" - -#include -#include - -/* A pair that maps an inode number to a mapped inode number; the - latter is a small unique ID for the former. */ -struct ino_map_ent -{ - ino_t ino; - size_t mapped_ino; -}; - -/* A table that manages and indexes these pairs. */ -struct ino_map -{ - /* A table of KEY,VAL pairs, where KEY is the raw ino_t value and - VAL is the small number that it maps to. */ - struct hash_table *map; - - /* The next mapped inode number to hand out. */ - size_t next_mapped_ino; - - /* Cache of the most recently allocated and otherwise-unused storage - for probing the table. */ - struct ino_map_ent *probe; -}; - -/* Hash an inode map entry. */ -static size_t -ino_hash (void const *x, size_t table_size) -{ - struct ino_map_ent const *p = x; - ino_t ino = p->ino; - - /* When INO is wider than size_t, exclusive-OR the words of INO into H. - This avoids loss of info, without applying % to the wider type, - which could be quite slow on some systems. */ - size_t h = ino; - unsigned int i; - unsigned int n_words = sizeof ino / sizeof h + (sizeof ino % sizeof h != 0); - for (i = 1; i < n_words; i++) - h ^= ino >> CHAR_BIT * sizeof h * i; - - return h % table_size; -} - -/* Return true if two inode map entries are the same. */ -static bool -ino_compare (void const *x, void const *y) -{ - struct ino_map_ent const *a = x; - struct ino_map_ent const *b = y; - return a->ino == b->ino; -} - -/* Allocate an inode map that will hand out integers starting with - NEXT_MAPPED_INO. Return NULL if memory is exhausted. */ -struct ino_map * -ino_map_alloc (size_t next_mapped_ino) -{ - struct ino_map *im = malloc (sizeof *im); - - if (im) - { - enum { INITIAL_INO_MAP_TABLE_SIZE = 1021 }; - im->map = hash_initialize (INITIAL_INO_MAP_TABLE_SIZE, NULL, - ino_hash, ino_compare, free); - if (! im->map) - { - free (im); - return NULL; - } - im->next_mapped_ino = next_mapped_ino; - im->probe = NULL; - } - - return im; -} - -/* Free an inode map. */ -void -ino_map_free (struct ino_map *map) -{ - hash_free (map->map); - free (map->probe); - free (map); -} - - -/* Insert into MAP the inode number INO if it's not there already, - and return its nonnegative mapped inode number. - If INO is already in MAP, return the existing mapped inode number. - Return INO_MAP_INSERT_FAILURE on memory or counter exhaustion. */ -size_t -ino_map_insert (struct ino_map *im, ino_t ino) -{ - struct ino_map_ent *ent; - - /* Find space for the probe, reusing the cache if available. */ - struct ino_map_ent *probe = im->probe; - if (probe) - { - /* If repeating a recent query, return the cached result. */ - if (probe->ino == ino) - return probe->mapped_ino; - } - else - { - im->probe = probe = malloc (sizeof *probe); - if (! probe) - return INO_MAP_INSERT_FAILURE; - } - - probe->ino = ino; - ent = hash_insert (im->map, probe); - if (! ent) - return INO_MAP_INSERT_FAILURE; - - if (ent != probe) - { - /* Use the existing entry. */ - probe->mapped_ino = ent->mapped_ino; - } - else - { - /* If adding 1 to map->next_mapped_ino would cause it to - overflow to zero, then it must equal INO_MAP_INSERT_FAILURE, - which is the value that should be returned in that case. - Verify that this works. */ - verify (INO_MAP_INSERT_FAILURE + 1 == 0); - - /* Prepare to allocate a new probe next time; this one is in use. */ - im->probe = NULL; - - /* INO is new; allocate a mapped inode number for it. */ - probe->mapped_ino = im->next_mapped_ino++; - } - - return probe->mapped_ino; -} -- cgit v1.2.3-54-g00ecf