/*
 * Configurable ps-like program.
 * Useful utility routines.
 *
 * Copyright (c) 2014 David I. Bell
 * Permission is granted to use, distribute, or modify this source,
 * provided that this copyright notice remains intact.
 */

#include <pwd.h>
#include <grp.h>
#include <sys/stat.h>
#include <dirent.h>

#include "ips.h"


/*
 * Definitions for collecting and looking up user names, group names,
 * and device names.
 */
#define	DEVICE_DIR	"/dev"		/* path of device directory */
#define	DEVICE_NULL	"/dev/null"	/* the null device name */
#define	MAX_DEV_PATH_LEN 512		/* maximum size of device path */
#define	MAX_NAME_LEN	16		/* length of user or group name */
#define	MAX_DEV_LEN	32		/* max length of saved device name */
#define	MAX_DEV_DEPTH	3		/* max depth of /dev name collection */
#define	USERNAME_ALLOC	1000		/* reallocation size for user names */
#define	GROUPNAME_ALLOC	1000		/* reallocation size for group names */
#define	DEVNAME_ALLOC	1000		/* reallocation size for device names */


/*
 * Structure holding login or group names corresponding to numeric ids.
 */
typedef	struct
{
	union
	{
		uid_t	uid;
		gid_t	gid;
	}	id;				/* user or group id */

	char	name[MAX_NAME_LEN + 2];		/* user or group name */
} NAME;


/*
 * Structure to hold information about devices.
 * This is only used for character devices.
 */
typedef	struct
{
	dev_t	id;			/* device id */
	dev_t	dev;			/* dev device is on */
	ino_t	inode;			/* inode device is on */
	char	name[MAX_DEV_LEN + 2];	/* name of device */
} DEVICE;


/*
 * Table of user names.
 */
static	int		userNameCount;
static	int		userNameAvail;
static	NAME *		userNameTable;


/*
 * Table of group names.
 */
static	int		groupNameCount;
static	int		groupNameAvail;
static	NAME *		groupNameTable;


/*
 * Table of device names.
 */
static	BOOL		devNameCollected;
static	int		devNameCount;
static	int		devNameAvail;
static	DEVICE *	devNameTable;


/*
 * Definitions for allocation of temporary string values.
 * These buffers are linked together, and freed all at once.
 */
#define	TEMPSTR_ALLOC_SIZE	(1024 * 16)
#define	TEMPSTR_MAX_SIZE	512


typedef	struct	TEMPSTR	TEMPSTR;

struct	TEMPSTR	
{
	TEMPSTR *	next;
	char		buf[TEMPSTR_ALLOC_SIZE];
};


/*
 * Amount of space left in the most recently allocated buffer.
 */
static	int	tempStrAvail;


/*
 * Linked list of string buffers.
 * Only the first one in the list has space for new allocation.
 */
static	TEMPSTR *	tempStrList;


/*
 * Definitions for shared hashed strings which are individually allocated and
 * freed.  These strings are used for holding environment variable strings
 * since they are very large and many processes would share the same strings.
 * They are linked into hash tables for quick lookup.
 */
#define	SHARED_HASH_SIZE	101
#define	SHARED_MAGIC		749712759


typedef	struct	SHARED_STR	SHARED_STR;

struct	SHARED_STR
{
	long		magic;		/* magic number */
	int		tableIndex;	/* index into table of the entry */
	int		count;		/* reference counter */
	int		len;		/* length of string */
	SHARED_STR *	next;		/* next string in list */
	char		buf[4];		/* string buffer (variable sized) */
};


static	SHARED_STR *	sharedTable[SHARED_HASH_SIZE];


static	SHARED_STR	dummySharedStr;


/*
 * Local routines.
 */
static	void	DeviceNameRecursion(char *, int, int);


/*
 * Allocate a shared string holding the specified text of the given length.
 * If the string is already in the shared string table, then it is found and
 * its use count is simply incremented.  Otherwise a new string is inserted.
 * The terminating NULL character is not included in the supplied length.
 * Returns NULL if the string could not be allocated.
 */
