[PATCH 2/2] fsck: use oidset for skiplist

["René Scharfe" <l.s.r@web.de>]

Object IDs to skip are stored in a shared static oid_array.  Lookups do
a binary search on the sorted array.  The code checks if the object IDs
are already in the correct order while loading and skips sorting in that
case.

Simplify the code by using an oidset instead.  Memory usage is a bit
higher, but lookups are done in constant time and there is no need to
worry about any sort order.

Embed the oidset into struct fsck_options to make its ownership clear
(no hidden sharing) and avoid unnecessary pointer indirection.

Signed-off-by: Rene Scharfe <l.s.r@web.de>
---
  fsck.c | 23 ++---------------------
  fsck.h |  8 +++++---
  2 files changed, 7 insertions(+), 24 deletions(-)

diff --git a/fsck.c b/fsck.c
index 83f4562390..9246afee22 100644
--- a/fsck.c
+++ b/fsck.c
@@ -10,7 +10,6 @@
  #include "fsck.h"
  #include "refs.h"
  #include "utf8.h"
-#include "sha1-array.h"
  #include "decorate.h"
  #include "oidset.h"
  #include "packfile.h"
@@ -182,19 +181,10 @@ static int fsck_msg_type(enum fsck_msg_id msg_id,
  
  static void init_skiplist(struct fsck_options *options, const char *path)
  {
-	static struct oid_array skiplist = OID_ARRAY_INIT;
-	int sorted;
  	FILE *fp;
  	struct strbuf sb = STRBUF_INIT;
  	struct object_id oid;
  
-	if (options->skiplist)
-		sorted = options->skiplist->sorted;
-	else {
-		sorted = 1;
-		options->skiplist = &skiplist;
-	}
-
  	fp = fopen(path, "r");
  	if (!fp)
  		die("Could not open skip list: %s", path);
@@ -202,17 +192,10 @@ static void init_skiplist(struct fsck_options *options, const char *path)
  		const char *p;
  		if (parse_oid_hex(sb.buf, &oid, &p) || *p != '\0')
  			die("Invalid SHA-1: %s", sb.buf);
-		oid_array_append(&skiplist, &oid);
-		if (sorted && skiplist.nr > 1 &&
-				oidcmp(&skiplist.oid[skiplist.nr - 2],
-				       &oid) > 0)
-			sorted = 0;
+		oidset_insert(&options->skiplist, &oid);
  	}
  	fclose(fp);
  	strbuf_release(&sb);
-
-	if (sorted)
-		skiplist.sorted = 1;
  }
  
  static int parse_msg_type(const char *str)
@@ -317,9 +300,7 @@ static void append_msg_id(struct strbuf *sb, const char *msg_id)
  
  static int object_on_skiplist(struct fsck_options *opts, struct object *obj)
  {
-	if (opts && opts->skiplist && obj)
-		return oid_array_lookup(opts->skiplist, &obj->oid) >= 0;
-	return 0;
+	return opts && obj && oidset_contains(&opts->skiplist, &obj->oid);
  }
  
  __attribute__((format (printf, 4, 5)))
diff --git a/fsck.h b/fsck.h
index c3cf5e0034..26120e6186 100644
--- a/fsck.h
+++ b/fsck.h
@@ -1,6 +1,8 @@
  #ifndef GIT_FSCK_H
  #define GIT_FSCK_H
  
+#include "oidset.h"
+
  #define FSCK_ERROR 1
  #define FSCK_WARN 2
  #define FSCK_IGNORE 3
@@ -34,12 +36,12 @@ struct fsck_options {
  	fsck_error error_func;
  	unsigned strict:1;
  	int *msg_type;
-	struct oid_array *skiplist;
+	struct oidset skiplist;
  	struct decoration *object_names;
  };
  
-#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL }
-#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL }
+#define FSCK_OPTIONS_DEFAULT { NULL, fsck_error_function, 0, NULL, OIDSET_INIT }
+#define FSCK_OPTIONS_STRICT { NULL, fsck_error_function, 1, NULL, OIDSET_INIT }
  
  /* descend in all linked child objects
   * the return value is:
-- 
2.18.0