+static bool satisfies(const TDB_DATA *data, const TDB_DATA *need)
+{
+ /* Don't need anything? Cool. */
+ if (!need)
+ return true;
+
+ /* This should be tdb_null or a real value. */
+ assert(data != &must_exist);
+ assert(data != &must_not_exist);
+ assert(data != ¬_exists_or_empty);
+
+ /* must_not_exist == must_not_exist, must_exist == must_exist, or
+ not_exists_or_empty == not_exists_or_empty. */
+ if (data->dsize == need->dsize && data->dptr == need->dptr)
+ return true;
+
+ /* Must not exist? data must not exist. */
+ if (need == &must_not_exist)
+ return data->dptr == NULL;
+
+ /* Must exist? */
+ if (need == &must_exist)
+ return data->dptr != NULL;
+
+ /* Either noexist or empty. */
+ if (need == ¬_exists_or_empty)
+ return data->dsize == 0;
+
+ /* Needs something specific. */
+ return key_eq(*data, *need);
+}
+
+static void move_to_front(struct key_user res[], unsigned int elem)
+{
+ if (elem != 0) {
+ struct key_user tmp = res[elem];
+ memmove(res + 1, res, elem*sizeof(res[0]));
+ res[0] = tmp;
+ }
+}
+
+static void restore_to_pos(struct key_user res[], unsigned int elem)
+{
+ if (elem != 0) {
+ struct key_user tmp = res[0];
+ memmove(res, res + 1, elem*sizeof(res[0]));
+ res[elem] = tmp;
+ }
+}
+
+static bool sort_deps(char *filename[], struct op *op[],
+ struct key_user res[], unsigned num,
+ const TDB_DATA *data, unsigned num_files)
+{
+ unsigned int i, files_done;
+ struct op *this_op;
+ bool done[num_files];
+
+ /* Nothing left? We're sorted. */
+ if (num == 0)
+ return true;
+
+ memset(done, 0, sizeof(done));
+
+ /* Since ops within a trace file are ordered, we just need to figure
+ * out which file to try next. Since we don't take into account
+ * inter-key relationships (which exist by virtue of trace file order),
+ * we minimize the chance of harm by trying to keep in serial order. */
+ for (files_done = 0, i = 0; i < num && files_done < num_files; i++) {
+ if (done[res[i].file])
+ continue;
+
+ this_op = &op[res[i].file][res[i].op_num];
+ /* Is what we have good enough for this op? */
+ if (satisfies(data, needs(this_op))) {
+ move_to_front(res, i);
+ if (sort_deps(filename, op, res+1, num-1,
+ gives(this_op, data), num_files))
+ return true;
+ restore_to_pos(res, i);
+ }
+ done[res[i].file] = true;
+ files_done++;
+ }
+
+ /* No combination worked. */
+ return false;
+}
+
+static void check_dep_sorting(struct key_user user[], unsigned num_users,
+ unsigned num_files)
+{
+#if DEBUG_DEPS
+ unsigned int i;
+ unsigned minima[num_files];
+
+ memset(minima, 0, sizeof(minima));
+ for (i = 0; i < num_users; i++) {
+ assert(minima[user[i].file] < user[i].op_num);
+ minima[user[i].file] = user[i].op_num;
+ }
+#endif
+}
+
+/* All these ops have the same serial number. Which comes first?
+ *
+ * This can happen both because read ops or failed write ops don't
+ * change serial number, and also due to race since we access the
+ * number unlocked (the race can cause less detectable ordering problems,
+ * in which case we'll deadlock and report: fix manually in that case).
+ */
+static void figure_deps(char *filename[], struct op *op[],
+ struct key_user user[], unsigned num_users,
+ unsigned num_files)
+{
+ /* We assume database starts empty. */
+ const struct TDB_DATA *data = &tdb_null;
+
+ if (!sort_deps(filename, op, user, num_users, data, num_files))
+ fail(filename[user[0].file], user[0].op_num+1,
+ "Could not resolve inter-dependencies");
+
+ check_dep_sorting(user, num_users, num_files);
+}
+
+static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[],
+ unsigned int num)
+{
+ unsigned int h;
+
+ /* Gcc nexted function extension. How cool is this? */
+ int compare_serial(const void *_a, const void *_b)
+ {
+ const struct key_user *a = _a, *b = _b;
+
+ /* First, maintain order within any trace file. */
+ if (a->file == b->file)
+ return a->op_num - b->op_num;
+
+ /* Otherwise, arrange by serial order. */
+ return op[a->file][a->op_num].serial
+ - op[b->file][b->op_num].serial;
+ }
+
+ /* Now sort into serial order. */
+ for (h = 0; h < total_keys * 2; h++) {
+ struct key_user *user = hash[h].user;
+
+ qsort(user, hash[h].num_users, sizeof(user[0]), compare_serial);
+ figure_deps(filename, op, user, hash[h].num_users, num);
+ }
+}
+
+static int destroy_depend(struct depend *dep)
+{
+ list_del(&dep->pre_list);
+ list_del(&dep->post_list);
+ return 0;
+}
+
projects / ccan / blobdiff