[Python][お勉強] Python入門(32) - イテレータ

今日もPythonのお勉強。
イテレータからやる。

イテレータオブジェクト
イテレータプロトコルをサポートするオブジェクトのこと。
必ずnext()という「ループにおいて次に処理対象となるオブジェクトを戻す」メソッドを持っている。

イテレータオブジェクトとジェネレータ。
ジェネレータはイテレータプロトコルをサポートしている。
よってジェネレータもイテレータの一種ということができる。

ビルトインオブジェクト
ビルトインオブジェクトはビルトイン関数iter()によってイテレータオブジェクトを作成できるように設計されている。

さっそくやってみる。

>>> L = [1,2,3,4,5]
>>> xx = iter(L)
>>> xx.next()
1
>>> xx.next()
2
>>> xx.next()
3
>>> xx.next()
4
>>> xx.next()
5
>>>

リストの例。

次はディクショナリ。

>>> D = {'a':1,'b':2,'c':3}
>>> xx = iter(D)
>>> xx.next()
'a'
>>> xx.next()
'c'
>>> xx.next()
'b'
>>> xx.next()
Traceback (most recent call last):
  File "", line 1, in ?
StopIteration
>>>

できた。
要素が無くなるとExceptionをはく。


ふーん。


おしまい。
.

[mod_chxj] ドキュメント更新

0.9.0用にドキュメントを更新。

やたらと時間がかかった・・・。

書いてて忘れてた機能をこれから追加。
metaタグにcharsetが入ってたら書き換えないといけない。





.

[Apache][CodeReading] Apache2.2.8コードリーディング13日目

今日もApacheリーディング。

今日作ったページは・・・

• allocator_alloc()/Apache2.2.8
• APR_UINT32_TRUNC_CASTマクロ/Apache2.2.8
• apr_thread_mutex_unlock()/Apache2.2.8
• apr_thread_mutex_lock()/Apache2.2.8
• PTHREAD_SETS_ERRNO定数/Apache2.2.8
• APR_UINT32_MAX定数/Apache2.2.8
• MIN_ALLOCローカル定数/Apache2.2.8
• BOUNDARY_SIZEローカル定数/Apache2.2.8
• APR_MEMNODE_T_SIZEマクロ/Apache2.2.8
• apr_size_t/Apache2.2.8
• APR_INLINEマクロ/Apache2.2.8

な感じ。


本日のメインはやっぱりallocator_alloc()。
apr_allocator_tの保持するfree[]に既にほしいサイズの領域があればそれを使い、無ければ新しくmallocするところ。

ソースコードを順に見ていく。と、その前に、前提知識としてfree[]を知っておく。
apr_allocator_tにはfreeというメンバがある。
このメンバはapr_memnode_tへのポインタの配列。

で、これはつまるところ何かというと、「malloc済みの空き領域」のリストの先頭の要素へのポインタの配列。

free[0]はsinkってコメントに書いてあるが、free[1]からfree[MAX_INDEX-1]のサイズに入りきらない大きさのメモリ領域用リストで、要は掃き溜め。ごみ。くず。

free[1]にはBOUNDARY_SIZE * (1+1)の大きさの領域のリストを保持している。つまり8192バイト。
free[2]にはBOUNDARY_SIZE * (1+2)の大きさの領域のリストを保持している。つまり12288バイト。
free[3]にはBOUNDARY_SIZE * (1+3)の大きさの領域のリストを保持している。つまり16384バイト。

・・・・。

というのがfree[MAX_INDEX-1]まであると。まだ一回もallocatorを使用していない場合にはfreeは全てNULLが入っている。

取得希望のサイズからfreeの添え字を取得するには・・

取得希望サイズ >> 12

とすれば求まる。

で、早速ソースを見ていく。

