Spain, at least in the south, had plenty of indoor accommodations, even in small towns, though not traditional “hostels”, although some were called “hostals”. Good guide books will list them.