hash tables

recursion

this is something that programmers deal with on a regular basis when faced with a problem were some set of tasks needs to be performed repeatedly on a set of data as well as that data’s subsets. many recursive functions can also be carried out with cunning use of loops, which is often better in the long run (as far as big-o-notation is concerned) but when the only way to do something (or the most efficient way) is to do it recursively, then writing a recursive function is the way to go. consider this: you have an array that contains either integers or other arrays, who contain integers or other arrays, and so on. you need to find the highest integer contained by the parent array, regardless of how deep the internal arrays may go. a loop would be a rather difficult way to achieve this considering you have no idea how many tiers to traverse. so recursion is a great way to do it. first write a function that just returns the highest value in the array (for the purposes of this article ill use php but this applies to almost all languages):

function highestVal ($array) {
    $curHigh = 0;
    if (is_array($array)) {
        foreach($array as $val) {
            if ($val > $curHigh) {
                $curHigh = $val;
            }
        }
    } else
        // return some error for incorrect data type
    }
    return $curHigh;
}

passing an array that contains only integers such as array(3,4,8,12,9,8,1) would return 12 in this case. but what if the array was array(3,2,8,9,4,array(12,3),1)? this function might return an error or at the very least not catch the 12 inside the internal array. so modifying the function to check if the $val is an array and recursively calling itself would then return the highest value of the inner array (and if that contained any inner arrays, they would also be assessed):

function highestVal ($array) {
    $curHigh = 0;
    if (is_array($array)) {
        foreach($array as $val) {
            if (is_array($val)) {
                $val = highestVal($val);
            }
            if ($val > $curHigh) {
                $curHigh = $val;
            }
        }
    } else {
        // return some error for incorrect data type
    }
    return $curHigh;
}

there you have it, a function that would return the highest value if an array containing any number of integers or arrays. recursion can have a high cost as far as resources are concerned but this function still maintainss a big-o value of O(n) because it only evaluates each member of each array one time.

MySQL, PHP

Jun 28, 2011

multithreading in php

ok… you got me… there is no such thing as actual multithreading in php. however, i have come up with a method that worked for me on a project where i had to write a web crawler and it the spider hasn’t failed yet. the basic idea is this: while php cannot multithread, your server certainly can so rather than try to jumo through a bunch of hoops to make php do what you want, just rely on the server to do the work.

the parent file
in order to multithread you must have a parent file that creates the threads (or children as i will refer to them for the remainder of this article). you will most likely have to account for the available resources and have the parent file check those resources to make sure that there is enough “room” for another child to be created, otherwise wait until there is “room.” another thing to pay attention to is the default max_execution_time in php. my method to handle both of these issues is to first set php’s max_execution_time to 0 (effectively turning it off) and then to store a running list of children in a database table to keep track of the count.

ini_set('max_execution_time', 0);
$maxThreadsAllowed = 50;
$activeThreads = 0;
$cyclesToRun = 250;
$count = 0;
$keepRunning = TRUE;
while ($keepRunning) {
    if ($activeThreads <= $maxThreadsAllowed) {
        exec('php -f childThread.php >> threadlog.txt &');
        $count++;
    }
    $sql = "'SELECT count(*) FROM threads WHERE completed = 0';
    $result = mysql_query($sql);
    $activeThreads = mysql_result($result, 0);
    if ($activeThreads == 0 && $count &;t= $cyclesToRun) {
        $break;
    }
}

initially there are no threads so i set $activeThreads to 0. for the purposes of this article i am assuming that the system will remain stable as long as there are no more than 50 threads running. the first time through the loop will always run since $keepRunning is initially TRUE. as long as there aren’t too many active children, a new child will be created each pass, otherwise it will be skipped and the count will be checked again. once the $activeCount hits 0 and the $count matches the $cyclesToRun the loop will break. you might ask yourself how the $activeCount will ever be more than 0 based on this code, the answer is in the child file.