char *
AllocateSharedString(const char * str, int len)
{
	int		begCh;
	int		midCh;
	int		endCh;
	int		tableIndex;
	SHARED_STR *	entry;

	if (len < 0)
		return NULL;

	if (len == 0)
		return emptyString;

	if ((len == 1) && (*str == '/'))
		return rootString;

	/*
	 * Get the first, middle, and last characters for comparison.
	 */
	begCh = str[0];
	midCh = str[len / 2];
	endCh = str[len - 1];

	/*
	 * Hash the characters along with the string length to select
	 * an offset into the hash table to use for this string.
	 */
	tableIndex = len + (begCh << 16) + (midCh << 20) + (endCh << 24);
	tableIndex = ((unsigned int) tableIndex) % SHARED_HASH_SIZE;

	/*
	 * Search the selected string list in the table for the string.
	 * Test the string length and the first, middle, and last characters.
	 * If they all match then compare the whole string explicitly.
	 */
	for (entry = sharedTable[tableIndex]; entry; entry = entry->next)
	{
		if ((entry->len != len) || (entry->buf[0] != begCh))
			continue;

		if (entry->buf[len / 2] != midCh)
			continue;

		if (entry->buf[len - 1] != endCh)
			continue;

		if (memcmp(entry->buf, str, len) != 0)
			continue;

		/*
		 * The string was found.
		 * Increment the use counter and return it.
		 */
		entry->count++;

		return entry->buf;
	}

	/*
	 * The string is not in the table, so we have to allocate a new one
	 * and link it in at the front of the appropriate shared table list.
	 * Note: the buffer in the structure has room for the terminating NULL.
	 */
	entry = (SHARED_STR *) malloc(sizeof(SHARED_STR) + len);

	if (entry == NULL)
		return NULL;

	entry->next = sharedTable[tableIndex];
	sharedTable[tableIndex] = entry;

	entry->magic = SHARED_MAGIC;
	entry->tableIndex = tableIndex;
	entry->count = 1;
	entry->len = len;

	memcpy(entry->buf, str, len);

	entry->buf[len] = '\0';

	return entry->buf;
}


/*
 * Free a string that had been allocated as a shared string.
 * This just decrements the usage count, and if it goes to zero,
 * then frees the string.
 */
void
FreeSharedString(char * str)
{
	SHARED_STR *	entry;
	SHARED_STR *	prev;
	int		tableIndex;

	if ((str == NULL) || (str == emptyString) || (str == rootString))
		return;

	/*
	 * Back up to the entry header of the string and make sure that it
	 * looks reasonable.  Calculate the offset to back up by using a
	 * dummy instance of the structure.
	 */
	char * beg = (char *) &dummySharedStr;
	char * end = (char *) &dummySharedStr.buf;

	entry = (SHARED_STR *) (str - (end - beg));

	tableIndex = entry->tableIndex;

	if ((entry->magic != SHARED_MAGIC) || (tableIndex < 0) ||
		(tableIndex >= SHARED_HASH_SIZE) || (entry->len < 0))
	{
		fprintf(stderr, "Freeing bad shared string header\n");

		exit(1);
	}

	/*
	 * Decrement the use counter, and if it is still positive,
	 * then the string is still in use.
	 */
	entry->count--;

	if (entry->count > 0)
		return;

	/*
	 * The string needs freeing.
	 * See if it is the first string in the hash table.
	 * If so, then removing it is easy.
	 */
	prev = sharedTable[tableIndex];

	if (prev == entry)
	{
		sharedTable[tableIndex] = entry->next;

		free((char *) entry);

		return;
	}

	/*
	 * We have to search the list for it.
	 * It is a fatal error if the string is not found.
	 */
	while (prev)
	{
		if (prev->next != entry)
		{
			prev = prev->next;

			continue;
		}

		prev->next = entry->next;

		free((char *) entry);

		return;
	}

	fprintf(stderr, "Freeing unknown shared string\n");
	exit(1);
}


