From 74030f2f871dde4a6bcac3c011fcc66a6c22be80 Mon Sep 17 00:00:00 2001 From: Mark Adler Date: Thu, 26 Mar 2026 15:35:49 -0700 Subject: Clean up skipset.h comment formatting. --- contrib/minizip/skipset.h | 187 ++++++++++++++++++++++++---------------------- 1 file changed, 97 insertions(+), 90 deletions(-) diff --git a/contrib/minizip/skipset.h b/contrib/minizip/skipset.h index 34e24438..ad09dd09 100644 --- a/contrib/minizip/skipset.h +++ b/contrib/minizip/skipset.h @@ -1,56 +1,59 @@ /* skipset.h -- set operations using a skiplist -// Copyright (C) 2024-2026 Mark Adler -// See MiniZip_info.txt for the license. - -// This implements a skiplist set, i.e. just keys, no data, with ~O(log n) time -// insert and search operations. The application defines the type of a key, and -// provides a function to compare two keys. - -// This header is not definitions of functions found in another source file -- -// it creates the set functions, with the application's key type, right where -// the #include is. Before this header is #included, these must be defined: -// -// 1. A macro or typedef for set_key_t, the type of a key. -// 2. A macro or function set_cmp(a, b) to compare two keys. The return values -// are < 0 for a < b, 0 for a == b, and > 0 for a > b. -// 3. A macro or function set_drop(s, k) to release the key k's resources, if -// any, when doing a set_end() or set_clear(). s is a pointer to the set -// that key is in, for use with set_free() if desired. -// -// Example usage: -// -// typedef int set_key_t; -// #define set_cmp(a, b) ((a) < (b) ? -1 : (a) == (b) ? 0 : 1) -// #define set_drop(s, k) -// #include "skipset.h" -// -// int test(void) { // return 0: good, 1: bad, -1: out of memory -// set_t set; -// if (setjmp(set.env)) -// return -1; -// set_start(&set); -// set_insert(&set, 2); -// set_insert(&set, 1); -// set_insert(&set, 7); -// int bad = !set_found(&set, 2); -// bad = bad || set_found(&set, 5); -// set_end(&set); -// return bad; -// } -// -// Interface summary (see more details below): -// - set_t is the type of the set being operated on (a set_t pointer is passed) -// - set_start() initializes a new, empty set (initialize set.env first) -// - set_insert() inserts a new key into the set, or not if it's already there -// - set_found() determines whether or not a key is in the set -// - set_end() ends the use of the set, freeing all memory -// - set_clear() empties the set, equivalent to set_end() and then set_start() -// - set_ok() checks if set appears to be usable, i.e. started and not ended -// -// Auxiliary functions available to the application: -// - set_alloc() allocates memory with optional tracking (#define SET_TRACK) -// - set_free() deallocates memory allocated by set_alloc() -// - set_rand() returns 32 random bits (seeded by set_start()) */ + Copyright (C) 2024-2026 Mark Adler + See MiniZip_info.txt for the license. + */ + +/* + This implements a skiplist set, i.e. just keys, no data, with ~O(log n) time + insert and search operations. The application defines the type of a key, and + provides a function to compare two keys. + + This header is not definitions of functions found in another source file -- + it creates the set functions, with the application's key type, right where + the #include is. Before this header is #included, these must be defined: + + 1. A macro or typedef for set_key_t, the type of a key. + 2. A macro or function set_cmp(a, b) to compare two keys. The return values + are < 0 for a < b, 0 for a == b, and > 0 for a > b. + 3. A macro or function set_drop(s, k) to release the key k's resources, if + any, when doing a set_end() or set_clear(). s is a pointer to the set + that key is in, for use with set_free() if desired. + + Example usage: + + typedef int set_key_t; + #define set_cmp(a, b) ((a) < (b) ? -1 : (a) == (b) ? 0 : 1) + #define set_drop(s, k) + #include "skipset.h" + + int test(void) { // return 0: good, 1: bad, -1: out of memory + set_t set; + if (setjmp(set.env)) + return -1; + set_start(&set); + set_insert(&set, 2); + set_insert(&set, 1); + set_insert(&set, 7); + int bad = !set_found(&set, 2); + bad = bad || set_found(&set, 5); + set_end(&set); + return bad; + } + + Interface summary (see more details below): + - set_t is the type of the set being operated on (a set_t pointer is passed) + - set_start() initializes a new, empty set (initialize set.env first) + - set_insert() inserts a new key into the set, or not if it's already there + - set_found() determines whether or not a key is in the set + - set_end() ends the use of the set, freeing all memory + - set_clear() empties the set, equivalent to set_end() and then set_start() + - set_ok() checks if set appears to be usable, i.e. started and not ended + + Auxiliary functions available to the application: + - set_alloc() allocates memory with optional tracking (#define SET_TRACK) + - set_free() deallocates memory allocated by set_alloc() + - set_rand() returns 32 random bits (seeded by set_start()) + */ #ifndef SKIPSET_H #define SKIPSET_H @@ -63,23 +66,27 @@ #include /* assert.h */ #include "ints.h" /* i16_t, ui32_t, ui64_t */ -/* Structures and functions below noted as "--private--" should not be used by -// the application. set_t is partially private and partially public -- see the -// comments there. +/* + Structures and functions below noted as "--private--" should not be used by + the application. set_t is partially private and partially public -- see the + comments there. -// There is no POSIX random() in MSVC, and rand() is awful. For portability, we -// cannot rely on a library function for random numbers. Instead we use the -// fast and effective algorithm below, invented by Melissa O'Neill. + There is no POSIX random() in MSVC, and rand() is awful. For portability, we + cannot rely on a library function for random numbers. Instead we use the + fast and effective algorithm below, invented by Melissa O'Neill. + */ -// *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / www.pcg-random.org -// Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) -// --private-- Random number generator state. */ +/* + *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / www.pcg-random.org + Licensed under Apache License 2.0 (NO WARRANTY, etc. see website) + --private-- Random number generator state. + */ typedef struct { ui64_t state; /* 64-bit generator state */ ui64_t inc; /* 63-bit sequence id */ } set_rand_t; /* --private-- Initialize the state *gen using seed and seq. seed seeds the -// advancing 64-bit state. seq is a sequence selection constant. */ + advancing 64-bit state. seq is a sequence selection constant. */ static void set_seed(set_rand_t *gen, ui64_t seed, ui64_t seq) { gen->inc = (seq << 1) | 1; gen->state = (seed + gen->inc) * 6364136223846793005ULL + gen->inc; @@ -111,7 +118,7 @@ struct set_node_s { }; /* A set. The application sets env, may use gen with set_rand(), and may read -// allocs and memory. The remaining variables are --private-- . */ + allocs and memory. The remaining variables are --private-- . */ typedef struct set_s { set_node_t *head; /* skiplist head -- no key, just links */ set_node_t *path; /* right[] is path to key from set_found() */ @@ -122,15 +129,15 @@ typedef struct set_s { jmp_buf env; /* setjmp() environment for allocation errors */ #ifdef SET_TRACK size_t allocs; /* number of allocations */ - size_t memory; /* total amount of allocated memory (>= requests) */ + size_t memory; /* total size of allocated memory (>= requests) */ #endif } set_t; /* Memory allocation and deallocation. set_alloc(set, ptr, size) returns a -// pointer to an allocation of size bytes if ptr is NULL, or the previous -// allocation ptr resized to size bytes. set_alloc() will never return NULL. -// set_free(set, ptr) frees an allocation created by set_alloc(). These may be -// used by the application. e.g. if allocation tracking is desired. */ + pointer to an allocation of size bytes if ptr is NULL, or the previous + allocation ptr resized to size bytes. set_alloc() will never return NULL. + set_free(set, ptr) frees an allocation created by set_alloc(). These may be + used by the application. e.g. if allocation tracking is desired. */ #ifdef SET_TRACK /* Track the number of allocations and the total backing memory size. */ # if defined(_WIN32) @@ -148,10 +155,10 @@ typedef struct set_s { # elif defined(__NetBSD__) # include # define SET_ALLOC_SIZE(ptr) malloc_usable_size(ptr) -# else // e.g. OpenBSD +# else /* e.g. OpenBSD */ # define SET_ALLOC_SIZE(ptr) 0 # endif -// With tracking. +/* With tracking. */ static void *set_alloc(set_t *set, void *ptr, size_t size) { size_t had = ptr == NULL ? 0 : SET_ALLOC_SIZE(ptr); void *mem = realloc(ptr, size); @@ -183,9 +190,9 @@ static void set_free(set_t *set, void *ptr) { #endif /* --private-- Grow node's array right[] as needed to be able to hold at least -// want links. If fill is true, assure that the first want links are filled in, -// setting them to set->head if not previously filled in. Otherwise it is -// assumed that the first want links are about to be filled in. */ + want links. If fill is true, assure that the first want links are filled in, + setting them to set->head if not previously filled in. Otherwise it is + assumed that the first want links are about to be filled in. */ static void set_grow(set_t *set, set_node_t *node, int want, int fill) { int i; if (node->size < want) { @@ -224,11 +231,11 @@ static void set_sweep(set_t *set) { } /* Initialize a new set. set->env must be initialized using setjmp() before -// set_start() is called. A longjmp(set->env, ENOMEM) will be used to handle a -// memory allocation failure during any of the operations. (See setjmp.h and -// errno.h.) The set can still be used if this happens, assuming that it didn't -// happen during set_start(). Whether set_start() completed or not, set_end() -// can be used to free the set's memory after a longjmp(). */ + set_start() is called. A longjmp(set->env, ENOMEM) will be used to handle a + memory allocation failure during any of the operations. (See setjmp.h and + errno.h.) The set can still be used if this happens, assuming that it didn't + happen during set_start(). Whether set_start() completed or not, set_end() + can be used to free the set's memory after a longjmp(). */ SKIPSET_EXPORT void set_start(set_t *set) { #ifdef SET_TRACK set->allocs = 0; @@ -237,7 +244,7 @@ SKIPSET_EXPORT void set_start(set_t *set) { set->head = set->path = set->node = NULL; /* in case set_node() fails */ set->path = set_node(set); set->head = set_node(set); - set_grow(set, set->head, 1, 1); /* one link back to head for an empty set */ + set_grow(set, set->head, 1, 1); /* one link back to head for empty set */ *(unsigned char *)&set->head->key = 137; /* set id */ set->depth = 0; set_uniq(&set->gen, set); @@ -245,7 +252,7 @@ SKIPSET_EXPORT void set_start(set_t *set) { } /* Return true if *set appears to be in a usable state. If *set has been zeroed -// out, then set_ok(set) will be false and set_end(set) will be safe. */ + out, then set_ok(set) will be false and set_end(set) will be safe. */ SKIPSET_EXPORT int set_ok(set_t *set) { return set->head != NULL && set->head->right != NULL && @@ -254,7 +261,7 @@ SKIPSET_EXPORT int set_ok(set_t *set) { #if 0 /* not used in minizip */ /* Empty the set. This frees the memory used for the previous set contents. -// After set_clear(), *set is ready for use, as if after a set_start(). */ + After set_clear(), *set is ready for use, as if after a set_start(). */ SKIPSET_EXPORT void set_clear(set_t *set) { assert(set_ok(set) && "improper use"); @@ -262,7 +269,7 @@ SKIPSET_EXPORT void set_clear(set_t *set) { set_sweep(set); /* Leave the head and path allocations as is. Clear their contents, with - // head pointing to itself and setting depth to zero, for an empty set. */ + head pointing to itself and setting depth to zero, for an empty set. */ set->head->right[0] = set->head; set->head->fill = 1; set->path->fill = 0; @@ -271,9 +278,9 @@ SKIPSET_EXPORT void set_clear(set_t *set) { #endif /* Done using the set -- free all allocations. The only operation on *set -// permitted after this is set_start(). Though another set_end() would do no -// harm. This can be done at any time after a set_start(), or after a longjmp() -// on any allocation failure, including during a set_start(). */ + permitted after this is set_start(). Though another set_end() would do no + harm. This can be done at any time after a set_start(), or after a longjmp() + on any allocation failure, including during a set_start(). */ SKIPSET_EXPORT void set_end(set_t *set) { if (set->head != NULL) { /* Empty the set and free the head node. */ @@ -300,13 +307,13 @@ SKIPSET_EXPORT void set_end(set_t *set) { } /* Look for key. Return 1 if found or 0 if not. This also puts the path to get -// there in set->path, for use by set_insert(). */ + there in set->path, for use by set_insert(). */ SKIPSET_EXPORT int set_found(set_t *set, set_key_t key) { set_node_t *head, *here; int i; assert(set_ok(set) && "improper use"); - /* Start at depth and work down and right as determined by key comparisons. */ + /* Start at depth. Work down and right as determined by key comparisons. */ head = set->head; here = head; i = set->depth; @@ -323,7 +330,7 @@ SKIPSET_EXPORT int set_found(set_t *set, set_key_t key) { return here != head && set_cmp(here->key, key) == 0; } -/* Insert the key key. Return 0 on success, or 1 if key is already in the set. */ +/* Insert the key key. Return 0 on success, or 1 if it's already in the set. */ SKIPSET_EXPORT int set_insert(set_t *set, set_key_t key) { int level = 0; int bit; @@ -335,7 +342,7 @@ SKIPSET_EXPORT int set_insert(set_t *set, set_key_t key) { return 1; /* Randomly generate a new level-- level 0 with probability 1/2, 1 with - // probability 1/4, 2 with probability 1/8, etc. */ + probability 1/4, 2 with probability 1/8, etc. */ for (;;) { if (set->ran == 1) /* Ran out. Get another 32 random bits. */ @@ -356,7 +363,7 @@ SKIPSET_EXPORT int set_insert(set_t *set, set_key_t key) { } /* Make a new node for the provided key, and insert it in the lists up to - // and including level. */ + and including level. */ set->node = set_node(set); set->node->key = key; set_grow(set, set->node, level + 1, 0); -- cgit v1.2.3-55-g6feb