static APR_INLINE
apr_memnode_t *allocator_alloc(apr_allocator_t *allocator, apr_size_t size)
{
apr_memnode_t *node, **ref;
apr_uint32_t max_index;
apr_size_t i, index;

/* Round up the block size to the next boundary, but always
* allocate at least a certain size (MIN_ALLOC).
*/
size = APR_ALIGN(size + APR_MEMNODE_T_SIZE, BOUNDARY_SIZE);
if (size < MIN_ALLOC)
  size = MIN_ALLOC;

最初の部分。
まず呼び出し元が取得したいサイズがsizeパラメータでわたってくる。
でいきなり4096バイトアライン。
sizeパラメータでわたってきてアライン調整した値がMIN_ALLOC(8192)より小さければ8192バイトにする。
つまり小さい領域はみな8192バイト使うということ。

そして、

207     /* Find the index for this node size by
208      * dividing its size by the boundary size
209      */
210     index = (size >> BOUNDARY_INDEX) - 1;
211
212     if (index > APR_UINT32_MAX) {
213         return NULL;
214     }

で、これから探そうとするサイズ用のfree[]の添え字を算出する。
index値がぶっとんだ値になってたらNULLを返しちゃう。

216     /* First see if there are any nodes in the area we know
217      * our node will fit into.
218      */
219     if (index <= allocator->max_index) {
220 #if APR_HAS_THREADS
221         if (allocator->mutex)
222             apr_thread_mutex_lock(allocator->mutex);
223 #endif /* APR_HAS_THREADS */
224
225         /* Walk the free list to see if there are
226          * any nodes on it of the requested size
227          *
228          * NOTE: an optimization would be to check
229          * allocator->free[index] first and if no
230          * node is present, directly use
231          * allocator->free[max_index].  This seems
232          * like overkill though and could cause
233          * memory waste.
234          */
235         max_index = allocator->max_index;
236         ref = &allocator->free[index];
237         i = index;
238         while (*ref == NULL && i < max_index) {
239            ref++;
240            i++;
241         }
242
243         if ((node = *ref) != NULL) {
244             /* If we have found a node and it doesn't have any
245              * nodes waiting in line behind it _and_ we are on
246              * the highest available index, find the new highest
247              * available index
248              */
249             if ((*ref = node->next) == NULL && i >= max_index) {
250                 do {
251                     ref--;
252                     max_index--;
253                 }
254                 while (*ref == NULL && max_index > 0);
255
256                 allocator->max_index = max_index;
257             }
258
259             allocator->current_free_index += node->index;
260             if (allocator->current_free_index > allocator->max_free_index)
261                 allocator->current_free_index = allocator->max_free_index;
262
263 #if APR_HAS_THREADS
264             if (allocator->mutex)
265                 apr_thread_mutex_unlock(allocator->mutex);
266 #endif /* APR_HAS_THREADS */
267
268             node->next = NULL;
269             node->first_avail = (char *)node + APR_MEMNODE_T_SIZE;
270
271             return node;
272         }
273
274 #if APR_HAS_THREADS
275         if (allocator->mutex)
276             apr_thread_mutex_unlock(allocator->mutex);
277 #endif /* APR_HAS_THREADS */
278     }

算出したindex値が現在allocatorが保持しているfree[]のmax_indexより小さければ
既にallocatorが持っている可能性が高いので上記のif文内を実行する。

allocatorのmax_indexは空きがあるfreeのindexの最大値。

221行目から222行目でロックをかける。初期化したてのallocatorはmutexがNULLなんでロックはかからない。

235行目から241行目はindexからmax_indexまでのfreeリストを1づつ見ていく。
要はfree[i] != NULLのものを探している。

243行目から272行目はfree[i] != NULLのものが見つかったときの処理。
なければunlockして319行目へいく。
見つかったらnode変数にfree[i]をセット。
そして、node->nextをfree[i]にセットする。
free[i]のリストの先頭要素をnodeに取り出しnodeの次の要素をfree[i]の先頭にしている。

249行目から257行目では、見つかったノードがfree[max_index]リストの最後の要素であった場合の処理をしている。
最後の要素であった場合には、max_indexの値を更新する。
max_index以下のfree[]が!= NULLであった場合にはその添え字をあたらしいmax_indexとしている。
もし、同じサイズでもう一度allocator_alloc()が呼ばれても、max_index値が更新されているので同じルートは通らない。その際は、free[0]かmallocをしにいく。

259行目から261行目でcurrent_free_indexを更新している。
この値はまだ良くわからないが、恐らくallocatorが貸し出し中のサイズを意味しているような気がする。
ただ、そうなると以下の疑問が生ずる。

• [疑問]max_free_indexよりcurrent_free_indexが大きい値の場合、なぜmax_free_indexの値で更新しているのか。
• [疑問]更新してしまっては貸し出し中のサイズがわからなくなってしまう。

きっともう少し読めばわかるとは思うが、後ほど参照できるように疑問点を挙げておく。

で、263行目から266行目でアンロック。

268行目でnode->nextをNULLでクリアし、
269行目でnode->first_availに利用できるメモリ領域の先頭アドレスを設定している。
269行目でわかるとおり、利用できるメモリアドレスはapr_memnode_tのコントロール領域の後ろに位置する。

271行目で呼び出し元へnodeを返す。



次はindexがallocator->max_indexよりも大きい場合の処理。
sink（掃き溜め）にある可能性が高いので、free[0]を探してみる処理。
そもそもfree[0]がNULLだったら319行目にいく。

280     /* If we found nothing, seek the sink (at index 0), if
281      * it is not empty.
282      */
283     else if (allocator->free[0]) {
284 #if APR_HAS_THREADS
285         if (allocator->mutex)
286             apr_thread_mutex_lock(allocator->mutex);
287 #endif /* APR_HAS_THREADS */
288
289         /* Walk the free list to see if there are
290          * any nodes on it of the requested size
291          */
292         ref = &allocator->free[0];
293         while ((node = *ref) != NULL && index > node->index)
294             ref = &node->next;
295
296         if (node) {
297             *ref = node->next;
298
299             allocator->current_free_index += node->index;
300             if (allocator->current_free_index > allocator->max_free_index)
301                 allocator->current_free_index = allocator->max_free_index;
302
303 #if APR_HAS_THREADS
304             if (allocator->mutex)
305                 apr_thread_mutex_unlock(allocator->mutex);
306 #endif /* APR_HAS_THREADS */
307
308             node->next = NULL;
309             node->first_avail = (char *)node + APR_MEMNODE_T_SIZE;
310
311             return node;
312         }
313
314 #if APR_HAS_THREADS
315         if (allocator->mutex)
316             apr_thread_mutex_unlock(allocator->mutex);
317 #endif /* APR_HAS_THREADS */
318     }

284行目から287行目でロックをかける。

292行目から294行目で収まるサイズを保持しているノードを探している。
十分わかりやすいのだが、もう少しへぼへぼに書くと、

for (p = free[0];
    p != NULL;
    p = p->next) {

if (p->index > index) break;
}

な感じか。

296行目からほしいサイズ以上のサイズをもつノードが見つかった場合の処理が続く。
297行目でリストをつなぎ直して、見つかったノードをリストからはずしている。

そして、299行目でcurrent_free_indexに取得したindex値を加算して、
303行目から306行目でアンロックと。

で、308行目、309行目でnextをNULLクリアし、
first_availに利用できるメモリ領域の先頭アドレスをセット。

で、できあがったnodeを呼び出し元に返している。


次は、free[]には持っていなかった場合。

320     /* If we haven't got a suitable node, malloc a new one
321      * and initialize it.
322      */
323     if ((node = malloc(size)) == NULL)
324         return NULL;
325
326     node->next = NULL;
327     node->index = (APR_UINT32_TRUNC_CAST)index;
328     node->first_avail = (char *)node + APR_MEMNODE_T_SIZE;
329     node->endp = (char *)node + size;
330
331     return node;
332 }

