From 9ae7f13f17e3d04d3ba88862299c8e42541eab47 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Tue, 18 Jun 2019 10:30:08 +0200 Subject: Introducing GNUNET_Uuid and matching hash map for 128 bit values. TNG: reducing size of AcknowledgementUUIDPs from 256 bits to 128 bits. --- src/util/Makefile.am | 1 + src/util/common_logging.c | 393 +++++++------- src/util/container_multiuuidmap.c | 1015 +++++++++++++++++++++++++++++++++++++ 3 files changed, 1192 insertions(+), 217 deletions(-) create mode 100644 src/util/container_multiuuidmap.c (limited to 'src/util') diff --git a/src/util/Makefile.am b/src/util/Makefile.am index 8a99197f8..fe5cc6e72 100644 --- a/src/util/Makefile.am +++ b/src/util/Makefile.am @@ -78,6 +78,7 @@ libgnunetutil_la_SOURCES = \ container_meta_data.c \ container_multihashmap.c \ container_multishortmap.c \ + container_multiuuidmap.c \ container_multipeermap.c \ container_multihashmap32.c \ crypto_symmetric.c \ diff --git a/src/util/common_logging.c b/src/util/common_logging.c index 5052134f8..b5678e5be 100644 --- a/src/util/common_logging.c +++ b/src/util/common_logging.c @@ -107,7 +107,8 @@ static __thread struct GNUNET_AsyncScopeSave current_async_scope; * Note that this message maybe truncated to the first BULK_TRACK_SIZE * characters, in which case it is NOT 0-terminated! */ -static GNUNET_THREAD_LOCAL char last_bulk[BULK_TRACK_SIZE] __attribute__ ((nonstring)); +static GNUNET_THREAD_LOCAL char last_bulk[BULK_TRACK_SIZE] + __attribute__ ((nonstring)); /** * Type of the last bulk message. @@ -211,7 +212,7 @@ struct LogDef }; -#if !defined(GNUNET_CULL_LOGGING) +#if ! defined(GNUNET_CULL_LOGGING) /** * Dynamic array of logging definitions */ @@ -263,17 +264,17 @@ get_type (const char *log) { if (NULL == log) return GNUNET_ERROR_TYPE_UNSPECIFIED; - if (0 == strcasecmp (log, _("DEBUG"))) + if (0 == strcasecmp (log, _ ("DEBUG"))) return GNUNET_ERROR_TYPE_DEBUG; - if (0 == strcasecmp (log, _("INFO"))) + if (0 == strcasecmp (log, _ ("INFO"))) return GNUNET_ERROR_TYPE_INFO; - if (0 == strcasecmp (log, _("MESSAGE"))) + if (0 == strcasecmp (log, _ ("MESSAGE"))) return GNUNET_ERROR_TYPE_MESSAGE; - if (0 == strcasecmp (log, _("WARNING"))) + if (0 == strcasecmp (log, _ ("WARNING"))) return GNUNET_ERROR_TYPE_WARNING; - if (0 == strcasecmp (log, _("ERROR"))) + if (0 == strcasecmp (log, _ ("ERROR"))) return GNUNET_ERROR_TYPE_ERROR; - if (0 == strcasecmp (log, _("NONE"))) + if (0 == strcasecmp (log, _ ("NONE"))) return GNUNET_ERROR_TYPE_NONE; return GNUNET_ERROR_TYPE_INVALID; } @@ -292,7 +293,7 @@ GNUNET_abort_ () } -#if !defined(GNUNET_CULL_LOGGING) +#if ! defined(GNUNET_CULL_LOGGING) /** * Utility function - reallocates logdefs array to be twice as large. */ @@ -353,7 +354,7 @@ setup_log_file (const struct tm *tm) if (0 == strftime (fn, sizeof (fn), log_file_name, tm)) return GNUNET_SYSERR; leftsquare = strrchr (fn, '['); - if ( (NULL != leftsquare) && (']' == leftsquare[1]) ) + if ((NULL != leftsquare) && (']' == leftsquare[1])) { char *logfile_copy = GNUNET_strdup (fn); @@ -371,8 +372,7 @@ setup_log_file (const struct tm *tm) return GNUNET_OK; /* no change */ log_rotate (last_fn); strcpy (last_fn, fn); - if (GNUNET_SYSERR == - GNUNET_DISK_directory_create_for_file (fn)) + if (GNUNET_SYSERR == GNUNET_DISK_directory_create_for_file (fn)) { fprintf (stderr, "Failed to create directory for `%s': %s\n", @@ -381,14 +381,12 @@ setup_log_file (const struct tm *tm) return GNUNET_SYSERR; } #if WINDOWS - altlog_fd = OPEN (fn, O_APPEND | - O_BINARY | - O_WRONLY | O_CREAT, - _S_IREAD | _S_IWRITE); + altlog_fd = + OPEN (fn, O_APPEND | O_BINARY | O_WRONLY | O_CREAT, _S_IREAD | _S_IWRITE); #else - altlog_fd = OPEN (fn, O_APPEND | - O_WRONLY | O_CREAT, - S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH); + altlog_fd = OPEN (fn, + O_APPEND | O_WRONLY | O_CREAT, + S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH); #endif if (-1 != altlog_fd) { @@ -512,7 +510,7 @@ GNUNET_get_log_call_status (int caller_level, /* We have no definitions to override globally configured log level, * so just use it right away. */ - if ( (min_level >= 0) && (GNUNET_NO == gnunet_force_log_present) ) + if ((min_level >= 0) && (GNUNET_NO == gnunet_force_log_present)) return caller_level <= min_level; /* Only look for forced definitions? */ @@ -520,7 +518,7 @@ GNUNET_get_log_call_status (int caller_level, for (i = 0; i < logdefs_len; i++) { ld = &logdefs[i]; - if (( (!force_only) || ld->force) && + if (((! force_only) || ld->force) && (line >= ld->from_line && line <= ld->to_line) && (0 == regexec (&ld->component_regex, comp, 0, NULL, 0)) && (0 == regexec (&ld->file_regex, file, 0, NULL, 0)) && @@ -591,73 +589,79 @@ parse_definitions (const char *constname, int force) { switch (p[0]) { - case ';': /* found a field separator */ + case ';': /* found a field separator */ p[0] = '\0'; switch (state) { - case 0: /* within a component name */ + case 0: /* within a component name */ comp = start; break; - case 1: /* within a file name */ + case 1: /* within a file name */ file = start; break; - case 2: /* within a function name */ + case 2: /* within a function name */ /* after a file name there must be a function name */ function = start; break; - case 3: /* within a from-to line range */ + case 3: /* within a from-to line range */ if (strlen (start) > 0) { errno = 0; from_line = strtol (start, &t, 10); - if ( (0 != errno) || (from_line < 0) ) + if ((0 != errno) || (from_line < 0)) { GNUNET_free (def); return counter; } - if ( (t < p) && ('-' == t[0]) ) + if ((t < p) && ('-' == t[0])) { errno = 0; start = t + 1; to_line = strtol (start, &t, 10); - if ( (0 != errno) || (to_line < 0) || (t != p) ) + if ((0 != errno) || (to_line < 0) || (t != p)) { GNUNET_free (def); return counter; } } - else /* one number means "match this line only" */ + else /* one number means "match this line only" */ to_line = from_line; } - else /* default to 0-max */ + else /* default to 0-max */ { from_line = 0; to_line = INT_MAX; } break; default: - fprintf(stderr, - _("ERROR: Unable to parse log definition: Syntax error at `%s'.\n"), - p); + fprintf ( + stderr, + _ ("ERROR: Unable to parse log definition: Syntax error at `%s'.\n"), + p); break; } start = p + 1; state++; break; - case '\0': /* found EOL */ + case '\0': /* found EOL */ keep_looking = 0; /* fall through to '/' */ - case '/': /* found a definition separator */ + case '/': /* found a definition separator */ switch (state) { - case 4: /* within a log level */ + case 4: /* within a log level */ p[0] = '\0'; state = 0; level = get_type ((const char *) start); - if ( (GNUNET_ERROR_TYPE_INVALID == level) || - (GNUNET_ERROR_TYPE_UNSPECIFIED == level) || - (0 != add_definition (comp, file, function, from_line, to_line, - level, force)) ) + if ((GNUNET_ERROR_TYPE_INVALID == level) || + (GNUNET_ERROR_TYPE_UNSPECIFIED == level) || + (0 != add_definition (comp, + file, + function, + from_line, + to_line, + level, + force))) { GNUNET_free (def); return counter; @@ -666,9 +670,10 @@ parse_definitions (const char *constname, int force) start = p + 1; break; default: - fprintf(stderr, - _("ERROR: Unable to parse log definition: Syntax error at `%s'.\n"), - p); + fprintf ( + stderr, + _ ("ERROR: Unable to parse log definition: Syntax error at `%s'.\n"), + p); break; } default: @@ -688,7 +693,7 @@ parse_all_definitions () { if (GNUNET_NO == gnunet_force_log_parsed) gnunet_force_log_present = - parse_definitions ("GNUNET_FORCE_LOG", 1) > 0 ? GNUNET_YES : GNUNET_NO; + parse_definitions ("GNUNET_FORCE_LOG", 1) > 0 ? GNUNET_YES : GNUNET_NO; gnunet_force_log_parsed = GNUNET_YES; if (GNUNET_NO == gnunet_log_parsed) @@ -707,14 +712,12 @@ parse_all_definitions () * @return #GNUNET_OK on success */ int -GNUNET_log_setup (const char *comp, - const char *loglevel, - const char *logfile) +GNUNET_log_setup (const char *comp, const char *loglevel, const char *logfile) { const char *env_logfile; min_level = get_type (loglevel); -#if !defined(GNUNET_CULL_LOGGING) +#if ! defined(GNUNET_CULL_LOGGING) parse_all_definitions (); #endif #ifdef WINDOWS @@ -761,8 +764,7 @@ GNUNET_log_setup (const char *comp, * @param logger_cls closure for @a logger */ void -GNUNET_logger_add (GNUNET_Logger logger, - void *logger_cls) +GNUNET_logger_add (GNUNET_Logger logger, void *logger_cls) { struct CustomLogger *entry; @@ -781,8 +783,7 @@ GNUNET_logger_add (GNUNET_Logger logger, * @param logger_cls closure for @a logger */ void -GNUNET_logger_remove (GNUNET_Logger logger, - void *logger_cls) +GNUNET_logger_remove (GNUNET_Logger logger, void *logger_cls) { struct CustomLogger *pos; struct CustomLogger *prev; @@ -828,8 +829,7 @@ output_message (enum GNUNET_ErrorType kind, EnterCriticalSection (&output_message_cs); #endif /* only use the standard logger if no custom loggers are present */ - if ( (NULL != GNUNET_stderr) && - (NULL == loggers) ) + if ((NULL != GNUNET_stderr) && (NULL == loggers)) { if (kind == GNUNET_ERROR_TYPE_MESSAGE) { @@ -841,9 +841,7 @@ output_message (enum GNUNET_ErrorType kind, * this way if the output is going to logfiles or robots * instead. */ - FPRINTF (GNUNET_stderr, - "* %s", - msg); + FPRINTF (GNUNET_stderr, "* %s", msg); } else if (GNUNET_YES == current_async_scope.have_scope) { @@ -881,11 +879,7 @@ output_message (enum GNUNET_ErrorType kind, pos = loggers; while (NULL != pos) { - pos->logger (pos->logger_cls, - kind, - comp, - datestr, - msg); + pos->logger (pos->logger_cls, kind, comp, datestr, msg); pos = pos->next; } #if WINDOWS @@ -907,8 +901,7 @@ flush_bulk (const char *datestr) char *last; const char *ft; - if ( (0 == last_bulk_time.abs_value_us) || - (0 == last_bulk_repeat) ) + if ((0 == last_bulk_time.abs_value_us) || (0 == last_bulk_repeat)) return; rev = 0; last = memchr (last_bulk, '\0', BULK_TRACK_SIZE); @@ -921,11 +914,17 @@ flush_bulk (const char *datestr) rev = 1; last[0] = '\0'; } - ft = GNUNET_STRINGS_relative_time_to_string (GNUNET_TIME_absolute_get_duration - (last_bulk_time), GNUNET_YES); - snprintf (msg, sizeof (msg), - _("Message `%.*s' repeated %u times in the last %s\n"), - BULK_TRACK_SIZE, last_bulk, last_bulk_repeat, ft); + ft = + GNUNET_STRINGS_relative_time_to_string (GNUNET_TIME_absolute_get_duration ( + last_bulk_time), + GNUNET_YES); + snprintf (msg, + sizeof (msg), + _ ("Message `%.*s' repeated %u times in the last %s\n"), + BULK_TRACK_SIZE, + last_bulk, + last_bulk_repeat, + ft); if (rev == 1) last[0] = '\n'; output_message (last_bulk_kind, last_bulk_comp, datestr, msg); @@ -941,8 +940,7 @@ flush_bulk (const char *datestr) * @param check_reset #GNUNET_YES to assert that the log skip counter is currently zero */ void -GNUNET_log_skip (int n, - int check_reset) +GNUNET_log_skip (int n, int check_reset) { int ok; @@ -993,15 +991,10 @@ mylog (enum GNUNET_ErrorType kind, va_list vacp; va_copy (vacp, va); - size = VSNPRINTF (NULL, - 0, - message, - vacp) + 1; + size = VSNPRINTF (NULL, 0, message, vacp) + 1; GNUNET_assert (0 != size); va_end (vacp); - memset (date, - 0, - DATE_STR_SIZE); + memset (date, 0, DATE_STR_SIZE); { char buf[size]; long long offset; @@ -1022,24 +1015,19 @@ mylog (enum GNUNET_ErrorType kind, else { if (0 == - strftime (date2, - DATE_STR_SIZE, - "%b %d %H:%M:%S-%%020llu", - tmptr)) - abort (); - if (0 > - snprintf (date, - sizeof (date), - date2, - (long long) (pc.QuadPart / - (performance_frequency.QuadPart / 1000)))) - abort (); + strftime (date2, DATE_STR_SIZE, "%b %d %H:%M:%S-%%020llu", tmptr)) + abort (); + if (0 > snprintf (date, + sizeof (date), + date2, + (long long) (pc.QuadPart / + (performance_frequency.QuadPart / 1000)))) + abort (); } #else struct timeval timeofday; - gettimeofday (&timeofday, - NULL); + gettimeofday (&timeofday, NULL); offset = GNUNET_TIME_get_offset (); if (offset > 0) { @@ -1047,80 +1035,59 @@ mylog (enum GNUNET_ErrorType kind, timeofday.tv_usec += (offset % 1000LL) * 1000LL; if (timeofday.tv_usec > 1000000LL) { - timeofday.tv_usec -= 1000000LL; - timeofday.tv_sec++; + timeofday.tv_usec -= 1000000LL; + timeofday.tv_sec++; } } else { timeofday.tv_sec += offset / 1000LL; - if (timeofday.tv_usec > - (offset % 1000LL) * 1000LL) + if (timeofday.tv_usec > -(offset % 1000LL) * 1000LL) { - timeofday.tv_usec += (offset % 1000LL) * 1000LL; + timeofday.tv_usec += (offset % 1000LL) * 1000LL; } else { - timeofday.tv_usec += 1000000LL + (offset % 1000LL) * 1000LL; - timeofday.tv_sec--; + timeofday.tv_usec += 1000000LL + (offset % 1000LL) * 1000LL; + timeofday.tv_sec--; } } tmptr = localtime (&timeofday.tv_sec); if (NULL == tmptr) { - strcpy (date, - "localtime error"); + strcpy (date, "localtime error"); } else { - if (0 == - strftime (date2, - DATE_STR_SIZE, - "%b %d %H:%M:%S-%%06u", - tmptr)) - abort (); - if (0 > - snprintf (date, - sizeof (date), - date2, - timeofday.tv_usec)) - abort (); + if (0 == strftime (date2, DATE_STR_SIZE, "%b %d %H:%M:%S-%%06u", tmptr)) + abort (); + if (0 > snprintf (date, sizeof (date), date2, timeofday.tv_usec)) + abort (); } #endif - VSNPRINTF (buf, - size, - message, - va); + VSNPRINTF (buf, size, message, va); #if ! (defined(GNUNET_CULL_LOGGING) || TALER_WALLET_ONLY) if (NULL != tmptr) (void) setup_log_file (tmptr); #endif if ((0 != (kind & GNUNET_ERROR_TYPE_BULK)) && (0 != last_bulk_time.abs_value_us) && - (0 == strncmp (buf, - last_bulk, - sizeof (last_bulk)))) + (0 == strncmp (buf, last_bulk, sizeof (last_bulk)))) { last_bulk_repeat++; - if ( (GNUNET_TIME_absolute_get_duration (last_bulk_time).rel_value_us > - BULK_DELAY_THRESHOLD) || - (last_bulk_repeat > BULK_REPEAT_THRESHOLD) ) + if ((GNUNET_TIME_absolute_get_duration (last_bulk_time).rel_value_us > + BULK_DELAY_THRESHOLD) || + (last_bulk_repeat > BULK_REPEAT_THRESHOLD)) flush_bulk (date); return; } flush_bulk (date); - strncpy (last_bulk, - buf, - sizeof (last_bulk)); + strncpy (last_bulk, buf, sizeof (last_bulk)); last_bulk_repeat = 0; last_bulk_kind = kind; last_bulk_time = GNUNET_TIME_absolute_get (); - strncpy (last_bulk_comp, - comp, - COMP_TRACK_SIZE); - output_message (kind, - comp, - date, - buf); + strncpy (last_bulk_comp, comp, COMP_TRACK_SIZE); + output_message (kind, comp, date, buf); } } @@ -1133,8 +1100,7 @@ mylog (enum GNUNET_ErrorType kind, * @param ... arguments for format string */ void -GNUNET_log_nocheck (enum GNUNET_ErrorType kind, - const char *message, ...) +GNUNET_log_nocheck (enum GNUNET_ErrorType kind, const char *message, ...) { va_list va; @@ -1154,8 +1120,10 @@ GNUNET_log_nocheck (enum GNUNET_ErrorType kind, * @param ... arguments for format string */ void -GNUNET_log_from_nocheck (enum GNUNET_ErrorType kind, const char *comp, - const char *message, ...) +GNUNET_log_from_nocheck (enum GNUNET_ErrorType kind, + const char *comp, + const char *message, + ...) { va_list va; char comp_w_pid[128]; @@ -1180,18 +1148,18 @@ const char * GNUNET_error_type_to_string (enum GNUNET_ErrorType kind) { if ((kind & GNUNET_ERROR_TYPE_ERROR) > 0) - return _("ERROR"); + return _ ("ERROR"); if ((kind & GNUNET_ERROR_TYPE_WARNING) > 0) - return _("WARNING"); + return _ ("WARNING"); if ((kind & GNUNET_ERROR_TYPE_MESSAGE) > 0) - return _("MESSAGE"); + return _ ("MESSAGE"); if ((kind & GNUNET_ERROR_TYPE_INFO) > 0) - return _("INFO"); + return _ ("INFO"); if ((kind & GNUNET_ERROR_TYPE_DEBUG) > 0) - return _("DEBUG"); + return _ ("DEBUG"); if ((kind & ~GNUNET_ERROR_TYPE_BULK) == 0) - return _("NONE"); - return _("INVALID"); + return _ ("NONE"); + return _ ("INVALID"); } @@ -1202,7 +1170,7 @@ GNUNET_error_type_to_string (enum GNUNET_ErrorType kind) * @return string form; will be overwritten by next call to GNUNET_h2s. */ const char * -GNUNET_h2s (const struct GNUNET_HashCode * hc) +GNUNET_h2s (const struct GNUNET_HashCode *hc) { static GNUNET_THREAD_LOCAL struct GNUNET_CRYPTO_HashAsciiEncoded ret; @@ -1223,7 +1191,7 @@ GNUNET_h2s (const struct GNUNET_HashCode * hc) * @return string form; will be overwritten by next call to GNUNET_h2s. */ const char * -GNUNET_h2s2 (const struct GNUNET_HashCode * hc) +GNUNET_h2s2 (const struct GNUNET_HashCode *hc) { static struct GNUNET_CRYPTO_HashAsciiEncoded ret; @@ -1248,11 +1216,8 @@ GNUNET_p2s (const struct GNUNET_CRYPTO_EddsaPublicKey *p) static struct GNUNET_CRYPTO_HashAsciiEncoded ret; struct GNUNET_HashCode hc; - GNUNET_CRYPTO_hash (p, - sizeof (*p), - &hc); - GNUNET_CRYPTO_hash_to_enc (&hc, - &ret); + GNUNET_CRYPTO_hash (p, sizeof (*p), &hc); + GNUNET_CRYPTO_hash_to_enc (&hc, &ret); ret.encoding[6] = '\0'; return (const char *) ret.encoding; } @@ -1273,11 +1238,8 @@ GNUNET_p2s2 (const struct GNUNET_CRYPTO_EddsaPublicKey *p) static struct GNUNET_CRYPTO_HashAsciiEncoded ret; struct GNUNET_HashCode hc; - GNUNET_CRYPTO_hash (p, - sizeof (*p), - &hc); - GNUNET_CRYPTO_hash_to_enc (&hc, - &ret); + GNUNET_CRYPTO_hash (p, sizeof (*p), &hc); + GNUNET_CRYPTO_hash_to_enc (&hc, &ret); ret.encoding[6] = '\0'; return (const char *) ret.encoding; } @@ -1298,11 +1260,8 @@ GNUNET_e2s (const struct GNUNET_CRYPTO_EcdhePublicKey *p) static struct GNUNET_CRYPTO_HashAsciiEncoded ret; struct GNUNET_HashCode hc; - GNUNET_CRYPTO_hash (p, - sizeof (*p), - &hc); - GNUNET_CRYPTO_hash_to_enc (&hc, - &ret); + GNUNET_CRYPTO_hash (p, sizeof (*p), &hc); + GNUNET_CRYPTO_hash_to_enc (&hc, &ret); ret.encoding[6] = '\0'; return (const char *) ret.encoding; } @@ -1323,11 +1282,8 @@ GNUNET_e2s2 (const struct GNUNET_CRYPTO_EcdhePublicKey *p) static struct GNUNET_CRYPTO_HashAsciiEncoded ret; struct GNUNET_HashCode hc; - GNUNET_CRYPTO_hash (p, - sizeof (*p), - &hc); - GNUNET_CRYPTO_hash_to_enc (&hc, - &ret); + GNUNET_CRYPTO_hash (p, sizeof (*p), &hc); + GNUNET_CRYPTO_hash_to_enc (&hc, &ret); ret.encoding[6] = '\0'; return (const char *) ret.encoding; } @@ -1347,10 +1303,27 @@ GNUNET_sh2s (const struct GNUNET_ShortHashCode *shc) { static char buf[64]; - GNUNET_STRINGS_data_to_string (shc, - sizeof (*shc), - buf, - sizeof (buf)); + GNUNET_STRINGS_data_to_string (shc, sizeof (*shc), buf, sizeof (buf)); + buf[6] = '\0'; + return (const char *) buf; +} + + +/** + * @ingroup logging + * Convert a UUID to a string (for printing debug messages). + * This is one of the very few calls in the entire API that is + * NOT reentrant! + * + * @param uuid the UUID + * @return string + */ +const char * +GNUNET_uuid2s (const struct GNUNET_Uuid *uuid) +{ + static char buf[32]; + + GNUNET_STRINGS_data_to_string (uuid, sizeof (*uuid), buf, sizeof (buf)); buf[6] = '\0'; return (const char *) buf; } @@ -1365,7 +1338,7 @@ GNUNET_sh2s (const struct GNUNET_ShortHashCode *shc) * @return string form; will be overwritten by next call to GNUNET_h2s_full. */ const char * -GNUNET_h2s_full (const struct GNUNET_HashCode * hc) +GNUNET_h2s_full (const struct GNUNET_HashCode *hc) { static struct GNUNET_CRYPTO_HashAsciiEncoded ret; @@ -1391,9 +1364,7 @@ GNUNET_i2s (const struct GNUNET_PeerIdentity *pid) if (NULL == pid) return "NULL"; ret = GNUNET_CRYPTO_eddsa_public_key_to_string (&pid->public_key); - strncpy (buf, - ret, - sizeof (buf) - 1); + strncpy (buf, ret, sizeof (buf) - 1); GNUNET_free (ret); buf[4] = '\0'; return buf; @@ -1419,9 +1390,7 @@ GNUNET_i2s2 (const struct GNUNET_PeerIdentity *pid) if (NULL == pid) return "NULL"; ret = GNUNET_CRYPTO_eddsa_public_key_to_string (&pid->public_key); - strncpy (buf, - ret, - sizeof (buf) - 1); + strncpy (buf, ret, sizeof (buf) - 1); GNUNET_free (ret); buf[4] = '\0'; return buf; @@ -1459,12 +1428,12 @@ GNUNET_i2s_full (const struct GNUNET_PeerIdentity *pid) * will be overwritten by next call to #GNUNET_a2s. */ const char * -GNUNET_a2s (const struct sockaddr *addr, - socklen_t addrlen) +GNUNET_a2s (const struct sockaddr *addr, socklen_t addrlen) { #ifndef WINDOWS -#define LEN GNUNET_MAX ((INET6_ADDRSTRLEN + 8), \ - (1 + sizeof (struct sockaddr_un) - sizeof (sa_family_t))) +#define LEN \ + GNUNET_MAX ((INET6_ADDRSTRLEN + 8), \ + (1 + sizeof (struct sockaddr_un) - sizeof (sa_family_t))) #else #define LEN (INET6_ADDRSTRLEN + 8) #endif @@ -1477,24 +1446,18 @@ GNUNET_a2s (const struct sockaddr *addr, unsigned int off; if (addr == NULL) - return _("unknown address"); + return _ ("unknown address"); switch (addr->sa_family) { case AF_INET: if (addrlen != sizeof (struct sockaddr_in)) return ""; v4 = (const struct sockaddr_in *) addr; - inet_ntop (AF_INET, - &v4->sin_addr, - buf, - INET_ADDRSTRLEN); + inet_ntop (AF_INET, &v4->sin_addr, buf, INET_ADDRSTRLEN); if (0 == ntohs (v4->sin_port)) return buf; strcat (buf, ":"); - GNUNET_snprintf (b2, - sizeof (b2), - "%u", - ntohs (v4->sin_port)); + GNUNET_snprintf (b2, sizeof (b2), "%u", ntohs (v4->sin_port)); strcat (buf, b2); return buf; case AF_INET6: @@ -1502,19 +1465,12 @@ GNUNET_a2s (const struct sockaddr *addr, return ""; v6 = (const struct sockaddr_in6 *) addr; buf[0] = '['; - inet_ntop (AF_INET6, - &v6->sin6_addr, - &buf[1], - INET6_ADDRSTRLEN); + inet_ntop (AF_INET6, &v6->sin6_addr, &buf[1], INET6_ADDRSTRLEN); if (0 == ntohs (v6->sin6_port)) return &buf[1]; strcat (buf, "]:"); - GNUNET_snprintf (b2, - sizeof (b2), - "%u", - ntohs (v6->sin6_port)); - strcat (buf, - b2); + GNUNET_snprintf (b2, sizeof (b2), "%u", ntohs (v6->sin6_port)); + strcat (buf, b2); return buf; case AF_UNIX: if (addrlen <= sizeof (sa_family_t)) @@ -1532,7 +1488,7 @@ GNUNET_a2s (const struct sockaddr *addr, &un->sun_path[off]); return buf; default: - return _("invalid address"); + return _ ("invalid address"); } } @@ -1546,13 +1502,14 @@ GNUNET_a2s (const struct sockaddr *addr, */ void GNUNET_log_config_missing (enum GNUNET_ErrorType kind, - const char *section, - const char *option) + const char *section, + const char *option) { GNUNET_log (kind, - _("Configuration fails to specify option `%s' in section `%s'!\n"), - option, - section); + _ ( + "Configuration fails to specify option `%s' in section `%s'!\n"), + option, + section); } @@ -1566,13 +1523,17 @@ GNUNET_log_config_missing (enum GNUNET_ErrorType kind, */ void GNUNET_log_config_invalid (enum GNUNET_ErrorType kind, - const char *section, - const char *option, - const char *required) + const char *section, + const char *option, + const char *required) { - GNUNET_log (kind, - _("Configuration specifies invalid value for option `%s' in section `%s': %s\n"), - option, section, required); + GNUNET_log ( + kind, + _ ( + "Configuration specifies invalid value for option `%s' in section `%s': %s\n"), + option, + section, + required); } @@ -1633,15 +1594,14 @@ GNUNET_async_scope_get (struct GNUNET_AsyncScopeSave *scope_ret) /** * Initializer */ -void __attribute__ ((constructor)) -GNUNET_util_cl_init () +void __attribute__ ((constructor)) GNUNET_util_cl_init () { GNUNET_stderr = stderr; #ifdef MINGW GNInitWinEnv (NULL); #endif #if WINDOWS - if (!InitializeCriticalSectionAndSpinCount (&output_message_cs, 0x00000400)) + if (! InitializeCriticalSectionAndSpinCount (&output_message_cs, 0x00000400)) GNUNET_abort_ (); #endif } @@ -1650,8 +1610,7 @@ GNUNET_util_cl_init () /** * Destructor */ -void __attribute__ ((destructor)) -GNUNET_util_cl_fini () +void __attribute__ ((destructor)) GNUNET_util_cl_fini () { #if WINDOWS DeleteCriticalSection (&output_message_cs); diff --git a/src/util/container_multiuuidmap.c b/src/util/container_multiuuidmap.c new file mode 100644 index 000000000..49eb64cfe --- /dev/null +++ b/src/util/container_multiuuidmap.c @@ -0,0 +1,1015 @@ +/* + This file is part of GNUnet. + Copyright (C) 2008, 2012 GNUnet e.V. + + GNUnet is free software: you can redistribute it and/or modify it + under the terms of the GNU Affero General Public License as published + by the Free Software Foundation, either version 3 of the License, + or (at your option) any later version. + + GNUnet is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Affero General Public License for more details. + + You should have received a copy of the GNU Affero General Public License + along with this program. If not, see . + + SPDX-License-Identifier: AGPL3.0-or-later +*/ +/** + * @file util/container_multiuuidmap.c + * @brief hash map for UUIDs where the same key may be present multiple times + * @author Christian Grothoff + */ + +#include "platform.h" +#include "gnunet_util_lib.h" + +#define LOG(kind, ...) \ + GNUNET_log_from (kind, "util-container-multiuuidmap", __VA_ARGS__) + +/** + * Maximum recursion depth for callbacks of + * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s + * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). + * Should be totally excessive, but if violated we die. + */ +#define NEXT_CACHE_SIZE 16 + + +/** + * An entry in the hash map with the full key. + */ +struct BigMapEntry +{ + + /** + * Value of the entry. + */ + void *value; + + /** + * If there is a hash collision, we create a linked list. + */ + struct BigMapEntry *next; + + /** + * Key for the entry. + */ + struct GNUNET_Uuid key; +}; + + +/** + * An entry in the hash map with just a pointer to the key. + */ +struct SmallMapEntry +{ + + /** + * Value of the entry. + */ + void *value; + + /** + * If there is a hash collision, we create a linked list. + */ + struct SmallMapEntry *next; + + /** + * Key for the entry. + */ + const struct GNUNET_Uuid *key; +}; + + +/** + * Entry in the map. + */ +union MapEntry +{ + /** + * Variant used if map entries only contain a pointer to the key. + */ + struct SmallMapEntry *sme; + + /** + * Variant used if map entries contain the full key. + */ + struct BigMapEntry *bme; +}; + + +/** + * Internal representation of the hash map. + */ +struct GNUNET_CONTAINER_MultiUuidmap +{ + /** + * All of our buckets. + */ + union MapEntry *map; + + /** + * Number of entries in the map. + */ + unsigned int size; + + /** + * Length of the "map" array. + */ + unsigned int map_length; + + /** + * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', + * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. + */ + int use_small_entries; + + /** + * Counts the destructive modifications (grow, remove) + * to the map, so that iterators can check if they are still valid. + */ + unsigned int modification_counter; + + /** + * Map entries indicating iteration positions currently + * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). + * Only used up to @e next_cache_off. + */ + union MapEntry next_cache[NEXT_CACHE_SIZE]; + + /** + * Offset of @e next_cache entries in use, must be smaller + * than #NEXT_CACHE_SIZE. + */ + unsigned int next_cache_off; +}; + + +/** + * Cursor into a multiuuidmap. + * Allows to enumerate elements asynchronously. + */ +struct GNUNET_CONTAINER_MultiUuidmapIterator +{ + /** + * Position in the bucket 'idx' + */ + union MapEntry me; + + /** + * Current bucket index. + */ + unsigned int idx; + + /** + * Modification counter as observed on the map when the iterator + * was created. + */ + unsigned int modification_counter; + + /** + * Map that we are iterating over. + */ + const struct GNUNET_CONTAINER_MultiUuidmap *map; +}; + + +/** + * Create a multi hash map. + * + * @param len initial size (map will grow as needed) + * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; + * #GNUNET_YES means that on 'put', the 'key' does not have + * to be copied as the destination of the pointer is + * guaranteed to be life as long as the value is stored in + * the hashmap. This can significantly reduce memory + * consumption, but of course is also a recipie for + * heap corruption if the assumption is not true. Only + * use this if (1) memory use is important in this case and + * (2) you have triple-checked that the invariant holds + * @return NULL on error + */ +struct GNUNET_CONTAINER_MultiUuidmap * +GNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys) +{ + struct GNUNET_CONTAINER_MultiUuidmap *map; + + GNUNET_assert (len > 0); + map = GNUNET_new (struct GNUNET_CONTAINER_MultiUuidmap); + map->map = GNUNET_malloc_large (len * sizeof (union MapEntry)); + if (NULL == map->map) + { + GNUNET_free (map); + return NULL; + } + map->map_length = len; + map->use_small_entries = do_not_copy_keys; + return map; +} + + +/** + * Destroy a hash map. Will not free any values + * stored in the hash map! + * + * @param map the map + */ +void +GNUNET_CONTAINER_multiuuidmap_destroy ( + struct GNUNET_CONTAINER_MultiUuidmap *map) +{ + GNUNET_assert (0 == map->next_cache_off); + for (unsigned int i = 0; i < map->map_length; i++) + { + union MapEntry me; + + me = map->map[i]; + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + struct SmallMapEntry *nxt; + + nxt = me.sme; + while (NULL != (sme = nxt)) + { + nxt = sme->next; + GNUNET_free (sme); + } + me.sme = NULL; + } + else + { + struct BigMapEntry *bme; + struct BigMapEntry *nxt; + + nxt = me.bme; + while (NULL != (bme = nxt)) + { + nxt = bme->next; + GNUNET_free (bme); + } + me.bme = NULL; + } + } + GNUNET_free (map->map); + GNUNET_free (map); +} + + +/** + * Compute the index of the bucket for the given key. + * + * @param map hash map for which to compute the index + * @param key what key should the index be computed for + * @return offset into the "map" array of "map" + */ +static unsigned int +idx_of (const struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key) +{ + unsigned int kx; + + GNUNET_assert (NULL != map); + GNUNET_memcpy (&kx, key, sizeof (kx)); + return kx % map->map_length; +} + + +/** + * Get the number of key-value pairs in the map. + * + * @param map the map + * @return the number of key value pairs + */ +unsigned int +GNUNET_CONTAINER_multiuuidmap_size ( + const struct GNUNET_CONTAINER_MultiUuidmap *map) +{ + return map->size; +} + + +/** + * Given a key find a value in the map matching the key. + * + * @param map the map + * @param key what to look for + * @return NULL if no value was found; note that + * this is indistinguishable from values that just + * happen to be NULL; use "contains" to test for + * key-value pairs with value NULL + */ +void * +GNUNET_CONTAINER_multiuuidmap_get ( + const struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key) +{ + union MapEntry me; + + me = map->map[idx_of (map, key)]; + if (map->use_small_entries) + { + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == GNUNET_memcmp (key, sme->key)) + return sme->value; + } + else + { + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == GNUNET_memcmp (key, &bme->key)) + return bme->value; + } + return NULL; +} + + +/** + * Iterate over all entries in the map. + * + * @param map the map + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration + */ +int +GNUNET_CONTAINER_multiuuidmap_iterate ( + struct GNUNET_CONTAINER_MultiUuidmap *map, + GNUNET_CONTAINER_MultiUuidmapIterator it, + void *it_cls) +{ + int count; + union MapEntry me; + union MapEntry *ce; + struct GNUNET_Uuid kc; + + count = 0; + GNUNET_assert (NULL != map); + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); + for (unsigned int i = 0; i < map->map_length; i++) + { + me = map->map[i]; + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) + { + ce->sme = sme->next; + if ((NULL != it) && (GNUNET_OK != it (it_cls, sme->key, sme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return GNUNET_SYSERR; + } + count++; + } + } + else + { + struct BigMapEntry *bme; + + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) + { + ce->bme = bme->next; + if (NULL != it) + { + kc = bme->key; + if (GNUNET_OK != it (it_cls, &kc, bme->value)) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return GNUNET_SYSERR; + } + } + count++; + } + } + } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return count; +} + + +/** + * We are about to free() the @a bme, make sure it is not in + * the list of next values for any iterator in the @a map's next_cache. + * + * @param map the map to check + * @param bme the entry that is about to be free'd + */ +static void +update_next_cache_bme (struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct BigMapEntry *bme) +{ + for (unsigned int i = 0; i < map->next_cache_off; i++) + if (map->next_cache[i].bme == bme) + map->next_cache[i].bme = bme->next; +} + + +/** + * We are about to free() the @a sme, make sure it is not in + * the list of next values for any iterator in the @a map's next_cache. + * + * @param map the map to check + * @param sme the entry that is about to be free'd + */ +static void +update_next_cache_sme (struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct SmallMapEntry *sme) +{ + for (unsigned int i = 0; i < map->next_cache_off; i++) + if (map->next_cache[i].sme == sme) + map->next_cache[i].sme = sme->next; +} + + +/** + * Remove the given key-value pair from the map. Note that if the + * key-value pair is in the map multiple times, only one of the pairs + * will be removed. + * + * @param map the map + * @param key key of the key-value pair + * @param value value of the key-value pair + * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair + * is not in the map + */ +int +GNUNET_CONTAINER_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key, + const void *value) +{ + union MapEntry me; + unsigned int i; + + map->modification_counter++; + i = idx_of (map, key); + me = map->map[i]; + if (map->use_small_entries) + { + struct SmallMapEntry *p = NULL; + + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + { + if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value)) + { + if (NULL == p) + map->map[i].sme = sme->next; + else + p->next = sme->next; + update_next_cache_sme (map, sme); + GNUNET_free (sme); + map->size--; + return GNUNET_YES; + } + p = sme; + } + } + else + { + struct BigMapEntry *p = NULL; + + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + { + if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value)) + { + if (NULL == p) + map->map[i].bme = bme->next; + else + p->next = bme->next; + update_next_cache_bme (map, bme); + GNUNET_free (bme); + map->size--; + return GNUNET_YES; + } + p = bme; + } + } + return GNUNET_NO; +} + + +/** + * Remove all entries for the given key from the map. + * Note that the values would not be "freed". + * + * @param map the map + * @param key identifies values to be removed + * @return number of values removed + */ +int +GNUNET_CONTAINER_multiuuidmap_remove_all ( + struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key) +{ + union MapEntry me; + unsigned int i; + int ret; + + map->modification_counter++; + + ret = 0; + i = idx_of (map, key); + me = map->map[i]; + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + struct SmallMapEntry *p; + + p = NULL; + sme = me.sme; + while (NULL != sme) + { + if (0 == GNUNET_memcmp (key, sme->key)) + { + if (NULL == p) + map->map[i].sme = sme->next; + else + p->next = sme->next; + update_next_cache_sme (map, sme); + GNUNET_free (sme); + map->size--; + if (NULL == p) + sme = map->map[i].sme; + else + sme = p->next; + ret++; + } + else + { + p = sme; + sme = sme->next; + } + } + } + else + { + struct BigMapEntry *bme; + struct BigMapEntry *p; + + p = NULL; + bme = me.bme; + while (NULL != bme) + { + if (0 == GNUNET_memcmp (key, &bme->key)) + { + if (NULL == p) + map->map[i].bme = bme->next; + else + p->next = bme->next; + update_next_cache_bme (map, bme); + GNUNET_free (bme); + map->size--; + if (NULL == p) + bme = map->map[i].bme; + else + bme = p->next; + ret++; + } + else + { + p = bme; + bme = bme->next; + } + } + } + return ret; +} + + +/** + * Check if the map contains any value under the given + * key (including values that are NULL). + * + * @param map the map + * @param key the key to test if a value exists for it + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multiuuidmap_contains ( + const struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key) +{ + union MapEntry me; + + me = map->map[idx_of (map, key)]; + if (map->use_small_entries) + { + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == GNUNET_memcmp (key, sme->key)) + return GNUNET_YES; + } + else + { + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == GNUNET_memcmp (key, &bme->key)) + return GNUNET_YES; + } + return GNUNET_NO; +} + + +/** + * Check if the map contains the given value under the given + * key. + * + * @param map the map + * @param key the key to test if a value exists for it + * @param value value to test for + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not + */ +int +GNUNET_CONTAINER_multiuuidmap_contains_value ( + const struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key, + const void *value) +{ + union MapEntry me; + + me = map->map[idx_of (map, key)]; + if (map->use_small_entries) + { + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value)) + return GNUNET_YES; + } + else + { + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value)) + return GNUNET_YES; + } + return GNUNET_NO; +} + + +/** + * Grow the given map to a more appropriate size. + * + * @param map the hash map to grow + */ +static void +grow (struct GNUNET_CONTAINER_MultiUuidmap *map) +{ + union MapEntry *old_map; + union MapEntry *new_map; + unsigned int old_len; + unsigned int new_len; + unsigned int idx; + + old_map = map->map; + old_len = map->map_length; + new_len = old_len * 2; + if (0 == new_len) /* 2^31 * 2 == 0 */ + new_len = old_len; /* never use 0 */ + if (new_len == old_len) + return; /* nothing changed */ + new_map = GNUNET_malloc_large (new_len * sizeof (union MapEntry)); + if (NULL == new_map) + return; /* grow not possible */ + map->modification_counter++; + map->map_length = new_len; + map->map = new_map; + for (unsigned int i = 0; i < old_len; i++) + { + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + + while (NULL != (sme = old_map[i].sme)) + { + old_map[i].sme = sme->next; + idx = idx_of (map, sme->key); + sme->next = new_map[idx].sme; + new_map[idx].sme = sme; + } + } + else + { + struct BigMapEntry *bme; + + while (NULL != (bme = old_map[i].bme)) + { + old_map[i].bme = bme->next; + idx = idx_of (map, &bme->key); + bme->next = new_map[idx].bme; + new_map[idx].bme = bme; + } + } + } + GNUNET_free (old_map); +} + + +/** + * Store a key-value pair in the map. + * + * @param map the map + * @param key key to use + * @param value value to use + * @param opt options for put + * @return #GNUNET_OK on success, + * #GNUNET_NO if a value was replaced (with REPLACE) + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the + * value already exists + */ +int +GNUNET_CONTAINER_multiuuidmap_put (struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key, + void *value, + enum GNUNET_CONTAINER_MultiHashMapOption opt) +{ + union MapEntry me; + unsigned int i; + + i = idx_of (map, key); + if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && + (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) + { + me = map->map[i]; + if (map->use_small_entries) + { + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == GNUNET_memcmp (key, sme->key)) + { + if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) + return GNUNET_SYSERR; + sme->value = value; + return GNUNET_NO; + } + } + else + { + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == GNUNET_memcmp (key, &bme->key)) + { + if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) + return GNUNET_SYSERR; + bme->value = value; + return GNUNET_NO; + } + } + } + if (map->size / 3 >= map->map_length / 4) + { + grow (map); + i = idx_of (map, key); + } + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + + sme = GNUNET_new (struct SmallMapEntry); + sme->key = key; + sme->value = value; + sme->next = map->map[i].sme; + map->map[i].sme = sme; + } + else + { + struct BigMapEntry *bme; + + bme = GNUNET_new (struct BigMapEntry); + bme->key = *key; + bme->value = value; + bme->next = map->map[i].bme; + map->map[i].bme = bme; + } + map->size++; + return GNUNET_OK; +} + + +/** + * Iterate over all entries in the map that match a particular key. + * + * @param map the map + * @param key key that the entries must correspond to + * @param it function to call on each entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, + * #GNUNET_SYSERR if it aborted iteration + */ +int +GNUNET_CONTAINER_multiuuidmap_get_multiple ( + struct GNUNET_CONTAINER_MultiUuidmap *map, + const struct GNUNET_Uuid *key, + GNUNET_CONTAINER_MultiUuidmapIterator it, + void *it_cls) +{ + int count; + union MapEntry me; + union MapEntry *ce; + + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); + count = 0; + me = map->map[idx_of (map, key)]; + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) + { + ce->sme = sme->next; + if (0 != GNUNET_memcmp (key, sme->key)) + continue; + if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return GNUNET_SYSERR; + } + count++; + } + } + else + { + struct BigMapEntry *bme; + + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) + { + ce->bme = bme->next; + if (0 != GNUNET_memcmp (key, &bme->key)) + continue; + if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return GNUNET_SYSERR; + } + count++; + } + } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return count; +} + + +/** + * @ingroup hashmap + * Call @a it on a random value from the map, or not at all + * if the map is empty. Note that this function has linear + * complexity (in the size of the map). + * + * @param map the map + * @param it function to call on a random entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, zero or one. + */ +unsigned int +GNUNET_CONTAINER_multiuuidmap_get_random ( + const struct GNUNET_CONTAINER_MultiUuidmap *map, + GNUNET_CONTAINER_MultiUuidmapIterator it, + void *it_cls) +{ + unsigned int off; + union MapEntry me; + + if (0 == map->size) + return 0; + if (NULL == it) + return 1; + off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size); + for (unsigned int idx = 0; idx < map->map_length; idx++) + { + me = map->map[idx]; + if (map->use_small_entries) + { + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + { + if (0 == off) + { + if (GNUNET_OK != it (it_cls, sme->key, sme->value)) + return GNUNET_SYSERR; + return 1; + } + off--; + } + } + else + { + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + { + if (0 == off) + { + if (GNUNET_OK != it (it_cls, &bme->key, bme->value)) + return GNUNET_SYSERR; + return 1; + } + off--; + } + } + } + GNUNET_break (0); + return GNUNET_SYSERR; +} + + +/** + * Create an iterator for a multiuuidmap. + * The iterator can be used to retrieve all the elements in the multiuuidmap + * one by one, without having to handle all elements at once (in contrast to + * #GNUNET_CONTAINER_multiuuidmap_iterate). Note that the iterator can not be + * used anymore if elements have been removed from 'map' after the creation of + * the iterator, or 'map' has been destroyed. Adding elements to 'map' may + * result in skipped or repeated elements. + * + * @param map the map to create an iterator for + * @return an iterator over the given multiuuidmap 'map' + */ +struct GNUNET_CONTAINER_MultiUuidmapIterator * +GNUNET_CONTAINER_multiuuidmap_iterator_create ( + const struct GNUNET_CONTAINER_MultiUuidmap *map) +{ + struct GNUNET_CONTAINER_MultiUuidmapIterator *iter; + + iter = GNUNET_new (struct GNUNET_CONTAINER_MultiUuidmapIterator); + iter->map = map; + iter->modification_counter = map->modification_counter; + iter->me = map->map[0]; + return iter; +} + + +/** + * Retrieve the next element from the hash map at the iterator's position. + * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' + * are not modified. + * This operation is only allowed if no elements have been removed from the + * multiuuidmap since the creation of 'iter', and the map has not been destroyed. + * Adding elements may result in repeating or skipping elements. + * + * @param iter the iterator to get the next element from + * @param key pointer to store the key in, can be NULL + * @param value pointer to store the value in, can be NULL + * @return #GNUNET_YES we returned an element, + * #GNUNET_NO if we are out of elements + */ +int +GNUNET_CONTAINER_multiuuidmap_iterator_next ( + struct GNUNET_CONTAINER_MultiUuidmapIterator *iter, + struct GNUNET_Uuid *key, + const void **value) +{ + /* make sure the map has not been modified */ + GNUNET_assert (iter->modification_counter == iter->map->modification_counter); + + /* look for the next entry, skipping empty buckets */ + while (1) + { + if (iter->idx >= iter->map->map_length) + return GNUNET_NO; + if (GNUNET_YES == iter->map->use_small_entries) + { + if (NULL != iter->me.sme) + { + if (NULL != key) + *key = *iter->me.sme->key; + if (NULL != value) + *value = iter->me.sme->value; + iter->me.sme = iter->me.sme->next; + return GNUNET_YES; + } + } + else + { + if (NULL != iter->me.bme) + { + if (NULL != key) + *key = iter->me.bme->key; + if (NULL != value) + *value = iter->me.bme->value; + iter->me.bme = iter->me.bme->next; + return GNUNET_YES; + } + } + iter->idx += 1; + if (iter->idx < iter->map->map_length) + iter->me = iter->map->map[iter->idx]; + } +} + + +/** + * Destroy a multiuuidmap iterator. + * + * @param iter the iterator to destroy + */ +void +GNUNET_CONTAINER_multiuuidmap_iterator_destroy ( + struct GNUNET_CONTAINER_MultiUuidmapIterator *iter) +{ + GNUNET_free (iter); +} + + +/* end of container_multiuuidmap.c */ -- cgit v1.2.3