the child file
the child file is where all the actual actions that are to be performed take place. in this example it will simply say 'Hello World.' the key here is to insert a new row into the threads table right away so that when the parent checks the $activeCount, there will be something there. then do the work. finally, update the row and set completed to 1 so that the thread is not included in the $activeCount.

$pid = getmypid();
$sql = 'INSERT INTO threads (pid, completed) VALUES (' . $pid . ', 0)';
$result = mysql_query($sql);
echo 'Hello World';
$sql = 'UPDATE threads SET completed = 1 WHERE pid = ' . $pid;
$result = mysql_query($sql);

thats it, albeit in a very basic way. the threads table tracks all the currently running children and the parent checks the table to ensure that there aren’t too many threads running. once all the threads are completed and the total number of cycles has been fulfilled the loop will break and the parent will stop.

assumptions
i am assuming that you already have a connection to a database and that whichever user php is running as has the proper permissions necessary to run exec() commands, user ini_set() and write to a threadlog.txt file

JavaScript/Ajax, PHP

Jun 2, 2010

variable variables in php and javascript

intro
ok, so the title of this one is a little weird but it is a very common thing that i run into, and i find myself looking this up each time and realized i should just add it to the blog. first off, what is a variable variable. basically its a variable whose name is assigned via a variable. so lets say you have a variable ($txt, or var txt) that you assign a value of “myVar” to. echo/alerting the txt variable will display myVar to the screen. well what if you want to use that word as the name of a variable and assign it a value of “test”. you could simply use $myVar = "test"; or var myVar = "test"; right? simple! but, if youve received a variable (say from some other method/function) containing a word, and you want to use that word as a new variable name. you need a way to declare the variable with the name stored inside the received variable. luckily both php and javascriptp have a way to do this.

php
in php you just use two dollar signs ($). so if you have a variable $a and inside of $a is a string “myVar,” then $$a = "hello"; would be the same thing as using $myVar = "hello";. to reference it later, echo $a; would print “myVar” to the screen and echo ${$a}; or echo $myVar; would print “hello” to the screen.

javascript
in javascript its a little more difficult but certainly possible. lets use the exact same scenario but switch to javascript syntax. to assign the string inside var a to a var myVar you would use window[a] = "hello"; referencing it later, alert(a); would yield an alert box containing “myVar” and alert(myVar); or alert(window[a]); would yield an alert box with “hello” inside.

conclusion
you may not have ever been faced with a situation where youve needed to do this, but for those of you who have and couldnt find the results, youre welcome! im faced with this right now, and knowing i can do this is certainly making my life much easier

Mar 2, 2010

sorting an associated array

intro
so, lets say you’ve got an associative array that you want to sort, a simple sort() might not always suffice depending on the array architecture. if you have an array that looks something like the one below, and you want to sort by the timestamp, you will have hard time doing so with something like sort():

array (
  1 => array (
      [timestamp] => 123456789
      [name] => "name"
      [message] => "hi there"
  )
  2 => array (
      [timestamp] => 123456987
      [name] => "name2"
      [message] => "hi yourself"
  )
)

solution
php has a great function called uasort() that allows you to define your own sorting scheme for the data. so, you write a function, lets call it mySort(), and then use the uasort() to reference the mySort function as follows:

uasort($myArray, "mySort");

in the case of the array above, i would write a function to sort by the timestamp as follows:

function mySort($a, $b) {
	if ($a["timestamp"] == $b["timestamp"]) return 0;
	return ($a["timestamp"] > $b["timestamp"]) ? -1 : 1;
}

$a and $b represent the two items to be compared, in this case $myArray[0] and $myArray[1]. if the two timestamps are equal there is no need to make a position swap so 0 is returned (which means no swap is necessary), otherwise it returns a -1 or a 1 (move the item up or down) base on whether its greater than the next item or not. since there is no build in sort function in php to apply a sort to a value thats nested deep within an array, these types of sorts come in handy all the time.