/*
 * Allocate a string which can later be freed along with all other such
 * allocated strings.  The string cannot be individually freed.
 * To avoid wastage, there is a maximum size that can be allocated.
 * Prints an error message and exits on failure.
 */
char *
AllocTempString(int len)
{
	TEMPSTR *	head;
	char *		cp;

	if ((len <= 0) || (len > TEMPSTR_MAX_SIZE))
	{
		fprintf(stderr, "Allocating bad length %d\n", len);

		exit(1);
	}

	if (len > tempStrAvail)
	{
		head = (TEMPSTR *) AllocMemory(sizeof(TEMPSTR));

		head->next = tempStrList;
		tempStrList = head;

		tempStrAvail = TEMPSTR_ALLOC_SIZE;
	}

	cp = &tempStrList->buf[TEMPSTR_ALLOC_SIZE - tempStrAvail];
	tempStrAvail -= len;

	return cp;
}


/*
 * Copy a null-terminated string into a temporary string.
 * The new string cannot be individually freed.
 * Prints an error message and exits on failure.
 */
char *
CopyTempString(const char * oldcp)
{
	char *	cp;
	int	len;

	len = strlen(oldcp) + 1;

	cp = AllocTempString(len);

	memcpy(cp, oldcp, len);

	return cp;
}


/*
 * Free all temporary strings.
 */
void
FreeTempStrings(void)
{
	TEMPSTR *	head;

	while (tempStrList)
	{
		head = tempStrList;
		tempStrList = head->next;

		free((char *) head);
	}

	tempStrAvail = 0;
}


/*
 * Allocate a buffer using malloc while complaining and exiting if the
 * allocation fails.  The array should eventually be freed using free(3).
 */
void *
AllocMemory(int len)
{
	void *	buffer;

	buffer = (void *) malloc(len);

	if (buffer == NULL)
	{
		fprintf(stderr, "Failed to allocate %d bytes\n", len);

		exit(1);
	}

	return buffer;
}


/*
 * Reallocate a buffer using realloc while complaining and exiting if the
 * allocation fails.  The array should eventually be freed using free(3).
 */
void *
ReallocMemory(void * oldBuffer, int len)
{
	char *	buffer;

	buffer = (void *) realloc(oldBuffer, len);

	if (buffer == NULL)
	{
		fprintf(stderr, "Failed to reallocate %d bytes\n", len);

		exit(1);
	}

	return buffer;
}


/*
 * Copy a null-terminated string value into a newly allocated string.
 * This does not return if the allocation fails.
 */
char *
CopyString(const char * str)
{
	char *	newStr;
	int	len;

	len = strlen(str) + 1;

	newStr = (char *) AllocMemory(len);

	memcpy(newStr, str, len);

	return newStr;
}


/*
 * Replace a string value by freeing it and replacing it with a
 * newly allocated value or NULL.
 */
void
ReplaceString(char ** variable, const char * newValue)
{
	free(*variable);

	*variable = NULL;

	if (newValue)
		*variable = CopyString(newValue);
}


/*
 * Replace null characters in the specified memory buffer with spaces
 * and replace other unprintable characters with question marks.
 */
void
MakePrintable(char * cp, int len)
{
	int	ch;

	while (len-- > 0)
	{
		ch = *cp;

		if (ch == '\0')
			*cp = ' ';
		else if ((ch < ' ') || (ch >= 0x7f))
			*cp = '?';

		cp++;
	}
}


/*
 * Routine to see if a text string is matched by a wildcard pattern.
 * Returns TRUE if the text is matched, or FALSE if it is not matched
 * or if the pattern is invalid.
 *  *		matches zero or more characters
 *  ?		matches a single character
 *  [abc]	matches 'a', 'b' or 'c'
 *  \c		quotes character c
 *  Adapted from code written by Ingo Wilken.
 */
