+/* Blue Sky: File Systems in the Cloud
+ *
+ * Copyright (C) 2009 The Regents of the University of California
+ * Written by Michael Vrable <mvrable@cs.ucsd.edu>
+ *
+ * TODO: Licensing
+ */
+
+#include <stdint.h>
+#include <glib.h>
+
+#include "bluesky.h"
+
+/* Core filesystem: handling of directories. */
+
+/* Hash a filename for a directory lookup. The string is hashed to a 64-bit
+ * value. It is guaranteed that the hash values 0, 1, and 2 are never returned
+ * (to allow the hash value to be used as an NFS cookie for a READDIR
+ * operation). */
+uint64_t bluesky_directory_hash(gchar *name)
+{
+ GChecksum *csum = g_checksum_new(G_CHECKSUM_MD5);
+ g_checksum_update(csum, (guchar *)name, -1);
+
+ guint64 hashbytes[2];
+ gsize hashsize = sizeof(hashbytes);
+ g_checksum_get_digest(csum, (guint8 *)hashbytes, &hashsize);
+
+ uint64_t hash = GUINT64_FROM_BE(hashbytes[0]);
+ if (hash < 3)
+ hash = 3;
+
+ g_checksum_free(csum);
+
+ return hash;
+}
+
+void bluesky_dirent_destroy(gpointer data)
+{
+ BlueSkyDirent *dirent = (BlueSkyDirent *)data;
+ g_free(dirent->name);
+ g_free(dirent);
+}
+
+static gint bluesky_dirent_compare(gconstpointer a, gconstpointer b,
+ gpointer unused)
+{
+ /* We can't simply subtract the hash values, since they are 64-bit and the
+ * result could overflow when converted to a gint. */
+ uint64_t hash1 = ((const BlueSkyDirent *)a)->hash;
+ uint64_t hash2 = ((const BlueSkyDirent *)b)->hash;
+
+ if (hash1 < hash2)
+ return -1;
+ else if (hash1 > hash2)
+ return 1;
+ else
+ return 0;
+}
+
+/* Perform a lookup for a file name within a directory. Returns the inode
+ * number if found, or 0 if not (0 is never a valid inode number). Should be
+ * called with the inode lock already held. */
+uint64_t bluesky_directory_lookup(BlueSkyInode *inode, gchar *name)
+{
+ g_return_val_if_fail(inode->type == BLUESKY_DIRECTORY, 0);
+ g_return_val_if_fail(inode->dirents != NULL, 0);
+
+ /* First, construct a hash of the file name. Search the directory for a
+ * match, then check to see if it does really match. */
+ uint64_t hash = bluesky_directory_hash(name);
+
+ BlueSkyDirent d = {name, hash, 0};
+ GSequenceIter *i = g_sequence_search(inode->dirents, &d,
+ bluesky_dirent_compare, NULL);
+ i = g_sequence_iter_prev(i);
+
+ if (g_sequence_iter_is_end(i))
+ return 0;
+ BlueSkyDirent *dirent = g_sequence_get(i);
+ g_print("Lookup(%s) -> 0x%016llx\n", name, dirent->hash);
+ if (dirent->hash != hash)
+ return 0;
+ if (g_strcmp0(name, dirent->name) != 0)
+ return 0;
+
+ return dirent->inum;
+}
+
+/* Insert a new entry into a directory. Should be called with the inode lock
+ * already held. */
+gboolean bluesky_directory_insert(BlueSkyInode *dir, gchar *name, uint64_t inum)
+{
+ /* First, construct a hash of the file name. Search the directory for a
+ * match, then check to see if it does really match. */
+ uint64_t hash = bluesky_directory_hash(name);
+
+ BlueSkyDirent *d = g_new(BlueSkyDirent, 1);
+ d->name = name;
+ d->hash = hash;
+ d->inum = inum;
+
+ GSequenceIter *i = g_sequence_search(dir->dirents, d,
+ bluesky_dirent_compare, NULL);
+ g_sequence_insert_before(i, d);
+
+ return TRUE;
+}
+
+/* Dump the contents of a directory to stdout. Debugging only. */
+void bluesky_directory_dump(BlueSkyInode *dir)
+{
+ g_print("Directory dump:\n");
+
+ GSequenceIter *i = g_sequence_get_begin_iter(dir->dirents);
+
+ while (!g_sequence_iter_is_end(i)) {
+ BlueSkyDirent *d = g_sequence_get(i);
+ g_print(" 0x%016llx [inum=%lld] %s\n", d->hash, d->inum, d->name);
+ i = g_sequence_iter_next(i);
+ }
+}