Finding free numbers in a range, crudely, with Unix tools

November 18, 2014

Suppose, not entirely hypothetically, that you have the zone file for the reverse mapping of a single /24 subnet (in Bind format) and you want to find a free IP address in that subnet. The first field in the zone file is the last octet of the IP (ie for '127.0.0.1' it is '1'), so this problem reduces to finding what numbers are not used in the file out of the range 1 to 254.

So let's do this really crudely with readily available Unix tools:

grep '^[0-9]' ptrzone | awk '{print $1}' | sort >/tmp/used
seq 1 254 | sort >/tmp/all
comm -13 /tmp/used /tmp/all | sort -n

(We must do a 'sort -n' only at the end because of a stupid GNU comm decision.)

We can get rid of one of the two files here by piping directly into comm, but unfortunately we can't get rid of both of them in standard Bourne shell. In Bash and zsh (and AT&T ksh), we can use what they each call 'process substitution' to directly embed each pipeline into the comm arguments:

comm -13 <(grep '^[0-9]' ptrzone | awk '{print $1}' | sort) <(seq 1 254 | sort) | sort -n

(This also works in rc, with a different syntax.)

Once upon a time I would have happily written the single-line version. These days my tendencies are towards the multi-line version unless I'm feeling excessively clever, partly because it's easier to check the intermediate steps.

(A neater version would condense runs of numbers into ranges, but I don't think you can do that simply with any existing common Unix tools. Perl experts can maybe do it in a single line.)

PS: One hazard of a very well stuffed $HOME/bin directory is that it turns out I already had a command to do this for me (and with the neater range-based output). Oh well, such things happen. Perhaps I should thin out my $HOME/bin on the grounds of disuse of much of it, but it's always hard to get rid of your personal little scripts.


Comments on this page:

By Edward Berner at 2014-11-19 01:56:51:

This was interesting to think about while waiting for some patches to install.

Here's an awk version:

cat foo | awk '{a[$1]=1} END {for(i=1;i<=254;i++) if (a[i]==0) print i}'

And a python one-liner based on a set difference:

cat foo | python -c 'import sys;print "\n".join(map(str,sorted(set(range(1,255) )-set([int(x.split()[0]) for x in sys.stdin]) ) ) )'

(I did the Python mostly because I was curious whether it could be done. Apparently it can, but it's not very pretty.)

-- Edward

By Ewen McNeill at 2014-11-19 05:13:04:

It's not really a one-liner, because it's more than 80 characters, but a random attempt in perl, which does give range lists:

perl -mSet::IntSpan -le'$a=Set::IntSpan->new(map{s/\s.*$//;$_}<>);$d=$a->X("1-254");print Set::IntSpan::run_list($d);'

using Set::IntSpan (libset-intspan-perl on Debian-ish systems; apparently written to do the .newsrc thing). Based on hints found here, which has an evil regex version. (It could be noticably shorter without having to say Set::IntSpan::... repeatedly.)

Eg, given:

1
2
3

will return 4-254.

Ewen

PS: This seems to be functionally equivalent, but even less readable:

perl -mSet::IntSpan -le'print Set::IntSpan::run_list(Set::IntSpan->new(map{s/\s.*$//;$_}<>)->X("1-254"));'

(but still not much shorter due to the Set::IntSpan repetition.

By Ewen McNeill at 2014-11-19 05:20:51:

Aha! You can call run_list() as a object method, so it's possible to make it a bit shorter:

perl -mSet::IntSpan -le'print Set::IntSpan->new(map{s/\s.*$//;$_}<>)->X("1-254")->run_list();'

but I'm running out of ideas to get it under 80 characters...

Ewen

Another idea:

   seq 0 255 | grep -vx -f <(awk '/^[0-9]/{print $1}')

I have two bin directories in my $HOME. One is under version control and contains all the scripts. The other is not version end, and that's where I dump the occasional open source program I built from scratch.

Anyway, since I keep the scripts in mercurial, I don't mind deleting defunct scripts because I can always resurrect them if need be.

Christian almost beat me to the solution I had in mind, except I’d write it the other way around and without awk:

   egrep -o '^[0-9]+' ptrzone | grep -vxf- <(seq 1 254)
By dozzie at 2014-11-20 08:02:18:

OK, so my solution:

grep -Eo '^[0-9]+' ptrzone | sort -n | awk '
  NR == 1 && $1 == 2       {print 1}
  NR == 1 && $1 >  2       {printf "%d..%d\n", 1, $1 - 1}
  NR > 1 && prev + 2 == $1 {print prev + 1}
  NR > 1 && prev + 2 <  $1 {printf "%d..%d\n", prev + 1, $1 - 1}
  {prev = $1}
  END {if (prev < 254) printf "%d..%d\n", prev, 254}
'
Written on 18 November 2014.
« Why I need a browser that's willing to accept bad TLS certificates
Sometimes the way to solve a problem is to rethink the problem »

Page tools: View Source, View Normal, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Tue Nov 18 23:26:13 2014
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.