BOOL
PatternMatch(const char * text, const char * pattern)
{
	const char *	retryPat;
	const char *	retryTxt;
	int		ch;
	BOOL		isFound;

	retryPat = NULL;
	retryTxt = NULL;

	while (*text || *pattern)
	{
		ch = *pattern++;

		switch (ch)
		{
			case '*':  
				retryPat = pattern;
				retryTxt = text;
				break;

			case '[':  
				isFound = FALSE;

				while ((ch = *pattern++) != ']')
				{
					if (ch == '\\')
						ch = *pattern++;

					if (ch == '\0')
						return FALSE;

					if (*text == ch)
						isFound = TRUE;
				}

				if (!isFound)
				{
					pattern = retryPat;
					text = ++retryTxt;
				}

				/*
				 * Fall into next case
				 */

			case '?':  
				if (*text++ == '\0')
					return FALSE;

				break;

			case '\\':  
				ch = *pattern++;

				if (ch == '\0')
					return FALSE;

				/*
				 * Fall into next case
				 */

			default:        
				if (*text == ch)
				{
					if (*text)
						text++;

					break;
				}

				if (*text)
				{
					pattern = retryPat;
					text = ++retryTxt;
					break;
				}

				return FALSE;
		}

		if (pattern == NULL)
			return FALSE;
	}

	return TRUE;
}


/*
 * Collect all of the user names in the system.
 * This is only done once per run.
 */
void
CollectUserNames(void)
{
	const struct passwd *	pwd;
	NAME *			name;

	if (userNameCount > 0)
		return;

	while ((pwd = getpwent()) != NULL)
	{
		if (userNameCount >= userNameAvail)
		{
			userNameAvail += USERNAME_ALLOC;

			userNameTable = (NAME *) realloc(userNameTable,
				(userNameAvail * sizeof(NAME)));

			if (userNameTable == NULL)
			{
				fprintf(stderr, "Cannot allocate memory\n");
				exit(1);
			}
		}

		name = &userNameTable[userNameCount++];

		name->id.uid = pwd->pw_uid;
		strncpy(name->name, pwd->pw_name, MAX_NAME_LEN);
		name->name[MAX_NAME_LEN] = '\0';
	}

	endpwent();
}


/*
 * Find the user name for the specified user id.
 * Returns NULL if the user name is not known.
 */
const char *
FindUserName(uid_t uid)
{
	const NAME *	user;
	int		count;

	user = userNameTable;
	count = userNameCount;

	while (count-- > 0)
	{
		if (user->id.uid == uid)
			return user->name;

		user++;
	}

	return NULL;
}


/*
 * Find the user id associated with a user name.
 * Returns BAD_UID if the user name is not known.
 */
uid_t
FindUserId(const char * name)
{
	const NAME *	user;
	int		count;

	user = userNameTable;
	count = userNameCount;

	while (count-- > 0)
	{
		if (strcmp(user->name, name) == 0)
			return user->id.uid;

		user++;
	}

	return BAD_UID;
}


/*
 * Collect all of the group names in the system.
 * This is only done once per run.
 */
void
CollectGroupNames(void)
{
	const struct group *	grp;
	NAME *			name;

	if (groupNameCount > 0)
		return;

	while ((grp = getgrent()) != NULL)
	{
		if (groupNameCount >= groupNameAvail)
		{
			groupNameAvail += GROUPNAME_ALLOC;

			groupNameTable = (NAME *) realloc(groupNameTable,
				(groupNameAvail * sizeof(NAME)));

			if (groupNameTable == NULL)
			{
				fprintf(stderr, "Cannot allocate memory\n");
				exit(1);
			}
		}

		name = &groupNameTable[groupNameCount++];

		name->id.gid = grp->gr_gid;
		strncpy(name->name, grp->gr_name, MAX_NAME_LEN);
		name->name[MAX_NAME_LEN] = '\0';
	}

	endgrent();
}


/*
 * Find the group name for the specified group id.
 * Returns NULL if the group name is not known.
 */