323行目でnode領域を確保し、
326行目から329行目でnext、index、first_avail、endpメンバをセットしている。

nextはNULLクリア。
indexは、これまでに算出したindex値をセット。
first_availには利用できるメモリ領域の先頭アドレスを設定している。

そして、mallocするときにだけ、endpを設定している。
mallocしたサイズを覚えておくためか？？？
endpは細切れにメモリ領域を使うときに使用する気がするが、
これも今のところよくわからない。

• [疑問]endpの使い道は何か。

と一応疑問点を挙げておく。


これでallocator_alloc()は一通り読んだ。
あとは疑問点を解消すべく先を読みすすむ。

期待通り、面白い。
何も考えずに使うとするとfree[1]ばかりが出来そうだが、きっとその辺はpoolとかでいろいろと
やっているに違いない。

あと、
apr_thread_mutex_unlock()とapr_thread_mutex_lock()はarch/unix系では
pthreadを読んでいるだけ。
特に面白くない。

おしまい。
.

[Python][お勉強] Python入門(31) - ジェネレータ

Pythonではジェネレータなるものが使用できる。

通常関数はreturnステートメントで呼び出し元に戻る。再度同じ関数をコールするとまた最初から実行され、
returnステートメントで呼び出し元に戻る。
ジェネレータを使うとyeildステートメントで呼び出し元に戻る。再度同じ関数をコールすると、yeildステートメントで呼び出し元に戻ったところから実行が再開され、またyeildステートメントで呼び出し元に戻る。