Nov 30, 2009

php email validation

intro
so here’s an extremely common task that i find myself doing all the time and thought id share. when building a simple sign up form there is usually a place for the singer upper to put an email address so they can receive whatever it is you have to offer. however, sometimes these forms are used to send you exorbitant amount of spam, or the user simply made a type when entering the address. either way the results are undesirable so you might want to validate the email address to make sure its legit,

the regexp
first things first, you have to make sure the email address is formatted properly. to do this you will want to compare the address to a regular expression for a match. php has a wonderful function called preg_match that will take care of this for you provided you know the regular expression to use, and i have it here for you:

/^([a-zA-Z0-9])+([a-zA-Z0-9\._-])*@([a-zA-Z0-9_-])+([a-zA-Z0-9\._-]+)+$/

this expression basically says “start with a letter or number; followed by any number of letters, numbers or periods; then an @ symbol; finish with one more more letters followed by at least one or more periods and/or letters”. to use this with php you simply assign this pattern to a variable and compare that variable against the address given:

$email = "someone@email.com";
$pattern = "/^([a-zA-Z0-9])+([a-zA-Z0-9\._-])*@([a-zA-Z0-9_-])+([a-zA-Z0-9\._-]+)+$/";
if (preg_match($pattern, $email)) {
	do something here
} else {
	$error = "invalid email";
}

notice i wrapped the preg_match() in an if statement. thats cause it returns a boolean true or false depending on whether a match is found or not. now we know the email address was formatted properly, this might be all you need but i prefer to take an additional step

checking the domain
checking the actual domain after the @ symbol can ensure that someone didn’t enter a properly formatted bogus address. first split the email address in half at the @ symbol then check the half after the the symbol to see if its legit:

list($username,$domain)=split('@',$email);
if(!checkdnsrr($domain,'MX')) {
	$error = "invalid domain";
}

in this case im checking to see if the checkdnsrr failed, and setting an error message if it does.

put it together
putting all the code together will give you a bit of script that will check the syntax of the email address, and if its correct, check the dns records for the domain name. i prefer to do the checks and set and error message when an error is found. then, after the checks, if any errors were found, i can display them rather than complete the form submission:

$error = "";
$email = "someone@email.com";
$pattern = "/^([a-zA-Z0-9])+([a-zA-Z0-9\._-])*@([a-zA-Z0-9_-])+([a-zA-Z0-9\._-]+)+$/";
if (preg_match($pattern, $email)) {
	list($username,$domain)=split('@',$email);
	if(!checkdnsrr($domain,'MX')) {
		$error = "invalid domain";
	}
} else {
	$error = "invalid email";
}
if (strlen($error)) {
	echo "error: " . $error;
} else {
	finish the submission of the form
}

Nov 16, 2009

converting text urls to clickable links

