diff options
Diffstat (limited to 'proc/hash.c')
| -rw-r--r-- | proc/hash.c | 292 |
1 files changed, 292 insertions, 0 deletions
diff --git a/proc/hash.c b/proc/hash.c new file mode 100644 index 00000000..d183c0ea --- /dev/null +++ b/proc/hash.c @@ -0,0 +1,292 @@ +/* Hash table functions + Copyright (C) 1993, 1994 Free Software Foundation + +This file is part of the GNU Hurd. + +The GNU Hurd 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 2, or (at your option) +any later version. + +The GNU Hurd 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 the GNU Hurd; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +/* Written by Michael I. Bushnell. */ + +#include <mach.h> +#include <sys/types.h> +#include <hurd/hurd_types.h> +#include <string.h> +#include <stdlib.h> +#include <sys/resource.h> + +#include "proc.h" + +#define HASH(pg) (id % ht->size) +#define REHASH(pg, h) ((id + (h * h)) % ht->size) + +struct htable +{ + void **tab; + int *ids; + int size; +}; +#define HASH_DEL ((void *) -1) + +static struct htable pghash, pidhash, taskhash, porthash, sidhash, collhash; +static struct htable pgcollhash, sesscollhash; + +/* Add ITEM to the hash table HT. LOCP is the address of a pointer located + in ITEM; *LOCP will be set to the address of ITEM's hash table pointer. + The lookup key of ITEM is ID. */ +static void +addhash (struct htable *ht, + void *item, + void ***locp, + int id) +{ + int h, firsth = -1; + void **oldlist; + int *oldids; + int oldsize; + int i; + + for (h = HASH (id); + (ht->tab[h] != 0 && ht->tab[h] != HASH_DEL && h != firsth); + firsth = (firsth == -1) ? h : firsth, h = REHASH (id, firsth)) + ; + + if (ht->tab[h] == 0 + || ht->tab[h] == HASH_DEL) + { + ht->tab[h] = item; + ht->ids[h] = id; + *locp = &ht->tab[h]; + return; + } + + /* We have to rehash this again? */ + oldlist = ht->tab; + oldsize = ht->size; + oldids = ht->ids; + + ht->size = nextprime (2 * ht->size); + ht->tab = malloc (ht->size * sizeof (void *)); + ht->ids = malloc (ht->size * sizeof (int)); + bzero (ht->tab, (ht->size * sizeof (void *))); + + if (oldlist) + for (i = 0; i < oldsize; i++) + if (oldlist[i] != 0 + && oldlist[i] != HASH_DEL) + addhash (ht, oldlist[i], locp, oldids[i]); + addhash (ht, item, locp, id); + + if (oldlist) + { + free (oldlist); + free (oldids); + } +} + +/* Find and return the item in hash table HT with key ID. */ +static void * +findhash (struct htable *ht, + int id) +{ + int h, firsth = -1; + void *ret; + + for (h = HASH (id); + (ht->tab[h] != 0 && ht->ids[h] != id && h != firsth); + firsth = (firsth == -1) ? h : firsth, h = REHASH (id, firsth)) + ; + + if (ht->ids[h] == id) + ret = ht->tab[h]; + else + ret = 0; + return ret; +} + +/* Find the process corresponding to a given pid. */ +struct proc * +pid_find (pid_t pid) +{ + return findhash (&pidhash, pid); +} + +/* Find the process corresponding to a given task. */ +struct proc * +task_find (task_t task) +{ + return findhash (&taskhash, task) ? : add_tasks (task); +} + +/* Find the process corresponding to a given task, but + if we don't already know about it, just return 0. */ +struct proc * +task_find_nocreate (task_t task) +{ + return findhash (&taskhash, task); +} + +/* Find the process corresponding to a given request port. */ +struct proc * +reqport_find (mach_port_t reqport) +{ + return findhash (&porthash, reqport); +} + +/* Find the process group corresponding to a given pgid. */ +struct pgrp * +pgrp_find (pid_t pgid) +{ + return findhash (&pghash, pgid); +} + +/* Find the session corresponding to a given sid. */ +struct session * +session_find (pid_t sid) +{ + return findhash (&sidhash, sid); +} + +/* Find the process collection corresponding to a gived refport. */ +struct coll * +coll_find (mach_port_t refport) +{ + return findhash (&collhash, refport); +} + +/* Add a new process to the various hash tables. */ +void +add_proc_to_hash (struct proc *p) +{ + addhash (&pidhash, p, &p->p_pidhashloc, p->p_pid); + addhash (&taskhash, p, &p->p_taskhashloc, p->p_task); + addhash (&porthash, p, &p->p_porthashloc, p->p_reqport); +} + +/* Add a new process group to the various hash tables. */ +void +add_pgrp_to_hash (struct pgrp *pg) +{ + addhash (&pghash, pg, &pg->pg_hashloc, pg->pg_pgid); + if (pg->pg_fakecoll) + addhash (&pgcollhash, pg, &pg->pg_fakecollhashloc, pg->pg_fakecoll); + else + pg->pg_fakecollhashloc = 0; +} + +/* A process group's fake collection port has changed; update + the hash tables apporpriately. */ +void +add_pgrp_fakecoll_to_hash (struct pgrp *pg) +{ + if (pg->pg_fakecollhashloc) + *pg->pg_fakecollhashloc = HASH_DEL; + addhash (&pgcollhash, pg, &pg->pg_fakecollhashloc, pg->pg_fakecoll); +} + +/* Add a new process collection to the various hash tables. */ +void +add_coll_to_hash (struct coll *c) +{ + addhash (&collhash, c, &c->c_hashloc, c->c_refport); +} + +/* Add a new session to the various hash tables. */ +void +add_session_to_hash (struct session *s) +{ + addhash (&sidhash, s, &s->s_hashloc, s->s_sid); + if (s->s_fakecoll) + addhash (&sesscollhash, s, &s->s_fakecollhashloc, s->s_fakecoll); + else + s->s_fakecollhashloc = 0; +} + +/* A session's fake collection port has changes; update the hash tables + appropriately. */ +void +add_session_fakecoll_to_hash (struct session *s) +{ + if (s->s_fakecollhashloc) + *s->s_fakecollhashloc = HASH_DEL; + addhash (&sesscollhash, s, &s->s_fakecollhashloc, s->s_fakecoll); +} + + +/* Remove a process group from the various hash tables. */ +void +remove_pgrp_from_hash (struct pgrp *pg) +{ + *pg->pg_hashloc = HASH_DEL; + if (pg->pg_fakecollhashloc) + *pg->pg_fakecollhashloc = HASH_DEL; +} + +/* Remove a process from the various hash tables. */ +void +remove_proc_from_hash (struct proc *p) +{ + *p->p_pidhashloc = HASH_DEL; + *p->p_taskhashloc = HASH_DEL; + *p->p_porthashloc = HASH_DEL; +} + +/* Remove a process collection from the various hash tables. */ +void +remove_coll_from_hash (struct coll *c) +{ + *c->c_hashloc = HASH_DEL; +} + +/* Remove a session from the various hash tables. */ +void +remove_session_from_hash (struct session *s) +{ + *s->s_hashloc = HASH_DEL; + if (s->s_fakecollhashloc) + *s->s_fakecollhashloc = HASH_DEL; +} + +/* Call function FUN of two args for each process. FUN's first arg is + the process, its second arg is ARG. */ +void +prociterate (void (*fun) (struct proc *, void *), void *arg) +{ + int i; + + for (i = 0; i < pidhash.size; i++) + if (pidhash.tab[i] && pidhash.tab[i] != HASH_DEL) + (*fun)(pidhash.tab[i], arg); +} + +/* Call function FUN of two args for each process collection. FUN's first + arg is the collection, its second arg is ARG. */ +void +colliterate (void (*fun) (struct coll *, void *), void *arg) +{ + int i; + + for (i = 0; i < collhash.size; i++) + if (collhash.tab[i] && collhash.tab[i] != HASH_DEL) + (*fun)(collhash.tab[i], arg); +} + +/* Tell if a pid is available for use */ +int +pidfree (pid_t pid) +{ + return (!pid_find (pid) && !pgrp_find (pid) + && !session_find (pid) && !zombie_check_pid (pid)); +} + |