SE250:lab-9:rwan064:string.c
Jump to navigation
Jump to search
<html> <head>
<title>string.c</title>
</head> <body bgcolor="#ffffff" text="#000000">
<a name="line1"> 1</a> <font color="#444444">/*
<a name="line2"> 2</a> File: string.c
<a name="line3"> 3</a> Author: Rajitha Wannigama
<a name="line4"> 4</a> Purpose: String type implementation in C.
<a name="line5"> 5</a> */</font>
<a name="line6"> 6</a>
<a name="line7"> 7</a> <font color="0000ff"><strong>#include <font color="#008000"><stdio.h></font></strong></font>
<a name="line8"> 8</a> <font color="0000ff"><strong>#include <font color="#008000"><stdlib.h></font></strong></font>
<a name="line9"> 9</a> <font color="0000ff"><strong>#include <font color="#008000"><string.h></font></strong></font>
<a name="line10"> 10</a> <font color="0000ff"><strong>#include <font color="#008000">"string.h"</font></strong></font>
<a name="line11"> 11</a>
<a name="line12"> 12</a> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">null_s</font> <font color="4444FF">=</font> <font color="4444FF">(</font><font color="#2040a0">String</font><font color="4444FF">*</font><font color="4444FF">)</font><font color="#FF0000">0</font><font color="4444FF">;</font>
<a name="line13"> 13</a>
<a name="line14"> 14</a> <font color="0000ff"><strong>#define INITIAL_CAPACITY 16</strong></font>
<a name="line15"> 15</a> <font color="0000ff"><strong>#define LOAD_FACTOR 2</strong></font>
<a name="line16"> 16</a>
<a name="line17"> 17</a> // <font color="#2040a0">Destination</font> <font color="#2040a0">and</font> <font color="#2040a0">source</font> <font color="#2040a0">must</font> <font color="#2040a0">already</font> <font color="#2040a0">exist</font>.
<a name="line18"> 18</a> <strong>void</strong> <font color="#2040a0">change_string</font><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">destination</font>, <strong>const</strong> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">source</font> <font color="4444FF">)</font>
<a name="line19"> 19</a> <font color="4444FF"><strong>{</strong></font>
<a name="line20"> 20</a> // <font color="#2040a0">Free</font> <font color="#2040a0">destination</font> <font color="#2040a0">memory</font>
<a name="line21"> 21</a> <font color="#2040a0">free</font><font color="4444FF">(</font> <font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line22"> 22</a> <font color="#2040a0">free</font><font color="4444FF">(</font> <font color="#2040a0">destination</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line23"> 23</a>
<a name="line24"> 24</a> <font color="#2040a0">destination</font> <font color="4444FF">=</font> <font color="#2040a0">create_string</font><font color="4444FF">(</font> <font color="#2040a0">source</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line25"> 25</a> <font color="4444FF"><strong>}</strong></font>
<a name="line26"> 26</a>
<a name="line27"> 27</a> <strong>char</strong><font color="4444FF">*</font> <font color="#2040a0">get_cstring</font><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">str</font> <font color="4444FF">)</font>
<a name="line28"> 28</a> <font color="4444FF"><strong>{</strong></font>
<a name="line29"> 29</a> <font color="#2040a0">size_t</font> <font color="#2040a0">size</font> <font color="4444FF">=</font> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font> <font color="4444FF">+</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line30"> 30</a> <strong>char</strong><font color="4444FF">*</font> <font color="#2040a0">cp</font> <font color="4444FF">=</font> <font color="4444FF">(</font><strong>char</strong><font color="4444FF">*</font><font color="4444FF">)</font> <font color="#2040a0">malloc</font><font color="4444FF">(</font> <strong>sizeof</strong><font color="4444FF">(</font><strong>char</strong><font color="4444FF">)</font> <font color="4444FF">*</font> <font color="#2040a0">size</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line31"> 31</a> <font color="#2040a0">strcpy</font><font color="4444FF">(</font> <font color="#2040a0">cp</font>, <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line32"> 32</a> <strong>return</strong> <font color="#2040a0">cp</font><font color="4444FF">;</font>
<a name="line33"> 33</a> <font color="4444FF"><strong>}</strong></font>
<a name="line34"> 34</a>
<a name="line35"> 35</a> <strong>void</strong> <font color="#2040a0">append_cstring</font><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">destination</font>, <strong>const</strong> <strong>char</strong> <font color="4444FF">*</font><font color="#2040a0">source</font> <font color="4444FF">)</font>
<a name="line36"> 36</a> <font color="4444FF"><strong>{</strong></font>
<a name="line37"> 37</a> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">s</font> <font color="4444FF">=</font> <font color="#2040a0">create_string</font><font color="4444FF">(</font> <font color="#2040a0">source</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line38"> 38</a> <font color="#2040a0">append_string</font><font color="4444FF">(</font> <font color="#2040a0">destination</font>, <font color="#2040a0">s</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line39"> 39</a> <font color="#2040a0">free</font><font color="4444FF">(</font> <font color="#2040a0">s</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line40"> 40</a> <font color="#2040a0">free</font><font color="4444FF">(</font> <font color="#2040a0">s</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line41"> 41</a> <font color="4444FF"><strong>}</strong></font>
<a name="line42"> 42</a>
<a name="line43"> 43</a> <strong>void</strong> <font color="#2040a0">append_string</font><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">destination</font>, <strong>const</strong> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">source</font> <font color="4444FF">)</font>
<a name="line44"> 44</a> <font color="4444FF"><strong>{</strong></font>
<a name="line45"> 45</a> <strong>unsigned</strong> <strong>int</strong> <font color="#2040a0">req_cap</font> <font color="4444FF">=</font> <font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font> <font color="4444FF">+</font> <font color="#2040a0">source</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font> <font color="4444FF">+</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line46"> 46</a> <strong>unsigned</strong> <strong>int</strong> <font color="#2040a0">act_cap</font> <font color="4444FF">=</font> <font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">capacity</font> <font color="4444FF">+</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line47"> 47</a> <strong>unsigned</strong> <strong>int</strong> <font color="#2040a0">i</font> <font color="4444FF">=</font> <font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font><font color="4444FF">;</font>
<a name="line48"> 48</a> <strong>int</strong> <font color="#2040a0">j</font> <font color="4444FF">=</font> <font color="#FF0000">0</font><font color="4444FF">;</font>
<a name="line49"> 49</a> <strong>if</strong> <font color="4444FF">(</font> <font color="#2040a0">act_cap</font> <font color="4444FF"><</font> <font color="#2040a0">req_cap</font> <font color="4444FF">)</font> <font color="4444FF"><strong>{</strong></font>
<a name="line50"> 50</a> <font color="#2040a0">ensure_capacity</font><font color="4444FF">(</font> <font color="#2040a0">destination</font>, <font color="#2040a0">req_cap</font> <font color="4444FF">*</font> <font color="#2040a0">LOAD_FACTOR</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line51"> 51</a> <font color="4444FF"><strong>}</strong></font>
<a name="line52"> 52</a> <strong>for</strong> <font color="4444FF">(</font> <font color="4444FF">;</font> <font color="#2040a0">i</font> <font color="4444FF"><</font> <font color="4444FF">(</font><font color="#2040a0">req_cap</font> <font color="4444FF">-</font> <font color="#FF0000">1</font><font color="4444FF">)</font><font color="4444FF">;</font> <font color="#2040a0">i</font><font color="4444FF">+</font><font color="4444FF">+</font> <font color="4444FF">)</font> <font color="4444FF"><strong>{</strong></font>
<a name="line53"> 53</a> <font color="4444FF">(</font><font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font><font color="4444FF">)</font><font color="4444FF">[</font><font color="#2040a0">i</font><font color="4444FF">]</font> <font color="4444FF">=</font> <font color="4444FF">(</font><font color="#2040a0">source</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font><font color="4444FF">)</font><font color="4444FF">[</font><font color="#2040a0">j</font><font color="4444FF">]</font><font color="4444FF">;</font>
<a name="line54"> 54</a> <font color="#2040a0">j</font><font color="4444FF">+</font><font color="4444FF">+</font><font color="4444FF">;</font>
<a name="line55"> 55</a> <font color="4444FF"><strong>}</strong></font>
<a name="line56"> 56</a> <font color="4444FF">(</font><font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font><font color="4444FF">)</font><font color="4444FF">[</font><font color="#2040a0">req_cap</font> <font color="4444FF">-</font> <font color="#FF0000">1</font><font color="4444FF">]</font> <font color="4444FF">=</font> <font color="#008000">'<font color="#77dd77">\0</font>'</font><font color="4444FF">;</font>
<a name="line57"> 57</a> <font color="#2040a0">destination</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font> <font color="4444FF">=</font> <font color="#2040a0">req_cap</font> <font color="4444FF">-</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line58"> 58</a> <font color="4444FF"><strong>}</strong></font>
<a name="line59"> 59</a>
<a name="line60"> 60</a> <strong>void</strong> <font color="#2040a0">ensure_capacity</font><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">s</font>, <strong>unsigned</strong> <strong>int</strong> <font color="#2040a0">cap</font> <font color="4444FF">)</font>
<a name="line61"> 61</a> <font color="4444FF"><strong>{</strong></font>
<a name="line62"> 62</a> <font color="#2040a0">s</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">=</font> <font color="4444FF">(</font><strong>char</strong><font color="4444FF">*</font><font color="4444FF">)</font> <font color="#2040a0">realloc</font><font color="4444FF">(</font> <font color="#2040a0">s</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font>, <font color="#2040a0">cap</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line63"> 63</a> // <font color="#2040a0">capacity</font> <font color="#2040a0">is</font> <font color="#2040a0">cap</font> <font color="4444FF">-</font> <font color="#FF0000">1</font> <font color="#2040a0">because</font> <font color="#2040a0">we</font> <font color="#2040a0">need</font> <font color="#2040a0">space</font> <strong>for</strong> <font color="#2040a0">NULL</font> <font color="#2040a0">character</font> <font color="#2040a0">and</font> <font color="#2040a0">this</font> <font color="#2040a0">is</font> <font color="#2040a0">not</font> <font color="#2040a0">included</font> <font color="#2040a0">in</font> <font color="#2040a0">the</font> <font color="#2040a0">capacity</font>.
<a name="line64"> 64</a> <font color="#2040a0">s</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">capacity</font> <font color="4444FF">=</font> <font color="#2040a0">cap</font> <font color="4444FF">-</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line65"> 65</a> <font color="4444FF"><strong>}</strong></font>
<a name="line66"> 66</a>
<a name="line67"> 67</a> <font color="#2040a0">String</font><font color="4444FF">*</font> <font color="#2040a0">create_empty_string</font><font color="4444FF">(</font> <strong>void</strong> <font color="4444FF">)</font>
<a name="line68"> 68</a> <font color="4444FF"><strong>{</strong></font>
<a name="line69"> 69</a> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">str</font><font color="4444FF">;</font>
<a name="line70"> 70</a> <font color="#2040a0">str</font> <font color="4444FF">=</font> <font color="4444FF">(</font><font color="#2040a0">String</font><font color="4444FF">*</font><font color="4444FF">)</font> <font color="#2040a0">malloc</font><font color="4444FF">(</font> <strong>sizeof</strong><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">)</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line71"> 71</a> // <font color="#2040a0">INITIAL_CAPACITY</font> <font color="#2040a0">plus</font> <font color="#2040a0">one</font> <font color="#2040a0">because</font> <font color="#2040a0">we</font> <font color="#2040a0">need</font> <font color="#2040a0">space</font> <strong>for</strong> \<font color="#FF0000">0</font> <font color="#2040a0">character</font>.
<a name="line72"> 72</a> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">=</font> <font color="4444FF">(</font><strong>char</strong><font color="4444FF">*</font><font color="4444FF">)</font> <font color="#2040a0">malloc</font><font color="4444FF">(</font> <font color="4444FF">(</font> <font color="#2040a0">INITIAL_CAPACITY</font> <font color="4444FF">+</font> <font color="#FF0000">1</font> <font color="4444FF">)</font> <font color="4444FF">*</font> <strong>sizeof</strong><font color="4444FF">(</font> <strong>char</strong> <font color="4444FF">)</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line73"> 73</a> <font color="4444FF">(</font><font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font><font color="4444FF">)</font><font color="4444FF">[</font><font color="#FF0000">0</font><font color="4444FF">]</font> <font color="4444FF">=</font> <font color="#008000">'<font color="#77dd77">\0</font>'</font><font color="4444FF">;</font>
<a name="line74"> 74</a>
<a name="line75"> 75</a> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font> <font color="4444FF">=</font> <font color="#FF0000">0</font><font color="4444FF">;</font>
<a name="line76"> 76</a> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">capacity</font> <font color="4444FF">=</font> <font color="#2040a0">INITIAL_CAPACITY</font><font color="4444FF">;</font>
<a name="line77"> 77</a>
<a name="line78"> 78</a> <strong>return</strong> <font color="#2040a0">str</font><font color="4444FF">;</font>
<a name="line79"> 79</a> <font color="4444FF"><strong>}</strong></font>
<a name="line80"> 80</a>
<a name="line81"> 81</a> <font color="#2040a0">String</font><font color="4444FF">*</font> <font color="#2040a0">create_string</font><font color="4444FF">(</font> <strong>const</strong> <strong>char</strong> <font color="4444FF">*</font><font color="#2040a0">source</font> <font color="4444FF">)</font>
<a name="line82"> 82</a> <font color="4444FF"><strong>{</strong></font>
<a name="line83"> 83</a> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">str</font><font color="4444FF">;</font>
<a name="line84"> 84</a>
<a name="line85"> 85</a> // <font color="#2040a0">Need</font> <font color="#2040a0">space</font> <strong>for</strong> <font color="#2040a0">NULL</font> <font color="#2040a0">terminating</font> <strong>char</strong> <font color="#2040a0">aswell</font> <font color="#2040a0">so</font> <font color="#2040a0">its</font> <font color="#2040a0">strlen</font> <font color="#2040a0">PLUS</font> <font color="#2040a0">one</font>.
<a name="line86"> 86</a> <font color="#2040a0">size_t</font> <font color="#2040a0">src_len</font> <font color="4444FF">=</font> <font color="#2040a0">strlen</font><font color="4444FF">(</font> <font color="#2040a0">source</font> <font color="4444FF">)</font> <font color="4444FF">+</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line87"> 87</a>
<a name="line88"> 88</a> <font color="#2040a0">str</font> <font color="4444FF">=</font> <font color="4444FF">(</font><font color="#2040a0">String</font><font color="4444FF">*</font><font color="4444FF">)</font> <font color="#2040a0">malloc</font><font color="4444FF">(</font> <strong>sizeof</strong><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">)</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line89"> 89</a>
<a name="line90"> 90</a> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">=</font> <font color="4444FF">(</font><strong>char</strong><font color="4444FF">*</font><font color="4444FF">)</font> <font color="#2040a0">malloc</font><font color="4444FF">(</font> <font color="#2040a0">src_len</font> <font color="4444FF">*</font> <strong>sizeof</strong><font color="4444FF">(</font> <strong>char</strong> <font color="4444FF">)</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line91"> 91</a> <font color="#2040a0">strcpy</font><font color="4444FF">(</font> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font>, <font color="#2040a0">source</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line92"> 92</a>
<a name="line93"> 93</a> // <font color="#2040a0">Because</font> <font color="#2040a0">length</font> <font color="#2040a0">of</font> <font color="#2040a0">string</font> <font color="#2040a0">doesn</font>'<font color="#2040a0">t</font> <font color="#2040a0">include</font> <font color="#2040a0">NULL</font> <font color="#2040a0">terminator</font>.
<a name="line94"> 94</a> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">length</font> <font color="4444FF">=</font> <font color="#2040a0">src_len</font> <font color="4444FF">-</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line95"> 95</a> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">capacity</font> <font color="4444FF">=</font> <font color="#2040a0">src_len</font> <font color="4444FF">-</font> <font color="#FF0000">1</font><font color="4444FF">;</font>
<a name="line96"> 96</a>
<a name="line97"> 97</a> <strong>return</strong> <font color="#2040a0">str</font><font color="4444FF">;</font>
<a name="line98"> 98</a> <font color="4444FF"><strong>}</strong></font>
<a name="line99"> 99</a>
<a name="line100">100</a> <strong>void</strong> <font color="#2040a0">print_string</font><font color="4444FF">(</font> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">str</font> <font color="4444FF">)</font>
<a name="line101">101</a> <font color="4444FF"><strong>{</strong></font>
<a name="line102">102</a> <strong>if</strong> <font color="4444FF">(</font> <font color="4444FF">(</font><font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font><font color="4444FF">)</font><font color="4444FF">[</font><font color="#FF0000">0</font><font color="4444FF">]</font> <font color="4444FF">=</font><font color="4444FF">=</font> <font color="#008000">'<font color="#77dd77">\0</font>'</font> <font color="4444FF">)</font> <font color="4444FF"><strong>{</strong></font>
<a name="line103">103</a> <font color="#2040a0">puts</font><font color="4444FF">(</font> <font color="#008000">"(null)"</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line104">104</a> <font color="4444FF"><strong>}</strong></font>
<a name="line105">105</a> <strong>else</strong> <font color="4444FF"><strong>{</strong></font>
<a name="line106">106</a> <font color="#2040a0">puts</font><font color="4444FF">(</font> <font color="#2040a0">str</font><font color="4444FF">-</font><font color="4444FF">></font><font color="#2040a0">str</font> <font color="4444FF">)</font><font color="4444FF">;</font>
<a name="line107">107</a> <font color="4444FF"><strong>}</strong></font>
<a name="line108">108</a> <font color="4444FF"><strong>}</strong></font>
<a name="line109">109</a>
<a name="line110">110</a> <strong>int</strong> <font color="#2040a0">compare_strings</font><font color="4444FF">(</font> <strong>const</strong> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">s1</font>, <strong>const</strong> <font color="#2040a0">String</font> <font color="4444FF">*</font><font color="#2040a0">s2</font> <font color="4444FF">)</font>
<a name="line111">111</a> <font color="4444FF"><strong>{</strong></font>
<a name="line112">112</a> <strong>return</strong> <font color="#FF0000">0</font><font color="4444FF">;</font>
<a name="line113">113</a> <font color="4444FF"><strong>}</strong></font>
syntax highlighted by <a href="http://www.palfrader.org/code2html">Code2HTML</a>, v. 0.9.1 </body> </html>