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

> 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 }