ただし普通に使おうとすると（通常の関数と同じようにコールすると）、ジェネレータオブジェクトが返されるだけなので、ちょっと使い方を注意する。

ジェネレータを使用した例

>>> def aaa(x):
...   for i in range(x):
...     yield i ** 2
...
>>>

と定義したとする。普通の関数のようにコールすると、、、

>>> aaa(10)
<generator>
>>>
　

とジェネレータオブジェクトが返されるだけ。
なので、いったん変数に入れるなりして、、、

>>> a = aaa(10)
>>> a.next()
0
>>> a.next()
1
>>> a.next()
4
>>> a.next()
9
>>> a.next()
16
>>> a.next()
25
>>> a.next()
36
>>>
　

nextメソッドをコールしてやる。すると呼び出す度に続きから再実行される。
このnextメソッドは「イテレータオブジェクト」の機能らしい。





おしまい。
.

[Python][お勉強] Python入門(30) - リスト内包表記

filterやreduceは他の言語とほぼ一緒な感じなのでとばして、リスト内包表記をやる。

まず、リスト内包表記を使わない例。forでがんばる例。

>>> res = []
>>> for x in 'spam':
...   res.append(ord(x))
...
>>> res
[115, 112, 97, 109]
>>>

これをmap関数を使うと・・・

>>> res = map(ord, 'spam')
>>> res
[115, 112, 97, 109]
>>>

なんて感じで書ける。
さらにリスト内包表記を使うと、、

>>> res = [ord(x) for x in 'spam']
>>> res
[115, 112, 97, 109]
>>>

な感じ。この例ではmap関数の方が楽であるもののいろいろと使えそう。


おしまい。




.

[Apache][CodeReading] Apache2.2.8コードリーディング12日目

今日は、ページを作っただけ。

作ったページは、

• allocator_alloc()/Apache2.2.8
• global_poolスタティック変数/Apache2.2.8
• apr_pool_create_ex()/Apache2.2.8
• apr_allocator_create()/Apache2.2.8
• APR_ALLOCATOR_MAX_FREE_UNLIMITED定数/Apache2.2.8

だけ。

作っただけなんで何もなし。。。



.

[Python][お勉強] Python入門(29) - map関数

シーケンスに対して順に個々のデータを操作するにはmap関数が使える。

たとえば、

>>> L = [1,2,3,4,5]
>>> L
[1, 2, 3, 4, 5]
>>>

といったリストがあったとする。
各要素に1を足したリストがほしいとする。
そういう場合には、

>>> map((lambda x: x+1),L)
[2, 3, 4, 5, 6]
>>>

というように第一引数にそれぞれの要素に対する処理を渡し、繰り返し処理をさせることができる。


また、第二引数以降にもうひとつ引数を足すと、

>>> map((lambda x,y: x*y),[1,2,3,4],[2,3,4,5])
[2, 6, 12, 20]
>>>

なんてこともできる。
これは第二引数と第三引数の各要素をひとつづつ、lambdaで定義した関数に引数として渡し、計算結果を最終結果として返している。





おしまい。
.