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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 




On 11/08/18 16:47, René Scharfe wrote:
> 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@xxxxxx>
> ---
>  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 }

Note that a NULL initialiser, for the object_names field, is missing
(not introduced by this patch). Since you have bumped into the 80th
column, you may not want to add that NULL to the end of these macros
(it is not _necessary_ after all). However, ... :-D

Otherwise, LGTM.

Thanks!

ATB,
Ramsay Jones

>  
>  /* descend in all linked child objects
>   * the return value is:



[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]

  Powered by Linux