Skip to content

Instantly share code, notes, and snippets.

@kazuho
Created March 27, 2014 07:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kazuho/9802167 to your computer and use it in GitHub Desktop.
Save kazuho/9802167 to your computer and use it in GitHub Desktop.
static int _log_exists(const char *dir, long long log_index, int *exists)
{
struct stat st;
char fnbuf[PATH_MAX];
snprintf(fnbuf, sizeof(fnbuf), "%s/%lld", dir, log_index);
if (fstat(path, &st) == 0) {
*exists = 1;
} else if (errno == ENOENT) {
*exists = 0;
} else {
fprintf(stderr, ")
return -1;
}
return 0;
}
long long unco_get_next_logindex(const char *dir)
{
long long min, max;
int exists;
// index starts from 1; search using Elias' gamma encoding (i.e. search at 1,2,4,8,16,... and then perform binary search)
for (max = 1; ; max *= 2) {
if (_log_exists(dir, max, &exists) != 0)
goto Error;
if (! exists)
break;
}
// binary search within [min, max)
min = max / 2 + 1;
while (min != max) {
mid = (min + max) / 2;
if (_log_exists(dir, mid, &exists) != 0)
goto Error;
if (exists)
min = mid + 1;
else
max = mid;
}
return min;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment