text: /* fdset.c implements the interface declared in fdset.h.  It will be
   * implemented by keeping a hashtable full of names for each of the different
   * types of fds, along with a template name that will be used if no specific
   * name is provided for a fileno.  The template is the type name specified with
   * a single ".%u" printf expansion appended to it.
   *
   * written nml 2003-02-13
   *
   */
  
  #include "zettair.h"
  
  #include "fdset.h"
  
  #include "def.h"
  #include "chash.h"
  #include "str.h"
  
  #include <assert.h>
  #include <errno.h>
  #include <fcntl.h>
  #include <limits.h>
  #include <stdlib.h>
  #include <sys/stat.h>
  #include <string.h>
  #include <stdio.h>
  
  /* Make multi-thread safe.  Note: only the fdset_pin and fdset_unpin
     functions obey this. */
  #ifdef ZET_MT
  #include <pthread.h>
  #endif /* ZET_MT */
  
  /* struct to represent a specific filename for a given type, fileno pair */
  struct specific {
      const char *filename;                 /* name of specific file */
      int write;                            /* whether to enable writing */
  };
  
  /* struct to hold specific and general information about a type */
  struct type {
      const char *template;                 /* filename template (containing one
                                             * %u printf conversion) */
      int write;                            /* whether to enable writing */
      struct chash *specific;               /* hashtable of specific entries */
  };
  
  /* struct to represent an open file descriptor */
  struct fd {
      int fd;                               /* file descriptor */
      unsigned int lru_count;               /* count to approximate LRU,
                                             * UINT_MAX if fd is pinned */
      unsigned int type;                    /* type of fd */
      unsigned int fileno;                  /* fd file number */
      struct fd * next;                     /* to place in a list */
  };
  
  /* internal function to give hash values for fds */
  static unsigned int fd_hash(const void *vfd) {
      const struct fd *fd = vfd;
  
      /* basic hash function - give type upper byte only (since its likely to be
       * small) and xor with fileno */
      return fd->fileno ^ (fd->type << ((sizeof(unsigned int) - 1) * 8));
  }
  
  /* internal function to compare fds */
  static int fd_cmp(const void *vone, const void *vtwo) {
      const struct fd *one = vone,
                      *two = vtwo;
  
      if (one->type == two->type) {
          if (one->fileno == two->fileno) {
              return 0;
          } else if (one->fileno < two->fileno) {
              return -1;
          } else {
              return 1;
          }
      } else if (one->type < two->type) {
          return -1;
      } else {
          return 1;
      }
  }
  
  struct fdset {
      struct chash *typehash;               /* hashtable of type entries */
      struct fd **fd;                       /* array of open fds */
      unsigned int fds;                     /* number of open fds */
      unsigned int fdsize;                  /* size of fd array */
      struct fd **key;                      /* keys in hash table */
      unsigned int keys;                    /* number of keys in hash table */
      unsigned int keysize;                 /* size of key array */
      struct chash *fdhash;                 /* hashtable for fast lookup of
                                             * fds */
      int umask;                            /* permission mask for opening new
                                             * files */
      unsigned int clock_pos;               /* last position in clock
                                             * algorithm */
      unsigned int lru_default;             /* number of second chances in clock
                                             * algorithm */
      unsigned int limit;                   /* maximum number of fds to open */
  #ifdef ZET_MT
      pthread_mutex_t mutex;
  #endif /* ZET_MT */
  };
  
  static struct fd * new_fd(void) {
      struct fd * fd = NULL;
  
      if (!(fd = malloc(sizeof(*fd))))
          return NULL;
      fd->lru_count = 0;
      fd->fd = -1;
      fd->next = NULL;
      return fd;
  }
  
  static struct fd **make_fd_array(unsigned int size) {
      struct fd **fd = NULL;
      if (!(fd = calloc(size, sizeof(*fd))))
          return NULL;
  
      int i;
      for (i = 0; i < size; i++) {
          if (!(fd[i] = new_fd())) {
              for (i--; i >= 0; i--)
                  free(fd[i]);
              free(fd);
              return NULL;
          }
      }
      return fd;
  }
  
  static int expand_fd_array(struct fd *** array_p, unsigned int * size_p) {
      unsigned int new_size = *size_p * 2 + 1;
      struct fd ** new_array = realloc(*array_p, sizeof(*new_array) * new_size);
      unsigned int i;
  
      if (new_array == NULL) {
          return -ENOMEM;
      }
      for (i = *size_p; i < new_size; i++) {
          if (!(new_array[i] = new_fd())) {
              unsigned int j;
  
              for (j = *size_p; j < i; j++) {
                  free(new_array[j]);
              }
              *array_p = new_array;
              return -ENOMEM;
          }
      }
      *array_p = new_array;
      *size_p = new_size;
      return 0;
  }
  
  struct fdset *fdset_new(int umask, unsigned int sizehint) {
      struct fdset *set;
  
      if ((set = malloc(sizeof(*set)))
       && (set->fdhash = chash_ptr_new(1, 1.0, fd_hash, fd_cmp))
       && (set->typehash = chash_luint_new(1, 1.0))) {
          set->umask = umask;
          set->fds = 0;
          set->keys = 0;
          set->lru_default = 3;    /* FIXME: get as param */
          set->limit = UINT_MAX;   /* no limit */
          set->clock_pos = 0;
          set->fdsize = 0;
          set->keysize = 0;
          set->fd = NULL;
          set->key = NULL;
  
          if (sizehint) {
              if (set->fd = make_fd_array(sizehint))
                  set->fdsize = sizehint;
  
              if (set->key = make_fd_array(sizehint))
                  set->keysize = sizehint;
  
              if (!set->fd || !set->key)
              {
                  fdset_delete(set);
                  return NULL;
              }
          }
  #ifdef ZET_MT
          pthread_mutex_init(&set->mutex, NULL);
  #endif /* ZET_MT */
      }
  
      return set;
  }
  
  static void specific_delete(void *userdata, unsigned long int key,
    void **data) {
      struct specific *sp = *data;
  
      free((void *) sp->filename);
      free(sp);
  }
  
  static void type_delete(void *userdata, unsigned long int key, void **data) {
      struct type *type = *data;
      chash_luint_ptr_foreach(type->specific, NULL, specific_delete);
      chash_delete(type->specific);
      free((void *) type->template);
      free(type);
  }
  
  void fdset_delete(struct fdset *set) {
      unsigned int i;
  
      chash_luint_ptr_foreach(set->typehash, NULL, type_delete);
      chash_delete(set->typehash);
      chash_delete(set->fdhash);
  
      for (i = 0; i < set->fds; i++) {
          close(set->fd[i]->fd);
          set->fd[i]->fd = -1;
          free(set->fd[i]);
      }
  
      for (i = 0; i < set->keysize; i++) {
          if (set->key[i]) {
              free(set->key[i]);
          }
      }
  
      for (i = set->fds; i < set->fdsize; i++) {
          if (set->fd[i]) {
              free(set->fd[i]);
          }
      }
  
  #ifdef ZET_MT
      pthread_mutex_destroy(&set->mutex);
  #endif /* ZET_MT */
  
      free(set->fd);
      free(set->key);
      free(set);
  }
  
  /* convert a string into a printf specifying by escaping potential format
   * specifiers and adding our own */
  static int maketemplate(char *dst, unsigned int dstlen, const char *src,
    unsigned int srclen) {
      char *dstend = dst + dstlen;
      const char *srcend = src + srclen;
  
      while ((dst < dstend) && (src < srcend) && *src) {
          switch (*src) {
          case '%':
              *dst++ = *src++;
              if (dst < dstend) {
                  *dst++ = '%';
              } else {
                  return 0;
              }
              break;
  
          default:
              *dst++ = *src++;
              break;
  
          case '\0':
              return 0;
              break;
          };
      }
  
      if (dst < dstend) {
          if (dstend - dst < 4) {
              return 0;
          }
          *dst++ = '.';
          *dst++ = '%';
          *dst++ = 'u';
          *dst = '\0';
          return 1;
      }
  
      return 0;
  }
  
  /* undo maketemplate conversion, returning length of created string */
  static unsigned int untemplate(char *dst, unsigned int dstlen,
    const char *src, unsigned int srclen) {
      char *dstend = dst + dstlen,
           *dstcpy = dst;
      const char *srcend = src + srclen;
  
      while ((dst < dstend) && (src < srcend) && *src) {
          switch (*src) {
          case '%':
              *dst++ = *src++;
              if (*src == '%') {
                  /* escaped it, skip */
                  src++;
              } else if (*src == 'u') {
                  /* end of string, end dst on second previous char */
                  dst -= 2;
                  assert(*dst == '.');
                  *dst = '\0';
                  return dst - dstcpy;
              } else {
                  /* don't know what happened */
                  assert(0);
              }
              break;
  
          default:
              *dst++ = *src++;
              break;
  
          case '\0':
              /* shouldn't happen */
              assert(0);
              break;
          };
      }
  
      /* shouldn't happen */
      assert(0);
      return 0;
  }
  
  int fdset_set_type_name(struct fdset *set, unsigned int typeno,
    const char *name, unsigned int namelen, int write) {
      char buf[FILENAME_MAX * 2 + 1];
      void **find;
      struct type *type = NULL;
  
      if (maketemplate(buf, FILENAME_MAX * 2 + 1, name, namelen)) {
          if ((chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK)
              /* trying to change the template for an existing type, don't do
               * this as it may have unintended consequences for files already
               * open. */
            || !((type = malloc(sizeof(*type)))
              && (type->specific = chash_luint_new(1, 1.0))
              && (chash_luint_ptr_insert(set->typehash, typeno, type)
                == CHASH_OK))) {
              /* couldn't insert new entry */
  
              if (type) {
                  if (type->specific) {
                      chash_delete(type->specific);
                  }
                  free(type);
              }
              return -EINVAL;
          }
  
          if ((type->template = str_dup(buf))) {
              type->write = !!write;
              return FDSET_OK;
          } else {
              void *remove;
  
              chash_luint_ptr_remove(set->typehash, typeno, &remove);
              chash_delete(type->specific);
              free(type);
              return -ENOMEM;
          }
      }
  
      return -EINVAL;
  }
  
  int fdset_create_new_type(struct fdset *set, const char *basename,
    const char *suffix, int write, unsigned int *typeno) {
      char name_buf[FILENAME_MAX + 1];
      int ret;
  
      ret = snprintf((char *) name_buf, FILENAME_MAX, "%s.%s", basename, suffix);
      if (ret >= FILENAME_MAX)
          return -EINVAL;
      else if (ret < 0)
          return -errno;
  
      *typeno = fdset_types(set);
      return fdset_set_type_name(set, *typeno, name_buf, ret, write);
  }
  
  int fdset_set_fd_name(struct fdset *set, unsigned int typeno,
    unsigned int fileno, const char *name, unsigned int namelen,
    int write) {
      struct type *type;
      void **find;
      struct specific *sp = NULL;
  
      if ((chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK)
        && (type = *find)) {
          if (chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK) {
              /* trying to set name thats already been set */
              sp = *find;
              if ((namelen == strvlen(sp->filename))
                && !str_ncmp(name, sp->filename, namelen)) {
                  /* setting it to the same thing it was, allow it (rebuild
                   * depends on this behaviour) */
                  return FDSET_OK;
              } else {
                  /* setting it to something different, return error */
                  return -EEXIST;
              }
          }
  
          if (!((sp = malloc(sizeof(*sp)))
              && (sp->filename
                = str_ndup(name, namelen))
              && (chash_luint_ptr_insert(type->specific, fileno, sp)
                == CHASH_OK))) {
              /* couldn't insert new entry */
  
              if (sp) {
                  if (sp->filename) {
                      free((void *) sp->filename);
                  }
                  free(sp);
              }
              return -ENOMEM;
          }
  
          sp->write = !!write;
          return FDSET_OK;
      }
  
      return -ENOENT;
  }
  
  int fdset_set_fd_delete_name(struct fdset *set, unsigned int typeno,
    unsigned int fileno, const char *name, unsigned int namelen) {
  
  	struct type *type;
      void **find;
      struct specific *sp = NULL;
  
      /* find target fd */
      if ((chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK)
        && (type = *find)) {
          if (chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK) {
              sp = *find;
  
              if ((namelen != strvlen(sp->filename))
                            || str_ncmp(name, sp->filename, namelen)) {
              	/* the user specified filename, and our recorded one don't match */
              	return -ENOENT;
              }
  
              /* remove from hash */
              if (chash_luint_ptr_remove(type->specific, fileno, find) == CHASH_OK) {
                  /* delete item */
                  if (sp) {
                      if (sp->filename) {
                          free((void *) sp->filename);
                      }
                      free(sp);
                  }
              	return FDSET_OK;
              }
          }
      }
      return -ENOENT;
  }
  
  static int fdset_ensure_fd_array_space(struct fdset *set) {
      if (set->fds >= set->fdsize) {
          int retval = expand_fd_array(&set->fd, &set->fdsize);
          if (retval < 0)
              return retval;
          assert(set->fdsize > set->fds);
      }
  
      if (set->keys >= set->keysize) {
          int retval = expand_fd_array(&set->key, &set->keysize);
          if (retval < 0)
              return retval;
          assert(set->keysize > set->keys);
      }
      return 0;
  }
  
  /* Insert a fd into our fdhash. */
  static int fdset_insert_fd(struct fdset *set, unsigned int typeno,
    unsigned int fileno, int fd) {
      int found;
      void **find;
      int retval;
      if ( (retval = fdset_ensure_fd_array_space(set)) < 0) {
          return retval;
      }
      set->fd[set->fds]->fd = fd;
      set->fd[set->fds]->type = typeno;
      set->fd[set->fds]->fileno = fileno;
      set->fd[set->fds]->lru_count = UINT_MAX;
      set->key[set->keys]->type = typeno;
      set->key[set->keys]->fileno = fileno;
      set->key[set->keys]->lru_count = UINT_MAX;
      if (chash_ptr_ptr_find_insert(set->fdhash, set->key[set->keys],
          &find, set->fd[set->fds], &found) != CHASH_OK) {
  
          return -errno;
      }
      if (found) {
          struct fd * found = *find;
          set->fd[set->fds]->next = found;
          *find = set->fd[set->fds];
      } else {
          set->keys++;
      }
      set->fds++;
      return FDSET_OK;
  }
  
  int fdset_create(struct fdset *set, unsigned int typeno, unsigned int fileno) {
      char filename[FILENAME_MAX + 1];
      int retval;
      unsigned int namelen = 0;
      int write = 0;
      int fd;
      int flags;
  
      if ((retval = fdset_name(set, typeno, fileno, filename, FILENAME_MAX,
          &namelen, &write)) != FDSET_OK) {
  
          return retval;
      }
      flags = (write * O_RDWR) | (!write * O_RDONLY) | O_CREAT | O_EXCL;
  
      /* make sure we're not over the limit */
      if (set->fds >= set->limit) {
          if ((retval = fdset_close(set)) != FDSET_OK) {
              return retval;
          }
      }
  
      /* ok, try to open this file non-create. */
      if ((fd = open((const char *) filename, flags, set->umask)) < 0) {
          if (errno == EMFILE || errno == ENFILE) {
              errno = 0;
              if ((retval = fdset_close(set)) != FDSET_OK) {
                  return retval;
              }
              if ((fd = open((const char *) filename, flags, set->umask)) < 0) {
                  return -errno;
              }
          } else {
              return -errno;
          }
      }
      assert(fd >= 0);
  
      /* we've got our fd; put it into our hashtable.
         We assume that if the file was just created, it can't be in
         the hashtable. */
      if ((retval = fdset_insert_fd(set, typeno, fileno, fd)) != FDSET_OK) {
          close(fd);
          return retval;
      }
  
      return fd;
  }
  
  int fdset_debug_create(struct fdset *set, unsigned int typeno,
    unsigned int fileno, const char * src_file, int src_line) {
      int retval;
      static int count = 0;
      retval = fdset_create(set, typeno, fileno);
      fprintf(stderr, "<create %d: fd %d, type %d, fileno %d (%s: %d)>\n",
        count++, retval, typeno, fileno, src_file, src_line);
      return retval;
  }
  
  int fdset_create_seek(struct fdset *set, unsigned int typeno,
    unsigned int fileno, unsigned long int offset) {
      int fd;
      if ((fd = fdset_create(set, typeno, fileno)) < 0) {
          return fd;
      }
  
      if (lseek(fd, offset, SEEK_SET) == (off_t) -1) {
          fdset_unpin(set, typeno, fileno, fd);
          return -errno;
      }
      return fd;
  }
  
  int fdset_debug_create_seek(struct fdset *set, unsigned int typeno,
    unsigned int fileno, unsigned long int offset, const char * src_file,
    int src_line) {
      int retval;
      static int count = 0;
      retval = fdset_create_seek(set, typeno, fileno, offset);
      fprintf(stderr, "<create %d: fd %d, type %d, fileno %d, offset %lu "
        "(%s: %d)>\n", count++, retval, typeno, fileno, offset,
        src_file, src_line);
      return retval;
  }
  
  static int fdset_pin_locked(struct fdset *set, unsigned int typeno,
    unsigned int fileno, unsigned long int offset, int whence) {
      const char *filename;
      char buf[FILENAME_MAX + 1];
      struct fd key,
                *found;
      void **find;
      struct type *type;
      struct specific *sp;
      int write;
      int retval;
      int fnd;
  
      /* first, search open fd hashtable for match */
      key.type = typeno;
      key.fileno = fileno;
      if (chash_ptr_ptr_find(set->fdhash, &key, &find) == CHASH_OK) {
          found = *find;
          while (found != NULL && found->lru_count == UINT_MAX) {
              found = found->next;
          }
          if (found != NULL) {
              found->lru_count = UINT_MAX;
              assert(found->fd > 0);
  
              if (((whence == SEEK_CUR) && (offset == 0))
                || (lseek(found->fd, offset, whence) != (off_t) -1)) {
                  return found->fd;
              } else {
                  return -errno;
              }
          }
      }
  
      /* otherwise, try to open a new fd */
      if ((retval = fdset_ensure_fd_array_space(set)) < 0) {
          return retval;
      }
  
      /* lookup filename in hash tables */
      if (chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK) {
          type = *find;
          find = NULL;
          if (((chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK)
              && ((sp = *find), (write = sp->write), (filename = sp->filename)))
            || ((snprintf((char *) buf, FILENAME_MAX,
              (const char *) type->template, fileno)
                <= FILENAME_MAX)
              && ((write = type->write), (filename = buf)))) {
              void **find = NULL;
              int flags = (write * O_RDWR) | (!write * O_RDONLY);
  
              if ((set->fds < set->limit)
                && ((set->fd[set->fds]->fd
                  = open((const char *) filename, flags, set->umask)) != -1)
                && ((set->fd[set->fds]->type = typeno),
                  (set->fd[set->fds]->fileno = fileno),
                  (set->fd[set->fds]->lru_count = UINT_MAX))
                && ((set->key[set->keys]->type = typeno),
                  (set->key[set->keys]->fileno = fileno),
                  (set->key[set->keys]->lru_count = UINT_MAX))
                /* insert into fds hashtable */
                && (chash_ptr_ptr_find_insert(set->fdhash, set->key[set->keys],
                    &find, set->fd[set->fds], &fnd) == CHASH_OK)) {
  
                  if (fnd) {
                      struct fd * found = *find;
                      set->fd[set->fds]->next = found;
                      *find = set->fd[set->fds];
                  } else {
                      set->keys++;
                  }
                  /* this is a new file, so SEEK_CUR is equivalent
                     to SEEK_SET.  We make this distinction to allow
                     indexing of non-seekable file descriptors, e.g.
                     <(gunzip foo.txt.gz); this is a bit of a hack. */
                  if (((whence == SEEK_CUR || whence == SEEK_SET)
                        && (offset == 0))
                    || (lseek(set->fd[set->fds]->fd, offset, whence)
                      != (off_t) -1)) {
  
                      return set->fd[set->fds++]->fd;
                  } else {
                      /* failed to seek, leave fd open but mark it as
                       * replaceable */
                      set->fd[set->fds++]->lru_count = 0;
                      return -errno;
                  }
              } else if (set->fd[set->fds]->fd >= 0) {
                  close(set->fd[set->fds]->fd);
                  set->fd[set->fds]->fd = -1;
                  return -ENOMEM;
              } else if (((set->fds >= set->limit)
                  || (errno == EMFILE) || (errno == ENFILE))
                && (fdset_close(set) == FDSET_OK)) {
                  /* having closed a file, try again */
                  void **find = NULL;
  
                  errno = 0;
                  if (((set->fd[set->fds]->fd
                      = open((const char *) filename, flags, set->umask)) != -1)
                    && ((set->fd[set->fds]->type = typeno),
                      (set->fd[set->fds]->fileno = fileno),
                      (set->fd[set->fds]->lru_count = UINT_MAX))
                    && ((set->key[set->keys]->type = typeno),
                        (set->key[set->keys]->fileno = fileno),
                        (set->key[set->keys]->lru_count = UINT_MAX))
                    /* insert into fds hashtable */
                    && (chash_ptr_ptr_find_insert(set->fdhash, set->fd[set->fds],
                        &find, set->fd[set->fds], &fnd) == CHASH_OK)) {
  
                      if (fnd) {
                          struct fd * found = *find;
                          set->fd[set->fds]->next = found;
                          *find = set->fd[set->fds];
                      } else {
                          set->keys++;
                      }
                      if (((whence == SEEK_CUR) && (offset == 0))
                        || (lseek(set->fd[set->fds]->fd, offset, whence)
                            != (off_t) -1)) {
  
                          return set->fd[set->fds++]->fd;
                      } else {
                          /* failed to seek, leave fd open but mark it as
                           * replaceable */
                          set->fd[set->fds++]->lru_count = 0;
                          return -errno;
                      }
                  } else {
                      /* couldn't open file */
                      return -errno;
                  }
              } else {
                  /* open failed */
                  assert(set->fd[set->fds]->fd == -1);
                  assert(errno);
                  return -errno;
              }
          } else {
              return -ENOSPC;  /* filename was too long */
          }
      }
  
      return -EINVAL;
  }
  
  int fdset_pin(struct fdset *set, unsigned int typeno, unsigned int fileno,
    unsigned long int offset, int whence) {
      int retval = 0;
  #ifdef ZET_MT
      pthread_mutex_lock(&set->mutex);
  #endif /* ZET_MT */
      retval = fdset_pin_locked(set, typeno, fileno, offset, whence);
  #ifdef ZET_MT
      pthread_mutex_unlock(&set->mutex);
  #endif /* ZET_MT */
      return retval;
  }
  
  int fdset_debug_pin(struct fdset *set, unsigned int typeno,
    unsigned int fileno, unsigned long int offset, int whence,
    const char * src_file, int src_line) {
      static int count = 0;
      int retval = 0;
      retval = fdset_pin(set, typeno, fileno, offset, whence);
      fprintf(stderr, "<pin %d: fd %d, type %d, fileno %d (%s: %d)>\n", count++,
        retval, typeno, fileno, src_file, src_line);
      return retval;
  }
  
  int fdset_name(struct fdset *set, unsigned int typeno, unsigned int fileno,
    char *buf, unsigned int buflen, unsigned int *len, int *write) {
      void **find;
      struct type *type;
      struct specific *sp;
  
      /* lookup name in hash tables */
      if (chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK) {
          type = *find;
          if ((chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK)
              && (sp = *find)) {
              *len = str_lcpy(buf, sp->filename, buflen);
              *write = sp->write;
          } else {
              *len = snprintf((char *) buf, buflen,
                  (const char *) type->template, fileno);
              *write = type->write;
          }
          return FDSET_OK;
      } else {
          return -ENOENT;
      }
  }
  
  int fdset_type_name(struct fdset *set, unsigned int typeno,
    char *buf, unsigned int buflen, unsigned int *len, int *write) {
      void **find;
      struct type *type;
  
      /* lookup name in hash tables */
      if (chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK) {
          type = *find;
          *write = type->write;
          *len
            = untemplate(buf, buflen, type->template, strvlen(type->template));
          return FDSET_OK;
      } else {
          return -ENOENT;
      }
  }
  
  static int fdset_unpin_locked(struct fdset *set, unsigned int typeno,
    unsigned int fileno, int fd) {
      struct fd key,
                *found;
      void **find;
  
      /* search open fd hashtable for match */
      key.type = typeno;
      key.fileno = fileno;
      if (chash_ptr_ptr_find(set->fdhash, &key, &find) == CHASH_OK) {
          found = *find;
          while (found != NULL && found->fd != fd)
              found = found->next;
          if (found == NULL) {
              return -ENOENT;
          }
          assert(found->lru_count == UINT_MAX);
          found->lru_count = set->lru_default;
          return FDSET_OK;
      } else {
          return -ENOENT;
      }
  }
  
  int fdset_unpin(struct fdset *set, unsigned int typeno, unsigned int fileno,
    int fd) {
      int retval = 0;
  #ifdef ZET_MT
      pthread_mutex_lock(&set->mutex);
  #endif /* ZET_MT */
      retval = fdset_unpin_locked(set, typeno, fileno, fd);
  #ifdef ZET_MT
      pthread_mutex_unlock(&set->mutex);
  #endif /* ZET_MT */
      return retval;
  }
  
  int fdset_debug_unpin(struct fdset *set, unsigned int typeno,
    unsigned int fileno, int fd, const char * src_file, int src_line) {
      static int count = 0;
      fprintf(stderr, "<unpin %d: fd %d, type %d, fileno %d (%s: %d)>\n",
        count++, fd, typeno, fileno, src_file, src_line);
      return fdset_unpin(set, typeno, fileno, fd);
  }
  
  static int fdset_fd_close(struct fdset *set, int index) {
      void **find;
      struct fd *found;
      struct fd *prev = NULL;
      int ret;
  
      /* XXX: for some reason (?) this close call can take an looong time (10s or
       * so) on mac OS X */
      if (close(set->fd[index]->fd) != 0) {
          assert(!CRASH);
          assert(errno);
          return -errno;
      }
      set->fd[index]->fd = -1;
  
      /* remove from fdhash */
      ret = chash_ptr_ptr_find(set->fdhash, set->fd[index], &find);
      assert(ret == CHASH_OK);
      found = *find;
      while (found != set->fd[index]) {
          prev = found;
          found = found->next;
          assert(found != NULL);
      }
      if (prev == NULL) {
          if (found->next) {
              *find = found->next;
          } else {
              void *val;
  
              /* have removed last from list */
              ret = chash_ptr_ptr_remove(set->fdhash, set->fd[index], &val);
              assert(ret == CHASH_OK);
          }
      } else {
          prev->next = found->next;
      }
      found->next = NULL;
  
      /* move it to the end of the array of fds */
      found = set->fd[index];
      set->fds--;
      memmove(&set->fd[index], &set->fd[index + 1],
        sizeof(found) * (set->fds - index));
      set->fd[set->fds] = found;
      return FDSET_OK;
  }
  
  int fdset_close(struct fdset *set) {
      int changed;
      unsigned int i;
  
      /* ensure that clock pos is valid */
      while (set->clock_pos > set->fds) {
          set->clock_pos -= set->fds;
      }
  
      /* clock approximation of LRU algorithm */
      do {
          changed = 0;
  
          for (i = set->clock_pos; i < set->fds; i++) {
              if (!set->fd[i]->lru_count) {
                  set->clock_pos = i;
                  return fdset_fd_close(set, i);
              } else {
                  /* decrements count by one if count is not set to UINT_MAX
                   * (UINT_MAX indicates that it is pinned and can't be
                   * closed) */
                  if (set->fd[i]->lru_count != UINT_MAX) {
                      set->fd[i]->lru_count--;
                      changed = 1;
                  }
              }
          }
  
          for (i = 0; i < set->clock_pos; i++) {
              if (!set->fd[i]->lru_count) {
                  set->clock_pos = i;
                  return fdset_fd_close(set, i);
              } else {
                  /* decrements count by one if count is not set to UINT_MAX
                   * (UINT_MAX indicates that it is pinned and can't be
                   * closed) */
                  if (set->fd[i]->lru_count != UINT_MAX) {
                      set->fd[i]->lru_count--;
                      changed = 1;
                  }
              }
          }
      } while (changed);
  
      /* all available fds are pinned */
      assert(fdset_opened(set) == fdset_pinned(set));
      return -ENOENT;
  }
  
  unsigned int fdset_opened(struct fdset *set) {
      return set->fds;
  }
  
  unsigned int fdset_pinned(struct fdset *set) {
      unsigned int i,
                   count = 0;
  
      for (i = 0; i < set->fds; i++) {
          if (set->fd[i]->lru_count == UINT_MAX) {
              count++;
          }
      }
  
      return count;
  }
  
  int fdset_isset(struct fdset *set, unsigned int typeno, unsigned int fileno,
    int *isset) {
      void **find;
      struct type *type;
      struct specific *sp;
  
      /* lookup name in hash tables */
      if (chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK) {
          type = *find;
          if ((chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK)
              && (sp = *find)) {
              *isset = 1;
          } else {
              *isset = 0;
          }
          return FDSET_OK;
      }
  
      return -EINVAL;
  }
  
  unsigned int fdset_types(struct fdset *set) {
      return chash_size(set->typehash);
  }
  
  int fdset_close_file(struct fdset *set, unsigned int typeno,
    unsigned int fileno) {
      struct fd key,
                *found;
      void **find;
      unsigned int i;
  
      /* first, search open fd hashtable for match */
      key.type = typeno;
      key.fileno = fileno;
      /* close all of the open fd's for this file */
      if (chash_ptr_ptr_find(set->fdhash, &key, &find) == CHASH_OK) {
          found = *find;
          while (found) {
              if (found->lru_count != UINT_MAX) {
                  /* XXX: linear search through fd array to determine position */
                  for (i = 0; (i < set->fds) && (set->fd[i] != found); i++) ;
                  assert((i < set->fds) && (set->fd[i] == found));
  
                  found = found->next;
                  fdset_fd_close(set, i);
              } else {
                  fprintf(stderr, "Still pinned: fd: %d, lru_count: %u, "
                    "type %u, fileno %u\n", found->fd, found->lru_count,
                    found->type, found->fileno);
                  /* can't unlink, we still have open references to it */
                  return -EBUSY;
              }
          }
      }
      return FDSET_OK;
  }
  
  int fdset_unlink(struct fdset *set, unsigned int typeno, unsigned int fileno) {
      char buf[FILENAME_MAX + 1];
      void **find;
      struct specific *sp;
      struct type *type;
      unsigned int len;
      int ret;
  
      ret = fdset_close_file(set, typeno, fileno);
      if (ret < 0)
          return ret;
  
      /* lookup name in hash tables */
      if (chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK) {
          type = *find;
          if ((chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK)
              && (sp = *find)) {
  
              if (sp->write) {
                  if (unlink(sp->filename) == 0) {
                      return FDSET_OK;
                  } else {
                      return -errno;
                  }
              } else {
                  return -EBADF;
              }
          } else if (type->write) {
              len = snprintf((char *) buf, FILENAME_MAX,
                  (const char *) type->template, fileno);
              assert(len <= FILENAME_MAX);
  
              if (unlink(buf) == 0) {
                  return FDSET_OK;
              } else {
                  return -errno;
              }
          } else {
              return -EBADF;
          }
      } else {
          return -ENOENT;
      }
  }
  
  /* debugging function to return the name of a repository.  DONT USE THIS FOR
   * ANYTHING SERIOUS (uses static buffer) */
  const char *fdset_debug_name(struct fdset *set, int typeno,
    unsigned int fileno) {
      void **find;
      struct type *type;
      struct specific *sp;
      static char buf[FILENAME_MAX + 1];
  
      /* lookup name in hash tables */
      if (chash_luint_ptr_find(set->typehash, typeno, &find) == CHASH_OK) {
          type = *find;
          if ((chash_luint_ptr_find(type->specific, fileno, &find) == CHASH_OK)
              && (sp = *find)) {
              str_lcpy(buf, sp->filename, FILENAME_MAX);
          } else {
              snprintf((char *) buf, FILENAME_MAX,
                  (const char *) type->template, fileno);
          }
          return buf;
      } else {
          return NULL;
      }
  }
  
  