const char *
FindGroupName(gid_t gid)
{
	const NAME *	group;
	int		count;

	group = groupNameTable;
	count = groupNameCount;

	while (count-- > 0)
	{
		if (group->id.gid == gid)
			return group->name;

		group++;
	}

	return NULL;
}


/*
 * Find the group id associated with a group name.
 * Returns BAD_GID if the group name is not known.
 */
gid_t
FindGroupId(const char * name)
{
	const NAME *	group;
	int		count;

	group = groupNameTable;
	count = groupNameCount;

	while (count-- > 0)
	{
		if (strcmp(group->name, name) == 0)
			return group->id.gid;

		group++;
	}

	return BAD_GID;
}


/*
 * Collect all device names that might be terminals or other
 * character devices.  This is done only once per run.
 */
void
CollectDeviceNames(void)
{
	char	pathBuffer[MAX_DEV_PATH_LEN + 2];

	if (devNameCollected)
		return;

	strcpy(pathBuffer, DEVICE_DIR);

	DeviceNameRecursion(pathBuffer, strlen(pathBuffer), MAX_DEV_DEPTH);

	devNameCollected = TRUE;
}


/*
 * Recursive routine to scan the /dev directory structure collecting
 * useful device information.
 */
static void
DeviceNameRecursion(char * pathBuffer, int usedLength, int maxDepth)
{
	DIR *			dir;
	const struct dirent *	dp;
	DEVICE *		device;
	int			len;
	struct stat		statBuf;

	if (maxDepth <= 0)
		return;

	/*
	 * Open the directory and scan its entries.
	 */
	dir = opendir(pathBuffer);

	if (dir == NULL)
		return;

	while ((dp = readdir(dir)) != NULL)
	{
		/*
		 * Make sure that the buffer is large enough for the
		 * full new path.
		 */
		len = strlen(dp->d_name);

		if (usedLength + len >= MAX_DEV_PATH_LEN)
			break;

		/*
		 * Ignore the . and .. entries.
		 */
		if ((len == 1) && (dp->d_name[0] == '.'))
			continue;

		if ((len == 2) && (dp->d_name[0] == '.') &&
			(dp->d_name[1] == '.'))
		{
			continue;
		}

		/*
		 * Build the full path and get its status.
		 */
		pathBuffer[usedLength] = '/';
		strcpy(pathBuffer + usedLength + 1, dp->d_name);

		if (lstat(pathBuffer, &statBuf) < 0)
			continue;

		/*
		 * If this is another directory level then walk down it
		 * too if the depth isn't exceeded.
		 */
		if (S_ISDIR(statBuf.st_mode))
		{
			DeviceNameRecursion(pathBuffer, usedLength + len + 1,
				maxDepth - 1);

			continue;
		}

		/*
		 * If this isn't a character device then ignore it
		 * since it can't be a terminal.
		 */
		if (!S_ISCHR(statBuf.st_mode))
			continue;

		/*
		 * Look for /dev/null for other uses.
		 */
		if (strcmp(pathBuffer, DEVICE_NULL) == 0)
		{
			nullDevice = statBuf.st_dev;
			nullInode = statBuf.st_ino;
		}

		/*
		 * We want to store the device name.
		 * Reallocate the table if necessary.
		 */
		if (devNameCount >= devNameAvail)
		{
			devNameAvail += DEVNAME_ALLOC;

			devNameTable = (DEVICE *) realloc(devNameTable,
				(devNameAvail * sizeof(DEVICE)));

			if (devNameTable == NULL)
			{
				fprintf(stderr, "Cannot allocate memory\n");
				exit(1);
			}
		}

		/*
		 * Store the device information, including its path
		 * beyond the /dev prefix.
		 */
		device = &devNameTable[devNameCount++];

		device->id = statBuf.st_rdev;
		device->dev = statBuf.st_dev;
		device->inode = statBuf.st_ino;

		strncpy(device->name, pathBuffer + sizeof(DEVICE_DIR),
			MAX_DEV_LEN);

		device->name[MAX_DEV_LEN] = '\0';
	}

	closedir(dir);
}