today i came across a challenge that i am surprise i have not faced before but it seemed worthy to make a post about. i have been working on a social networking tool for a company and they wanted all urls to automatically be parsed into clickable links regardless of the syntax (ie http://www.site.com, site.com, www.site.com). the solution was extremely simple: write a regular expression to match any url and use to make a comparison. heres the code:

<?php
$pattern = "@\b(https?://)?(([0-9a-zA-Z_!~*'().&=+$%-]+:)?[0-9a-zA-Z_!~*'().&=+$%-]+\@)?(([0-9]{1,3}\.){3}[0-9]{1,3}|([0-9a-zA-Z_!~*'()-]+\.)*([0-9a-zA-Z][0-9a-zA-Z-]{0,61})?[0-9a-zA-Z]\.[a-zA-Z]{2,6})(:[0-9]{1,4})?((/[0-9a-zA-Z_!~*'().;?:\@&=+$,%#-]+)*/?)@";
$new_text = preg_replace($pattern, '<a href="\0">\0</a>', $old_text);
?>

thats it, simple and effective. this is similar to how Facebook converts any url into a link in a status update. with the url in tack you could then use that url to capture a screenshop of the website and make it display along with the link.

MySQL, PHP

Feb 3, 2009

connecting to a mysql database

introduction
a lot of web based applications rely on the use of a database in order to store their data. in this article i will discuss how to connect to a database using php.

the code
connecting to a database is really quite simple in php. you will need to know the following information about the database in order to establish a connection: server, name, username, and password. to make it easy to visualize i prefer to set variables for each and then use the variable names when i make the actual connection call:

<?php
$db_name = "my_database";
$db_serv = "localhost";
$db_user = "my_username";
$db_pass = "my_password";

$db_conn = mysql_connect($db_serv, $db_user, $db_pass);
mysql_connect($db_name, $db_conn);
?>

that’s it! now that you have established a connection you can make queries to the database to recall data:

<?php
$sql = "SELECT * FROM some_table";
$result = mysql_query($sql);
?>

conclusion
its really quite simple and storing information in a database not only makes a site run more smoothly, but it also allows you to create powerful content management options so you can quickly update information on the site without changing anything in the site’s files themselves. this is great for template based sites where the pages stay pretty much the same and the content inside them varies depending on a given combination of variables.

MySQL, PHP

Feb 3, 2009

password encryption

introduction
ive worked on a lot of programs and websites that involve requiring the user to login in order to gain access and it occurred to me that there is a useful bit of information that i can share from these experiences. what i am referring to is the encryption process to protect the password of the user. more often than not i use an encryption method called md5. happens to have a built in function that will convert any string into an md5 quite easily. combine that with a login/signup form and a database to store it in, and you’re well on your way to a secure login system.

md5
md5 (message-digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. as an internet standard (rcf 1321), md5 has been employed in a wide variety of security applications, and is also commonly used to check the integrity of files. an md5 hash is typically expressed as a 32 digit hexadecimal number. for example, the md5 of the word ‘the’ would be ’8fc42c6ddf9966db3b09e84365034357′

the code
as i already stated, in php there is a predefined function to convert a string into an md5 hash. its quite simple actually: md5("the"); would be the method used to return the hash stated above. let’s say you created a signup form that looked something like the following:

<form name="signup" method="post" action="">
<input type="text" name="username" />
<input type="password" name="password" />
<input type="submit" name="submit" value="Login" />
</form>

once the user clicks submit php can be used to process the information and store it in a database to be recalled later (assuming we already have a ):

<?php
if ($_POST) {
	$username = $_POST["username"];
	$password = md5($_POST["password"]);

	$sql = "INSERT INTO users (username, password)
		VALUES ('$username','$password')";
	$result = mysql_query($sql);
}
?>

notice that i encrypt the password before storing it into the database. this way if anyone ever gets access to your database, they’ll have a rather difficult time deciphering what the passwords are. to login to the software a similar form would be used however this time, after converting the entered password to an md5 we would do a look up to see if the users exists and if the password is correct:

<?php
if ($_POST) {
	$username = $_POST["username"];
	$password = md5($_POST["password"]);

	$sql = "SELECT * FROM users WHERE username = '$username'";
	$result = mysql_query($sql);

	// make sure there is a user with this username
	if (mysql_num_rows($result) == 0) {
		$msg = "No Such User!";
	// there is a user, now check the password
	} elseif ($password != $row["password"]) {
		$msg = "Incorrect Password!";
	} else {
		$msg = "Logged In";

		// set the user to logged in
		$_SESSION["logged_in"] = true;
	}
}
?>

and there you have it
this is a good way to protect the information between users as well as reassure them that their login information is encrypted. md5 is not the be-all-end-all for encryption methods, and while difficult, it is possible to reverse engineer the hashes, but it is certainly a great first line of defense when creating password protected logins.

Dec 3, 2008