/*
 * Find the device name for the specified device id.
 * Returns NULL if the device name is not known.
 */
const char *
FindDeviceName(dev_t devid)
{
	const DEVICE *	device;
	int		count;

	if (devid <= 0)
		return "-";

	device = devNameTable;
	count = devNameCount;

	while (count-- > 0)
	{
		if (device->id == devid)
			return device->name;

		device++;
	}

	return NULL;
}


/*
 * Find the device name for a device and inode pair.
 * These arguments are for the inode which contains the device.
 */
const char *
FindDeviceFromInode(dev_t dev, ino_t inode)
{
	const DEVICE *	device;
	int		count;

	device = devNameTable;
	count = devNameCount;

	while (count-- > 0)
	{
		if ((device->dev == dev) && (device->inode == inode))
			return device->name;

		device++;
	}

	return NULL;
}


/*
 * Parse a decimal number from a string and return it's value.
 * The supplied string pointer is updated past the number read.
 * Leading spaces or tabs are ignored.
 * An invalid character stops the parse.
 */
long
GetDecimalNumber(const char ** cpp)
{
	long	value;
	BOOL	isNeg;
	const char *	cp;

	cp = *cpp;

	isNeg = FALSE;

	while (isBlank(*cp))
		cp++;

	if (*cp == '-')
	{
		isNeg = TRUE;
		cp++;
	}

	value = 0;

	while (isDigit(*cp))
		value = value * 10 + *cp++ - '0';

	if (isNeg)
		value = -value;

	*cpp = cp;

	return value;
}


/*
 * Parse a floating point number from a string and return it's value.
 * The supplied string pointer is updated past the number read.
 * Leading spaces or tabs are ignored.
 * An invalid character stops the parse.
 */
double
GetFloatingNumber(const char ** cpp)
{
	double	value;
	double	scale;
	BOOL	isNeg;
	const char *	cp;

	cp = *cpp;

	isNeg = FALSE;

	while (isBlank(*cp))
		cp++;

	if (*cp == '-')
	{
		isNeg = TRUE;
		cp++;
	}

	value = 0.0;
	scale = 1.0;

	while (isDigit(*cp))
		value = value * 10 + *cp++ - '0';

	if (*cp == '.')
		cp++;

	while (isDigit(*cp))
	{
		value = value * 10.0 + *cp++ - '0';
		scale *= 10.0;
	}

	value /= scale;

	if (isNeg)
		value = -value;

	*cpp = cp;

	return value;
}


/*
 * Calculate the elapsed time in milliseconds between two timevals.
 * The new timeval can be NULL in which case the current time is used.
 * If the time appears to go backwards or if the old time is zero
 * then a value of 0 is returned.
 */
long
ElapsedMilliSeconds(const struct timeval * oldTime,
	const struct timeval * newTime)
{
	long		elapsedSeconds;
	long		elapsedMicroSeconds;
	struct	timeval	currentTime;

	/*
	 * Assume no elapsed time if the old time is zero.
	 */
	if (oldTime->tv_sec == 0)
		return 0;

	/*
	 * If no new time is given then get it now.
	 */
	if (newTime == NULL)
	{
		GetTimeOfDay(&currentTime);
		newTime = &currentTime;
	}

	elapsedSeconds = newTime->tv_sec - oldTime->tv_sec;
	elapsedMicroSeconds = newTime->tv_usec - oldTime->tv_usec;

	if (elapsedMicroSeconds < 0)
	{
		elapsedMicroSeconds += 1000000;
		elapsedSeconds--;
	}

	if (elapsedSeconds < 0)
		return 0;

 	return (elapsedSeconds * 1000) + (elapsedMicroSeconds / 1000);
}


/*
 * Get the current time of day, checking whether it fails.
 */
void
GetTimeOfDay(struct timeval * retTimeVal)
{
	if (gettimeofday(retTimeVal, NULL) == 0)
		return;

	fprintf(stderr, "Cannot get time of day\n");

	exit(1);
}

/* END CODE */